PHP Conference Japan 2024

SplPriorityQueue クラス

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

はじめに

SplPriorityQueue クラスは、優先順位つきキューの主要な機能を提供します。 最大ヒープを使用して実装しています。

注意: 優先度が等しい要素の順番は 未定義 です。 優先度が等しい要素の順序は、挿入された順序と異なるかもしれません。

クラス概要

class SplPriorityQueue implements Iterator, Countable {
/* 定数 */
public const int EXTR_BOTH;
public const int EXTR_PRIORITY;
public const int EXTR_DATA;
/* メソッド */
public compare(mixed $priority1, mixed $priority2): int
public count(): int
public current(): mixed
public extract(): mixed
public insert(mixed $value, mixed $priority): true
public isCorrupted(): bool
public isEmpty(): bool
public key(): int
public next(): void
public rewind(): void
public setExtractFlags(int $flags): int
public top(): mixed
public valid(): bool
}

目次

add a note

User Contributed Notes 4 notes

up
16
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
20
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
10
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
11
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
?>
To Top