vendor/laminas/laminas-stdlib/src/PriorityQueue.php line 33

Open in your IDE?
  1. <?php
  2. declare(strict_types=1);
  3. namespace Laminas\Stdlib;
  4. use Countable;
  5. use IteratorAggregate;
  6. use ReturnTypeWillChange;
  7. use Serializable;
  8. use UnexpectedValueException;
  9. use function array_map;
  10. use function count;
  11. use function get_class;
  12. use function is_array;
  13. use function serialize;
  14. use function sprintf;
  15. use function unserialize;
  16. /**
  17.  * Re-usable, serializable priority queue implementation
  18.  *
  19.  * SplPriorityQueue acts as a heap; on iteration, each item is removed from the
  20.  * queue. If you wish to re-use such a queue, you need to clone it first. This
  21.  * makes for some interesting issues if you wish to delete items from the queue,
  22.  * or, as already stated, iterate over it multiple times.
  23.  *
  24.  * This class aggregates items for the queue itself, but also composes an
  25.  * "inner" iterator in the form of an SplPriorityQueue object for performing
  26.  * the actual iteration.
  27.  */
  28. class PriorityQueue implements CountableIteratorAggregateSerializable
  29. {
  30.     public const EXTR_DATA     0x00000001;
  31.     public const EXTR_PRIORITY 0x00000002;
  32.     public const EXTR_BOTH     0x00000003;
  33.     /**
  34.      * Inner queue class to use for iteration
  35.      *
  36.      * @var string
  37.      */
  38.     protected $queueClass SplPriorityQueue::class;
  39.     /**
  40.      * Actual items aggregated in the priority queue. Each item is an array
  41.      * with keys "data" and "priority".
  42.      *
  43.      * @var array
  44.      */
  45.     protected $items = [];
  46.     /**
  47.      * Inner queue object
  48.      *
  49.      * @var SplPriorityQueue
  50.      */
  51.     protected $queue;
  52.     /**
  53.      * Insert an item into the queue
  54.      *
  55.      * Priority defaults to 1 (low priority) if none provided.
  56.      *
  57.      * @param  mixed $data
  58.      * @param  int $priority
  59.      * @return PriorityQueue
  60.      */
  61.     public function insert($data$priority 1)
  62.     {
  63.         $priority      = (int) $priority;
  64.         $this->items[] = [
  65.             'data'     => $data,
  66.             'priority' => $priority,
  67.         ];
  68.         $this->getQueue()->insert($data$priority);
  69.         return $this;
  70.     }
  71.     /**
  72.      * Remove an item from the queue
  73.      *
  74.      * This is different than {@link extract()}; its purpose is to dequeue an
  75.      * item.
  76.      *
  77.      * This operation is potentially expensive, as it requires
  78.      * re-initialization and re-population of the inner queue.
  79.      *
  80.      * Note: this removes the first item matching the provided item found. If
  81.      * the same item has been added multiple times, it will not remove other
  82.      * instances.
  83.      *
  84.      * @param  mixed $datum
  85.      * @return bool False if the item was not found, true otherwise.
  86.      */
  87.     public function remove($datum)
  88.     {
  89.         $found false;
  90.         foreach ($this->items as $key => $item) {
  91.             if ($item['data'] === $datum) {
  92.                 $found true;
  93.                 break;
  94.             }
  95.         }
  96.         if ($found) {
  97.             unset($this->items[$key]);
  98.             $this->queue null;
  99.             if (! $this->isEmpty()) {
  100.                 $queue $this->getQueue();
  101.                 foreach ($this->items as $item) {
  102.                     $queue->insert($item['data'], $item['priority']);
  103.                 }
  104.             }
  105.             return true;
  106.         }
  107.         return false;
  108.     }
  109.     /**
  110.      * Is the queue empty?
  111.      *
  112.      * @return bool
  113.      */
  114.     public function isEmpty()
  115.     {
  116.         return === $this->count();
  117.     }
  118.     /**
  119.      * How many items are in the queue?
  120.      *
  121.      * @return int
  122.      */
  123.     #[ReturnTypeWillChange]
  124.     public function count()
  125.     {
  126.         return count($this->items);
  127.     }
  128.     /**
  129.      * Peek at the top node in the queue, based on priority.
  130.      *
  131.      * @return mixed
  132.      */
  133.     public function top()
  134.     {
  135.         return $this->getIterator()->top();
  136.     }
  137.     /**
  138.      * Extract a node from the inner queue and sift up
  139.      *
  140.      * @return mixed
  141.      */
  142.     public function extract()
  143.     {
  144.         $value $this->getQueue()->extract();
  145.         $keyToRemove     null;
  146.         $highestPriority null;
  147.         foreach ($this->items as $key => $item) {
  148.             if ($item['data'] !== $value) {
  149.                 continue;
  150.             }
  151.             if (null === $highestPriority) {
  152.                 $highestPriority $item['priority'];
  153.                 $keyToRemove     $key;
  154.                 continue;
  155.             }
  156.             if ($highestPriority >= $item['priority']) {
  157.                 continue;
  158.             }
  159.             $highestPriority $item['priority'];
  160.             $keyToRemove     $key;
  161.         }
  162.         if ($keyToRemove !== null) {
  163.             unset($this->items[$keyToRemove]);
  164.         }
  165.         return $value;
  166.     }
  167.     /**
  168.      * Retrieve the inner iterator
  169.      *
  170.      * SplPriorityQueue acts as a heap, which typically implies that as items
  171.      * are iterated, they are also removed. This does not work for situations
  172.      * where the queue may be iterated multiple times. As such, this class
  173.      * aggregates the values, and also injects an SplPriorityQueue. This method
  174.      * retrieves the inner queue object, and clones it for purposes of
  175.      * iteration.
  176.      *
  177.      * @return SplPriorityQueue
  178.      */
  179.     #[ReturnTypeWillChange]
  180.     public function getIterator()
  181.     {
  182.         $queue $this->getQueue();
  183.         return clone $queue;
  184.     }
  185.     /**
  186.      * Serialize the data structure
  187.      *
  188.      * @return string
  189.      */
  190.     public function serialize()
  191.     {
  192.         return serialize($this->__serialize());
  193.     }
  194.     /**
  195.      * Magic method used for serializing of an instance.
  196.      *
  197.      * @return array
  198.      */
  199.     public function __serialize()
  200.     {
  201.         return $this->items;
  202.     }
  203.     /**
  204.      * Unserialize a string into a PriorityQueue object
  205.      *
  206.      * Serialization format is compatible with {@link Laminas\Stdlib\SplPriorityQueue}
  207.      *
  208.      * @param  string $data
  209.      * @return void
  210.      */
  211.     public function unserialize($data)
  212.     {
  213.         $toUnserialize unserialize($data);
  214.         if (! is_array($toUnserialize)) {
  215.             throw new UnexpectedValueException(sprintf(
  216.                 'Cannot deserialize %s instance; corrupt serialization data',
  217.                 self::class
  218.             ));
  219.         }
  220.         $this->__unserialize($toUnserialize);
  221.     }
  222.    /**
  223.     * Magic method used to rebuild an instance.
  224.     *
  225.     * @param array $data Data array.
  226.     * @return void
  227.     */
  228.     public function __unserialize($data)
  229.     {
  230.         foreach ($data as $item) {
  231.             $this->insert($item['data'], $item['priority']);
  232.         }
  233.     }
  234.     /**
  235.      * Serialize to an array
  236.      *
  237.      * By default, returns only the item data, and in the order registered (not
  238.      * sorted). You may provide one of the EXTR_* flags as an argument, allowing
  239.      * the ability to return priorities or both data and priority.
  240.      *
  241.      * @param  int $flag
  242.      * @return array
  243.      */
  244.     public function toArray($flag self::EXTR_DATA)
  245.     {
  246.         switch ($flag) {
  247.             case self::EXTR_BOTH:
  248.                 return $this->items;
  249.             case self::EXTR_PRIORITY:
  250.                 return array_map(function ($item) {
  251.                     return $item['priority'];
  252.                 }, $this->items);
  253.             case self::EXTR_DATA:
  254.             default:
  255.                 return array_map(function ($item) {
  256.                     return $item['data'];
  257.                 }, $this->items);
  258.         }
  259.     }
  260.     /**
  261.      * Specify the internal queue class
  262.      *
  263.      * Please see {@link getIterator()} for details on the necessity of an
  264.      * internal queue class. The class provided should extend SplPriorityQueue.
  265.      *
  266.      * @param  string $class
  267.      * @return PriorityQueue
  268.      */
  269.     public function setInternalQueueClass($class)
  270.     {
  271.         $this->queueClass = (string) $class;
  272.         return $this;
  273.     }
  274.     /**
  275.      * Does the queue contain the given datum?
  276.      *
  277.      * @param  mixed $datum
  278.      * @return bool
  279.      */
  280.     public function contains($datum)
  281.     {
  282.         foreach ($this->items as $item) {
  283.             if ($item['data'] === $datum) {
  284.                 return true;
  285.             }
  286.         }
  287.         return false;
  288.     }
  289.     /**
  290.      * Does the queue have an item with the given priority?
  291.      *
  292.      * @param  int $priority
  293.      * @return bool
  294.      */
  295.     public function hasPriority($priority)
  296.     {
  297.         foreach ($this->items as $item) {
  298.             if ($item['priority'] === $priority) {
  299.                 return true;
  300.             }
  301.         }
  302.         return false;
  303.     }
  304.     /**
  305.      * Get the inner priority queue instance
  306.      *
  307.      * @throws Exception\DomainException
  308.      * @return SplPriorityQueue
  309.      */
  310.     protected function getQueue()
  311.     {
  312.         if (null === $this->queue) {
  313.             $this->queue = new $this->queueClass();
  314.             if (! $this->queue instanceof \SplPriorityQueue) {
  315.                 throw new Exception\DomainException(sprintf(
  316.                     'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
  317.                     get_class($this->queue)
  318.                 ));
  319.             }
  320.         }
  321.         return $this->queue;
  322.     }
  323.     /**
  324.      * Add support for deep cloning
  325.      *
  326.      * @return void
  327.      */
  328.     public function __clone()
  329.     {
  330.         if (null !== $this->queue) {
  331.             $this->queue = clone $this->queue;
  332.         }
  333.     }
  334. }