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