| 1 |
efrain |
1 |
<?php
|
|
|
2 |
|
|
|
3 |
/**
|
|
|
4 |
* A simple array-backed queue, based off of the classic Okasaki
|
|
|
5 |
* persistent amortized queue. The basic idea is to maintain two
|
|
|
6 |
* stacks: an input stack and an output stack. When the output
|
|
|
7 |
* stack runs out, reverse the input stack and use it as the output
|
|
|
8 |
* stack.
|
|
|
9 |
*
|
|
|
10 |
* We don't use the SPL implementation because it's only supported
|
|
|
11 |
* on PHP 5.3 and later.
|
|
|
12 |
*
|
|
|
13 |
* Exercise: Prove that push/pop on this queue take amortized O(1) time.
|
|
|
14 |
*
|
|
|
15 |
* Exercise: Extend this queue to be a deque, while preserving amortized
|
|
|
16 |
* O(1) time. Some care must be taken on rebalancing to avoid quadratic
|
|
|
17 |
* behaviour caused by repeatedly shuffling data from the input stack
|
|
|
18 |
* to the output stack and back.
|
|
|
19 |
*/
|
|
|
20 |
class HTMLPurifier_Queue {
|
|
|
21 |
private $input;
|
|
|
22 |
private $output;
|
|
|
23 |
|
|
|
24 |
public function __construct($input = array()) {
|
|
|
25 |
$this->input = $input;
|
|
|
26 |
$this->output = array();
|
|
|
27 |
}
|
|
|
28 |
|
|
|
29 |
/**
|
|
|
30 |
* Shifts an element off the front of the queue.
|
|
|
31 |
*/
|
|
|
32 |
public function shift() {
|
|
|
33 |
if (empty($this->output)) {
|
|
|
34 |
$this->output = array_reverse($this->input);
|
|
|
35 |
$this->input = array();
|
|
|
36 |
}
|
|
|
37 |
if (empty($this->output)) {
|
|
|
38 |
return NULL;
|
|
|
39 |
}
|
|
|
40 |
return array_pop($this->output);
|
|
|
41 |
}
|
|
|
42 |
|
|
|
43 |
/**
|
|
|
44 |
* Pushes an element onto the front of the queue.
|
|
|
45 |
*/
|
|
|
46 |
public function push($x) {
|
|
|
47 |
array_push($this->input, $x);
|
|
|
48 |
}
|
|
|
49 |
|
|
|
50 |
/**
|
|
|
51 |
* Checks if it's empty.
|
|
|
52 |
*/
|
|
|
53 |
public function isEmpty() {
|
|
|
54 |
return empty($this->input) && empty($this->output);
|
|
|
55 |
}
|
|
|
56 |
}
|