28851216392

Committed 07 Jul 2026 08:05AM UTC coverage: 98.329% (-0.006%) from 98.335%

Build # 28851216392

Build Type

Pull #2222

github

Committed by

web-flow

Commit Message

Merge e23869691 into fcab913eb

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

Coverage Stats

6063 of 6378 branches covered (95.06%)

Branch coverage included in aggregate %.

854 of 864 new or added lines in 6 files covered. (98.84%)

8 existing lines in 1 file now uncovered.

42835 of 43351 relevant lines covered (98.81%)

1556.78 hits per line

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

98.06

/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 last item whose cumulative end offset
   * is ≤ `offset` (binary lifting on the internal tree). O(log N).
   */
  public findIndexAtOffset(offset: number): number {
    if (offset <= 0 || this.length === 0) return 0;

    let idx = 0;
    let newOffset = 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] <= newOffset) {
        idx = next;
        newOffset -= this._tree[idx];
      }
    }
    return Math.max(0, idx - 1);
  }
}

/**
 * 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 {	127✔
5	const div = doc.createElement('div');	127✔
6	div.style.position = 'absolute';	127✔
7	div.style.top = `${Number.MAX_SAFE_INTEGER}px`;	127✔
8	doc.body.appendChild(div);	127✔
9	const size = Math.abs(div.getBoundingClientRect().top);	127✔
10	doc.body.removeChild(div);	127✔
11	return size;	127✔
12	}	127✔
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,	166✔
37	sizes: Float64Array,	166✔
38	tree: Float64Array,	166✔
39	total: number	166✔
40	) {	166✔
41	this.length = length;	166✔
42	this._sizes = sizes;	166✔
43	this._tree = tree;	166✔
44	this._total = total;	166✔
45	}	166✔
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);	127✔
52	const tree = new Float64Array(length + 1);	127✔
53	const total = length * fillSize;	127✔
54		127✔
55	// O(N) build (vs O(N log N) for N individual insertions)	127✔
56	for (let i = 1; i <= length; i++) {	127✔
57	tree[i] += fillSize;	7,819✔
58	const j = i + (i & -i);	7,819✔
59	if (j <= length) {	7,819✔
60	tree[j] += tree[i];	7,637✔
61	}	7,637✔
62	}	7,819✔
63	return new BIT(length, sizes, tree, total);	127✔
64	}	127✔
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,682✔
88	}	1,682✔
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;	857✔
96	for (let j = i; j > 0; j -= j & -j) {	857✔
97	sum += this._tree[j];	298✔
98	}	298✔
99	return sum;	857✔
100	}	857✔
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;	815!
108		815✔
109	const old = this._sizes[index];	815✔
110	if (old === newSize) return false;	815✔
111		473✔
112	const delta = newSize - old;	473✔
113	this._sizes[index] = newSize;	473✔
114	this._total += delta;	473✔
115	for (let i = index + 1; i <= this.length; i += i & -i) {	815✔
116	this._tree[i] += delta;	1,230✔
117	}	1,230✔
118	return true;	473✔
119	}	815✔
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 last item whose cumulative end offset	9✔
134	* is ≤ `offset` (binary lifting on the internal tree). O(log N).	9✔
135	*/	9✔
136	public findIndexAtOffset(offset: number): number {	9✔
137	if (offset <= 0 \|\| this.length === 0) return 0;	217!
138		217✔
139	let idx = 0;	217✔
140	let newOffset = offset;	217✔
141		217✔
142	for (let bit = 1 << (31 - Math.clz32(this.length)); bit > 0; bit >>= 1) {	217✔
143	const next = idx + bit;	915✔
144	if (next <= this.length && this._tree[next] <= newOffset) {	915✔
145	idx = next;	317✔
146	newOffset -= this._tree[idx];	317✔
147	}	317✔
148	}	915✔
149	return Math.max(0, idx - 1);	217✔
150	}	217✔
151	}	9✔
152		9✔
153	/**	9✔
154	* Describes the currently visible (and over-scanned) range of items.	9✔
155	*/	9✔
156	export interface VisibleRange {	9✔
157	/** Index of the first rendered item (inclusive) */	9✔
158	startIndex: number;	9✔
159	/** Index of the last rendered item (inclusive) */	9✔
160	endIndex: number;	9✔
161	}	9✔
162		9✔
163	/**	9✔
164	* Pure scroll-math engine for a single axis of virtual scrolling.	9✔
165	*	9✔
166	* All size state is held as plain arrays. Consumers can register an	9✔
167	* `onSizeChange` callback to react whenever item sizes or the item count	9✔
168	* changes (e.g. to trigger a Lit `requestUpdate()`).	9✔
169	*/	9✔
170	export class VirtualScrollEngine {	9✔
171	private _maxBrowserSize = Number.POSITIVE_INFINITY;	127✔
172		127✔
173	/**	127✔
174	* The ratio `totalSize / maxBrowserSize` when `totalSize` exceeds the	127✔
175	* maximum DOM coordinate the browser supports; `1` otherwise.	127✔
176	* Used to map virtual scroll positions to DOM scroll positions.	127✔
177	*/	127✔
178	private _virtualRatio = 1;	127✔
179		127✔
180	/** Binary Indexed Tree for O(log N) size queries and updates. */	127✔
181	private _tree: BIT \| null = null;	127✔
182		127✔
183	/**	127✔
184	* Called whenever item sizes or the item count change.	127✔
185	* Assign a callback (e.g. `() => this.requestUpdate()`) to react to size updates.	127✔
186	*/	127✔
187	public onSizeChange: (() => void) \| null = null;	127✔
188		9✔
189	/** Total virtual size of all items in px. */	9✔
190	public get totalSize(): number {	9✔
191	return this._tree?.totalSize ?? 0;	1,043!
192	}	1,043✔
193		9✔
194	/** Actual DOM space size (clamped to the maximum browser size) */	9✔
195	public get domSize(): number {	9✔
196	return this._virtualRatio !== 1 ? this._maxBrowserSize : this.totalSize;	830!
197	}	830✔
198		9✔
199	/**	9✔
200	* Initializes the maximum browser size by probing the document, and updates the virtual ratio accordingly.	9✔
201	*/	9✔
202	public initMaxBrowserSize(doc: Document): void {	9✔
203	this._maxBrowserSize = getMaxBrowserSizeProbePx(doc);	127✔
204	this._updateVirtualRatio();	127✔
205	}	127✔
206		9✔
207	/**	9✔
208	* Grows or shrinks the internal sizes array to `length`.	9✔
209	* New entries are filled with `estimatedSize`.	9✔
210	* Existing measured sizes are preserved.	9✔
211	*/	9✔
212	public resize(length: number, estimatedSize: number): void {	9✔
213	if (this._tree?.length === length) return;	174✔
214		166✔
215	this._tree = this._tree	166✔
216	? this._tree.cloneResized(length, estimatedSize)	39✔
217	: BIT.filled(length, estimatedSize);	127✔
218	this._updateVirtualRatio();	174✔
219	this.onSizeChange?.();	174✔
220	}	174✔
221		9✔
222	/**	9✔
223	* Records the measured DOM size for a single item.	9✔
224	*/	9✔
225	public measureItem(index: number, size: number): void {	9✔
226	if (!this._tree?.update(index, size)) return;	815✔
227		473✔
228	this._updateVirtualRatio();	473✔
229	this.onSizeChange?.();	473✔
230	}	815✔
231		9✔
232	/**	9✔
233	* Returns the DOM scroll offset in pixels that brings item at `index` into view	9✔
234	* at the leading edge of the viewport.	9✔
235	*/	9✔
236	public getScrollOffsetForIndex(index: number): number {	9✔
237	if (!this._tree \|\| index <= 0) return 0;	438✔
238		27✔
239	const clamped = Math.min(index, this._tree.length);	27✔
240	return this._tree.prefixSum(clamped) / this._virtualRatio;	27✔
241	}	438✔
242		9✔
243	/** Returns the item index at the given DOM scroll position. */	9✔
244	public getIndexAtScroll(scrollPosition: number): number {	9✔
245	if (!this._tree \|\| scrollPosition <= 0) return 0;	426✔
246	return this._tree.findIndexAtOffset(scrollPosition * this._virtualRatio);	217✔
247	}	426✔
248		9✔
249	/**	9✔
250	* Returns the visible + over-scanned item range for the given scroll state.	9✔
251	*/	9✔
252	public getVisibleRange(	9✔
253	scrollPosition: number,	415✔
254	viewportSize: number,	415✔
255	overScan: number,	415✔
256	totalItems: number	415✔
257	): VisibleRange {	415✔
258	if (totalItems === 0 \|\| viewportSize <= 0) {	415✔
259	return { startIndex: 0, endIndex: -1 };	202✔
260	}	202✔
261		213✔
262	const start = Math.max(0, this.getIndexAtScroll(scrollPosition) - overScan);	213✔
263	const endScrollPosition = scrollPosition + viewportSize;	213✔
264	const endRaw = this.getIndexAtScroll(endScrollPosition);	213✔
265	const end = Math.min(totalItems - 1, endRaw + overScan);	213✔
266		213✔
267	return { startIndex: start, endIndex: end };	213✔
268	}	415✔
269		9✔
270	/**	9✔
271	* Returns the CSS `translateY` / `translateX` value (px) to apply to the	9✔
272	* absolutely-positioned content wrapper.	9✔
273	*	9✔
274	* The content wrapper is `position: absolute; top: 0; left: 0` inside a	9✔
275	* track element that is `totalSize` px tall/wide. Translating it to	9✔
276	* `getContentPosition(startIndex)` places the first rendered item exactly	9✔
277	* at its virtual scroll position within the track.	9✔
278	*/	9✔
279	public getContentPosition(index: number): number {	9✔
280	return this.getScrollOffsetForIndex(index);	415✔
281	}	415✔
282		9✔
283	/**	9✔
284	* Returns the sum of actual sizes for items in [startIndex, endIndex].	9✔
285	* Used to clamp the content translate offset under coordinate compression	9✔
286	* so rendered items never overflow past `domSize`.	9✔
287	*/	9✔
288	public getPhysicalRangeSize(startIndex: number, endIndex: number): number {	9✔
289	if (!this._tree) return 0;	415!
290		415✔
291	const start = Math.max(0, startIndex);	415✔
292	const end = Math.min(Math.max(endIndex + 1, start), this._tree.length);	415✔
293	return this._tree.prefixSum(end) - this._tree.prefixSum(start);	415✔
294	}	415✔
295		9✔
296	private _updateVirtualRatio(): void {	9✔
297	const totalSize = this._tree?.totalSize ?? 0;	766✔
298	this._virtualRatio =	766✔
299	this._maxBrowserSize === Number.POSITIVE_INFINITY \|\|	766✔
300	totalSize <= this._maxBrowserSize	766✔
301	? 1	766!
NEW 302	: totalSize / this._maxBrowserSize;	×
303	}	766✔
304	}	9✔

IgniteUI / igniteui-webcomponents / 28851216392

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