/usr/share/php/HTMLPurifier/Queue.php is in php-htmlpurifier 4.7.0-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | <?php
/**
* 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.
*/
class HTMLPurifier_Queue {
private $input;
private $output;
public function __construct($input = array()) {
$this->input = $input;
$this->output = array();
}
/**
* Shifts an element off the front of the queue.
*/
public function shift() {
if (empty($this->output)) {
$this->output = array_reverse($this->input);
$this->input = array();
}
if (empty($this->output)) {
return NULL;
}
return array_pop($this->output);
}
/**
* Pushes an element onto the front of the queue.
*/
public function push($x) {
array_push($this->input, $x);
}
/**
* Checks if it's empty.
*/
public function isEmpty() {
return empty($this->input) && empty($this->output);
}
}
|