php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login

go to bug id or search bugs for

Request #60926 LIFO/FIFO iterator modes for priority queues
Submitted: 2012-01-29 19:31 UTC Modified: -
Votes:5
Avg. Score:3.8 ± 1.2
Reproduced:4 of 4 (100.0%)
Same Version:1 (25.0%)
Same OS:1 (25.0%)
From: franssen dot roland at gmail dot com Assigned:
Status: Open Package: SPL related
PHP Version: 5.4.0RC6 OS: Ubuntu
Private report: No CVE-ID: None
View Developer Edit
Welcome back! If you're the original bug submitter, here's where you can edit the bug or add additional notes.
If you forgot your password, you can retrieve your password here.
Password:
Status:
Package:
Bug Type:
Summary:
From: franssen dot roland at gmail dot com
New email:
PHP Version: OS:

 

 [2012-01-29 19:31 UTC] franssen dot roland at gmail dot com 
Description:
------------
PHP version is actually PHP5.4RC3

It would be nice to be able to maintain the input order in a SPL priority queue when multiple values share the same priority.

E.g. FIFO and LIFO

The current "mode" is neither one of these. I guess this is best peformance-wise but sometimes you want to be explicitly, for instance when registering event listeners; you expect them to run in order.

Test script:
---------------
<?php
$queue = new \SplPriorityQueue;
$queue->insert('a', 100);
$queue->insert('b', 100);
$queue->insert('c', 110);
$queue->insert('d', 90);

foreach($queue as $element) {
    var_dump($element);
    echo '<br>';
}
echo '<br>';
$queue2 = new \SplPriorityQueue;
$queue2->insert('a', 100);
$queue2->insert('b', 100);

foreach($queue2 as $element) {
    var_dump($element);
    echo '<br>';
}

Expected result:
----------------
string(1) "c"
string(1) "a"
string(1) "b"
string(1) "d"

string(1) "a"
string(1) "b" 

Actual result:
--------------
string(1) "c"
string(1) "b"
string(1) "a"
string(1) "d"

string(1) "a"
string(1) "b"

Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2012-01-30 03:09 UTC] carloschilazo at gmail dot com 
I believe this goes against the definition of a priority queue, if you insert them 
with the same priority then it really does not matter which one comes first...

I understand what you are asking, but if you need them like that then you could 
maybe use another data structure or a mixture, or user different priorities..
 [2012-01-30 18:23 UTC] franssen dot roland at gmail dot com 
> "it really does not matter which one comes first"
So why cant we control it then? ;-)

However, you probably mean you shouldn't have to rely on it. Which makes sense.

Still.. i was so close with a out-of-the-box event listener data structure ^^ I guess i'll compose the priority queue for internal usage and store the order of shared priorities myself. It can be done.
 [2012-01-30 18:53 UTC] franssen dot roland at gmail dot com 
Of course the idea initially was to avoid "arrays" here... not to end up using both.

Think i'll have to bench;
* object using array only (data + priority + order); no use fancy PHP 5.3 stuff ;-)
* object using priority queue (data + priority) and array (order); not against semantics (?)
* object extending priority queue and extra array internally (order); all logic nicely encapsulated in compare() / against semantics (?)
 [2018-04-25 23:24 UTC] cmb@php.net 
Related To: Bug #76265
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved. 		Last updated: Thu Nov 21 18:01:29 2024 UTC