Class HTMLPurifier_Queue

InheritanceHTMLPurifier_Queue

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.

Public Methods

Hide inherited methods

MethodDescriptionDefined By
__construct() HTMLPurifier_Queue
isEmpty() Checks if it's empty. HTMLPurifier_Queue
push() Pushes an element onto the front of the queue. HTMLPurifier_Queue
shift() Shifts an element off the front of the queue. HTMLPurifier_Queue

Method Details

__construct() public method

public void __construct ( $input = [] )
$input
isEmpty() public method

Checks if it's empty.

public void isEmpty ( )
push() public method

Pushes an element onto the front of the queue.

public void push ( $x )
$x
shift() public method

Shifts an element off the front of the queue.

public void shift ( )