From f17490f009519572f8994bda98af92069bc99ce0 Mon Sep 17 00:00:00 2001 From: "Edward Z. Yang" Date: Sun, 13 Oct 2013 01:15:55 -0700 Subject: [PATCH] Implementation of a Zipper, for efficient splice. Signed-off-by: Edward Z. Yang --- library/HTMLPurifier.includes.php | 1 + library/HTMLPurifier.safe-includes.php | 1 + library/HTMLPurifier/Zipper.php | 145 +++++++++++++++++++++++++++++++++ tests/HTMLPurifier/ZipperTest.php | 25 ++++++ 4 files changed, 172 insertions(+) create mode 100644 library/HTMLPurifier/Zipper.php create mode 100644 tests/HTMLPurifier/ZipperTest.php diff --git a/library/HTMLPurifier.includes.php b/library/HTMLPurifier.includes.php index f18db992..d4904da0 100644 --- a/library/HTMLPurifier.includes.php +++ b/library/HTMLPurifier.includes.php @@ -73,6 +73,7 @@ require 'HTMLPurifier/URISchemeRegistry.php'; require 'HTMLPurifier/UnitConverter.php'; require 'HTMLPurifier/VarParser.php'; require 'HTMLPurifier/VarParserException.php'; +require 'HTMLPurifier/Zipper.php'; require 'HTMLPurifier/AttrDef/CSS.php'; require 'HTMLPurifier/AttrDef/Clone.php'; require 'HTMLPurifier/AttrDef/Enum.php'; diff --git a/library/HTMLPurifier.safe-includes.php b/library/HTMLPurifier.safe-includes.php index b9847559..c87d0411 100644 --- a/library/HTMLPurifier.safe-includes.php +++ b/library/HTMLPurifier.safe-includes.php @@ -67,6 +67,7 @@ require_once $__dir . '/HTMLPurifier/URISchemeRegistry.php'; require_once $__dir . '/HTMLPurifier/UnitConverter.php'; require_once $__dir . '/HTMLPurifier/VarParser.php'; require_once $__dir . '/HTMLPurifier/VarParserException.php'; +require_once $__dir . '/HTMLPurifier/Zipper.php'; require_once $__dir . '/HTMLPurifier/AttrDef/CSS.php'; require_once $__dir . '/HTMLPurifier/AttrDef/Clone.php'; require_once $__dir . '/HTMLPurifier/AttrDef/Enum.php'; diff --git a/library/HTMLPurifier/Zipper.php b/library/HTMLPurifier/Zipper.php new file mode 100644 index 00000000..2a4c430c --- /dev/null +++ b/library/HTMLPurifier/Zipper.php @@ -0,0 +1,145 @@ +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); + } + + /** + * 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: + * + * $r1 = array_splice($arr, $i, $delete, $replacement); + * + * list($z, $t) = HTMLPurifier_Zipper::fromArray($arr); + * $t = $z->advance($t, $i); + * $t = $z->splice($t, $delete, $replacement); + * $r2 = $z->toArray($t); + * + * assert($r1 === $r2); + * + * NB: the absolute index location after this operation is + * *unchanged!* + * + * @param Current contents of hole. + */ + public function splice($t, $delete, $replacement) { + // delete + $r = $t; + for ($i = $delete; $i > 0; $i--) { + $r = $this->delete(); + } + // insert + for ($i = count($replacement)-1; $i >= 0; $i--) { + $this->insertAfter($r); + $r = $replacement[$i]; + } + return $r; + } +} diff --git a/tests/HTMLPurifier/ZipperTest.php b/tests/HTMLPurifier/ZipperTest.php new file mode 100644 index 00000000..f847f411 --- /dev/null +++ b/tests/HTMLPurifier/ZipperTest.php @@ -0,0 +1,25 @@ +assertIdentical($t, 0); + $t = $z->next($t); + $this->assertIdentical($t, 1); + $t = $z->prev($t); + $this->assertIdentical($t, 0); + $t = $z->advance($t, 2); + $this->assertIdentical($t, 2); + $t = $z->delete(); + $this->assertIdentical($t, 3); + $z->insertBefore(4); + $z->insertAfter(5); + $this->assertIdentical($z->toArray($t), array(0,1,4,3,5)); + $t = $z->splice($t, 2, array(6,7)); + $this->assertIdentical($t, 6); + $this->assertIdentical($z->toArray($t), array(0,1,4,6,7)); + } + + // ToDo: QuickCheck style test comparing with array_splice +} -- 2.11.4.GIT