index : flyspray | |
Archlinux32 customized Flyspray installation | gitolite user |
summaryrefslogtreecommitdiff |
-rw-r--r-- | vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php | 56 |
diff --git a/vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php b/vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php new file mode 100644 index 0000000..f58db90 --- /dev/null +++ b/vendor/ezyang/htmlpurifier/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); + } +} |