[ Index ]

PHP Cross Reference of Unnamed Project




/se3master/var/www/se3/includes/library/HTMLPurifier/ -> Queue.php (summary)

(no description)

File Size: 56 lines (2 kb)
Included or required: 1 time
Referenced: 0 times
Includes or requires: 0 files

Defines 1 class

HTMLPurifier_Queue:: (4 methods):

Class: HTMLPurifier_Queue  - X-Ref

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

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.
__construct($input = array()   X-Ref
No description

shift()   X-Ref
Shifts an element off the front of the queue.

push($x)   X-Ref
Pushes an element onto the front of the queue.

isEmpty()   X-Ref
Checks if it's empty.

Generated: Tue Mar 17 22:47:18 2015 Cross-referenced by PHPXref 0.7.1