[Summary view]

   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  }