Deque.php

<?php

declare(strict_types=1);

/*
 * This file is part of the univeros/framework
 *
 * For the full copyright and license information, please view
 * the LICENSE file that was distributed with this source code.
 */

namespace Altair\Structure;

use Altair\Structure\Contracts\CapacityInterface;
use Altair\Structure\Contracts\SequenceInterface;
use Altair\Structure\Traits\SequenceTrait;
use Altair\Structure\Traits\SquaredCapacityTrait;
use ArrayAccess;
use IteratorAggregate;
use Traversable;

/**
 * Deque.
 *
 * A Deque ("deck") is a Sequence of values in a contiguous buffer that grows and shrinks automatically. The name is a
 * common abbreviation of "double-ended queue" and is used internally by `Altair\Structure\Queue`.
 *
 * Two pointers are used to keep track of a head and a tail. The pointers can "wrap around" the end of the buffer, which
 * avoids to the need to move other values around to make room.
 *
 * Accessing a value by index requires a translation between the index and its corresponding position in the buffer:
 * ((head + position) % capacity).
 *
 * @link https://medium.com/@rtheunissen/efficient-data-structures-for-php-7-9dda7af674cd#.gl62k1xqr
 *
 * @template TValue
 *
 * @implements SequenceInterface<TValue>
 * @implements IteratorAggregate<int, TValue>
 * @implements ArrayAccess<int, TValue>
 */
class Deque implements IteratorAggregate, ArrayAccess, SequenceInterface, CapacityInterface
{
    /** @use SequenceTrait<TValue> */
    use SequenceTrait;
    use SquaredCapacityTrait;

    /**
     * @inheritDoc
     *
     * @param array<array-key, TValue>|Traversable<array-key, TValue>|null $values
     */
    public function __construct($values = null)
    {
        $this->pushAll($this->normalizeItems($values ?? []));
    }
}