library/HTMLPurifier/Queue.php

   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 }