File indexing completed on 2024-12-22 05:36:22

 <?php
 
 /**
  * A simple array-backed queue, based off of the classic Okasaki
  * persistent amortized queue.  The basic idea is to maintain two
  * stacks: an input stack and an output stack.  When the output
  * stack runs out, reverse the input stack and use it as the output
  * stack.
  *
  * We don't use the SPL implementation because it's only supported
  * on PHP 5.3 and later.
  *
  * Exercise: Prove that push/pop on this queue take amortized O(1) time.
  *
  * Exercise: Extend this queue to be a deque, while preserving amortized
  * O(1) time.  Some care must be taken on rebalancing to avoid quadratic
  * behaviour caused by repeatedly shuffling data from the input stack
  * to the output stack and back.
  */
 class HTMLPurifier_Queue {
     private $input;
     private $output;
 
     public function __construct($input = array()) {
         $this->input = $input;
         $this->output = array();
     }
 
     /**
      * Shifts an element off the front of the queue.
      */
     public function shift() {
         if (empty($this->output)) {
             $this->output = array_reverse($this->input);
             $this->input = array();
         }
         if (empty($this->output)) {
             return NULL;
         }
         return array_pop($this->output);
     }
 
     /**
      * Pushes an element onto the front of the queue.
      */
     public function push($x) {
         array_push($this->input, $x);
     }
 
     /**
      * Checks if it's empty.
      */
     public function isEmpty() {
         return empty($this->input) && empty($this->output);
     }
 }