library/HTMLPurifier/Zipper.php

   1 <?php
   2
   3 /**
   4  * A zipper is a purely-functional data structure which contains
   5  * a focus that can be efficiently manipulated.  It is known as
   6  * a "one-hole context".  This mutable variant implements a zipper
   7  * for a list as a pair of two arrays, laid out as follows:
   8  *
   9  *      Base list: 1 2 3 4 [ ] 6 7 8 9
  10  *      Front list: 1 2 3 4
  11  *      Back list: 9 8 7 6
  12  *
  13  * User is expected to keep track of the "current element" and properly
  14  * fill it back in as necessary.  (ToDo: Maybe it's more user friendly
  15  * to implicitly track the current element?)
  16  *
  17  * Nota bene: the current class gets confused if you try to store NULLs
  18  * in the list.
  19  */
  20
  21 class HTMLPurifier_Zipper
  22 {
  23     public $front, $back;
  24
  25     public function __construct($front, $back) {
  26         $this->front = $front;
  27         $this->back = $back;
  28     }
  29
  30     /**
  31      * Creates a zipper from an array, with a hole in the
  32      * 0-index position.
  33      * @param Array to zipper-ify.
  34      * @return Tuple of zipper and element of first position.
  35      */
  36     static public function fromArray($array) {
  37         $z = new self(array(), array_reverse($array));
  38         $t = $z->delete(); // delete the "dummy hole"
  39         return array($z, $t);
  40     }
  41
  42     /**
  43      * Convert zipper back into a normal array, optionally filling in
  44      * the hole with a value. (Usually you should supply a $t, unless you
  45      * are at the end of the array.)
  46      */
  47     public function toArray($t = NULL) {
  48         $a = $this->front;
  49         if ($t !== NULL) $a[] = $t;
  50         for ($i = count($this->back)-1; $i >= 0; $i--) {
  51             $a[] = $this->back[$i];
  52         }
  53         return $a;
  54     }
  55
  56     /**
  57      * Move hole to the next element.
  58      * @param $t Element to fill hole with
  59      * @return Original contents of new hole.
  60      */
  61     public function next($t) {
  62         if ($t !== NULL) array_push($this->front, $t);
  63         return empty($this->back) ? NULL : array_pop($this->back);
  64     }
  65
  66     /**
  67      * Iterated hole advancement.
  68      * @param $t Element to fill hole with
  69      * @param $i How many forward to advance hole
  70      * @return Original contents of new hole, i away
  71      */
  72     public function advance($t, $n) {
  73         for ($i = 0; $i < $n; $i++) {
  74             $t = $this->next($t);
  75         }
  76         return $t;
  77     }
  78
  79     /**
  80      * Move hole to the previous element
  81      * @param $t Element to fill hole with
  82      * @return Original contents of new hole.
  83      */
  84     public function prev($t) {
  85         if ($t !== NULL) array_push($this->back, $t);
  86         return empty($this->front) ? NULL : array_pop($this->front);
  87     }
  88
  89     /**
  90      * Delete contents of current hole, shifting hole to
  91      * next element.
  92      * @return Original contents of new hole.
  93      */
  94     public function delete() {
  95         return empty($this->back) ? NULL : array_pop($this->back);
  96     }
  97
  98     /**
  99      * Returns true if we are at the end of the list.
 100      * @return bool
 101      */
 102     public function done() {
 103         return empty($this->back);
 104     }
 105
 106     /**
 107      * Insert element before hole.
 108      * @param Element to insert
 109      */
 110     public function insertBefore($t) {
 111         if ($t !== NULL) array_push($this->front, $t);
 112     }
 113
 114     /**
 115      * Insert element after hole.
 116      * @param Element to insert
 117      */
 118     public function insertAfter($t) {
 119         if ($t !== NULL) array_push($this->back, $t);
 120     }
 121
 122     /**
 123      * Splice in multiple elements at hole.  Functional specification
 124      * in terms of array_splice:
 125      *
 126      *      $arr1 = $arr;
 127      *      $old1 = array_splice($arr1, $i, $delete, $replacement);
 128      *
 129      *      list($z, $t) = HTMLPurifier_Zipper::fromArray($arr);
 130      *      $t = $z->advance($t, $i);
 131      *      list($old2, $t) = $z->splice($t, $delete, $replacement);
 132      *      $arr2 = $z->toArray($t);
 133      *
 134      *      assert($old1 === $old2);
 135      *      assert($arr1 === $arr2);
 136      *
 137      * NB: the absolute index location after this operation is
 138      * *unchanged!*
 139      *
 140      * @param Current contents of hole.
 141      */
 142     public function splice($t, $delete, $replacement) {
 143         // delete
 144         $old = array();
 145         $r = $t;
 146         for ($i = $delete; $i > 0; $i--) {
 147             $old[] = $r;
 148             $r = $this->delete();
 149         }
 150         // insert
 151         for ($i = count($replacement)-1; $i >= 0; $i--) {
 152             $this->insertAfter($r);
 153             $r = $replacement[$i];
 154         }
 155         return array($old, $r);
 156     }
 157 }