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

 <?php
 
 /**
  * A zipper is a purely-functional data structure which contains
  * a focus that can be efficiently manipulated.  It is known as
  * a "one-hole context".  This mutable variant implements a zipper
  * for a list as a pair of two arrays, laid out as follows:
  *
  *      Base list: 1 2 3 4 [ ] 6 7 8 9
  *      Front list: 1 2 3 4
  *      Back list: 9 8 7 6
  *
  * User is expected to keep track of the "current element" and properly
  * fill it back in as necessary.  (ToDo: Maybe it's more user friendly
  * to implicitly track the current element?)
  *
  * Nota bene: the current class gets confused if you try to store NULLs
  * in the list.
  */
 
 class HTMLPurifier_Zipper
 {
     public $front, $back;
 
     public function __construct($front, $back) {
         $this->front = $front;
         $this->back = $back;
     }
 
     /**
      * Creates a zipper from an array, with a hole in the
      * 0-index position.
      * @param Array to zipper-ify.
      * @return Tuple of zipper and element of first position.
      */
     static public function fromArray($array) {
         $z = new self(array(), array_reverse($array));
         $t = $z->delete(); // delete the "dummy hole"
         return array($z, $t);
     }
 
     /**
      * Convert zipper back into a normal array, optionally filling in
      * the hole with a value. (Usually you should supply a $t, unless you
      * are at the end of the array.)
      */
     public function toArray($t = NULL) {
         $a = $this->front;
         if ($t !== NULL) $a[] = $t;
         for ($i = count($this->back)-1; $i >= 0; $i--) {
             $a[] = $this->back[$i];
         }
         return $a;
     }
 
     /**
      * Move hole to the next element.
      * @param $t Element to fill hole with
      * @return Original contents of new hole.
      */
     public function next($t) {
         if ($t !== NULL) array_push($this->front, $t);
         return empty($this->back) ? NULL : array_pop($this->back);
     }
 
     /**
      * Iterated hole advancement.
      * @param $t Element to fill hole with
      * @param $i How many forward to advance hole
      * @return Original contents of new hole, i away
      */
     public function advance($t, $n) {
         for ($i = 0; $i < $n; $i++) {
             $t = $this->next($t);
         }
         return $t;
     }
 
     /**
      * Move hole to the previous element
      * @param $t Element to fill hole with
      * @return Original contents of new hole.
      */
     public function prev($t) {
         if ($t !== NULL) array_push($this->back, $t);
         return empty($this->front) ? NULL : array_pop($this->front);
     }
 
     /**
      * Delete contents of current hole, shifting hole to
      * next element.
      * @return Original contents of new hole.
      */
     public function delete() {
         return empty($this->back) ? NULL : array_pop($this->back);
     }
 
     /**
      * Returns true if we are at the end of the list.
      * @return bool
      */
     public function done() {
         return empty($this->back);
     }
 
     /**
      * Insert element before hole.
      * @param Element to insert
      */
     public function insertBefore($t) {
         if ($t !== NULL) array_push($this->front, $t);
     }
 
     /**
      * Insert element after hole.
      * @param Element to insert
      */
     public function insertAfter($t) {
         if ($t !== NULL) array_push($this->back, $t);
     }
 
     /**
      * Splice in multiple elements at hole.  Functional specification
      * in terms of array_splice:
      *
      *      $arr1 = $arr;
      *      $old1 = array_splice($arr1, $i, $delete, $replacement);
      *
      *      list($z, $t) = HTMLPurifier_Zipper::fromArray($arr);
      *      $t = $z->advance($t, $i);
      *      list($old2, $t) = $z->splice($t, $delete, $replacement);
      *      $arr2 = $z->toArray($t);
      *
      *      assert($old1 === $old2);
      *      assert($arr1 === $arr2);
      *
      * NB: the absolute index location after this operation is
      * *unchanged!*
      *
      * @param Current contents of hole.
      */
     public function splice($t, $delete, $replacement) {
         // delete
         $old = array();
         $r = $t;
         for ($i = $delete; $i > 0; $i--) {
             $old[] = $r;
             $r = $this->delete();
         }
         // insert
         for ($i = count($replacement)-1; $i >= 0; $i--) {
             $this->insertAfter($r);
             $r = $replacement[$i];
         }
         return array($old, $r);
     }
 }