This is a naive but functional Priority Queue data structure implemented with only xDict:<br>
<?php
highlight_string('
<?php
require_once(\'./../xdict.class.php\');
class PriorityQueue implements Iterator,Countable ,JsonSerializable{
private $xdict=null;
public function __construct(){
$this->xdict=xdict(0);
$this->xdict->return_array_type=true;
}
function rewind() {
return $this->xdict->rewind();
}
function current() {
return $this->xdict->current()[0];
}
function key() {
return $this->xdict->key();
}
function next() {
$x=$this->xdict->next()[0];
$this->xdict->shift();
return $x;
}
function valid() {
return $this->xdict->valid();
}
public function clear (){
return $this->xdict->clear();
}
public function count(){
return $this->xdict->count();
}
public function copy (){
return clone($this);
}
public function isEmpty (){
return $this->xdict->isEmpty();
}
public function peek (){
return $this->xdict->first()[0];
}
public function pop (){
if($this->isEmpty()) throw new UnderflowException(\'The queue is already empty\');
return $this->xdict->shift(true)[0];
}
public function push ($value,$priority ){
if($this->isEmpty()){
$this->xdict->push([$value,$priority]);
}else{
if(in_array($value,$this->xdict->column(0))) return;//you can remove this to authorize the same value with different priority values in queue
$this->xdict->push([$value,$priority]);
while(!$this->xdict->isEmpty()){
$copy[]=$this->xdict->shift();
}
$c0=array_column($copy,1);
$c1=array_keys($copy);
array_multisort($c0,SORT_NUMERIC,SORT_DESC,$c1,SORT_NUMERIC,SORT_ASC,$copy);
$this->xdict->fill_with($copy);
}
}
public function toArray (){
return $this->xdict->column(0);
}
public function __debugInfo(){
return $this->xdict->column(0);
}
public function jsonSerialize() {
$anonymous=function(&$v){
if(is_object($v)) $v=serialize($v);
if(is_resource($v)) $v=get_resource_type($v).\'_#\'.@intval($v);
};
$x=$this->xdict->column(0);
array_walk_recursive($x,$anonymous);
return $x;
}
public function __clone() {
$this->xdict = clone ($this->xdict);
}
}
echo \'<pre>\';
$queue = new PriorityQueue();
$queue->push("a", 5);
$queue->push("c", 10);
$queue->push("b", 10);
$queue->push("d", 5);
$queue->push("y", 15);
$queue->push("y", 2);
$queue->push("8", 4);
$queue->push("9", 4);
var_dump($queue);
var_dump(
$queue->pop(),
$queue->pop(),
$queue->pop()
);
var_dump($queue);
foreach($queue as $v){
echo $v.\'<br>\';
}
var_dump($queue);
echo \'</pre>\';
?>');
require_once('./../xdict.class.php');
class PriorityQueue implements Iterator,Countable ,JsonSerializable{
private $xdict=null;
public function __construct(){
$this->xdict=xdict(0);
$this->xdict->return_array_type=true;
}
function rewind() {
return $this->xdict->rewind();
}
function current() {
return $this->xdict->current()[0];
}
function key() {
return $this->xdict->key();
}
function next() {
$x=$this->xdict->next()[0];
$this->xdict->shift();
return $x;
}
function valid() {
return $this->xdict->valid();
}
public function clear (){
return $this->xdict->clear();
}
public function count(){
return $this->xdict->count();
}
public function copy (){
return clone($this);
}
public function isEmpty (){
return $this->xdict->isEmpty();
}
public function peek (){
return $this->xdict->first()[0];
}
public function pop (){
if($this->isEmpty()) throw new UnderflowException('The queue is already empty');
return $this->xdict->shift(true)[0];
}
public function push ($value,$priority ){
if($this->isEmpty()){
$this->xdict->push([$value,$priority]);
}else{
if(in_array($value,$this->xdict->column(0))) return;//you can remove this to authorize the same value with different priority values in queue
$this->xdict->push([$value,$priority]);
while(!$this->xdict->isEmpty()){
$copy[]=$this->xdict->shift();
}
$c0=array_column($copy,1);
$c1=array_keys($copy);
array_multisort($c0,SORT_NUMERIC,SORT_DESC,$c1,SORT_NUMERIC,SORT_ASC,$copy);
// var_dump($copy);
$this->xdict->fill_with($copy,false);
// var_dump($this);
}
}
public function toArray (){
return $this->xdict->column(0);
}
public function __debugInfo(){
return $this->xdict->column(0);
}
public function jsonSerialize() {
$anonymous=function(&$v){
if(is_object($v)) $v=serialize($v);
if(is_resource($v)) $v=get_resource_type($v).'_#'.@intval($v);
};
$x=$this->xdict->column(0);
array_walk_recursive($x,$anonymous);
return $x;
}
public function __clone() {
$this->xdict = clone ($this->xdict);
}
}
echo '<pre>';
$queue = new PriorityQueue();
$queue->push("a", 5);
$queue->push("c", 10);
$queue->push("b", 10);
$queue->push("d", 5);
$queue->push("y", 15);
$queue->push("y", 2);
$queue->push("8", 4);
$queue->push("9", 4);
var_dump($queue);
var_dump(
$queue->pop(),
$queue->pop(),
$queue->pop()
);
var_dump($queue);
foreach($queue as $v){
echo $v.'<br>';
}
var_dump($queue);
echo '</pre>';
|
Download
