aboutsummaryrefslogtreecommitdiffstats
path: root/library/HTMLPurifier/Zipper.php
diff options
context:
space:
mode:
Diffstat (limited to 'library/HTMLPurifier/Zipper.php')
-rw-r--r--library/HTMLPurifier/Zipper.php157
1 files changed, 157 insertions, 0 deletions
diff --git a/library/HTMLPurifier/Zipper.php b/library/HTMLPurifier/Zipper.php
new file mode 100644
index 000000000..6e21ea070
--- /dev/null
+++ b/library/HTMLPurifier/Zipper.php
@@ -0,0 +1,157 @@
+<?php
+
+/**
+ * A zipper is a purely-functional data structure which contains
+ * a focus that can be efficiently manipulated. It is known as
+ * a "one-hole context". This mutable variant implements a zipper
+ * for a list as a pair of two arrays, laid out as follows:
+ *
+ * Base list: 1 2 3 4 [ ] 6 7 8 9
+ * Front list: 1 2 3 4
+ * Back list: 9 8 7 6
+ *
+ * User is expected to keep track of the "current element" and properly
+ * fill it back in as necessary. (ToDo: Maybe it's more user friendly
+ * to implicitly track the current element?)
+ *
+ * Nota bene: the current class gets confused if you try to store NULLs
+ * in the list.
+ */
+
+class HTMLPurifier_Zipper
+{
+ public $front, $back;
+
+ public function __construct($front, $back) {
+ $this->front = $front;
+ $this->back = $back;
+ }
+
+ /**
+ * Creates a zipper from an array, with a hole in the
+ * 0-index position.
+ * @param Array to zipper-ify.
+ * @return Tuple of zipper and element of first position.
+ */
+ static public function fromArray($array) {
+ $z = new self(array(), array_reverse($array));
+ $t = $z->delete(); // delete the "dummy hole"
+ return array($z, $t);
+ }
+
+ /**
+ * Convert zipper back into a normal array, optionally filling in
+ * the hole with a value. (Usually you should supply a $t, unless you
+ * are at the end of the array.)
+ */
+ public function toArray($t = NULL) {
+ $a = $this->front;
+ if ($t !== NULL) $a[] = $t;
+ for ($i = count($this->back)-1; $i >= 0; $i--) {
+ $a[] = $this->back[$i];
+ }
+ return $a;
+ }
+
+ /**
+ * Move hole to the next element.
+ * @param $t Element to fill hole with
+ * @return Original contents of new hole.
+ */
+ public function next($t) {
+ if ($t !== NULL) array_push($this->front, $t);
+ return empty($this->back) ? NULL : array_pop($this->back);
+ }
+
+ /**
+ * Iterated hole advancement.
+ * @param $t Element to fill hole with
+ * @param $i How many forward to advance hole
+ * @return Original contents of new hole, i away
+ */
+ public function advance($t, $n) {
+ for ($i = 0; $i < $n; $i++) {
+ $t = $this->next($t);
+ }
+ return $t;
+ }
+
+ /**
+ * Move hole to the previous element
+ * @param $t Element to fill hole with
+ * @return Original contents of new hole.
+ */
+ public function prev($t) {
+ if ($t !== NULL) array_push($this->back, $t);
+ return empty($this->front) ? NULL : array_pop($this->front);
+ }
+
+ /**
+ * Delete contents of current hole, shifting hole to
+ * next element.
+ * @return Original contents of new hole.
+ */
+ public function delete() {
+ return empty($this->back) ? NULL : array_pop($this->back);
+ }
+
+ /**
+ * Returns true if we are at the end of the list.
+ * @return bool
+ */
+ public function done() {
+ return empty($this->back);
+ }
+
+ /**
+ * Insert element before hole.
+ * @param Element to insert
+ */
+ public function insertBefore($t) {
+ if ($t !== NULL) array_push($this->front, $t);
+ }
+
+ /**
+ * Insert element after hole.
+ * @param Element to insert
+ */
+ public function insertAfter($t) {
+ if ($t !== NULL) array_push($this->back, $t);
+ }
+
+ /**
+ * Splice in multiple elements at hole. Functional specification
+ * in terms of array_splice:
+ *
+ * $arr1 = $arr;
+ * $old1 = array_splice($arr1, $i, $delete, $replacement);
+ *
+ * list($z, $t) = HTMLPurifier_Zipper::fromArray($arr);
+ * $t = $z->advance($t, $i);
+ * list($old2, $t) = $z->splice($t, $delete, $replacement);
+ * $arr2 = $z->toArray($t);
+ *
+ * assert($old1 === $old2);
+ * assert($arr1 === $arr2);
+ *
+ * NB: the absolute index location after this operation is
+ * *unchanged!*
+ *
+ * @param Current contents of hole.
+ */
+ public function splice($t, $delete, $replacement) {
+ // delete
+ $old = array();
+ $r = $t;
+ for ($i = $delete; $i > 0; $i--) {
+ $old[] = $r;
+ $r = $this->delete();
+ }
+ // insert
+ for ($i = count($replacement)-1; $i >= 0; $i--) {
+ $this->insertAfter($r);
+ $r = $replacement[$i];
+ }
+ return array($old, $r);
+ }
+}