<?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); } }