Monotonic Deque

A horizontal pipe of cells, front on the left and back on the right. The head cell glows in the active tone — it is the current window max under direction="decreasing", or the current window min under direction="increasing". Two pop trays bracket the body: the front tray fires when the sliding window rolls past the head, the back tray fires when a newer value dominates the tail. Cells share a layoutId across snapshots so they glide into their new positions instead of remounting.

Pure visualisation primitive — the caller owns the algorithm. Pass the current items (front to back), an optional lastPoppedFront / lastPoppedBack for the just-evicted cells, and an optional justPushed id for the entry-from-the-back morph. Generic enough to cover any sliding-window-max / sliding-window-min lesson, the "next greater element with eviction" shape, and any teaching surface where double-ended pops are the load-bearing visual. Distinct from MonotonicStackBuilder, which replays a one-ended build from a fixed values array and a step index.

Installation

npx shadcn@latest add https://craftbits.dev/r/monotonic-deque.json

Usage

import { MonotonicDeque } from "@craft-bits/core";
 
<MonotonicDeque
  items={[
    { id: "i-2", value: 5, label: "i=2" },
    { id: "i-3", value: 1, label: "i=3" },
  ]}
/>

Driving it from a sliding-window-maximum reducer — pass the freshly-popped cells per step so the pop trays fire:

const [items, setItems] = useState<MonotonicDequeItem[]>([]);
const [poppedFront, setPoppedFront] = useState<MonotonicDequeItem[]>([]);
const [poppedBack, setPoppedBack] = useState<MonotonicDequeItem[]>([]);
const [justPushed, setJustPushed] = useState<string | null>(null);
 
<MonotonicDeque
  items={items}
  lastPoppedFront={poppedFront}
  lastPoppedBack={poppedBack}
  justPushed={justPushed}
/>

Sliding-window minimum — flip the invariant to keep front-to-back values strictly increasing:

<MonotonicDeque items={items} direction="increasing" />

Read-only snapshot, no pop trays — pass only items and the body renders as a static row:

<MonotonicDeque items={items} tone="default" />

Custom end labels — drop the conventional front / back for a domain-specific framing:

<MonotonicDeque
  items={items}
  frontLabel="oldest"
  backLabel="newest"
/>

Understanding the component

1. Caller owns the snapshot. items is a ReadonlyArray ordered front to back. The component never mutates it, never recomputes the invariant — it trusts that the caller's reducer already enforces the monotonic property. Pass the same items array twice and nothing animates.
2. Two-sided pop trays. lastPoppedFront cells animate out to the left in the error tone (window expiry — "this index left the window"). lastPoppedBack cells animate out to the right in the active tone (domination — "a newer, larger value made this irrelevant"). Both clear when you pass an empty array on the next step.
3. Shared-layout morph. Every item carries a stable id used as the layoutId. When the front evicts, the remaining cells glide left in a single spring instead of unmounting and remounting. When the back pops, the same morph keeps the body settled while the popped cells fly out to the right tray.
4. Just-pushed pulse. justPushed={id} triggers an entry-from-the-back animation on the matching cell — it slides in from the right with a small scale pop. Pass null to suppress the pulse on snapshots that did not push.
5. Direction sets the head meaning. direction="decreasing" reads the head as the current window max (sliding-window-maximum). direction="increasing" reads the head as the current window min. The label flips in the screen-reader summary and the data-direction attribute, but the component never re-orders items — that is the caller's job.
6. Five tones. default reads as "neutral playback"; accent as "active deque" (the default); success as "settled / committed"; warning as "watch this head"; error as "constraint violated". The tone paints the head ring, the back-pop tray, and the body shadow — the front-pop tray always uses the error tone since front evictions are always expiries.
7. Reduced motion. The shared-layout morph, the entry pop, both pop trays, and the staggered cell reveals all collapse to instant under prefers-reduced-motion: reduce. The snapshot still updates; only the motion drops.

Props

Accessibility

• The deque body is a role="list" with an explicit aria-label naming the direction, and each cell is a role="listitem" with an explicit aria-label naming its position from the front, its value, its optional source label, and whether the cell is the current head.
• Both pop-tray cells carry explicit aria-labels describing which end they were popped from and the value lost, so screen-reader users hear the cascade as it happens, not just the settled state.
• An off-screen role="status" paragraph summarises the entire deque, the head value, and the most recent pop counts on every render via aria-live="polite".
• The component exposes data-tone, data-direction, and data-empty on the root; every cell exposes data-state (head / body / popped-front / popped-back) so consumer apps can hook custom styles or assistive tooling.
• Tone is never the only signal — the head cell also gains a thicker inset ring and a contrasting fill, and the front-pop tray always paints in the error tone regardless of the body tone, so colourblind users see the distinction even when hues collide.
• Motion respects prefers-reduced-motion: reduce — the shared-layout morph, the entry pulse, both pop trays, and the staggered reveal all collapse to instant. The snapshot still updates; only the motion drops.

Credits

• Extracted from: algoflashcards (src/lessons/primitives/observation/MonotonicDeque.tsx). The source was a 2500-line lesson component bundling a four-phase reducer (brute-force scan, discovery bridge, deque construction, code bridge), per-step prediction gates for the back-pop and front-evict decisions, audio cues for every push / pop / evict, a MagicMoveBlock code morph between the brute and deque passes, a fast-forward auto-play mode for elements past an interactive limit, micro-queries about amortised cost, and a per-phase score breakdown. The library extract keeps only the pure visualisation primitive — the front-to-back row, the head glow, the two-sided pop trays, the just-pushed pulse — and lets the caller compose any reducer-driven phases, prediction gates, scoring, narration, or sound on top via the title / footer slots.