|
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-2010 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 20096 2010-01-06 02:05:09Z 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-2010 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 |