Class Deque

data_structures/deque.ts:80–865

 * @typeParam T The type of the values stored in the deque.
 */
export class Deque<T> implements Iterable<T>, ReadonlyDeque<T> {
  #buffer: (T | undefined)[];
  #head: number;
  #length: number;
  /** Always `#capacity - 1`. Used to wrap indices via `& #mask`. */
  #mask: number;

  get #capacity(): number {
    return this.#mask + 1;
  }

  /**
   * Creates an empty deque, optionally populated from an iterable.
   *
   * @example Creating an empty deque
   * ```ts
   * import { Deque } from "@std/data-structures/deque";
   * import { assertEquals } from "@std/assert";
   *
   * const deque = new Deque<number>();
   * assertEquals(deque.length, 0);
   * ```
   *
   * @example Creating a deque from an iterable
   * ```ts
   * import { Deque } from "@std/data-structures/deque";
   * import { assertEquals } from "@std/assert";
   *
   * const deque = new Deque([1, 2, 3]);
   * assertEquals([...deque], [1, 2, 3]);
   * ```
   *
   * @param source An optional iterable to populate the deque.
   */
  constructor(source?: Iterable<T>) {
    if (source === undefined || source === null) {
      this.#buffer = new Array(MIN_CAPACITY);
      this.#head = 0;
      this.#length = 0;
      this.#mask = MIN_CAPACITY - 1;
      return;
    }
    if (source instanceof Deque) {
      const capacity = nextPowerOfTwo(source.#length);
      this.#buffer = Deque.#copyBuffer(source, capacity);
      this.#head = 0;
      this.#length = source.#length;
      this.#mask = capacity - 1;
      return;
    }
    if (
      typeof source !== "object" && typeof source !== "string" ||
      !(Symbol.iterator in Object(source))
    ) {
      throw new TypeError(
        "Cannot construct a Deque: the 'source' parameter is not iterable, did you mean to call Deque.from?",
      );
    }