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 if (version_compare(PHP_VERSION, '5.3.0', '<')) {

    22     /**

    23      * SplPriorityQueue 

    24      *

    25      * PHP 5.2.X userland implementation of PHP's SplPriorityQueue

    26      */

    27     class SplPriorityQueue implements Iterator , Countable 

    28     {

    29         /**

    30          * Extract data only

    31          */

    32         const EXTR_DATA = 0x00000001;

    33 

    34         /**

    35          * Extract priority only

    36          */

    37         const EXTR_PRIORITY = 0x00000002;

    38 

    39         /**

    40          * Extract an array of ('data' => $value, 'priority' => $priority)

    41          */

    42         const EXTR_BOTH = 0x00000003;

    43 

    44         /**

    45          * Count of items in the queue

    46          * @var int

    47          */

    48         protected $count = 0;

    49 

    50         /**

    51          * Flag indicating what should be returned when iterating or extracting

    52          * @var int

    53          */

    54         protected $extractFlags = self::EXTR_DATA;

    55 

    56         /**

    57          * @var bool|array

    58          */

    59         protected $preparedQueue = false;

    60 

    61         /**

    62          * All items in the queue

    63          * @var array

    64          */

    65         protected $queue = array();

    66 

    67         /**

    68          * Constructor

    69          * 

    70          * Creates a new, empty queue

    71          * 

    72          * @return void

    73          */

    74         public function __construct()

    75         {

    76         }

    77 

    78         /**

    79          * Compare two priorities

    80          *

    81          * Returns positive integer if $priority1 is greater than $priority2, 0 

    82          * if equal, negative otherwise.

    83          *

    84          * Unused internally, and only included in order to retain the same 

    85          * interface as PHP's SplPriorityQueue.

    86          *

    87          * @param  mixed $priority1

    88          * @param  mixed $priority2

    89          * @return int

    90          */

    91         public function compare($priority1, $priority2)

    92         {

    93             if ($priority1 > $priority2) {

    94                 return 1;

    95             }

    96             if ($priority1 == $priority2) {

    97                 return 0;

    98             }

    99 

   100             return -1;

   101         }

   102 

   103         /**

   104          * Countable: return number of items composed in the queue

   105          * 

   106          * @return int

   107          */

   108         public function count()

   109         {

   110             return $this->count;

   111         }

   112 

   113         /**

   114          * Iterator: return current item

   115          *

   116          * @return mixed

   117          */

   118         public function current()

   119         {

   120             if (!$this->preparedQueue) {

   121                 $this->rewind();

   122             }

   123             if (!$this->count) {

   124                 throw new OutOfBoundsException('Cannot iterate SplPriorityQueue; no elements present');

   125             }

   126 

   127 if (!is_array($this->preparedQueue)) {

   128     throw new DomainException(sprintf(

   129         "Queue was prepared, but is empty?\n    PreparedQueue: %s\n    Internal Queue: %s\n",

   130         var_export($this->preparedQueue, 1),

   131         var_export($this->queue, 1)

   132     ));

   133 }

   134 

   135             $return      = array_shift($this->preparedQueue);

   136             $priority    = $return['priority'];

   137             $priorityKey = $return['priorityKey'];

   138             $key         = $return['key'];

   139             unset($return['key']);

   140             unset($return['priorityKey']);

   141             unset($this->queue[$priorityKey][$key]);

   142 

   143             switch ($this->extractFlags) {

   144                 case self::EXTR_DATA:

   145                     return $return['data'];

   146                 case self::EXTR_PRIORITY:

   147                     return $return['priority'];

   148                 case self::EXTR_BOTH:

   149                 default:

   150                     return $return;

   151             };

   152         }

   153 

   154         /**

   155          * Extract a node from top of the heap and sift up

   156          *

   157          * Returns either the value, the priority, or both, depending on the extract flag.

   158          *

   159          * @return mixed;

   160          */

   161         public function extract()

   162         {

   163             if (!$this->count) {

   164                 return null;

   165             }

   166 

   167             if (!$this->preparedQueue) {

   168                 $this->prepareQueue();

   169             }

   170 

   171             if (empty($this->preparedQueue)) {

   172                 return null;

   173             }

   174 

   175             $return      = array_shift($this->preparedQueue);

   176             $priority    = $return['priority'];

   177             $priorityKey = $return['priorityKey'];

   178             $key         = $return['key'];

   179             unset($return['key']);

   180             unset($return['priorityKey']);

   181             unset($this->queue[$priorityKey][$key]);

   182             $this->count--;

   183 

   184             switch ($this->extractFlags) {

   185                 case self::EXTR_DATA:

   186                     return $return['data'];

   187                 case self::EXTR_PRIORITY:

   188                     return $return['priority'];

   189                 case self::EXTR_BOTH:

   190                 default:

   191                     return $return;

   192             };

   193         }

   194 

   195         /**

   196          * Insert a value into the heap, at the specified priority

   197          *

   198          * @param  mixed $value

   199          * @param  mixed $priority

   200          * @return void

   201          */

   202         public function insert($value, $priority)

   203         {

   204             if (!is_scalar($priority)) {

   205                 $priority = serialize($priority);

   206             }

   207             if (!isset($this->queue[$priority])) {

   208                 $this->queue[$priority] = array();

   209             }

   210             $this->queue[$priority][] = $value;

   211             $this->count++;

   212             $this->preparedQueue = false;

   213         }

   214 

   215         /**

   216          * Is the queue currently empty?

   217          *

   218          * @return bool

   219          */

   220         public function isEmpty()

   221         {

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

   223         }

   224 

   225         /**

   226          * Iterator: return current key

   227          *

   228          * @return mixed Usually an int or string

   229          */

   230         public function key()

   231         {

   232             return $this->count;

   233         }

   234 

   235         /**

   236          * Iterator: Move pointer forward

   237          *

   238          * @return void

   239          */

   240         public function next()

   241         {

   242             $this->count--;

   243         }

   244 

   245         /**

   246          * Recover from corrupted state and allow further actions on the queue

   247          *

   248          * Unimplemented, and only included in order to retain the same interface as PHP's 

   249          * SplPriorityQueue.

   250          *

   251          * @return void

   252          */

   253         public function recoverFromCorruption()

   254         {

   255         }

   256 

   257         /**

   258          * Iterator: Move pointer to first item

   259          *

   260          * @return void

   261          */

   262         public function rewind()

   263         {

   264             if (!$this->preparedQueue) {

   265                 $this->prepareQueue();

   266             }

   267         }

   268 

   269         /**

   270          * Set the extract flags

   271          * 

   272          * Defines what is extracted by SplPriorityQueue::current(), 

   273          * SplPriorityQueue::top() and SplPriorityQueue::extract().

   274          * 

   275          * - SplPriorityQueue::EXTR_DATA (0x00000001): Extract the data

   276          * - SplPriorityQueue::EXTR_PRIORITY (0x00000002): Extract the priority

   277          * - SplPriorityQueue::EXTR_BOTH (0x00000003): Extract an array containing both

   278          *

   279          * The default mode is SplPriorityQueue::EXTR_DATA.

   280          *

   281          * @param  int $flags

   282          * @return void

   283          */

   284         public function setExtractFlags($flags)

   285         {

   286             $expected = array(

   287                 self::EXTR_DATA => true,

   288                 self::EXTR_PRIORITY => true,

   289                 self::EXTR_BOTH => true,

   290             );

   291             if (!isset($expected[$flags])) {

   292                 throw new InvalidArgumentException(sprintf('Expected an EXTR_* flag; received %s', $flags));

   293             }

   294             $this->extractFlags = $flags;

   295         }

   296 

   297         /**

   298          * Return the value or priority (or both) of the top node, depending on 

   299          * the extract flag

   300          *

   301          * @return mixed

   302          */

   303         public function top()

   304         {

   305             $this->sort();

   306             $keys = array_keys($this->queue);

   307             $key  = array_shift($keys);

   308             if (preg_match('/^(a|O):/', $key)) {

   309                 $key = unserialize($key);

   310             }

   311 

   312             if ($this->extractFlags == self::EXTR_PRIORITY) {

   313                 return $key;

   314             }

   315 

   316             if ($this->extractFlags == self::EXTR_DATA) {

   317                 return $this->queue[$key][0];

   318             }

   319 

   320             return array(

   321                 'data'     => $this->queue[$key][0],

   322                 'priority' => $key,

   323             );

   324         }

   325 

   326         /**

   327          * Iterator: is the current position valid for the queue

   328          *

   329          * @return bool

   330          */

   331         public function valid()

   332         {

   333             return (bool) $this->count;

   334         }

   335 

   336         /**

   337          * Sort the queue

   338          * 

   339          * @return void

   340          */

   341         protected function sort()

   342         {

   343             krsort($this->queue);

   344         }

   345 

   346         /**

   347          * Prepare the queue for iteration and/or extraction

   348          * 

   349          * @return void

   350          */

   351         protected function prepareQueue()

   352         {

   353             $this->sort();

   354             $count = $this->count;

   355             $queue = array();

   356             foreach ($this->queue as $priority => $values) {

   357                 $priorityKey = $priority;

   358                 if (preg_match('/^(a|O):/', $priority)) {

   359                     $priority = unserialize($priority);

   360                 }

   361                 foreach ($values as $key => $value) {

   362                     $queue[$count] = array(

   363                         'data'        => $value,

   364                         'priority'    => $priority,

   365                         'priorityKey' => $priorityKey,

   366                         'key'         => $key,

   367                     );

   368                     $count--;

   369                 }

   370             }

   371             $this->preparedQueue = $queue;

   372         }

   373     }

   374 }

   375 

   376 /**

   377  * Serializable version of SplPriorityQueue

   378  *

   379  * Also, provides predictable heap order for datums added with the same priority

   380  * (i.e., they will be emitted in the same order they are enqueued).

   381  *

   382  * @category   Zend

   383  * @package    Zend_Stdlib

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

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

   386  */

   387 class Zend_Stdlib_SplPriorityQueue extends SplPriorityQueue implements Serializable

   388 {

   389     /**

   390      * @var int Seed used to ensure queue order for items of the same priority

   391      */

   392     protected $serial = PHP_INT_MAX;

   393 

   394     /**

   395      * @var bool

   396      */

   397     protected $isPhp53;

   398 

   399     /**

   400      * Constructor

   401      * 

   402      * @return void

   403      */

   404     public function __construct()

   405     {

   406         $this->isPhp53 = version_compare(PHP_VERSION, '5.3', '>=');

   407     }

   408 

   409     /**

   410      * Insert a value with a given priority

   411      *

   412      * Utilizes {@var $serial} to ensure that values of equal priority are 

   413      * emitted in the same order in which they are inserted.

   414      * 

   415      * @param  mixed $datum 

   416      * @param  mixed $priority 

   417      * @return void

   418      */

   419     public function insert($datum, $priority)

   420     {

   421         // If using the native PHP SplPriorityQueue implementation, we need to

   422         // hack around it to ensure that items registered at the same priority

   423         // return in the order registered. In the userland version, this is not

   424         // necessary.

   425         if ($this->isPhp53) {

   426             if (!is_array($priority)) {

   427                 $priority = array($priority, $this->serial--);

   428             }

   429         }

   430         parent::insert($datum, $priority);

   431     }

   432 

   433     /**

   434      * Serialize to an array

   435      *

   436      * Array will be priority => data pairs

   437      * 

   438      * @return array

   439      */

   440     public function toArray()

   441     {

   442         $this->setExtractFlags(self::EXTR_BOTH);

   443         $array = array();

   444         while ($this->valid()) {

   445             $array[] = $this->current();

   446             $this->next();

   447         }

   448         $this->setExtractFlags(self::EXTR_DATA);

   449 

   450         // Iterating through a priority queue removes items

   451         foreach ($array as $item) {

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

   453         }

   454 

   455         // Return only the data

   456         $return = array();

   457         foreach ($array as $item) {

   458             $return[] = $item['data'];

   459         }

   460 

   461         return $return;

   462     }

   463 

   464     /**

   465      * Serialize

   466      * 

   467      * @return string

   468      */

   469     public function serialize()

   470     {

   471         $data = array();

   472         $this->setExtractFlags(self::EXTR_BOTH);

   473         while ($this->valid()) {

   474             $data[] = $this->current();

   475             $this->next();

   476         }

   477         $this->setExtractFlags(self::EXTR_DATA);

   478 

   479         // Iterating through a priority queue removes items

   480         foreach ($data as $item) {

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

   482         }

   483 

   484         return serialize($data);

   485     }

   486 

   487     /**

   488      * Deserialize

   489      * 

   490      * @param  string $data

   491      * @return void

   492      */

   493     public function unserialize($data)

   494     {

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

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

   497         }

   498     }

   499 }