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_Stdlib

    17  * @copyright  Copyright (c) 2005-2012 Zend Technologies USA Inc. (http://www.zend.com)

    18  * @license    http://framework.zend.com/license/new-bsd     New BSD License

    19  */

    20 

    21 require_once 'Zend/Stdlib/SplPriorityQueue.php';

    22 

    23 /**

    24  * Re-usable, serializable priority queue implementation

    25  *

    26  * SplPriorityQueue acts as a heap; on iteration, each item is removed from the

    27  * queue. If you wish to re-use such a queue, you need to clone it first. This 

    28  * makes for some interesting issues if you wish to delete items from the queue,

    29  * or, as already stated, iterate over it multiple times.

    30  *

    31  * This class aggregates items for the queue itself, but also composes an 

    32  * "inner" iterator in the form of an SplPriorityQueue object for performing

    33  * the actual iteration.

    34  *

    35  * @category   Zend

    36  * @package    Zend_Stdlib

    37  * @copyright  Copyright (c) 2005-2012 Zend Technologies USA Inc. (http://www.zend.com)

    38  * @license    http://framework.zend.com/license/new-bsd     New BSD License

    39  */

    40 class Zend_Stdlib_PriorityQueue implements Countable, IteratorAggregate, Serializable

    41 {

    42     const EXTR_DATA     = 0x00000001;

    43     const EXTR_PRIORITY = 0x00000002;

    44     const EXTR_BOTH     = 0x00000003;

    45 

    46     /**

    47      * Inner queue class to use for iteration

    48      * @var string

    49      */

    50     protected $queueClass = 'Zend_Stdlib_SplPriorityQueue';

    51 

    52     /**

    53      * Actual items aggregated in the priority queue. Each item is an array

    54      * with keys "data" and "priority".

    55      * @var array

    56      */

    57     protected $items      = array();

    58 

    59     /**

    60      * Inner queue object

    61      * @var SplPriorityQueue

    62      */

    63     protected $queue;

    64 

    65     /**

    66      * Insert an item into the queue

    67      *

    68      * Priority defaults to 1 (low priority) if none provided.

    69      * 

    70      * @param  mixed $data 

    71      * @param  int $priority 

    72      * @return Zend_Stdlib_PriorityQueue

    73      */

    74     public function insert($data, $priority = 1)

    75     {

    76         $priority = (int) $priority;

    77         $this->items[] = array(

    78             'data'     => $data,

    79             'priority' => $priority,

    80         );

    81         $this->getQueue()->insert($data, $priority);

    82         return $this;

    83     }

    84 

    85     /**

    86      * Remove an item from the queue

    87      *

    88      * This is different than {@link extract()}; its purpose is to dequeue an

    89      * item.

    90      *

    91      * This operation is potentially expensive, as it requires 

    92      * re-initialization and re-population of the inner queue.

    93      * 

    94      * Note: this removes the first item matching the provided item found. If

    95      * the same item has been added multiple times, it will not remove other 

    96      * instances.

    97      *

    98      * @param  mixed $datum

    99      * @return boolean False if the item was not found, true otherwise.

   100      */

   101     public function remove($datum)

   102     {

   103         $found = false;

   104         foreach ($this->items as $key => $item) {

   105             if ($item['data'] === $datum) {

   106                 $found = true;

   107                 break;

   108             }

   109         }

   110         if ($found) {

   111             unset($this->items[$key]);

   112             $this->queue = null;

   113             $queue = $this->getQueue();

   114             foreach ($this->items as $item) {

   115                 $queue->insert($item['data'], $item['priority']);

   116             }

   117             return true;

   118         }

   119         return false;

   120     }

   121 

   122     /**

   123      * Is the queue empty?

   124      * 

   125      * @return bool

   126      */

   127     public function isEmpty()

   128     {

   129         return (0 === $this->count());

   130     }

   131 

   132     /**

   133      * How many items are in the queue?

   134      * 

   135      * @return int

   136      */

   137     public function count()

   138     {

   139         return count($this->items);

   140     }

   141 

   142     /**

   143      * Peek at the top node in the queue, based on priority.

   144      * 

   145      * @return mixed

   146      */

   147     public function top()

   148     {

   149         return $this->getIterator()->top();

   150     }

   151 

   152     /**

   153      * Extract a node from the inner queue and sift up 

   154      * 

   155      * @return mixed

   156      */

   157     public function extract()

   158     {

   159         return $this->getQueue()->extract();

   160     }

   161 

   162     /**

   163      * Retrieve the inner iterator

   164      *

   165      * SplPriorityQueue acts as a heap, which typically implies that as items

   166      * are iterated, they are also removed. This does not work for situations

   167      * where the queue may be iterated multiple times. As such, this class 

   168      * aggregates the values, and also injects an SplPriorityQueue. This method 

   169      * retrieves the inner queue object, and clones it for purposes of 

   170      * iteration.

   171      * 

   172      * @return SplPriorityQueue

   173      */

   174     public function getIterator()

   175     {

   176         $queue = $this->getQueue();

   177         return clone $queue;

   178     }

   179 

   180     /**

   181      * Serialize the data structure

   182      * 

   183      * @return string

   184      */

   185     public function serialize()

   186     {

   187         return serialize($this->items);

   188     }

   189 

   190     /**

   191      * Unserialize a string into a Zend_Stdlib_PriorityQueue object

   192      *

   193      * Serialization format is compatible with {@link Zend_Stdlib_SplPriorityQueue}

   194      * 

   195      * @param  string $data 

   196      * @return void

   197      */

   198     public function unserialize($data)

   199     {

   200         foreach (unserialize($data) as $item) {

   201             $this->insert($item['data'], $item['priority']);

   202         }

   203     }

   204 

   205     /**

   206      * Serialize to an array

   207      *

   208      * By default, returns only the item data, and in the order registered (not

   209      * sorted). You may provide one of the EXTR_* flags as an argument, allowing

   210      * the ability to return priorities or both data and priority.

   211      * 

   212      * @param  int $flag 

   213      * @return array

   214      */

   215     public function toArray($flag = self::EXTR_DATA)

   216     {

   217         switch ($flag) {

   218             case self::EXTR_BOTH:

   219                 return $this->items;

   220             case self::EXTR_PRIORITY:

   221                 return array_map(array($this, 'returnPriority'), $this->items);

   222             case self::EXTR_DATA:

   223             default:

   224                 return array_map(array($this, 'returnData'), $this->items);

   225         }

   226     }

   227 

   228     /**

   229      * Specify the internal queue class

   230      *

   231      * Please see {@link getIterator()} for details on the necessity of an

   232      * internal queue class. The class provided should extend SplPriorityQueue.

   233      * 

   234      * @param  string $class 

   235      * @return Zend_Stdlib_PriorityQueue

   236      */

   237     public function setInternalQueueClass($class)

   238     {

   239         $this->queueClass = (string) $class;

   240         return $this;

   241     }

   242 

   243     /**

   244      * Does the queue contain the given datum?

   245      * 

   246      * @param  mixed $datum 

   247      * @return bool

   248      */

   249     public function contains($datum)

   250     {

   251         foreach ($this->items as $item) {

   252             if ($item['data'] === $datum) {

   253                 return true;

   254             }

   255         }

   256         return false;

   257     }

   258 

   259     /**

   260      * Does the queue have an item with the given priority?

   261      * 

   262      * @param  int $priority 

   263      * @return bool

   264      */

   265     public function hasPriority($priority)

   266     {

   267         foreach ($this->items as $item) {

   268             if ($item['priority'] === $priority) {

   269                 return true;

   270             }

   271         }

   272         return false;

   273     }

   274 

   275     /**

   276      * Get the inner priority queue instance

   277      * 

   278      * @return Zend_Stdlib_SplPriorityQueue

   279      */

   280     protected function getQueue()

   281     {

   282         if (null === $this->queue) {

   283             $this->queue = new $this->queueClass();

   284             if (!$this->queue instanceof SplPriorityQueue) {

   285                 throw new DomainException(sprintf(

   286                     'Zend_Stdlib_PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',

   287                     get_class($this->queue)

   288                 ));

   289             }

   290         }

   291         return $this->queue;

   292     }

   293 

   294     /**

   295      * Return priority from an internal item

   296      *

   297      * Used as a lambda in toArray().

   298      * 

   299      * @param  array $item 

   300      * @return mixed

   301      */

   302     public function returnPriority($item)

   303     {

   304         return $item['priority'];

   305     }

   306 

   307     /**

   308      * Return data from an internal item

   309      *

   310      * Used as a lambda in toArray().

   311      * 

   312      * @param  array $item 

   313      * @return mixed

   314      */

   315     public function returnData($item)

   316     {

   317         return $item['data'];

   318     }

   319 }