PHP Classes

File: examples/PriorityQueue.php

Recommend this page to a friend!
  Classes of zinsou A.A.E.MoÔse  >  PHP Dictionary to Array class  >  examples/PriorityQueue.php  >  Download  
File: examples/PriorityQueue.php
Role: Example script
Content type: text/plain
Description: example script
Class: PHP Dictionary to Array class
Manipulate value collections as arrays or objects
Author: By
Last change: replace bad file description Stack by Priority Queue
Date: 3 years ago
Size: 5,485 bytes
 

Contents

Class file image Download
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>';

For more information send a message to info at phpclasses dot org.