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 */
20class 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