Xes
73154ae174
Fuente: https://github.com/chamilo/chamilo-lms/releases/download/v1.11.40/chamilo-1.11.40.zip sha256: 1cf4bf2cc7bae1ef1a1eff643235db1d552f78ddf4b6dd1e2d2dac9868679439 Snapshot independiente (rama huerfana); diffable vs 1.11.38. vendor incluido.
57 lines
1.5 KiB
PHP
57 lines
1.5 KiB
PHP
<?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);
|
|
}
|
|
}
|