ILIAS  release_5-2 Revision v5.2.25-18-g3f80b82851
HTMLPurifier_Queue Class Reference

A simple array-backed queue, based off of the classic Okasaki persistent amortized queue. More...

+ Collaboration diagram for HTMLPurifier_Queue:

Public Member Functions

 __construct ($input=array())
 
 shift ()
 Shifts an element off the front of the queue. More...
 
 push ($x)
 Pushes an element onto the front of the queue. More...
 
 isEmpty ()
 Checks if it's empty. More...
 

Private Attributes

 $input
 
 $output
 

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 20 of file Queue.php.

Constructor & Destructor Documentation

◆ __construct()

HTMLPurifier_Queue::__construct (   $input = array())

Definition at line 24 of file Queue.php.

References $input, array, and input.

24  {
25  $this->input = $input;
26  $this->output = array();
27  }
input
Definition: langcheck.php:166
Create styles array
The data for the language used.

Member Function Documentation

◆ isEmpty()

HTMLPurifier_Queue::isEmpty ( )

Checks if it's empty.

Definition at line 53 of file Queue.php.

References input.

53  {
54  return empty($this->input) && empty($this->output);
55  }
input
Definition: langcheck.php:166

◆ push()

HTMLPurifier_Queue::push (   $x)

Pushes an element onto the front of the queue.

Definition at line 46 of file Queue.php.

References $x, and input.

46  {
47  array_push($this->input, $x);
48  }
$x
Definition: example_009.php:98
input
Definition: langcheck.php:166

◆ shift()

HTMLPurifier_Queue::shift ( )

Shifts an element off the front of the queue.

Definition at line 32 of file Queue.php.

References array, and input.

32  {
33  if (empty($this->output)) {
34  $this->output = array_reverse($this->input);
35  $this->input = array();
36  }
37  if (empty($this->output)) {
38  return NULL;
39  }
40  return array_pop($this->output);
41  }
input
Definition: langcheck.php:166
Create styles array
The data for the language used.

Field Documentation

◆ $input

HTMLPurifier_Queue::$input
private

Definition at line 21 of file Queue.php.

Referenced by __construct().

◆ $output

HTMLPurifier_Queue::$output
private

Definition at line 22 of file Queue.php.


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