search/Zend/Search/Lucene/PriorityQueue.php

   1 <?php
   2 /**
   3  * Zend Framework
   4  *
   5  * LICENSE
   6  *
   7  * This source file is subject to the new BSD license that is bundled
   8  * with this package in the file LICENSE.txt.
   9  * It is also available through the world-wide-web at this URL:
  10  * http://framework.zend.com/license/new-bsd
  11  * If you did not receive a copy of the license and are unable to
  12  * obtain it through the world-wide-web, please send an email
  13  * to license@zend.com so we can send you a copy immediately.
  14  *
  15  * @category   Zend
  16  * @package    Zend_Search_Lucene
  17  * @copyright  Copyright (c) 2005-2007 Zend Technologies USA Inc. (http://www.zend.com)
  18  * @license    http://framework.zend.com/license/new-bsd     New BSD License
  19  */
  20
  21
  22 /**
  23  * Abstract Priority Queue
  24  *
  25  * It implements a priority queue.
  26  * Please go to "Data Structures and Algorithms",
  27  * Aho, Hopcroft, and Ullman, Addison-Wesley, 1983 (corrected 1987 edition),
  28  * for implementation details.
  29  *
  30  * It provides O(log(N)) time of put/pop operations, where N is a size of queue
  31  *
  32  * @category   Zend
  33  * @package    Zend_Search_Lucene
  34  * @copyright  Copyright (c) 2005-2007 Zend Technologies USA Inc. (http://www.zend.com)
  35  * @license    http://framework.zend.com/license/new-bsd     New BSD License
  36  */
  37 abstract class Zend_Search_Lucene_PriorityQueue
  38 {
  39     /**
  40      * Queue heap
  41      *
  42      * Heap contains balanced partial ordered binary tree represented in array
  43      * [0] - top of the tree
  44      * [1] - first child of [0]
  45      * [2] - second child of [0]
  46      * ...
  47      * [2*n + 1] - first child of [n]
  48      * [2*n + 2] - second child of [n]
  49      *
  50      * @var array
  51      */
  52     private $_heap = array();
  53
  54
  55     /**
  56      * Add element to the queue
  57      *
  58      * O(log(N)) time
  59      *
  60      * @param mixed $element
  61      */
  62     public function put($element)
  63     {
  64         $nodeId   = count($this->_heap);
  65         $parentId = ($nodeId-1) >> 1;   // floor( ($nodeId-1)/2 )
  66
  67         while ($nodeId != 0  &&  $this->_less($element, $this->_heap[$parentId])) {
  68             // Move parent node down
  69             $this->_heap[$nodeId] = $this->_heap[$parentId];
  70
  71             // Move pointer to the next level of tree
  72             $nodeId   = $parentId;
  73             $parentId = ($nodeId-1) >> 1;   // floor( ($nodeId-1)/2 )
  74         }
  75
  76         // Put new node into the tree
  77         $this->_heap[$nodeId] = $element;
  78     }
  79
  80
  81     /**
  82      * Return least element of the queue
  83      *
  84      * Constant time
  85      *
  86      * @return mixed
  87      */
  88     public function top()
  89     {
  90         if (count($this->_heap) == 0) {
  91             return null;
  92         }
  93
  94         return $this->_heap[0];
  95     }
  96
  97
  98     /**
  99      * Removes and return least element of the queue
 100      *
 101      * O(log(N)) time
 102      *
 103      * @return mixed
 104      */
 105     public function pop()
 106     {
 107         if (count($this->_heap) == 0) {
 108             return null;
 109         }
 110
 111         $top = $this->_heap[0];
 112         $lastId = count($this->_heap) - 1;
 113
 114         /**
 115          * Find appropriate position for last node
 116          */
 117         $nodeId  = 0;     // Start from a top
 118         $childId = 1;     // First child
 119
 120         // Choose smaller child
 121         if ($lastId > 2  &&  $this->_less($this->_heap[2], $this->_heap[1])) {
 122             $childId = 2;
 123         }
 124
 125         while ($childId < $lastId  &&
 126                $this->_less($this->_heap[$childId], $this->_heap[$lastId])
 127           ) {
 128             // Move child node up
 129             $this->_heap[$nodeId] = $this->_heap[$childId];
 130
 131             $nodeId  = $childId;               // Go down
 132             $childId = ($nodeId << 1) + 1;     // First child
 133
 134             // Choose smaller child
 135             if (($childId+1) < $lastId  &&
 136                 $this->_less($this->_heap[$childId+1], $this->_heap[$childId])
 137                ) {
 138                 $childId++;
 139             }
 140         }
 141
 142         // Move last element to the new position
 143         $this->_heap[$nodeId] = $this->_heap[$lastId];
 144         unset($this->_heap[$lastId]);
 145
 146         return $top;
 147     }
 148
 149
 150     /**
 151      * Clear queue
 152      */
 153     public function clear()
 154     {
 155         $this->_heap = array();
 156     }
 157
 158
 159     /**
 160      * Compare elements
 161      *
 162      * Returns true, if $el1 is less than $el2; else otherwise
 163      *
 164      * @param mixed $el1
 165      * @param mixed $el2
 166      * @return boolean
 167      */
 168     abstract protected function _less($el1, $el2);
 169 }
 170