Queue and deque.

export type Step = {
	kind: 'allocate' | 'copy' | 'switch' | 'head' | 'write' | 'read' | 'clear' | 'missing';
	/** A slot index, a capacity for allocate and switch, or -1 for none. */
	from: number;
	to: number;
};
export type Lookup<T> = { found: true; value: T } | { found: false };

// Entries sit in slots head, head + 1, … and wrap past the last slot to 0.
// Neither end shifts the other entries. Only the head and the length move.
export class RingDeque<T> {
	#slots: (T | undefined)[] = new Array(4).fill(undefined);
	#head = 0;
	#length = 0;
	#steps: Step[] = [];
	#capture: boolean;

	constructor(capture = false) {
		this.#capture = capture;
	}
	get length(): number {
		return this.#length;
	}
	get capacity(): number {
		return this.#slots.length;
	}
	/** The slot that holds the front entry. Exposed for inspection. */
	get head(): number {
		return this.#head;
	}

	pushBack(value: T): void {
		this.#steps = [];
		if (this.#length === this.capacity) this.#grow();
		const slot = (this.#head + this.#length) % this.capacity;
		this.#slots[slot] = value;
		this.#length++;
		this.#record('write', -1, slot);
	}

	pushFront(value: T): void {
		this.#steps = [];
		if (this.#length === this.capacity) this.#grow();
		const head = (this.#head - 1 + this.capacity) % this.capacity;
		this.#record('head', this.#head, head);
		this.#head = head;
		this.#slots[head] = value;
		this.#length++;
		this.#record('write', -1, head);
	}

	popFront(): Lookup<T> {
		this.#steps = [];
		if (this.#length === 0) return this.#missing();
		const slot = this.#head;
		const value = this.#take(slot);
		this.#head = (slot + 1) % this.capacity;
		this.#record('head', slot, this.#head);
		return { found: true, value };
	}

	popBack(): Lookup<T> {
		this.#steps = [];
		if (this.#length === 0) return this.#missing();
		return { found: true, value: this.#take(this.#backSlot()) };
	}

	peekFront(): Lookup<T> {
		this.#steps = [];
		return this.#length === 0 ? this.#missing() : this.#read(this.#head);
	}

	peekBack(): Lookup<T> {
		this.#steps = [];
		return this.#length === 0 ? this.#missing() : this.#read(this.#backSlot());
	}

	// Front to back. The outer array is a copy; stored objects are not cloned.
	values(): T[] {
		return Array.from(
			{ length: this.#length },
			(_, i) => this.#slots[(this.#head + i) % this.capacity] as T
		);
	}

	trace(): Step[] {
		return this.#steps.map((step) => ({ ...step }));
	}

	#backSlot(): number {
		return (this.#head + this.#length - 1) % this.capacity;
	}

	#read(slot: number): Lookup<T> {
		this.#record('read', slot, slot);
		return { found: true, value: this.#slots[slot] as T };
	}

	#take(slot: number): T {
		const value = this.#slots[slot] as T;
		this.#record('read', slot, slot);
		this.#slots[slot] = undefined; // Let go of the entry.
		this.#length--;
		this.#record('clear', slot, -1);
		return value;
	}

	#missing(): Lookup<T> {
		this.#record('missing', -1, -1);
		return { found: false };
	}

	// Full: copy front to back into twice as many slots, starting at slot 0.
	#grow(): void {
		const previous = this.capacity;
		const next: (T | undefined)[] = new Array(previous * 2).fill(undefined);
		this.#record('allocate', previous, next.length);
		for (let i = 0; i < this.#length; i++) {
			const from = (this.#head + i) % previous;
			next[i] = this.#slots[from];
			this.#record('copy', from, i);
		}
		this.#slots = next;
		this.#head = 0;
		this.#record('switch', previous, next.length);
	}

	#record(kind: Step['kind'], from: number, to: number): void {
		if (this.#capture) this.#steps.push({ kind, from, to });
	}
}

type Step struct {
	Kind string `json:"kind"`
	From int    `json:"from"`
	To   int    `json:"to"`
}

// Entries sit in slots head, head+1, … and wrap past the last slot to 0.
// Neither end shifts the other entries. Only the head and the length move.
type RingDeque[T any] struct {
	slots   []T
	head    int
	length  int
	steps   []Step
	capture bool
}

func NewRingDeque[T any](capture bool) *RingDeque[T] {
	return &RingDeque[T]{slots: make([]T, 4), capture: capture}
}

func (d *RingDeque[T]) Len() int      { return d.length }
func (d *RingDeque[T]) Capacity() int { return len(d.slots) }

// Head is the slot that holds the front entry. Exposed for inspection.
func (d *RingDeque[T]) Head() int { return d.head }

func (d *RingDeque[T]) PushBack(value T) {
	d.steps = nil
	if d.length == len(d.slots) {
		d.grow()
	}
	slot := (d.head + d.length) % len(d.slots)
	d.slots[slot] = value
	d.length++
	d.record("write", -1, slot)
}

func (d *RingDeque[T]) PushFront(value T) {
	d.steps = nil
	if d.length == len(d.slots) {
		d.grow()
	}
	head := (d.head - 1 + len(d.slots)) % len(d.slots)
	d.record("head", d.head, head)
	d.head = head
	d.slots[head] = value
	d.length++
	d.record("write", -1, head)
}

func (d *RingDeque[T]) PopFront() (T, bool) {
	d.steps = nil
	if d.length == 0 {
		return d.missing()
	}
	slot := d.head
	value := d.take(slot)
	d.head = (slot + 1) % len(d.slots)
	d.record("head", slot, d.head)
	return value, true
}

func (d *RingDeque[T]) PopBack() (T, bool) {
	d.steps = nil
	if d.length == 0 {
		return d.missing()
	}
	return d.take(d.backSlot()), true
}

func (d *RingDeque[T]) PeekFront() (T, bool) {
	d.steps = nil
	if d.length == 0 {
		return d.missing()
	}
	return d.read(d.head), true
}

func (d *RingDeque[T]) PeekBack() (T, bool) {
	d.steps = nil
	if d.length == 0 {
		return d.missing()
	}
	return d.read(d.backSlot()), true
}

// Values returns the entries front to back, in a new slice.
func (d *RingDeque[T]) Values() []T {
	values := make([]T, d.length)
	for i := range values {
		values[i] = d.slots[(d.head+i)%len(d.slots)]
	}
	return values
}

func (d *RingDeque[T]) Trace() []Step { return append([]Step{}, d.steps...) }

func (d *RingDeque[T]) backSlot() int { return (d.head + d.length - 1) % len(d.slots) }

func (d *RingDeque[T]) read(slot int) T {
	d.record("read", slot, slot)
	return d.slots[slot]
}

func (d *RingDeque[T]) take(slot int) T {
	value := d.slots[slot]
	d.record("read", slot, slot)
	var zero T
	d.slots[slot] = zero // Release the entry's reference, if T holds one.
	d.length--
	d.record("clear", slot, -1)
	return value
}

func (d *RingDeque[T]) missing() (T, bool) {
	d.record("missing", -1, -1)
	var zero T
	return zero, false
}

// Full: copy front to back into twice as many slots, starting at slot 0.
func (d *RingDeque[T]) grow() {
	previous := len(d.slots)
	next := make([]T, previous*2)
	d.record("allocate", previous, len(next))
	for i := 0; i < d.length; i++ {
		from := (d.head + i) % previous
		next[i] = d.slots[from]
		d.record("copy", from, i)
	}
	d.slots, d.head = next, 0
	d.record("switch", previous, len(next))
}

func (d *RingDeque[T]) record(kind string, from, to int) {
	if d.capture {
		d.steps = append(d.steps, Step{kind, from, to})
	}
}