/
Queue.php
147 lines (125 loc) · 3.13 KB
/
Queue.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
<?php
namespace Restack;
use Restack\Dependency\Sortable;
use Restack\Exception\InvalidItemException;
use SplPriorityQueue;
/**
* Queued datastructure.
* Items added to the queue are accessed in FIFO
* order (First In, First Out)
*
* @category Restack
* @package Restack
*/
class Queue extends Index implements Sortable
{
const DEFAULT_ORDER = 1;
/**
* Item base index for normalising order
* @var integer
*/
private $base = PHP_INT_MAX;
/**
* Map an item to a given position
* @var array
*/
private $order = array();
/**
* The queue instance
* @var SplPriorityQueue
*/
private $queue;
/**
* Clear the queue
* @return void
*/
public function clear()
{
parent::clear();
$this->base = PHP_INT_MAX;
$this->order = array();
$this->queue = null;
}
/**
* Add an element to the queue
* @param mixed $item
* @param integer $priority
* @throws Restack\Exception\InvalidItemException
* @return void
*/
public function insert($item, $priority = self::DEFAULT_ORDER)
{
parent::insert($item);
$this->setOrder($item, $priority);
}
/**
* Remove an element from the queue
* @param mixed $item
* @throws Restack\Exception\InvalidItemException
* @return void
*/
public function remove($item)
{
$key = $this->search($item);
if (false !== $key)
{
unset($this->order[$key]);
}
parent::remove($item);
}
/**
* Get a cloned queue instance for iterating
* @return SplPriorityQueue
*/
public function getIterator()
{
return clone $this->getQueue();
}
/**
* Get the priority of an item
* @param mixed $item
* @throws Restack\Exception\InvalidItemException
* @return integer
*/
public function getOrder($item)
{
$key = $this->search($item);
if (false === $key)
{
throw new InvalidItemException('Item does not exist in storage');
}
return reset($this->order[$key]);
}
/**
* Set the priority of an item
* @param mixed $item
* @param integer $order
* @throws Restack\Exception\InvalidItemException
* @return void
*/
public function setOrder($item, $order)
{
$key = $this->search($item);
if (false === $key)
{
throw new InvalidItemException('Item does not exist in storage');
}
$this->order[$key] = array((int) $order, $this->base--);
}
/**
* Get the queue instance
* @return SplPriorityQueue
*/
public function getQueue()
{
if (self::STATE_UNSORTED === $this->getState())
{
$this->queue = new SplPriorityQueue;
foreach ($this->getItems() as $key => $item)
{
$this->queue->insert($item, $this->order[$key]);
}
}
return $this->queue;
}
}