aboutsummaryrefslogtreecommitdiffstats
path: root/library/HTMLPurifier/Queue.php
diff options
context:
space:
mode:
Diffstat (limited to 'library/HTMLPurifier/Queue.php')
-rw-r--r--library/HTMLPurifier/Queue.php56
1 files changed, 56 insertions, 0 deletions
diff --git a/library/HTMLPurifier/Queue.php b/library/HTMLPurifier/Queue.php
new file mode 100644
index 000000000..f58db9042
--- /dev/null
+++ b/library/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);
+ }
+}