| 1 |
efrain |
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 |
}
|