• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

IgniteUI / igniteui-webcomponents / 29910521557

22 Jul 2026 10:04AM UTC coverage: 98.312% (-0.02%) from 98.332%
29910521557

Pull #2222

github

web-flow
Merge 454550177 into 56f91ebc1
Pull Request #2222: feat: Added virtualization component

6106 of 6429 branches covered (94.98%)

Branch coverage included in aggregate %.

1006 of 1019 new or added lines in 7 files covered. (98.72%)

43174 of 43697 relevant lines covered (98.8%)

1545.97 hits per line

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

97.13
/src/components/virtualization/engine.ts
1
/**
9✔
2
 * Caches the result of `getMaxBrowserSizeProbePx` per `Document`. The
9✔
3
 * maximum scrollable coordinate a browser supports doesn't change between
9✔
4
 * calls, so repeated probes across multiple virtual-scroll instances in the
9✔
5
 * same document are wasted DOM work.
9✔
6
 */
9✔
7
const _maxBrowserSizeCache = new WeakMap<Document, number>();
9✔
8

9✔
9
/**
9✔
10
 * Probes the browser for the maximum scrollable coordinate it supports.
9✔
11
 */
9✔
12
function getMaxBrowserSizeProbePx(doc: Document): number {
129✔
13
  const cached = _maxBrowserSizeCache.get(doc);
129✔
14
  if (cached !== undefined) {
129✔
15
    return cached;
127✔
16
  }
127✔
17

2✔
18
  const container = doc.body ?? doc.documentElement;
129!
19
  if (!container) {
129!
NEW
20
    return Number.POSITIVE_INFINITY;
×
NEW
21
  }
✔
22

2✔
23
  const div = doc.createElement('div');
2✔
24
  div.style.position = 'absolute';
2✔
25
  div.style.top = `${Number.MAX_SAFE_INTEGER}px`;
2✔
26
  container.appendChild(div);
2✔
27
  const size = Math.abs(div.getBoundingClientRect().top);
2✔
28
  container.removeChild(div);
2✔
29

2✔
30
  _maxBrowserSizeCache.set(doc, size);
2✔
31
  return size;
2✔
32
}
2✔
33

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

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

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

9✔
52
  /** Running total maintained alongside tree updates in O(1). */
9✔
53
  private _total: number;
9✔
54

9✔
55
  /**
9✔
56
   * Highest power-of-two ≤ `length`, precomputed once for the binary
9✔
57
   * lifting in `findIndexAtOffset` instead of recomputing it via
9✔
58
   * `Math.clz32` on every call (this runs on every scroll event).
9✔
59
   */
9✔
60
  private readonly _topBit: number;
9✔
61

9✔
62
  private constructor(
9✔
63
    length: number,
168✔
64
    sizes: Float64Array,
168✔
65
    tree: Float64Array,
168✔
66
    total: number
168✔
67
  ) {
168✔
68
    this.length = length;
168✔
69
    this._sizes = sizes;
168✔
70
    this._tree = tree;
168✔
71
    this._total = total;
168✔
72
    this._topBit = length > 0 ? 1 << (31 - Math.clz32(length)) : 0;
168✔
73
  }
168✔
74

9✔
75
  /**
9✔
76
   * Creates a BIT of `length` items all initialized to `fillSize`. O(N).
9✔
77
   */
9✔
78
  public static filled(length: number, fillSize: number): BIT {
9✔
79
    return BIT.fromSizes(new Float64Array(length).fill(fillSize));
129✔
80
  }
129✔
81

9✔
82
  /**
9✔
83
   * Creates a BIT from an existing sizes array. O(N).
9✔
84
   */
9✔
85
  public static fromSizes(sizes: Float64Array): BIT {
9✔
86
    const length = sizes.length;
168✔
87
    const tree = new Float64Array(length + 1);
168✔
88
    let total = 0;
168✔
89

168✔
90
    for (let i = 1; i <= length; i++) {
168✔
91
      tree[i] += sizes[i - 1];
13,575✔
92
      total += sizes[i - 1];
13,575✔
93
      const j = i + (i & -i);
13,575✔
94
      if (j <= length) {
13,575✔
95
        tree[j] += tree[i];
13,334✔
96
      }
13,334✔
97
    }
13,575✔
98
    return new BIT(length, sizes, tree, total);
168✔
99
  }
168✔
100

9✔
101
  /** Total size of all items. O(1). */
9✔
102
  public get totalSize(): number {
9✔
103
    return this._total;
1,726✔
104
  }
1,726✔
105

9✔
106
  /**
9✔
107
   * Prefix sum of items [0, i) — the virtual scroll offset at the leading
9✔
108
   * edge of item i. O(log N).
9✔
109
   */
9✔
110
  public prefixSum(i: number): number {
9✔
111
    let sum = 0;
953✔
112
    for (let j = i; j > 0; j -= j & -j) {
953✔
113
      sum += this._tree[j];
604✔
114
    }
604✔
115
    return sum;
953✔
116
  }
953✔
117

9✔
118
  /**
9✔
119
   * Update the size of the item at 0-based index.
9✔
120
   * Returns true when the size actually changed. O(log N).
9✔
121
   */
9✔
122
  public update(index: number, newSize: number): boolean {
9✔
123
    if (index < 0 || index >= this.length) return false;
885!
124

885✔
125
    const old = this._sizes[index];
885✔
126
    if (old === newSize) return false;
885✔
127

497✔
128
    const delta = newSize - old;
497✔
129
    this._sizes[index] = newSize;
497✔
130
    this._total += delta;
497✔
131
    for (let i = index + 1; i <= this.length; i += i & -i) {
885✔
132
      this._tree[i] += delta;
1,422✔
133
    }
1,422✔
134
    return true;
497✔
135
  }
885✔
136

9✔
137
  /**
9✔
138
   * Returns a new BIT of `newLength` items.
9✔
139
   * Existing measured sizes are preserved up to `min(this.length, newLength)`;
9✔
140
   * new slots are filled with `fillSize`. Single O(N) build pass.
9✔
141
   */
9✔
142
  public cloneResized(newLength: number, fillSize: number): BIT {
9✔
143
    const sizes = new Float64Array(newLength).fill(fillSize);
39✔
144
    sizes.set(this._sizes.subarray(0, Math.min(this.length, newLength)));
39✔
145
    return BIT.fromSizes(sizes);
39✔
146
  }
39✔
147

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

232✔
156
    let idx = 0;
232✔
157
    let remaining = offset;
232✔
158

232✔
159
    for (let bit = this._topBit; bit > 0; bit >>= 1) {
232✔
160
      const next = idx + bit;
1,139✔
161
      if (next <= this.length && this._tree[next] <= remaining) {
1,139✔
162
        idx = next;
484✔
163
        remaining -= this._tree[idx];
484✔
164
      }
484✔
165
    }
1,139✔
166
    return Math.min(this.length - 1, idx);
232✔
167
  }
232✔
168
}
9✔
169

9✔
170
/**
9✔
171
 * Describes the currently visible (and over-scanned) range of items.
9✔
172
 */
9✔
173
export interface VisibleRange {
9✔
174
  /** Index of the first rendered item (inclusive) */
9✔
175
  startIndex: number;
9✔
176
  /** Index of the last rendered item (inclusive) */
9✔
177
  endIndex: number;
9✔
178
}
9✔
179

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

129✔
190
  /**
129✔
191
   * The ratio `totalSize / maxBrowserSize` when `totalSize` exceeds the
129✔
192
   * maximum DOM coordinate the browser supports; `1` otherwise.
129✔
193
   * Used to map virtual scroll positions to DOM scroll positions.
129✔
194
   */
129✔
195
  private _virtualRatio = 1;
129✔
196

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

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

9✔
206
  /** Total virtual size of all items in px. */
9✔
207
  public get totalSize(): number {
9✔
208
    return this._tree?.totalSize ?? 0;
1,061!
209
  }
1,061✔
210

9✔
211
  /** Actual DOM space size (clamped to the maximum browser size) */
9✔
212
  public get domSize(): number {
9✔
213
    return this._virtualRatio !== 1 ? this._maxBrowserSize : this.totalSize;
842!
214
  }
842✔
215

9✔
216
  /**
9✔
217
   * Initializes the maximum browser size by probing the document, and updates the virtual ratio accordingly.
9✔
218
   */
9✔
219
  public initMaxBrowserSize(doc: Document): void {
9✔
220
    this._maxBrowserSize = getMaxBrowserSizeProbePx(doc);
129✔
221
    this._updateVirtualRatio();
129✔
222
  }
129✔
223

9✔
224
  /**
9✔
225
   * Grows or shrinks the internal sizes array to `length`.
9✔
226
   * New entries are filled with `estimatedSize`.
9✔
227
   * Existing measured sizes are preserved.
9✔
228
   */
9✔
229
  public resize(length: number, estimatedSize: number): void {
9✔
230
    if (this._tree?.length === length) return;
176✔
231

168✔
232
    this._tree = this._tree
168✔
233
      ? this._tree.cloneResized(length, estimatedSize)
39✔
234
      : BIT.filled(length, estimatedSize);
129✔
235
    this._updateVirtualRatio();
176✔
236
    this.onSizeChange?.();
176✔
237
  }
176✔
238

9✔
239
  /**
9✔
240
   * Records the measured DOM size for a single item.
9✔
241
   */
9✔
242
  public measureItem(index: number, size: number): void {
9✔
243
    if (!this._tree?.update(index, size)) return;
885✔
244

497✔
245
    this._updateVirtualRatio();
497✔
246
    this.onSizeChange?.();
497✔
247
  }
885✔
248

9✔
249
  /**
9✔
250
   * Returns the DOM scroll offset in pixels that brings item at `index` into view
9✔
251
   * at the leading edge of the viewport.
9✔
252
   */
9✔
253
  public getScrollOffsetForIndex(index: number): number {
9✔
254
    if (!this._tree || index <= 0) return 0;
521✔
255

111✔
256
    const clamped = Math.min(index, this._tree.length);
111✔
257
    return this._tree.prefixSum(clamped) / this._virtualRatio;
111✔
258
  }
521✔
259

9✔
260
  /** Returns the item index at the given DOM scroll position. */
9✔
261
  public getIndexAtScroll(scrollPosition: number): number {
9✔
262
    if (!this._tree || scrollPosition <= 0) return 0;
438✔
263
    return this._tree.findIndexAtOffset(scrollPosition * this._virtualRatio);
232✔
264
  }
438✔
265

9✔
266
  /**
9✔
267
   * Returns the visible + over-scanned item range for the given scroll state.
9✔
268
   */
9✔
269
  public getVisibleRange(
9✔
270
    scrollPosition: number,
421✔
271
    viewportSize: number,
421✔
272
    overScan: number,
421✔
273
    totalItems: number
421✔
274
  ): VisibleRange {
421✔
275
    if (totalItems === 0 || viewportSize <= 0) {
421✔
276
      return { startIndex: 0, endIndex: -1 };
202✔
277
    }
202✔
278

219✔
279
    const start = Math.max(0, this.getIndexAtScroll(scrollPosition) - overScan);
219✔
280
    const endScrollPosition = scrollPosition + viewportSize;
219✔
281
    const endRaw = this.getIndexAtScroll(endScrollPosition);
219✔
282
    const end = Math.min(totalItems - 1, endRaw + overScan);
219✔
283

219✔
284
    return { startIndex: start, endIndex: end };
219✔
285
  }
421✔
286

9✔
287
  /**
9✔
288
   * Returns the CSS `translateY` / `translateX` value (px) to apply to the
9✔
289
   * absolutely-positioned content wrapper.
9✔
290
   *
9✔
291
   * The content wrapper is `position: absolute; top: 0; left: 0` inside a
9✔
292
   * track element that is `totalSize` px tall/wide. Translating it to
9✔
293
   * `getContentPosition(startIndex)` places the first rendered item exactly
9✔
294
   * at its virtual scroll position within the track.
9✔
295
   */
9✔
296
  public getContentPosition(index: number): number {
9✔
297
    return this.getScrollOffsetForIndex(index);
421✔
298
  }
421✔
299

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

421✔
308
    const start = Math.max(0, startIndex);
421✔
309
    const end = Math.min(Math.max(endIndex + 1, start), this._tree.length);
421✔
310
    return this._tree.prefixSum(end) - this._tree.prefixSum(start);
421✔
311
  }
421✔
312

9✔
313
  private _updateVirtualRatio(): void {
9✔
314
    const totalSize = this._tree?.totalSize ?? 0;
794✔
315
    this._virtualRatio =
794✔
316
      this._maxBrowserSize === Number.POSITIVE_INFINITY ||
794✔
317
      totalSize <= this._maxBrowserSize
794✔
318
        ? 1
794!
NEW
319
        : totalSize / this._maxBrowserSize;
×
320
  }
794✔
321
}
9✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc