<?php

namespace LWVendor;

/**
 * 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);
    }
}
/**
 * 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_alias('LWVendor\\HTMLPurifier_Queue', 'HTMLPurifier_Queue', \false);