window-aggregate-store

1	# Ticket: Implement `WindowStore` for the window-aggregate store
2	
3	## Context
4	
5	`window-aggregate-store` ingests `(timestamp, value)` points and answers exact
6	aggregate queries over time windows: total `count`, `sum`, `min`, `max`, and (for
7	range queries) the matching values. It also evicts old points. Everything is
8	integer; no floating point appears in any result.
9	
10	The data types (`src/store/types.ts`) are already in place and must not change.
11	**Only the `WindowStore` class is unimplemented.**
12	
13	## Your task
14	
15	Implement the class methods in:
16	
17	    src/store/windowStore.ts
18	
19	The full contract is written as JSDoc directly above the class in that file , it
20	is authoritative. The summary below repeats it. All arithmetic is integer.
21	
22	You may edit only `src/store/windowStore.ts` (add private state and helpers
23	inside it). Do not modify `types.ts`, the public exports, or the tests.
24	
25	## The contract
26	
27	### Points & insertion sequence
28	
29	`insert(tsMs, value)` records one point. Each point gets an INSERTION SEQUENCE
30	number assigned in call order (first insert is seq 0, then 1, 2, …),
31	monotonically for the store's lifetime. Sequence numbers never reset and are not
32	renumbered by eviction. Multiple points may share a `tsMs` (and a value); they
33	stay distinct. Timestamps may arrive out of order.
34	
35	### Half-open windows
36	
37	Every window is HALF-OPEN: a point with timestamp `ts` matches `[lo, hi)` iff
38	`lo <= ts && ts < hi` , start inclusive, end exclusive. This applies identically
39	to range queries, fixed windows, and the eviction cutoff.
40	
41	### Pinned value ordering
42	
43	Wherever a `values` array is returned, points are ordered ascending by `tsMs`,
44	ties at an identical `tsMs` broken by ascending insertion sequence. Aggregates
45	(count/sum/min/max) are over exactly the same matching set.
46	
47	### Empty result (pinned sentinel)
48	
49	A window/query with no matching points has `count: 0`, `sum: 0`, `min: null`,
50	`max: null`, and (for `queryRange`) `values: []`. `null` is the only empty
51	sentinel , never 0, ±Infinity, or undefined.
52	
53	### Methods
54	
55	- `insert(tsMs: number, value: number): void` , record one point at the next
56	  insertion sequence number.
57	
58	- `queryRange(startMs: number, endMs: number): AggregateResult` , aggregate over
59	  points with `startMs <= ts < endMs`. `values` is the matching values in the
60	  pinned order. If `startMs >= endMs` the range is empty.
61	
62	- `queryFixedWindows(startMs, endMs, intervalMs): WindowAggregate[]` , tile
63	  `[startMs, endMs)` into consecutive half-open windows of width `intervalMs`:
64	  `[startMs, startMs+intervalMs)`, `[startMs+intervalMs, startMs+2*intervalMs)`,
65	  … . INCLUDE empty windows. Emit them ascending by `windowStartMs`. The window
66	  count is `ceil((endMs - startMs) / intervalMs)` when `endMs > startMs`, else 0.
67	  The FINAL window keeps its natural half-open span `[windowStartMs,
68	  windowStartMs + intervalMs)` even if that extends past `endMs`, and matches
69	  points by that span. Each entry is `{ windowStartMs, count, sum, min, max }`
70	  (no per-window `values`). `intervalMs >= 1`.
71	
72	- `evictBefore(cutoffMs: number): number` , permanently remove every point with
73	  `ts < cutoffMs` (a point at exactly `cutoffMs` is kept) and return the count
74	  removed. Every later query must reflect the removal exactly, including min/max
75	  recomputed over only the survivors.
76	
77	### Tiny example
78	
79	```
80	const s = new WindowStore();
81	s.insert(10, 5);   // seq 0
82	s.insert(10, 2);   // seq 1 (same ts)
83	s.insert(20, 9);   // seq 2
84	s.queryRange(10, 20);
85	//=> { count: 2, sum: 7, min: 2, max: 5, values: [5, 2] }
86	```
87	
88	`ts=20` is excluded (end-exclusive); the two `ts=10` points appear in insertion
89	order, so `values` is `[5, 2]`.
90	
91	## Definition of done
92	
93	- `npm run typecheck` is clean.
94	- `npm test` passes the full suite in `test/` , pinned behavioural cases plus a
95	  differential fuzz suite that checks the store against an independent model.
96	- Implement the feature within the `WindowStore` class (and private helpers you
97	  add in `src/store/windowStore.ts`). Do not modify the provided types, the
98	  public exports, or the test files.
99	
100	### Scale (secondary)
101	
102	Some graded cases insert up to ~10^5–10^6 points and issue up to ~10^5 queries.
103	The per-operation time budget is generous: a correctly-indexed implementation
104	(keeping points ordered / using cumulative structures so each query touches far
105	fewer than all points) finishes comfortably. Correctness is the primary bar; a
106	pathological design that rescans every point on every query may be too slow on
107	the large cases, but most of the grade is the exact-semantics tests.
108	
109	## Running locally
110	
111	```bash
112	npm install      # already done in the provided environment
113	npm run typecheck
114	npm test
115	```
116

1	/**
2	 * Data types for the window-aggregate store. Provided complete; do not modify.
3	 *
4	 * All numeric fields are integers. Timestamps and values may be any integer
5	 * (negative allowed for values; timestamps are non-negative). The store keeps
6	 * (timestamp, value) points and answers exact aggregate queries over half-open
7	 * time windows. See the JSDoc on `WindowStore` (src/store/windowStore.ts) for
8	 * the authoritative semantics.
9	 */
10	
11	/**
12	 * The result of an aggregate query over a set of matching points.
13	 *
14	 * `count`/`sum` are always integers. When `count === 0` (no matching points),
15	 * `sum` is 0, `min`/`max` are the pinned empty sentinel `null`, and `values` is
16	 * the empty array. Otherwise `min`/`max` are the smallest/largest matching value
17	 * and `values` lists every matching value in the PINNED order (ascending by
18	 * timestamp, ties broken by ascending insertion sequence).
19	 */
20	export interface AggregateResult {
21	  /** Number of matching points. */
22	  count: number;
23	  /** Sum of matching values (0 when count is 0). */
24	  sum: number;
25	  /** Smallest matching value, or null when there are no matching points. */
26	  min: number | null;
27	  /** Largest matching value, or null when there are no matching points. */
28	  max: number | null;
29	  /**
30	   * Every matching value, in the pinned order: ascending by timestamp, ties at
31	   * an identical timestamp broken by ascending insertion sequence (the order in
32	   * which the points were inserted into the store). Empty when count is 0.
33	   */
34	  values: number[];
35	}
36	
37	/**
38	 * One consecutive fixed window's aggregate, as returned by
39	 * `queryFixedWindows`. Unlike {@link AggregateResult} this carries the window's
40	 * start instant but NOT the per-window `values` array (only count/sum/min/max).
41	 */
42	export interface WindowAggregate {
43	  /** The inclusive start instant of this half-open window `[windowStartMs, windowStartMs + intervalMs)`. */
44	  windowStartMs: number;
45	  /** Number of points falling in this window. */
46	  count: number;
47	  /** Sum of values in this window (0 when count is 0). */
48	  sum: number;
49	  /** Smallest value in this window, or null when the window is empty. */
50	  min: number | null;
51	  /** Largest value in this window, or null when the window is empty. */
52	  max: number | null;
53	}
54

1	import type { AggregateResult, WindowAggregate } from "./types.js";
2	
3	/**
4	 * An exact time-windowed aggregation store over integer `(timestamp, value)`
5	 * points. Inserts record a point at an integer millisecond timestamp; queries
6	 * report exact `count`/`sum`/`min`/`max` (and, for ranges, the matching values)
7	 * over HALF-OPEN time windows; eviction removes old points. INTEGER arithmetic
8	 * throughout , no floats appear in any result.
9	 *
10	 * Implement EVERY method below to the pinned semantics. The boundaries, tie
11	 * ordering, empty handling and eviction consistency are the whole point: the
12	 * obvious implementation gets several of them wrong.
13	 *
14	 * ## Points & insertion sequence
15	 *
16	 * Each `insert(tsMs, value)` appends a point. Every point carries an INSERTION
17	 * SEQUENCE number assigned in call order: the first ever `insert` is seq 0, the
18	 * next seq 1, and so on, monotonically, for the lifetime of the store.
19	 * Insertion sequence NEVER resets and is NOT renumbered by eviction. Multiple
20	 * points may share the same `tsMs` (and even the same value); they remain
21	 * distinct points with distinct sequence numbers. Timestamps need not arrive in
22	 * order.
23	 *
24	 * ## Pinned value ordering
25	 *
26	 * Wherever a `values` array is returned, points are ordered ASCENDING BY
27	 * `tsMs`, and ties at an identical `tsMs` are broken by ASCENDING INSERTION
28	 * SEQUENCE (i.e. the order the tied points were inserted). This total order is
29	 * used for the `values` arrays; aggregates (count/sum/min/max) do not depend on
30	 * order but must be consistent with exactly the same matching set.
31	 *
32	 * ## Half-open windows (pinned)
33	 *
34	 * Every window in this store is HALF-OPEN: a point with timestamp `ts` matches
35	 * a window `[lo, hi)` iff `lo <= ts && ts < hi`. The start is INCLUSIVE, the end
36	 * is EXCLUSIVE. This rule is applied identically by `queryRange`,
37	 * `queryFixedWindows` and the cutoff in `evictBefore`.
38	 *
39	 * ## Empty result (pinned sentinel)
40	 *
41	 * A window (or whole query) with no matching points has `count: 0`, `sum: 0`,
42	 * `min: null`, `max: null`, and (for `queryRange`) `values: []`. `null` is the
43	 * one and only empty sentinel; never use 0, +/-Infinity, or undefined.
44	 *
45	 * ## Methods
46	 *
47	 * - `insert(tsMs, value)`: record one point at integer `tsMs` with integer
48	 *   `value`, assigning it the next insertion sequence number. Returns nothing.
49	 *
50	 * - `queryRange(startMs, endMs)`: aggregate over all points with
51	 *   `startMs <= ts < endMs` (half-open). Returns
52	 *   `{ count, sum, min, max, values }` where `values` is the matching values in
53	 *   the pinned order. If `startMs >= endMs` the range is empty: return the empty
54	 *   result. Eviction is reflected exactly (evicted points never match).
55	 *
56	 * - `queryFixedWindows(startMs, endMs, intervalMs)`: tile `[startMs, endMs)`
57	 *   into CONSECUTIVE half-open windows of width `intervalMs`:
58	 *   `[startMs, startMs + intervalMs)`, `[startMs + intervalMs, startMs + 2*intervalMs)`,
59	 *   and so on. INCLUDE empty windows (a window with no points still appears,
60	 *   with count 0 and the null sentinels). Windows are emitted in ascending
61	 *   `windowStartMs` order. The number of windows is `ceil((endMs - startMs) /
62	 *   intervalMs)` when `endMs > startMs`, else 0. The FINAL window is the partial
63	 *   window that begins at the largest `startMs + k*intervalMs` that is `< endMs`;
64	 *   it is still emitted with its natural half-open span
65	 *   `[windowStartMs, windowStartMs + intervalMs)` (so it MAY extend past `endMs`),
66	 *   but points are matched ONLY by that half-open span , a point at exactly
67	 *   `endMs` or beyond never matches because no window's start is `>= endMs`... yet
68	 *   a point in `[lastWindowStart, lastWindowStart + intervalMs)` DOES match the
69	 *   final window even if its timestamp is `>= endMs`. (`intervalMs >= 1`.) Each
70	 *   entry is `{ windowStartMs, count, sum, min, max }`; no per-window `values`.
71	 *
72	 * - `evictBefore(cutoffMs)`: permanently remove every point with `ts < cutoffMs`
73	 *   (half-open: a point at exactly `cutoffMs` is KEPT). Return the integer count
74	 *   of points removed. After eviction, every subsequent query must reflect the
75	 *   removal exactly: evicted points contribute to no count/sum, and min/max are
76	 *   recomputed over only the surviving matching points (an evicted extreme is
77	 *   gone). Insertion sequence numbers of survivors are unchanged.
78	 *
79	 * ## Tiny example
80	 *
81	 *     const s = new WindowStore();
82	 *     s.insert(10, 5);   // seq 0
83	 *     s.insert(10, 2);   // seq 1 (same ts as seq 0)
84	 *     s.insert(20, 9);   // seq 2
85	 *     s.queryRange(10, 20);
86	 *     //=> { count: 2, sum: 7, min: 2, max: 5, values: [5, 2] }
87	 *     //   ts=20 is EXCLUDED (end-exclusive); the two ts=10 points are ordered
88	 *     //   by insertion sequence, so values is [5, 2] not [2, 5].
89	 *
90	 * You may edit ONLY this file (and add private helpers/state here). Do not modify
91	 * `types.ts`, the public exports, or the tests.
92	 */
93	export class WindowStore {
94	  /**
95	   * Insert one point.
96	   * @param tsMs integer timestamp in ms (non-negative).
97	   * @param value integer value (may be negative).
98	   */
99	  insert(tsMs: number, value: number): void {
100	    void tsMs;
101	    void value;
102	    throw new Error("WindowStore.insert not implemented");
103	  }
104	
105	  /**
106	   * Aggregate over points with `startMs <= ts < endMs` (half-open).
107	   * @returns `{ count, sum, min, max, values }` per the class contract.
108	   */
109	  queryRange(startMs: number, endMs: number): AggregateResult {
110	    void startMs;
111	    void endMs;
112	    throw new Error("WindowStore.queryRange not implemented");
113	  }
114	
115	  /**
116	   * Tile `[startMs, endMs)` into consecutive half-open windows of width
117	   * `intervalMs` and aggregate each (including empty windows).
118	   * @returns one {@link WindowAggregate} per window, ascending by windowStartMs.
119	   */
120	  queryFixedWindows(startMs: number, endMs: number, intervalMs: number): WindowAggregate[] {
121	    void startMs;
122	    void endMs;
123	    void intervalMs;
124	    throw new Error("WindowStore.queryFixedWindows not implemented");
125	  }
126	
127	  /**
128	   * Remove every point with `ts < cutoffMs` (a point at exactly `cutoffMs` is
129	   * kept). @returns the number of points removed.
130	   */
131	  evictBefore(cutoffMs: number): number {
132	    void cutoffMs;
133	    throw new Error("WindowStore.evictBefore not implemented");
134	  }
135	}
136

{
  "name": "window-aggregate-store",
  "version": "0.1.0",
  "private": true,
  "description": "Exact time-windowed aggregation store over integer (timestamp, value) points: half-open range/fixed-window aggregates (count/sum/min/max) with pinned tie ordering and exact eviction semantics.",
  "type": "module",
  "engines": {
    "node": ">=20"
  },
  "scripts": {
    "build": "tsc -p tsconfig.json",
    "typecheck": "tsc -p tsconfig.json --noEmit",
    "test": "vitest run",
    "test:watch": "vitest"
  },
  "devDependencies": {
    "@types/node": "20.14.10",
    "typescript": "5.5.3",
    "vitest": "1.6.0"
  }
}
---TSCONFIG---
{
  "compilerOptions": {
    "target": "ES2022",
    "module": "ESNext",
    "moduleResolution": "Bundler",
    "lib": ["ES2022"],
    "types": ["node"],
    "rootDir": ".",
    "outDir": "dist",
    "strict": true,
    "noUnusedLocals": true,
    "noUnusedParameters": true,
    "noImplicitReturns": true,
    "noFallthroughCasesInSwitch": true,
    "exactOptionalPropertyTypes": false,
    "esModuleInterop": true,
    "forceConsistentCasingInFileNames": true,
    "resolveJsonModule": true,
    "skipLibCheck": true,
    "verbatimModuleSyntax": false
  },
  "include": ["src", "test"],
  "exclude": ["node_modules", "dist"]
}
---FILES---
types.ts
windowStore.ts
smoke.test.ts

1	import { describe, expect, it } from "vitest";
2	import { WindowStore } from "../src/store/windowStore.js";
3	import type { AggregateResult, WindowAggregate } from "../src/store/types.js";
4	
5	/**
6	 * Smoke tests for the *provided* surface only. They confirm the store is
7	 * constructible, that the methods exist with the right arity, and that the
8	 * result types are shaped as documented , WITHOUT relying on any aggregation
9	 * policy (the methods are still stubs that throw), so they pass in the shipped
10	 * project and the type-check stays green. The behavioural suite is added at
11	 * grading time.
12	 */
13	
14	describe("provided surface", () => {
15	  it("constructs a WindowStore", () => {
16	    const s = new WindowStore();
17	    expect(s).toBeInstanceOf(WindowStore);
18	  });
19	
20	  it("exposes the documented methods with the expected arity", () => {
21	    const s = new WindowStore();
22	    expect(typeof s.insert).toBe("function");
23	    expect(s.insert.length).toBe(2);
24	    expect(typeof s.queryRange).toBe("function");
25	    expect(s.queryRange.length).toBe(2);
26	    expect(typeof s.queryFixedWindows).toBe("function");
27	    expect(s.queryFixedWindows.length).toBe(3);
28	    expect(typeof s.evictBefore).toBe("function");
29	    expect(s.evictBefore.length).toBe(1);
30	  });
31	
32	  it("the stub methods are wired but unimplemented (they throw)", () => {
33	    const s = new WindowStore();
34	    expect(() => s.insert(0, 0)).toThrow();
35	    expect(() => s.queryRange(0, 1)).toThrow();
36	    expect(() => s.queryFixedWindows(0, 1, 1)).toThrow();
37	    expect(() => s.evictBefore(0)).toThrow();
38	  });
39	
40	  it("the result types are usable from a test (compile-time shape check)", () => {
41	    const empty: AggregateResult = { count: 0, sum: 0, min: null, max: null, values: [] };
42	    expect(empty.count).toBe(0);
43	    expect(empty.min).toBeNull();
44	    const w: WindowAggregate = { windowStartMs: 0, count: 0, sum: 0, min: null, max: null };
45	    expect(w.windowStartMs).toBe(0);
46	    expect(w.max).toBeNull();
47	  });
48	});
49

The file /home/user/app/src/store/windowStore.ts has been updated successfully. (file state is current in your context , no need to Read it back)

> window-aggregate-store@0.1.0 typecheck
> tsc -p tsconfig.json --noEmit

RUN  v1.6.0 /home/user/app

filter:  /tmp/verify.test.ts
include: test/**/*.test.ts
exclude:  **/node_modules/**, **/dist/**, **/cypress/**, **/.{idea,git,cache,output,temp}/**, **/{karma,rollup,webpack,vite,vitest,jest,ava,babel,nyc,cypress,tsup,build,eslint,prettier}.config.*
watch exclude:  **/node_modules/**, **/dist/**

No test files found, exiting with code 1

RUN  v1.6.0 /home/user/app

 ✓ test/_scratch_verify.test.ts  (2 tests) 373ms

 Test Files  1 passed (1)
      Tests  2 passed (2)
   Start at  20:45:36
   Duration  743ms (transform 99ms, setup 0ms, collect 95ms, tests 373ms, environment 0ms, prepare 124ms)

insert ms 4100 query ms 8895 fixed ms 187 acc 60581217 fwlen 1000
 Test Files  1 passed (1)
      Tests  1 passed (1)