Admin Control Panel v2.0

✎ Editing: Zipper.php ← Back

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

}

Cancel