{"action":"created","issue":{"url":"https://api.github.com/repos/zendframework/zend-stdlib/issues/18","labels_url":"https://api.github.com/repos/zendframework/zend-stdlib/issues/18/labels{/name}","comments_url":"https://api.github.com/repos/zendframework/zend-stdlib/issues/18/comments","events_url":"https://api.github.com/repos/zendframework/zend-stdlib/issues/18/events","html_url":"https://github.com/zendframework/zend-stdlib/issues/18","id":105252874,"number":18,"title":"Optimization of the SplPriorityQueue","user":{"login":"dimon-smith","id":14151562,"avatar_url":"https://avatars.githubusercontent.com/u/14151562?v=3","gravatar_id":"","url":"https://api.github.com/users/dimon-smith","html_url":"https://github.com/dimon-smith","followers_url":"https://api.github.com/users/dimon-smith/followers","following_url":"https://api.github.com/users/dimon-smith/following{/other_user}","gists_url":"https://api.github.com/users/dimon-smith/gists{/gist_id}","starred_url":"https://api.github.com/users/dimon-smith/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dimon-smith/subscriptions","organizations_url":"https://api.github.com/users/dimon-smith/orgs","repos_url":"https://api.github.com/users/dimon-smith/repos","events_url":"https://api.github.com/users/dimon-smith/events{/privacy}","received_events_url":"https://api.github.com/users/dimon-smith/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-09-07T18:02:11Z","updated_at":"2015-09-17T15:23:23Z","closed_at":null,"body":"I'm sorry, I do not do PR. But I'll show you the code.\r\n\r\nEvent Manager uses the queue.\r\n1) For the experiment, I did a SplPriorityQueue with php. If you add an element to the queue, this leads to complex calculations. But not every Queue will be used by the event manager!!!!!!!\r\n- Therefore, I propose to add items only to the array, but SplPriorityQueue create only when the getIterator() method uses.\r\n\r\n2) Delete operations are very complex in terms of computing. Two or more operations - even worse :)\r\n- The solution is the same. I propose to add items only to the array, but SplPriorityQueue create only when the getIterator() method uses.\r\n```php\r\n<?php\r\n\r\nnamespace Zend\\Stdlib;\r\n\r\nuse Countable;\r\nuse IteratorAggregate;\r\nuse Serializable;\r\n\r\n/**\r\n * Optimized for add and remove operations.\r\n */\r\nclass PriorityQueue implements Countable, IteratorAggregate, Serializable\r\n{\r\n    const EXTR_DATA     = 0x00000001;\r\n    const EXTR_PRIORITY = 0x00000002;\r\n    const EXTR_BOTH     = 0x00000003;\r\n\r\n    /**\r\n     * Inner queue class to use for iteration\r\n     * @var string\r\n     */\r\n    protected $queueClass = 'Zend\\Stdlib\\SplPriorityQueue';\r\n\r\n    /**\r\n     * Actual items aggregated in the priority queue. Each item is an array\r\n     * with keys \"data\" and \"priority\".\r\n     * @var array\r\n     */\r\n    protected $items      = [];\r\n\r\n    /**\r\n     * Inner queue object\r\n     * @var SplPriorityQueue\r\n     */\r\n    protected $queue;\r\n\r\n    /**\r\n     * Insert an item into the queue\r\n     *\r\n     * Priority defaults to 1 (low priority) if none provided.\r\n     *\r\n     * @param  mixed $data\r\n     * @param  int $priority\r\n     * @return PriorityQueue\r\n     */\r\n    public function insert($data, $priority = 1)\r\n    {\r\n        $priority = (int) $priority;\r\n        $this->items[] = [\r\n            'data'     => $data,\r\n            'priority' => $priority,\r\n        ];\r\n        $this->queue = null;\r\n        return $this;\r\n    }\r\n\r\n    /**\r\n     * Remove an item from the queue\r\n     *\r\n     * This is different than {@link extract()}; its purpose is to dequeue an\r\n     * item.\r\n     *\r\n     * This operation is potentially expensive, as it requires\r\n     * re-initialization and re-population of the inner queue.\r\n     *\r\n     * Note: this removes the first item matching the provided item found. If\r\n     * the same item has been added multiple times, it will not remove other\r\n     * instances.\r\n     *\r\n     * @param  mixed $datum\r\n     * @return bool False if the item was not found, true otherwise.\r\n     */\r\n    public function remove($datum)\r\n    {\r\n        $found = false;\r\n        foreach ($this->items as $key => $item) {\r\n            if ($item['data'] === $datum) {\r\n                unset($this->items[$key]);\r\n                $this->queue = null;\r\n                $found = true;\r\n                break;\r\n            }\r\n        }\r\n        return $found;\r\n    }\r\n\r\n    /**\r\n     * Is the queue empty?\r\n     *\r\n     * @return bool\r\n     */\r\n    public function isEmpty()\r\n    {\r\n        return (0 === $this->count());\r\n    }\r\n\r\n    /**\r\n     * How many items are in the queue?\r\n     *\r\n     * @return int\r\n     */\r\n    public function count()\r\n    {\r\n        return count($this->items);\r\n    }\r\n\r\n    /**\r\n     * Peek at the top node in the queue, based on priority.\r\n     *\r\n     * @return mixed\r\n     */\r\n    public function top()\r\n    {\r\n        return $this->getIterator()->top();\r\n    }\r\n\r\n    /**\r\n     * Extract a node from the inner queue and sift up\r\n     *\r\n     * @return mixed\r\n     */\r\n    public function extract()\r\n    {\r\n        return $this->getQueue()->extract();\r\n    }\r\n\r\n    /**\r\n     * Retrieve the inner iterator\r\n     *\r\n     * SplPriorityQueue acts as a heap, which typically implies that as items\r\n     * are iterated, they are also removed. This does not work for situations\r\n     * where the queue may be iterated multiple times. As such, this class\r\n     * aggregates the values, and also injects an SplPriorityQueue. This method\r\n     * retrieves the inner queue object, and clones it for purposes of\r\n     * iteration.\r\n     *\r\n     * @return SplPriorityQueue\r\n     */\r\n    public function getIterator()\r\n    {\r\n        $queue = $this->getQueue();\r\n        return clone $queue;\r\n    }\r\n\r\n    /**\r\n     * Serialize the data structure\r\n     *\r\n     * @return string\r\n     */\r\n    public function serialize()\r\n    {\r\n        return serialize($this->items);\r\n    }\r\n\r\n    /**\r\n     * Unserialize a string into a PriorityQueue object\r\n     *\r\n     * Serialization format is compatible with {@link Zend\\Stdlib\\SplPriorityQueue}\r\n     *\r\n     * @param  string $data\r\n     * @return void\r\n     */\r\n    public function unserialize($data)\r\n    {\r\n        foreach (unserialize($data) as $item) {\r\n            $this->insert($item['data'], $item['priority']);\r\n        }\r\n    }\r\n\r\n    /**\r\n     * Serialize to an array\r\n     *\r\n     * By default, returns only the item data, and in the order registered (not\r\n     * sorted). You may provide one of the EXTR_* flags as an argument, allowing\r\n     * the ability to return priorities or both data and priority.\r\n     *\r\n     * @param  int $flag\r\n     * @return array\r\n     */\r\n    public function toArray($flag = self::EXTR_DATA)\r\n    {\r\n        switch ($flag) {\r\n            case self::EXTR_BOTH:\r\n                return $this->items;\r\n            case self::EXTR_PRIORITY:\r\n                return array_map(function ($item) {\r\n                    return $item['priority'];\r\n                }, $this->items);\r\n            case self::EXTR_DATA:\r\n            default:\r\n                return array_map(function ($item) {\r\n                    return $item['data'];\r\n                }, $this->items);\r\n        }\r\n    }\r\n\r\n    /**\r\n     * Specify the internal queue class\r\n     *\r\n     * Please see {@link getIterator()} for details on the necessity of an\r\n     * internal queue class. The class provided should extend SplPriorityQueue.\r\n     *\r\n     * @param  string $class\r\n     * @return PriorityQueue\r\n     */\r\n    public function setInternalQueueClass($class)\r\n    {\r\n        $this->queueClass = (string) $class;\r\n        return $this;\r\n    }\r\n\r\n    /**\r\n     * Does the queue contain the given datum?\r\n     *\r\n     * @param  mixed $datum\r\n     * @return bool\r\n     */\r\n    public function contains($datum)\r\n    {\r\n        foreach ($this->items as $item) {\r\n            if ($item['data'] === $datum) {\r\n                return true;\r\n            }\r\n        }\r\n        return false;\r\n    }\r\n\r\n    /**\r\n     * Does the queue have an item with the given priority?\r\n     *\r\n     * @param  int $priority\r\n     * @return bool\r\n     */\r\n    public function hasPriority($priority)\r\n    {\r\n        foreach ($this->items as $item) {\r\n            if ($item['priority'] === $priority) {\r\n                return true;\r\n            }\r\n        }\r\n        return false;\r\n    }\r\n\r\n    /**\r\n     * Get the inner priority queue instance\r\n     *\r\n     * @throws Exception\\DomainException\r\n     * @return SplPriorityQueue\r\n     */\r\n    protected function getQueue()\r\n    {\r\n        if (null === $this->queue) {\r\n            $this->queue = new $this->queueClass();\r\n            if (!$this->queue instanceof \\SplPriorityQueue) {\r\n                throw new Exception\\DomainException(sprintf(\r\n                    'PriorityQueue expects an internal queue of type SplPriorityQueue; received \"%s\"',\r\n                    get_class($this->queue)\r\n                ));\r\n            }\r\n            foreach ($this->items as $item) {\r\n                $this->queue->insert($item['data'], $item['priority']);\r\n            }\r\n        }\r\n        return $this->queue;\r\n    }\r\n\r\n    /**\r\n     * Add support for deep cloning\r\n     *\r\n     * @return void\r\n     */\r\n    public function __clone()\r\n    {\r\n        if (null !== $this->queue) {\r\n            $this->queue = clone $this->queue;\r\n        }\r\n    }\r\n}\r\n\r\n```"},"comment":{"url":"https://api.github.com/repos/zendframework/zend-stdlib/issues/comments/141120933","html_url":"https://github.com/zendframework/zend-stdlib/issues/18#issuecomment-141120933","issue_url":"https://api.github.com/repos/zendframework/zend-stdlib/issues/18","id":141120933,"user":{"login":"dimon-smith","id":14151562,"avatar_url":"https://avatars.githubusercontent.com/u/14151562?v=3","gravatar_id":"","url":"https://api.github.com/users/dimon-smith","html_url":"https://github.com/dimon-smith","followers_url":"https://api.github.com/users/dimon-smith/followers","following_url":"https://api.github.com/users/dimon-smith/following{/other_user}","gists_url":"https://api.github.com/users/dimon-smith/gists{/gist_id}","starred_url":"https://api.github.com/users/dimon-smith/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dimon-smith/subscriptions","organizations_url":"https://api.github.com/users/dimon-smith/orgs","repos_url":"https://api.github.com/users/dimon-smith/repos","events_url":"https://api.github.com/users/dimon-smith/events{/privacy}","received_events_url":"https://api.github.com/users/dimon-smith/received_events","type":"User","site_admin":false},"created_at":"2015-09-17T15:23:23Z","updated_at":"2015-09-17T15:23:23Z","body":"@weierophinney \r\n\r\n\r\nCompare the FastPriorityQueue\\PriorityQueue and Zend\\Stdlib\\SplPriorityQueue - this is a valid comparison.\r\n\r\nCompare FastPriorityQueue\\PriorityQueue and Zend\\Stdlib\\PriorityQueue - this is not a valid comparison.\r\n\r\nMy proposal regarding the optimization of the Zend\\Stdlib\\PriorityQueue."}}