[Summary view] [Print] [Text view]

   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  }