| 1: | <?php |
| 2: | |
| 3: | /** |
| 4: | * A zipper is a purely-functional data structure which contains |
| 5: | * a focus that can be efficiently manipulated. It is known as |
| 6: | * a "one-hole context". This mutable variant implements a zipper |
| 7: | * for a list as a pair of two arrays, laid out as follows: |
| 8: | * |
| 9: | * Base list: 1 2 3 4 [ ] 6 7 8 9 |
| 10: | * Front list: 1 2 3 4 |
| 11: | * Back list: 9 8 7 6 |
| 12: | * |
| 13: | * User is expected to keep track of the "current element" and properly |
| 14: | * fill it back in as necessary. (ToDo: Maybe it's more user friendly |
| 15: | * to implicitly track the current element?) |
| 16: | * |
| 17: | * Nota bene: the current class gets confused if you try to store NULLs |
| 18: | * in the list. |
| 19: | */ |
| 20: | |
| 21: | class HTMLPurifier_Zipper |
| 22: | { |
| 23: | public $front, $back; |
| 24: | |
| 25: | public function __construct($front, $back) { |
| 26: | $this->front = $front; |
| 27: | $this->back = $back; |
| 28: | } |
| 29: | |
| 30: | /** |
| 31: | * Creates a zipper from an array, with a hole in the |
| 32: | * 0-index position. |
| 33: | * @param Array to zipper-ify. |
| 34: | * @return Tuple of zipper and element of first position. |
| 35: | */ |
| 36: | static public function fromArray($array) { |
| 37: | $z = new self(array(), array_reverse($array)); |
| 38: | $t = $z->delete(); // delete the "dummy hole" |
| 39: | return array($z, $t); |
| 40: | } |
| 41: | |
| 42: | /** |
| 43: | * Convert zipper back into a normal array, optionally filling in |
| 44: | * the hole with a value. (Usually you should supply a $t, unless you |
| 45: | * are at the end of the array.) |
| 46: | */ |
| 47: | public function toArray($t = NULL) { |
| 48: | $a = $this->front; |
| 49: | if ($t !== NULL) $a[] = $t; |
| 50: | for ($i = count($this->back)-1; $i >= 0; $i--) { |
| 51: | $a[] = $this->back[$i]; |
| 52: | } |
| 53: | return $a; |
| 54: | } |
| 55: | |
| 56: | /** |
| 57: | * Move hole to the next element. |
| 58: | * @param $t Element to fill hole with |
| 59: | * @return Original contents of new hole. |
| 60: | */ |
| 61: | public function next($t) { |
| 62: | if ($t !== NULL) array_push($this->front, $t); |
| 63: | return empty($this->back) ? NULL : array_pop($this->back); |
| 64: | } |
| 65: | |
| 66: | /** |
| 67: | * Iterated hole advancement. |
| 68: | * @param $t Element to fill hole with |
| 69: | * @param $i How many forward to advance hole |
| 70: | * @return Original contents of new hole, i away |
| 71: | */ |
| 72: | public function advance($t, $n) { |
| 73: | for ($i = 0; $i < $n; $i++) { |
| 74: | $t = $this->next($t); |
| 75: | } |
| 76: | return $t; |
| 77: | } |
| 78: | |
| 79: | /** |
| 80: | * Move hole to the previous element |
| 81: | * @param $t Element to fill hole with |
| 82: | * @return Original contents of new hole. |
| 83: | */ |
| 84: | public function prev($t) { |
| 85: | if ($t !== NULL) array_push($this->back, $t); |
| 86: | return empty($this->front) ? NULL : array_pop($this->front); |
| 87: | } |
| 88: | |
| 89: | /** |
| 90: | * Delete contents of current hole, shifting hole to |
| 91: | * next element. |
| 92: | * @return Original contents of new hole. |
| 93: | */ |
| 94: | public function delete() { |
| 95: | return empty($this->back) ? NULL : array_pop($this->back); |
| 96: | } |
| 97: | |
| 98: | /** |
| 99: | * Returns true if we are at the end of the list. |
| 100: | * @return bool |
| 101: | */ |
| 102: | public function done() { |
| 103: | return empty($this->back); |
| 104: | } |
| 105: | |
| 106: | /** |
| 107: | * Insert element before hole. |
| 108: | * @param Element to insert |
| 109: | */ |
| 110: | public function insertBefore($t) { |
| 111: | if ($t !== NULL) array_push($this->front, $t); |
| 112: | } |
| 113: | |
| 114: | /** |
| 115: | * Insert element after hole. |
| 116: | * @param Element to insert |
| 117: | */ |
| 118: | public function insertAfter($t) { |
| 119: | if ($t !== NULL) array_push($this->back, $t); |
| 120: | } |
| 121: | |
| 122: | /** |
| 123: | * Splice in multiple elements at hole. Functional specification |
| 124: | * in terms of array_splice: |
| 125: | * |
| 126: | * $arr1 = $arr; |
| 127: | * $old1 = array_splice($arr1, $i, $delete, $replacement); |
| 128: | * |
| 129: | * list($z, $t) = HTMLPurifier_Zipper::fromArray($arr); |
| 130: | * $t = $z->advance($t, $i); |
| 131: | * list($old2, $t) = $z->splice($t, $delete, $replacement); |
| 132: | * $arr2 = $z->toArray($t); |
| 133: | * |
| 134: | * assert($old1 === $old2); |
| 135: | * assert($arr1 === $arr2); |
| 136: | * |
| 137: | * NB: the absolute index location after this operation is |
| 138: | * *unchanged!* |
| 139: | * |
| 140: | * @param Current contents of hole. |
| 141: | */ |
| 142: | public function splice($t, $delete, $replacement) { |
| 143: | // delete |
| 144: | $old = array(); |
| 145: | $r = $t; |
| 146: | for ($i = $delete; $i > 0; $i--) { |
| 147: | $old[] = $r; |
| 148: | $r = $this->delete(); |
| 149: | } |
| 150: | // insert |
| 151: | for ($i = count($replacement)-1; $i >= 0; $i--) { |
| 152: | $this->insertAfter($r); |
| 153: | $r = $replacement[$i]; |
| 154: | } |
| 155: | return array($old, $r); |
| 156: | } |
| 157: | } |
| 158: |