Merge pull request #481 from wallabag/dev1.5.2

1.5.2

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

+    }

+}