[Summary view] [Print] [Text 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  }