Bug #53710 [Asn->Wfx]: Data registered with equal priority not returned in expected order

Edit report at https://bugs.php.net/bug.php?id=53710&edit=1 ID: 53710 Updated by: colder@php.net Reported by: weierophinney@php.net Summary: Data registered with equal priority not returned in expected order -Status: Assigned +Status: Wont fix Type: Bug Package: SPL related Operating System: Linux 32-bit PHP Version: 5.3.5 Assigned To: colder Block user comment: N Private report: N New Comment: There is no such guarantee. The only guarantee that you'll get from SplPriorityQueue is that you won't get an element out of order. Elements with the same priority are extracted in arbitrary order, the rest is implementation dependant. Previous Comments: ------------------------------------------------------------------------ [2011-01-17 19:44:44] daniel at berste dot in Reproduced on OSX (PHP compiled from MacPorts): $ php --version PHP 5.3.5 (cli) (built: Jan 9 2011 20:15:19) Copyright (c) 1997-2010 The PHP Group Zend Engine v2.3.0, Copyright (c) 1998-2010 Zend Technologies with Xdebug v2.1.0, Copyright (c) 2002-2010, by Derick Rethans $ cat test.php <?php $queue = new SplPriorityQueue(); $queue->insert('foo', 100); $queue->insert('bar', 100); $queue->insert('baz', 100); $queue->insert('bat', 100); foreach ($queue as $data) { echo $data, "\n"; } $ php test.php foo bat baz bar ------------------------------------------------------------------------ [2011-01-10 22:23:46] weierophinney@php.net Description: ------------ SplPriorityQueue does not behave as expected when data is registered with equal priority. One would expect one of the following situations: * The data retain the same order as how they were registered * The data are ordered based on value Neither of these are the case, however. From empirical analysis, it appears that the following happens: * The first item registered at that priority will always be the first returned * The remaining items are returned in the reverse order in which they were enqueued. Test script: --------------- $queue = new SplPriorityQueue(); $queue->insert('foo', 100); $queue->insert('bar', 100); $queue->insert('baz', 100); $queue->insert('bat', 100); foreach ($queue as $data) { echo $data, "\n"; } Expected result: ---------------- // IDEALLY order in which they are registered: foo bar baz bat // OR following same rules as priority queue -- higher values == higher priority foo baz bat bar Actual result: -------------- foo bat baz bar ------------------------------------------------------------------------ -- Edit this bug report at https://bugs.php.net/bug.php?id=53710&edit=1