1 files changed, 56 insertions, 0 deletions
diff --git a/inc/3rdparty/htmlpurifier/HTMLPurifier/Queue.php b/inc/3rdparty/htmlpurifier/HTMLPurifier/Queue.php
new file mode 100644
index 00000000..a75894d4
--- /dev/null
+++ b/inc/3rdparty/htmlpurifier/HTMLPurifier/Queue.php
@@ -0,0 +1,56 @@
+<?php
+/**
+ * A simple array-backed queue, based off of the classic Okasaki
+ * persistent amortized queue.  The basic idea is to maintain two
+ * stacks: an input stack and an output stack.  When the output
+ * stack runs out, reverse the input stack and use it as the output
+ * stack.
+ *
+ * We don't use the SPL implementation because it's only supported
+ * on PHP 5.3 and later.
+ *
+ * Exercise: Prove that push/pop on this queue take amortized O(1) time.
+ *
+ * Exercise: Extend this queue to be a deque, while preserving amortized
+ * O(1) time.  Some care must be taken on rebalancing to avoid quadratic
+ * behaviour caused by repeatedly shuffling data from the input stack
+ * to the output stack and back.
+ */
+class HTMLPurifier_Queue {
+    private $input;
+    private $output;
+    public function __construct($input = array()) {
+        $this->input = $input;
+        $this->output = array();
+    }
+    /**
+     * Shifts an element off the front of the queue.
+     */
+    public function shift() {
+        if (empty($this->output)) {
+            $this->output = array_reverse($this->input);
+            $this->input = array();
+        }
+        if (empty($this->output)) {
+            return NULL;
+        }
+        return array_pop($this->output);
+    }
+    /**
+     * Pushes an element onto the front of the queue.
+     */
+    public function push($x) {
+        array_push($this->input, $x);
+    }
+    /**
+     * Checks if it's empty.
+     */
+    public function isEmpty() {
+        return empty($this->input) && empty($this->output);
+    }
+}

diff --git a/inc/3rdparty/htmlpurifier/HTMLPurifier/Queue.php b/inc/3rdparty/htmlpurifier/HTMLPurifier/Queue.php new file mode 100644 index 00000000..a75894d4 --- /dev/null +++ b/inc/3rdparty/htmlpurifier/HTMLPurifier/Queue.php
@@ -0,0 +1,56 @@
	1	<?php
	2
	3	/**
	4	* A simple array-backed queue, based off of the classic Okasaki
	5	* persistent amortized queue. The basic idea is to maintain two
	6	* stacks: an input stack and an output stack. When the output
	7	* stack runs out, reverse the input stack and use it as the output
	8	* stack.
	9	*
	10	* We don't use the SPL implementation because it's only supported
	11	* on PHP 5.3 and later.
	12	*
	13	* Exercise: Prove that push/pop on this queue take amortized O(1) time.
	14	*
	15	* Exercise: Extend this queue to be a deque, while preserving amortized
	16	* O(1) time. Some care must be taken on rebalancing to avoid quadratic
	17	* behaviour caused by repeatedly shuffling data from the input stack
	18	* to the output stack and back.
	19	*/
	20	class HTMLPurifier_Queue {
	21	private $input;
	22	private $output;
	23
	24	public function __construct($input = array()) {
	25	$this->input = $input;
	26	$this->output = array();
	27	}
	28
	29	/**
	30	* Shifts an element off the front of the queue.
	31	*/
	32	public function shift() {
	33	if (empty($this->output)) {
	34	$this->output = array_reverse($this->input);
	35	$this->input = array();
	36	}
	37	if (empty($this->output)) {
	38	return NULL;
	39	}
	40	return array_pop($this->output);
	41	}
	42
	43	/**
	44	* Pushes an element onto the front of the queue.
	45	*/
	46	public function push($x) {
	47	array_push($this->input, $x);
	48	}
	49
	50	/**
	51	* Checks if it's empty.
	52	*/
	53	public function isEmpty() {
	54	return empty($this->input) && empty($this->output);
	55	}
	56	}