Source of file PriorityQueue.php
Size: 4,381 Bytes - Last Modified: 2021-12-23T10:29:30+00:00
/var/www/docs.ssmods.com/process/src/thirdparty/Zend/Search/Lucene/PriorityQueue.php
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172 | <?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-2010 Zend Technologies USA Inc. (http://www.zend.com) * @license http://framework.zend.com/license/new-bsd New BSD License * @version $Id: PriorityQueue.php 20096 2010-01-06 02:05:09Z bkarwin $ */ /** * 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-2010 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); } |