PriorityQueue.php #1

<?php
/**
 * Zend Framework
 *
 * LICENSE
 *
 * This source file is subject to the new BSD license that is bundled
 * with this package in the file LICENSE.txt.
 * It is also available through the world-wide-web at this URL:
 * http://framework.zend.com/license/new-bsd
 * If you did not receive a copy of the license and are unable to
 * obtain it through the world-wide-web, please send an email
 * to license@zend.com so we can send you a copy immediately.
 *
 * @category   Zend
 * @package    Zend_Search_Lucene
 * @copyright  Copyright (c) 2005-2012 Zend Technologies USA Inc. (http://www.zend.com)
 * @license    http://framework.zend.com/license/new-bsd     New BSD License
 * @version    $Id: PriorityQueue.php 24594 2012-01-05 21:27:01Z matthew $
 */


/**
 * Abstract Priority Queue
 *
 * It implements a priority queue.
 * Please go to "Data Structures and Algorithms",
 * Aho, Hopcroft, and Ullman, Addison-Wesley, 1983 (corrected 1987 edition),
 * for implementation details.
 *
 * It provides O(log(N)) time of put/pop operations, where N is a size of queue
 *
 * @category   Zend
 * @package    Zend_Search_Lucene
 * @copyright  Copyright (c) 2005-2012 Zend Technologies USA Inc. (http://www.zend.com)
 * @license    http://framework.zend.com/license/new-bsd     New BSD License
 */
abstract class Zend_Search_Lucene_PriorityQueue
{
    /**
     * Queue heap
     *
     * Heap contains balanced partial ordered binary tree represented in array
     * [0] - top of the tree
     * [1] - first child of [0]
     * [2] - second child of [0]
     * ...
     * [2*n + 1] - first child of [n]
     * [2*n + 2] - second child of [n]
     *
     * @var array
     */
    private $_heap = array();


    /**
     * Add element to the queue
     *
     * O(log(N)) time
     *
     * @param mixed $element
     */
    public function put($element)
    {
        $nodeId   = count($this->_heap);
        $parentId = ($nodeId-1) >> 1;   // floor( ($nodeId-1)/2 )

        while ($nodeId != 0  &&  $this->_less($element, $this->_heap[$parentId])) {
            // Move parent node down
            $this->_heap[$nodeId] = $this->_heap[$parentId];

            // Move pointer to the next level of tree
            $nodeId   = $parentId;
            $parentId = ($nodeId-1) >> 1;   // floor( ($nodeId-1)/2 )
        }

        // Put new node into the tree
        $this->_heap[$nodeId] = $element;
    }


    /**
     * Return least element of the queue
     *
     * Constant time
     *
     * @return mixed
     */
    public function top()
    {
        if (count($this->_heap) == 0) {
            return null;
        }

        return $this->_heap[0];
    }


    /**
     * Removes and return least element of the queue
     *
     * O(log(N)) time
     *
     * @return mixed
     */
    public function pop()
    {
        if (count($this->_heap) == 0) {
            return null;
        }

        $top = $this->_heap[0];
        $lastId = count($this->_heap) - 1;

        /**
         * Find appropriate position for last node
         */
        $nodeId  = 0;     // Start from a top
        $childId = 1;     // First child

        // Choose smaller child
        if ($lastId > 2  &&  $this->_less($this->_heap[2], $this->_heap[1])) {
            $childId = 2;
        }

        while ($childId < $lastId  &&
               $this->_less($this->_heap[$childId], $this->_heap[$lastId])
          ) {
            // Move child node up
            $this->_heap[$nodeId] = $this->_heap[$childId];

            $nodeId  = $childId;               // Go down
            $childId = ($nodeId << 1) + 1;     // First child

            // Choose smaller child
            if (($childId+1) < $lastId  &&
                $this->_less($this->_heap[$childId+1], $this->_heap[$childId])
               ) {
                $childId++;
            }
        }

        // Move last element to the new position
        $this->_heap[$nodeId] = $this->_heap[$lastId];
        unset($this->_heap[$lastId]);

        return $top;
    }


    /**
     * Clear queue
     */
    public function clear()
    {
        $this->_heap = array();
    }


    /**
     * Compare elements
     *
     * Returns true, if $el1 is less than $el2; else otherwise
     *
     * @param mixed $el1
     * @param mixed $el2
     * @return boolean
     */
    abstract protected function _less($el1, $el2);
}