php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
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! If you don't have a Git account, you can't do anything here.
If you reported this bug, you can edit this bug over here.
(description)
Block user comment
Status: Assign to:
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 (?)
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Wed Dec 11 20:01:26 2024 UTC