La classe SplPriorityQueue

    (PHP 5 >= 5.3.0, PHP 7, PHP 8)

    Introduction

    La classe SplPriorityQueue fournit les fonctionnalités principales d'une queue à priorités, implémentées avec une pile maximale.

    Note: L'ordre des éléments qui ont une priorité identique est undefined. Il peut être différent que l'ordre dans lequel ils ont été inséré.

    Synopsis de la classe

    class SplPriorityQueue implements Iterator, Countable {
    /* Constantes */
    public const int EXTR_BOTH;
    public const int EXTR_PRIORITY;
    public const int EXTR_DATA;
    /* Méthodes */
    public compare(mixed $priority1, mixed $priority2): int
    public count(): int
    public current(): mixed
    public extract(): mixed
    public getExtractFlags(): int
    public insert(mixed $value, mixed $priority): true
    public isCorrupted(): bool
    public isEmpty(): bool
    public key(): int
    public next(): void
    public recoverFromCorruption(): true
    public rewind(): void
    public setExtractFlags(int $flags): int
    public top(): mixed
    public valid(): bool
    }

    Sommaire

    Found A Problem?

    Learn How To Improve This Page • Submit a Pull Request • Report a Bug
    ＋add a note

    User Contributed Notes 4 notes

    up
    21
    rajatn at rediff dot co dot in
    14 years ago
    quick implementation of SPL Priority Queue:

    <?php

    class PQtest extends SplPriorityQueue
    {
    public function     compare($priority1, $priority2)
    {
    if (    $priority1 === $priority2) return 0;
    return     $priority1 < $priority2 ? -1 : 1;
    }
    }

    $objPQ = new PQtest();

    $objPQ->insert('A',3);
    $objPQ->insert('B',6);
    $objPQ->insert('C',1);
    $objPQ->insert('D',2);

    echo     "COUNT->".$objPQ->count()."<BR>";

    //mode of extraction
    $objPQ->setExtractFlags(PQtest::EXTR_BOTH);

    //Go to TOP
    $objPQ->top();

    while(    $objPQ->valid()){
    print_r($objPQ->current());
    echo     "<BR>";
    $objPQ->next();
    }

    ?>

    output:

    COUNT->4
    Array ( [data] => B [priority] => 6 )
    Array ( [data] => A [priority] => 3 )
    Array ( [data] => D [priority] => 2 )
    Array ( [data] => C [priority] => 1 )
    up
    14
    doublecompile at gmail dot com
    9 years ago
    I've used the SplPriorityQueue to determine an HTTP client's preferred MIME types.

    <?php
    $queue     = new \SplPriorityQueue();
    foreach (    preg_split('#,\s*#', $_SERVER['HTTP_ACCEPT']) as $accept) {
    $split = preg_split('#;\s*q=#', $accept, 2);
    $queue->insert($split[0], isset($split[1]) ? (float)$split[1] : 1.0);
    }
    foreach (    $queue as $mime) {
    echo     $mime, PHP_EOL;
    }
    ?>

    My browser sends:
    Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8

    And this script outputs:
    text/html
    application/xhtml+xml
    application/xml
    */*

    A better example:
    Accept: text/html, application/xml,text/css;q=0.4,text/plain; q=0.9, application/json;q=0.8

    And this script outputs:
    text/html
    application/xml
    text/plain
    application/json
    text/css
    up
    9
    Hayley Watson
    10 years ago
    For a heap-based priority queue to be at its most effective, the "priority" should be something that can take on a wide range of values (lengths, timestamps, populations). It optimises the tasks of searching the queue for the appropriate place to insert an item (and inserting it); and removing the first item in the list.

    Items may potentially be inserted into the queue wherever two adjacent items have different priorities. The heap structure is an efficient way of indexing such insertion points when there are many of them distributed throughout the list.

    If you have a sharply-limited enumeration of possible priority values, then there are very few insertion possible insertion points - one for each priority value. In that situation, one can make the insertion points explicit (and thus eliminate the need to maintain a heap indexing them) by implementing your priority queue as a list of simple queues from which you draw successive items from the highest-priority nonempty queue.
    up
    10
    lsroudi at gmail dot com
    10 years ago
    <?php

    /**
    * Description of PriorityQueue
    *
    * (c) lsroudi http://lsroudi.com/ <lsroudi@gmail.com>
    *
    * For the full copyright and license information, please view the LICENSE
    * file that was distributed with this source code.
    */
    interface PriorityLoggerInterface {

    public function     insert($value, $priority);
    }

    class     PriorityLogger extends SplPriorityQueue implements PriorityLoggerInterface {

    }

    class     Logger {

    const     ERROR = 3;
    const     NOTICE = 1;
    const     WARNING = 2;

    private     $priorityLogger;

    public function     __construct(PriorityLoggerInterface $priorityLogger)
    {
    $this->priorityLogger = $priorityLogger;
    }

    public function     addMessage($value, $priority)
    {
    $this->priorityLogger->insert($value, $priority);
    }

    public function     getPriorityLogger()
    {
    return     $this->priorityLogger;
    }

    }

    $priorityLogger = new PriorityLogger();

    $logger = new Logger($priorityLogger);
    $logger->addMessage('Message with notice type', Logger::NOTICE);
    $logger->addMessage('Message with warning type', Logger::WARNING);
    $logger->addMessage('Message with error type', Logger::ERROR);

    $priorityLoggerQueue = $logger->getPriorityLogger();

    foreach (    $priorityLoggerQueue as $queue){
    print     $queue . PHP_EOL;
    }

    //Résultat
    //Message with error type
    //Message with warning type
    //Message with notice type
    ?>
    ＋add a note
    To Top