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