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
21class 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}
158