diff options
author | zotlabs <mike@macgirvin.com> | 2017-03-27 14:11:25 -0700 |
---|---|---|
committer | zotlabs <mike@macgirvin.com> | 2017-03-27 14:11:25 -0700 |
commit | 8292553a2087a412e0b10f5593d461d371169adb (patch) | |
tree | 2648714d80a19154ec19defa92aaa3229cae23c6 /vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php | |
parent | 5cbf60320355845e2abdec0422055d3fe321e84e (diff) | |
parent | 6375401e0af6c52d151dd2b944aa6a054b8ddc05 (diff) | |
download | volse-hubzilla-8292553a2087a412e0b10f5593d461d371169adb.tar.gz volse-hubzilla-8292553a2087a412e0b10f5593d461d371169adb.tar.bz2 volse-hubzilla-8292553a2087a412e0b10f5593d461d371169adb.zip |
Merge branch 'dev' of https://github.com/redmatrix/hubzilla into xdev_merge
Diffstat (limited to 'vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php')
-rw-r--r-- | vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php b/vendor/ezyang/htmlpurifier/library/HTMLPurifier/Queue.php new file mode 100644 index 000000000..f58db9042 --- /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); + } +} |