src/vs/editor/common/model/prefixSumComputer.ts
308 LOC · 294 covered · 14 uncovered · 85 ranges · 215 concepts · 34 introducers · 156 tests
File neighbourhood
The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.
Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file
In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.
Graph controls are ready.
Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.
1
>
/*---------------------------------------------------------------------------------------------
prefixSumComputer.ts ×20
2
>
* Copyright (c) Microsoft Corporation. All rights reserved.
3
>
* Licensed under the MIT License. See License.txt in the project root for license information.
4
>
*--------------------------------------------------------------------------------------------*/
5
>
6
>
import { arrayInsert } from '../../../base/common/arrays.js';
7
>
import { toUint32 } from '../../../base/common/uint.js';
8
>
9
>
export class PrefixSumComputer {
10
>
11
>
/**
12
>
* values[i] is the value at index i
13
>
*/
14
>
private values: Uint32Array;
15
>
16
>
/**
17
>
* prefixSum[i] = SUM(heights[j]), 0 <= j <= i
18
>
*/
19
>
private prefixSum: Uint32Array;
20
>
21
>
/**
22
>
* prefixSum[i], 0 <= i <= prefixSumValidIndex can be trusted
23
>
*/
24
>
private readonly prefixSumValidIndex: Int32Array;
25
>
26
>
constructor(values: Uint32Array) {
28
>
this.prefixSum = new Uint32Array(values.length);
29
>
this.prefixSumValidIndex = new Int32Array(1);
30
>
this.prefixSumValidIndex[0] = -1;
31
>
}
33
>
public getCount(): number {
34
return this.values.length;
35
}
37
>
public insertValues(insertIndex: number, insertValues: Uint32Array): boolean {
39
>
const oldValues = this.values;
40
>
const oldPrefixSum = this.prefixSum;
41
>
const insertValuesLen = insertValues.length;
42
>
43
>
if (insertValuesLen === 0) {
44
return false;
45
}
47
>
this.values = new Uint32Array(oldValues.length + insertValuesLen);
48
>
this.values.set(oldValues.subarray(0, insertIndex), 0);
49
>
this.values.set(oldValues.subarray(insertIndex), insertIndex + insertValuesLen);
50
>
this.values.set(insertValues, insertIndex);
51
>
52
>
if (insertIndex - 1 < this.prefixSumValidIndex[0]) {
53
this.prefixSumValidIndex[0] = insertIndex - 1;
54
}
56
>
this.prefixSum = new Uint32Array(this.values.length);
57
>
if (this.prefixSumValidIndex[0] >= 0) {
58
this.prefixSum.set(oldPrefixSum.subarray(0, this.prefixSumValidIndex[0] + 1));
59
}
61
>
}
63
>
public setValue(index: number, value: number): boolean {
65
>
value = toUint32(value);
66
>
67
>
if (this.values[index] === value) {
69
>
}
71
>
if (index - 1 < this.prefixSumValidIndex[0]) {
73
>
}
77
>
public removeValues(startIndex: number, count: number): boolean {
79
>
count = toUint32(count);
80
>
81
>
const oldValues = this.values;
82
>
const oldPrefixSum = this.prefixSum;
83
>
84
>
if (startIndex >= oldValues.length) {
85
return false;
86
}
88
>
const maxCount = oldValues.length - startIndex;
89
>
if (count >= maxCount) {
91
>
}
93
>
if (count === 0) {
94
return false;
95
}
97
>
this.values = new Uint32Array(oldValues.length - count);
98
>
this.values.set(oldValues.subarray(0, startIndex), 0);
99
>
this.values.set(oldValues.subarray(startIndex + count), startIndex);
100
>
101
>
this.prefixSum = new Uint32Array(this.values.length);
102
>
if (startIndex - 1 < this.prefixSumValidIndex[0]) {
104
>
}
106
>
this.prefixSum.set(oldPrefixSum.subarray(0, this.prefixSumValidIndex[0] + 1));
prefixSumComputer.ts ×2
107
>
}
109
>
}
111
>
public getTotalSum(): number {
114
>
}
118
>
/**
119
>
* Returns the sum of the first `index + 1` many items.
120
>
* @returns `SUM(0 <= j <= index, values[j])`.
121
>
*/
122
>
public getPrefixSum(index: number): number {
125
>
}
127
>
index = toUint32(index);
128
>
return this._getPrefixSum(index);
131
>
private _getPrefixSum(index: number): number {
134
>
}
136
>
let startIndex = this.prefixSumValidIndex[0] + 1;
137
>
if (startIndex === 0) {
138
>
this.prefixSum[0] = this.values[0];
139
>
startIndex++;
140
>
}
141
>
142
>
if (index >= this.values.length) {
143
index = this.values.length - 1;
144
}
146
>
for (let i = startIndex; i <= index; i++) {
148
>
}
149
>
this.prefixSumValidIndex[0] = Math.max(this.prefixSumValidIndex[0], index);
prefixSumComputer.ts ×4
150
>
return this.prefixSum[index];
151
>
}
153
>
public getIndexOf(sum: number): PrefixSumIndexOfResult {
155
>
156
>
// Compute all sums (to get a fully valid prefixSum)
157
>
this.getTotalSum();
158
>
159
>
let low = 0;
160
>
let high = this.values.length - 1;
161
>
let mid = 0;
162
>
let midStop = 0;
163
>
let midStart = 0;
164
>
165
>
while (low <= high) {
166
>
mid = low + ((high - low) / 2) | 0;
167
>
168
>
midStop = this.prefixSum[mid];
169
>
midStart = midStop - this.values[mid];
170
>
171
>
if (sum < midStart) {
177
>
}
179
>
180
>
return new PrefixSumIndexOfResult(mid, sum - midStart);
181
>
}
183
>
184
>
/**
185
>
* {@link getIndexOf} has an amortized runtime complexity of O(1).
186
>
*
187
>
* ({@link PrefixSumComputer.getIndexOf} is just O(log n))
188
>
*/
189
>
export class ConstantTimePrefixSumComputer {
190
>
private _values: number[];
191
>
private _isValid: boolean;
192
>
private _validEndIndex: number;
193
>
194
>
/**
195
>
* _prefixSum[i] = SUM(values[j]), 0 <= j <= i
196
>
*/
197
>
private _prefixSum: number[];
198
>
199
>
/**
200
>
* _indexBySum[sum] = idx => _prefixSum[idx - 1] <= sum < _prefixSum[idx]
201
>
*/
202
>
private _indexBySum: number[];
203
>
204
>
constructor(values: number[]) {
206
>
this._isValid = false;
207
>
this._validEndIndex = -1;
208
>
this._prefixSum = [];
209
>
this._indexBySum = [];
210
>
}
212
>
/**
213
>
* @returns SUM(0 <= j < values.length, values[j])
214
>
*/
215
>
public getTotalSum(): number {
217
>
return this._indexBySum.length;
218
>
}
220
>
/**
221
>
* Returns the sum of the first `count` many items.
222
>
* @returns `SUM(0 <= j < count, values[j])`.
223
>
*/
224
>
public getPrefixSum(count: number): number {
226
>
if (count === 0) {
228
>
}
232
>
/**
233
>
* @returns `result`, such that `getPrefixSum(result.index) + result.remainder = sum`
234
>
*/
235
>
public getIndexOf(sum: number): PrefixSumIndexOfResult {
237
>
const idx = this._indexBySum[sum];
238
>
if (idx === undefined) {
239
>
// sum does not have a direct entry in _indexBySum (e.g. sum >= getTotalSum() or the array is empty / all values are zero)
prefixSumComputer.ts ×1
240
>
const lastIdx = Math.max(0, this._values.length - 1);
241
>
const lastPrefixSum = lastIdx > 0 ? this._prefixSum[lastIdx - 1] : 0;
242
>
return new PrefixSumIndexOfResult(lastIdx, sum - lastPrefixSum);
243
>
}
245
>
return new PrefixSumIndexOfResult(idx, sum - viewLinesAbove);
246
>
}
248
>
public removeValues(start: number, deleteCount: number): void {
250
>
this._invalidate(start);
251
>
}
253
>
public insertValues(insertIndex: number, insertArr: number[]): void {
255
>
this._invalidate(insertIndex);
256
>
}
258
>
private _invalidate(index: number): void {
260
>
this._validEndIndex = Math.min(this._validEndIndex, index - 1);
261
>
}
263
>
private _ensureValid(): void {
266
>
}
268
>
for (let i = this._validEndIndex + 1, len = this._values.length; i < len; i++) {
270
>
const sumAbove = i > 0 ? this._prefixSum[i - 1] : 0;
271
>
272
>
this._prefixSum[i] = sumAbove + value;
273
>
for (let j = 0; j < value; j++) {
275
>
}
278
>
// trim things
279
>
this._prefixSum.length = this._values.length;
280
>
this._indexBySum.length = this._values.length > 0 ? this._prefixSum[this._values.length - 1] : 0;
281
>
282
>
// mark as valid
283
>
this._isValid = true;
284
>
this._validEndIndex = this._values.length - 1;
285
>
}
287
>
public setValue(index: number, value: number): void {
290
>
return;
291
>
}
293
>
this._invalidate(index);
296
>
297
>
298
>
export class PrefixSumIndexOfResult {
299
>
_prefixSumIndexOfResultBrand: void = undefined;
300
>
301
>
constructor(
303
>
public readonly remainder: number
304
>
) {
305
>
this.index = index;
306
>
this.remainder = remainder;
307
>
}