HTMLPurifier_Queue Klassenreferenz

Öffentliche Methoden
	__construct ($input=array())
	shift ()
	push ($x)
	isEmpty ()

Private Attribute
	$input
	$output

Ausführliche Beschreibung

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.

Definiert in Zeile 20 der Datei Queue.php.

Beschreibung der Konstruktoren und Destruktoren

__construct

(

$input = array())

Definiert in Zeile 24 der Datei Queue.php.

Benutzt $input.

Dokumentation der Elementfunktionen

isEmpty

(

)

Checks if it's empty.

Definiert in Zeile 53 der Datei Queue.php.

push

(

$x)

Pushes an element onto the front of the queue.

Definiert in Zeile 46 der Datei Queue.php.

shift

(

)

Shifts an element off the front of the queue.

Definiert in Zeile 32 der Datei Queue.php.

Dokumentation der Datenelemente

$input

private

Definiert in Zeile 21 der Datei Queue.php.

Wird benutzt von __construct().

$output

private

Definiert in Zeile 22 der Datei Queue.php.

---

Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Datei:

• HTMLPurifier/Queue.php