29898063965

Committed 22 Jul 2026 06:50AM UTC coverage: 98.318% (-0.01%) from 98.332%

Build # 29898063965

Build Type

Pull #2222

github

Committed by

web-flow

Commit Message

Merge 082136c07 into 20331d724

Pull Request Pull Request #2222: feat: Added virtualization component

Coverage Stats

6107 of 6428 branches covered (95.01%)

Branch coverage included in aggregate %.

987 of 999 new or added lines in 6 files covered. (98.8%)

24 existing lines in 1 file now uncovered.

43157 of 43679 relevant lines covered (98.8%)

1546.35 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.07

/src/components/virtualization/engine.ts

/**
 * Probes the browser for the maximum scrollable coordinate it supports.
 */
function getMaxBrowserSizeProbePx(doc: Document): number {
  const div = doc.createElement('div');
  div.style.position = 'absolute';
  div.style.top = `${Number.MAX_SAFE_INTEGER}px`;
  doc.body.appendChild(div);
  const size = Math.abs(div.getBoundingClientRect().top);
  doc.body.removeChild(div);
  return size;
}

/**
 * Binary Indexed Tree (Fenwick tree) over item sizes.
 *
 * Replaces the previous O(N) prefix-sum rebuild that occurred on every
 * `measureItem` call. All hot-path operations are O(log N):
 *   - Point update (item measured)        : O(log N)
 *   - Prefix sum (scroll offset)          : O(log N)
 *   - Index at offset (scroll → item)     : O(log N) via binary lifting
 */
class BIT {
  public readonly length: number;

  /** 1-indexed BIT; each cell holds a partial range sum. */
  private readonly _tree: Float64Array;

  /** Raw per-item sizes (0-indexed) — kept for O(1) reads and delta calc. */
  private readonly _sizes: Float64Array;

  /** Running total maintained alongside tree updates in O(1). */
  private _total: number;

  private constructor(
    length: number,
    sizes: Float64Array,
    tree: Float64Array,
    total: number
  ) {
    this.length = length;
    this._sizes = sizes;
    this._tree = tree;
    this._total = total;
  }

  /**
   * Creates a BIT of `length` items all initialized to `fillSize`. O(N).
   */
  public static filled(length: number, fillSize: number): BIT {
    const sizes = new Float64Array(length).fill(fillSize);
    const tree = new Float64Array(length + 1);
    const total = length * fillSize;

    // O(N) build (vs O(N log N) for N individual insertions)
    for (let i = 1; i <= length; i++) {
      tree[i] += fillSize;
      const j = i + (i & -i);
      if (j <= length) {
        tree[j] += tree[i];
      }
    }
    return new BIT(length, sizes, tree, total);
  }

  /**
   * Creates a BIT from an existing sizes array. O(N).
   */
  public static fromSizes(sizes: Float64Array): BIT {
    const length = sizes.length;
    const tree = new Float64Array(length + 1);
    let total = 0;

    for (let i = 1; i <= length; i++) {
      tree[i] += sizes[i - 1];
      total += sizes[i - 1];
      const j = i + (i & -i);
      if (j <= length) {
        tree[j] += tree[i];
      }
    }
    return new BIT(length, sizes, tree, total);
  }

  /** Total size of all items. O(1). */
  public get totalSize(): number {
    return this._total;
  }

  /**
   * Prefix sum of items [0, i) — the virtual scroll offset at the leading
   * edge of item i. O(log N).
   */
  public prefixSum(i: number): number {
    let sum = 0;
    for (let j = i; j > 0; j -= j & -j) {
      sum += this._tree[j];
    }
    return sum;
  }

  /**
   * Update the size of the item at 0-based index.
   * Returns true when the size actually changed. O(log N).
   */
  public update(index: number, newSize: number): boolean {
    if (index < 0 || index >= this.length) return false;

    const old = this._sizes[index];
    if (old === newSize) return false;

    const delta = newSize - old;
    this._sizes[index] = newSize;
    this._total += delta;
    for (let i = index + 1; i <= this.length; i += i & -i) {
      this._tree[i] += delta;
    }
    return true;
  }

  /**
   * Returns a new BIT of `newLength` items.
   * Existing measured sizes are preserved up to `min(this.length, newLength)`;
   * new slots are filled with `fillSize`. Single O(N) build pass.
   */
  public cloneResized(newLength: number, fillSize: number): BIT {
    const sizes = new Float64Array(newLength).fill(fillSize);
    sizes.set(this._sizes.subarray(0, Math.min(this.length, newLength)));
    return BIT.fromSizes(sizes);
  }

  /**
   * Returns the 0-based index of the item that contains the given scroll `offset`,
   * i.e. the largest i such that `prefixSum(i) <= offset < prefixSum(i + 1)`.
   * O(log N) via binary lifting on the internal tree.
   */
  public findIndexAtOffset(offset: number): number {
    if (offset <= 0 || this.length === 0) return 0;

    let idx = 0;
    let remaining = offset;

    for (let bit = 1 << (31 - Math.clz32(this.length)); bit > 0; bit >>= 1) {
      const next = idx + bit;
      if (next <= this.length && this._tree[next] <= remaining) {
        idx = next;
        remaining -= this._tree[idx];
      }
    }
    return Math.min(this.length - 1, idx);
  }
}

/**
 * Describes the currently visible (and over-scanned) range of items.
 */
export interface VisibleRange {
  /** Index of the first rendered item (inclusive) */
  startIndex: number;
  /** Index of the last rendered item (inclusive) */
  endIndex: number;
}

/**
 * Pure scroll-math engine for a single axis of virtual scrolling.
 *
 * All size state is held as plain arrays. Consumers can register an
 * `onSizeChange` callback to react whenever item sizes or the item count
 * changes (e.g. to trigger a Lit `requestUpdate()`).
 */
export class VirtualScrollEngine {
  private _maxBrowserSize = Number.POSITIVE_INFINITY;

  /**
   * The ratio `totalSize / maxBrowserSize` when `totalSize` exceeds the
   * maximum DOM coordinate the browser supports; `1` otherwise.
   * Used to map virtual scroll positions to DOM scroll positions.
   */
  private _virtualRatio = 1;

  /** Binary Indexed Tree for O(log N) size queries and updates. */
  private _tree: BIT | null = null;

  /**
   * Called whenever item sizes or the item count change.
   * Assign a callback (e.g. `() => this.requestUpdate()`) to react to size updates.
   */
  public onSizeChange: (() => void) | null = null;

  /** Total virtual size of all items in px. */
  public get totalSize(): number {
    return this._tree?.totalSize ?? 0;
  }

  /** Actual DOM space size (clamped to the maximum browser size) */
  public get domSize(): number {
    return this._virtualRatio !== 1 ? this._maxBrowserSize : this.totalSize;
  }

  /**
   * Initializes the maximum browser size by probing the document, and updates the virtual ratio accordingly.
   */
  public initMaxBrowserSize(doc: Document): void {
    this._maxBrowserSize = getMaxBrowserSizeProbePx(doc);
    this._updateVirtualRatio();
  }

  /**
   * Grows or shrinks the internal sizes array to `length`.
   * New entries are filled with `estimatedSize`.
   * Existing measured sizes are preserved.
   */
  public resize(length: number, estimatedSize: number): void {
    if (this._tree?.length === length) return;

    this._tree = this._tree
      ? this._tree.cloneResized(length, estimatedSize)
      : BIT.filled(length, estimatedSize);
    this._updateVirtualRatio();
    this.onSizeChange?.();
  }

  /**
   * Records the measured DOM size for a single item.
   */
  public measureItem(index: number, size: number): void {
    if (!this._tree?.update(index, size)) return;

    this._updateVirtualRatio();
    this.onSizeChange?.();
  }

  /**
   * Returns the DOM scroll offset in pixels that brings item at `index` into view
   * at the leading edge of the viewport.
   */
  public getScrollOffsetForIndex(index: number): number {
    if (!this._tree || index <= 0) return 0;

    const clamped = Math.min(index, this._tree.length);
    return this._tree.prefixSum(clamped) / this._virtualRatio;
  }

  /** Returns the item index at the given DOM scroll position. */
  public getIndexAtScroll(scrollPosition: number): number {
    if (!this._tree || scrollPosition <= 0) return 0;
    return this._tree.findIndexAtOffset(scrollPosition * this._virtualRatio);
  }

  /**
   * Returns the visible + over-scanned item range for the given scroll state.
   */
  public getVisibleRange(
    scrollPosition: number,
    viewportSize: number,
    overScan: number,
    totalItems: number
  ): VisibleRange {
    if (totalItems === 0 || viewportSize <= 0) {
      return { startIndex: 0, endIndex: -1 };
    }

    const start = Math.max(0, this.getIndexAtScroll(scrollPosition) - overScan);
    const endScrollPosition = scrollPosition + viewportSize;
    const endRaw = this.getIndexAtScroll(endScrollPosition);
    const end = Math.min(totalItems - 1, endRaw + overScan);

    return { startIndex: start, endIndex: end };
  }

  /**
   * Returns the CSS `translateY` / `translateX` value (px) to apply to the
   * absolutely-positioned content wrapper.
   *
   * The content wrapper is `position: absolute; top: 0; left: 0` inside a
   * track element that is `totalSize` px tall/wide. Translating it to
   * `getContentPosition(startIndex)` places the first rendered item exactly
   * at its virtual scroll position within the track.
   */
  public getContentPosition(index: number): number {
    return this.getScrollOffsetForIndex(index);
  }

  /**
   * Returns the sum of actual sizes for items in [startIndex, endIndex].
   * Used to clamp the content translate offset under coordinate compression
   * so rendered items never overflow past `domSize`.
   */
  public getPhysicalRangeSize(startIndex: number, endIndex: number): number {
    if (!this._tree) return 0;

    const start = Math.max(0, startIndex);
    const end = Math.min(Math.max(endIndex + 1, start), this._tree.length);
    return this._tree.prefixSum(end) - this._tree.prefixSum(start);
  }

  private _updateVirtualRatio(): void {
    const totalSize = this._tree?.totalSize ?? 0;
    this._virtualRatio =
      this._maxBrowserSize === Number.POSITIVE_INFINITY ||
      totalSize <= this._maxBrowserSize
        ? 1
        : totalSize / this._maxBrowserSize;
  }
}

1	/**	9✔
2	* Probes the browser for the maximum scrollable coordinate it supports.	9✔
3	*/	9✔
4	function getMaxBrowserSizeProbePx(doc: Document): number {	129✔
5	const div = doc.createElement('div');	129✔
6	div.style.position = 'absolute';	129✔
7	div.style.top = `${Number.MAX_SAFE_INTEGER}px`;	129✔
8	doc.body.appendChild(div);	129✔
9	const size = Math.abs(div.getBoundingClientRect().top);	129✔
10	doc.body.removeChild(div);	129✔
11	return size;	129✔
12	}	129✔
13		9✔
14	/**	9✔
15	* Binary Indexed Tree (Fenwick tree) over item sizes.	9✔
16	*	9✔
17	* Replaces the previous O(N) prefix-sum rebuild that occurred on every	9✔
18	* `measureItem` call. All hot-path operations are O(log N):	9✔
19	* - Point update (item measured) : O(log N)	9✔
20	* - Prefix sum (scroll offset) : O(log N)	9✔
21	* - Index at offset (scroll → item) : O(log N) via binary lifting	9✔
22	*/	9✔
23	class BIT {	9✔
24	public readonly length: number;	9✔
25		9✔
26	/** 1-indexed BIT; each cell holds a partial range sum. */	9✔
27	private readonly _tree: Float64Array;	9✔
28		9✔
29	/** Raw per-item sizes (0-indexed) — kept for O(1) reads and delta calc. */	9✔
30	private readonly _sizes: Float64Array;	9✔
31		9✔
32	/** Running total maintained alongside tree updates in O(1). */	9✔
33	private _total: number;	9✔
34		9✔
35	private constructor(	9✔
36	length: number,	168✔
37	sizes: Float64Array,	168✔
38	tree: Float64Array,	168✔
39	total: number	168✔
40	) {	168✔
41	this.length = length;	168✔
42	this._sizes = sizes;	168✔
43	this._tree = tree;	168✔
44	this._total = total;	168✔
45	}	168✔
46		9✔
47	/**	9✔
48	* Creates a BIT of `length` items all initialized to `fillSize`. O(N).	9✔
49	*/	9✔
50	public static filled(length: number, fillSize: number): BIT {	9✔
51	const sizes = new Float64Array(length).fill(fillSize);	129✔
52	const tree = new Float64Array(length + 1);	129✔
53	const total = length * fillSize;	129✔
54		129✔
55	// O(N) build (vs O(N log N) for N individual insertions)	129✔
56	for (let i = 1; i <= length; i++) {	129✔
57	tree[i] += fillSize;	13,319✔
58	const j = i + (i & -i);	13,319✔
59	if (j <= length) {	13,319✔
60	tree[j] += tree[i];	13,126✔
61	}	13,126✔
62	}	13,319✔
63	return new BIT(length, sizes, tree, total);	129✔
64	}	129✔
65		9✔
66	/**	9✔
67	* Creates a BIT from an existing sizes array. O(N).	9✔
68	*/	9✔
69	public static fromSizes(sizes: Float64Array): BIT {	9✔
70	const length = sizes.length;	39✔
71	const tree = new Float64Array(length + 1);	39✔
72	let total = 0;	39✔
73		39✔
74	for (let i = 1; i <= length; i++) {	39✔
75	tree[i] += sizes[i - 1];	256✔
76	total += sizes[i - 1];	256✔
77	const j = i + (i & -i);	256✔
78	if (j <= length) {	256✔
79	tree[j] += tree[i];	208✔
80	}	208✔
81	}	256✔
82	return new BIT(length, sizes, tree, total);	39✔
83	}	39✔
84		9✔
85	/** Total size of all items. O(1). */	9✔
86	public get totalSize(): number {	9✔
87	return this._total;	1,762✔
88	}	1,762✔
89		9✔
90	/**	9✔
91	* Prefix sum of items [0, i) — the virtual scroll offset at the leading	9✔
92	* edge of item i. O(log N).	9✔
93	*/	9✔
94	public prefixSum(i: number): number {	9✔
95	let sum = 0;	966✔
96	for (let j = i; j > 0; j -= j & -j) {	966✔
97	sum += this._tree[j];	649✔
98	}	649✔
99	return sum;	966✔
100	}	966✔
101		9✔
102	/**	9✔
103	* Update the size of the item at 0-based index.	9✔
104	* Returns true when the size actually changed. O(log N).	9✔
105	*/	9✔
106	public update(index: number, newSize: number): boolean {	9✔
107	if (index < 0 \|\| index >= this.length) return false;	930!
108		930✔
109	const old = this._sizes[index];	930✔
110	if (old === newSize) return false;	930✔
111		521✔
112	const delta = newSize - old;	521✔
113	this._sizes[index] = newSize;	521✔
114	this._total += delta;	521✔
115	for (let i = index + 1; i <= this.length; i += i & -i) {	930✔
116	this._tree[i] += delta;	1,542✔
117	}	1,542✔
118	return true;	521✔
119	}	930✔
120		9✔
121	/**	9✔
122	* Returns a new BIT of `newLength` items.	9✔
123	* Existing measured sizes are preserved up to `min(this.length, newLength)`;	9✔
124	* new slots are filled with `fillSize`. Single O(N) build pass.	9✔
125	*/	9✔
126	public cloneResized(newLength: number, fillSize: number): BIT {	9✔
127	const sizes = new Float64Array(newLength).fill(fillSize);	39✔
128	sizes.set(this._sizes.subarray(0, Math.min(this.length, newLength)));	39✔
129	return BIT.fromSizes(sizes);	39✔
130	}	39✔
131		9✔
132	/**	9✔
133	* Returns the 0-based index of the item that contains the given scroll `offset`,	9✔
134	* i.e. the largest i such that `prefixSum(i) <= offset < prefixSum(i + 1)`.	9✔
135	* O(log N) via binary lifting on the internal tree.	9✔
136	*/	9✔
137	public findIndexAtOffset(offset: number): number {	9✔
138	if (offset <= 0 \|\| this.length === 0) return 0;	239!
139		239✔
140	let idx = 0;	239✔
141	let remaining = offset;	239✔
142		239✔
143	for (let bit = 1 << (31 - Math.clz32(this.length)); bit > 0; bit >>= 1) {	239✔
144	const next = idx + bit;	1,204✔
145	if (next <= this.length && this._tree[next] <= remaining) {	1,204✔
146	idx = next;	513✔
147	remaining -= this._tree[idx];	513✔
148	}	513✔
149	}	1,204✔
150	return Math.min(this.length - 1, idx);	239✔
151	}	239✔
152	}	9✔
153		9✔
154	/**	9✔
155	* Describes the currently visible (and over-scanned) range of items.	9✔
156	*/	9✔
157	export interface VisibleRange {	9✔
158	/** Index of the first rendered item (inclusive) */	9✔
159	startIndex: number;	9✔
160	/** Index of the last rendered item (inclusive) */	9✔
161	endIndex: number;	9✔
162	}	9✔
163		9✔
164	/**	9✔
165	* Pure scroll-math engine for a single axis of virtual scrolling.	9✔
166	*	9✔
167	* All size state is held as plain arrays. Consumers can register an	9✔
168	* `onSizeChange` callback to react whenever item sizes or the item count	9✔
169	* changes (e.g. to trigger a Lit `requestUpdate()`).	9✔
170	*/	9✔
171	export class VirtualScrollEngine {	9✔
172	private _maxBrowserSize = Number.POSITIVE_INFINITY;	129✔
173		129✔
174	/**	129✔
175	* The ratio `totalSize / maxBrowserSize` when `totalSize` exceeds the	129✔
176	* maximum DOM coordinate the browser supports; `1` otherwise.	129✔
177	* Used to map virtual scroll positions to DOM scroll positions.	129✔
178	*/	129✔
179	private _virtualRatio = 1;	129✔
180		129✔
181	/** Binary Indexed Tree for O(log N) size queries and updates. */	129✔
182	private _tree: BIT \| null = null;	129✔
183		129✔
184	/**	129✔
185	* Called whenever item sizes or the item count change.	129✔
186	* Assign a callback (e.g. `() => this.requestUpdate()`) to react to size updates.	129✔
187	*/	129✔
188	public onSizeChange: (() => void) \| null = null;	129✔
189		9✔
190	/** Total virtual size of all items in px. */	9✔
191	public get totalSize(): number {	9✔
192	return this._tree?.totalSize ?? 0;	1,073!
193	}	1,073✔
194		9✔
195	/** Actual DOM space size (clamped to the maximum browser size) */	9✔
196	public get domSize(): number {	9✔
197	return this._virtualRatio !== 1 ? this._maxBrowserSize : this.totalSize;	850!
198	}	850✔
199		9✔
200	/**	9✔
201	* Initializes the maximum browser size by probing the document, and updates the virtual ratio accordingly.	9✔
202	*/	9✔
203	public initMaxBrowserSize(doc: Document): void {	9✔
204	this._maxBrowserSize = getMaxBrowserSizeProbePx(doc);	129✔
205	this._updateVirtualRatio();	129✔
206	}	129✔
207		9✔
208	/**	9✔
209	* Grows or shrinks the internal sizes array to `length`.	9✔
210	* New entries are filled with `estimatedSize`.	9✔
211	* Existing measured sizes are preserved.	9✔
212	*/	9✔
213	public resize(length: number, estimatedSize: number): void {	9✔
214	if (this._tree?.length === length) return;	176✔
215		168✔
216	this._tree = this._tree	168✔
217	? this._tree.cloneResized(length, estimatedSize)	39✔
218	: BIT.filled(length, estimatedSize);	129✔
219	this._updateVirtualRatio();	176✔
220	this.onSizeChange?.();	176✔
221	}	176✔
222		9✔
223	/**	9✔
224	* Records the measured DOM size for a single item.	9✔
225	*/	9✔
226	public measureItem(index: number, size: number): void {	9✔
227	if (!this._tree?.update(index, size)) return;	930✔
228		521✔
229	this._updateVirtualRatio();	521✔
230	this.onSizeChange?.();	521✔
231	}	930✔
232		9✔
233	/**	9✔
234	* Returns the DOM scroll offset in pixels that brings item at `index` into view	9✔
235	* at the leading edge of the viewport.	9✔
236	*/	9✔
237	public getScrollOffsetForIndex(index: number): number {	9✔
238	if (!this._tree \|\| index <= 0) return 0;	527✔
239		116✔
240	const clamped = Math.min(index, this._tree.length);	116✔
241	return this._tree.prefixSum(clamped) / this._virtualRatio;	116✔
242	}	527✔
243		9✔
244	/** Returns the item index at the given DOM scroll position. */	9✔
245	public getIndexAtScroll(scrollPosition: number): number {	9✔
246	if (!this._tree \|\| scrollPosition <= 0) return 0;	446✔
247	return this._tree.findIndexAtOffset(scrollPosition * this._virtualRatio);	239✔
248	}	446✔
249		9✔
250	/**	9✔
251	* Returns the visible + over-scanned item range for the given scroll state.	9✔
252	*/	9✔
253	public getVisibleRange(	9✔
254	scrollPosition: number,	425✔
255	viewportSize: number,	425✔
256	overScan: number,	425✔
257	totalItems: number	425✔
258	): VisibleRange {	425✔
259	if (totalItems === 0 \|\| viewportSize <= 0) {	425✔
260	return { startIndex: 0, endIndex: -1 };	202✔
261	}	202✔
262		223✔
263	const start = Math.max(0, this.getIndexAtScroll(scrollPosition) - overScan);	223✔
264	const endScrollPosition = scrollPosition + viewportSize;	223✔
265	const endRaw = this.getIndexAtScroll(endScrollPosition);	223✔
266	const end = Math.min(totalItems - 1, endRaw + overScan);	223✔
267		223✔
268	return { startIndex: start, endIndex: end };	223✔
269	}	425✔
270		9✔
271	/**	9✔
272	* Returns the CSS `translateY` / `translateX` value (px) to apply to the	9✔
273	* absolutely-positioned content wrapper.	9✔
274	*	9✔
275	* The content wrapper is `position: absolute; top: 0; left: 0` inside a	9✔
276	* track element that is `totalSize` px tall/wide. Translating it to	9✔
277	* `getContentPosition(startIndex)` places the first rendered item exactly	9✔
278	* at its virtual scroll position within the track.	9✔
279	*/	9✔
280	public getContentPosition(index: number): number {	9✔
281	return this.getScrollOffsetForIndex(index);	425✔
282	}	425✔
283		9✔
284	/**	9✔
285	* Returns the sum of actual sizes for items in [startIndex, endIndex].	9✔
286	* Used to clamp the content translate offset under coordinate compression	9✔
287	* so rendered items never overflow past `domSize`.	9✔
288	*/	9✔
289	public getPhysicalRangeSize(startIndex: number, endIndex: number): number {	9✔
290	if (!this._tree) return 0;	425!
291		425✔
292	const start = Math.max(0, startIndex);	425✔
293	const end = Math.min(Math.max(endIndex + 1, start), this._tree.length);	425✔
294	return this._tree.prefixSum(end) - this._tree.prefixSum(start);	425✔
295	}	425✔
296		9✔
297	private _updateVirtualRatio(): void {	9✔
298	const totalSize = this._tree?.totalSize ?? 0;	818✔
299	this._virtualRatio =	818✔
300	this._maxBrowserSize === Number.POSITIVE_INFINITY \|\|	818✔
301	totalSize <= this._maxBrowserSize	818✔
302	? 1	818!
NEW 303	: totalSize / this._maxBrowserSize;	×
304	}	818✔
305	}	9✔

IgniteUI / igniteui-webcomponents / 29898063965

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous