| 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: | } |
| 57: |