HTMLPurifier_Queue Class Reference

Public Member Functions
	__construct ($input=array())
	shift ()
	push ($x)
	isEmpty ()

Detailed Description

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.

Definition at line 8353 of file HTMLPurifier.standalone.php.

Constructor & Destructor Documentation

__construct()

HTMLPurifier_Queue::__construct

(

$input = array()

)

Definition at line 8357 of file HTMLPurifier.standalone.php.

Member Function Documentation

isEmpty()

HTMLPurifier_Queue::isEmpty

(

)

Checks if it's empty.

Definition at line 8386 of file HTMLPurifier.standalone.php.

push()

HTMLPurifier_Queue::push

(

$x

)

Pushes an element onto the front of the queue.

Definition at line 8379 of file HTMLPurifier.standalone.php.

shift()

HTMLPurifier_Queue::shift

(

)

Shifts an element off the front of the queue.

Definition at line 8365 of file HTMLPurifier.standalone.php.

---

The documentation for this class was generated from the following file:

• plugins/htmlpurifier/HTMLPurifier.standalone.php