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