final move of files

[web.mtrack] / Zend / Search / Lucene / PriorityQueue.php

diff --git a/Zend/Search/Lucene/PriorityQueue.php b/Zend/Search/Lucene/PriorityQueue.php
new file mode 100644 (file)
index 0000000..5de3e53
--- /dev/null
+++ b/Zend/Search/Lucene/PriorityQueue.php
@@ -0,0 +1,171 @@
+<?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-2009 Zend Technologies USA Inc. (http://www.zend.com)
+ * @license    http://framework.zend.com/license/new-bsd     New BSD License
+ * @version    $Id: PriorityQueue.php 16541 2009-07-07 06:59:03Z 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-2009 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);
+}
+