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     private $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      * Insert element before hole.
 100      * @param Element to insert
 101      */
 102     public function insertBefore($t) {
 103         if ($t !== NULL) array_push($this->front, $t);
 104     }
 105
 106     /**
 107      * Insert element after hole.
 108      * @param Element to insert
 109      */
 110     public function insertAfter($t) {
 111         if ($t !== NULL) array_push($this->back, $t);
 112     }
 113
 114     /**
 115      * Splice in multiple elements at hole.  Functional specification
 116      * in terms of array_splice:
 117      *
 118      *      $r1 = array_splice($arr, $i, $delete, $replacement);
 119      *
 120      *      list($z, $t) = HTMLPurifier_Zipper::fromArray($arr);
 121      *      $t = $z->advance($t, $i);
 122      *      $t = $z->splice($t, $delete, $replacement);
 123      *      $r2 = $z->toArray($t);
 124      *
 125      *      assert($r1 === $r2);
 126      *
 127      * NB: the absolute index location after this operation is
 128      * *unchanged!*
 129      *
 130      * @param Current contents of hole.
 131      */
 132     public function splice($t, $delete, $replacement) {
 133         // delete
 134         $r = $t;
 135         for ($i = $delete; $i > 0; $i--) {
 136             $r = $this->delete();
 137         }
 138         // insert
 139         for ($i = count($replacement)-1; $i >= 0; $i--) {
 140             $this->insertAfter($r);
 141             $r = $replacement[$i];
 142         }
 143         return $r;
 144     }
 145 }