src/vs/base/common/arrays.ts
949 LOC · 777 covered · 172 uncovered · 171 ranges · 20961 concepts · 64 introducers · 12741 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
>
/*---------------------------------------------------------------------------------------------
map.ts ×97
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 { findFirstIdxMonotonousOrArrLen } from './arraysFind.js';
7
>
import { CancellationToken } from './cancellation.js';
8
>
import { CancellationError } from './errors.js';
9
>
import { ISplice } from './sequence.js';
10
>
11
>
/**
12
>
* Returns the last entry and the initial N-1 entries of the array, as a tuple of [rest, last].
13
>
*
14
>
* The array must have at least one element.
15
>
*
16
>
* @param arr The input array
17
>
* @returns A tuple of [rest, last] where rest is all but the last element and last is the last element
18
>
* @throws Error if the array is empty
19
>
*/
20
>
export function tail<T>(arr: T[]): [T[], T] {
22
throw new Error('Invalid tail call');
23
}
25
>
return [arr.slice(0, arr.length - 1), arr[arr.length - 1]];
26
>
}
28
>
export function equals<T>(one: ReadonlyArray<T> | undefined, other: ReadonlyArray<T> | undefined, itemEquals: (a: T, b: T) => boolean = (a, b) => a === b): boolean {
31
>
}
35
>
}
37
>
if (one.length !== other.length) {
39
>
}
41
>
for (let i = 0, len = one.length; i < len; i++) {
44
>
}
47
>
return true;
48
>
}
50
>
/**
51
>
* Remove the element at `index` by replacing it with the last element. This is faster than `splice`
52
>
* but changes the order of the array
53
>
*/
54
>
export function removeFastWithoutKeepingOrder<T>(array: T[], index: number) {
56
>
if (index < last) {
57
>
array[index] = array[last];
58
>
}
59
>
array.pop();
60
>
}
62
>
/**
63
>
* Performs a binary search algorithm over a sorted array.
64
>
*
65
>
* @param array The array being searched.
66
>
* @param key The value we search for.
67
>
* @param comparator A function that takes two array elements and returns zero
68
>
* if they are equal, a negative number if the first element precedes the
69
>
* second one in the sorting order, or a positive number if the second element
70
>
* precedes the first one.
71
>
* @return See {@link binarySearch2}
72
>
*/
73
>
export function binarySearch<T>(array: ReadonlyArray<T>, key: T, comparator: (op1: T, op2: T) => number): number {
75
>
}
77
>
/**
78
>
* Performs a binary search algorithm over a sorted collection. Useful for cases
79
>
* when we need to perform a binary search over something that isn't actually an
80
>
* array, and converting data to an array would defeat the use of binary search
81
>
* in the first place.
82
>
*
83
>
* @param length The collection length.
84
>
* @param compareToKey A function that takes an index of an element in the
85
>
* collection and returns zero if the value at this index is equal to the
86
>
* search key, a negative number if the value precedes the search key in the
87
>
* sorting order, or a positive number if the search key precedes the value.
88
>
* @return A non-negative index of an element, if found. If not found, the
89
>
* result is -(n+1) (or ~n, using bitwise notation), where n is the index
90
>
* where the key should be inserted to maintain the sorting order.
91
>
*/
92
>
export function binarySearch2(length: number, compareToKey: (index: number) => number): number {
94
>
high = length - 1;
95
>
96
>
while (low <= high) {
98
>
const comp = compareToKey(mid);
99
>
if (comp < 0) {
105
>
}
108
>
}
110
>
type Compare<T> = (a: T, b: T) => number;
111
>
112
>
/**
113
>
* Finds the nth smallest element in the array using quickselect algorithm.
114
>
* The data does not need to be sorted.
115
>
*
116
>
* @param nth The zero-based index of the element to find (0 = smallest, 1 = second smallest, etc.)
117
>
* @param data The unsorted array
118
>
* @param compare A comparator function that defines the sort order
119
>
* @returns The nth smallest element
120
>
* @throws TypeError if nth is >= data.length
121
>
*/
122
>
export function quickSelect<T>(nth: number, data: T[], compare: Compare<T>): T {
124
>
nth = nth | 0;
125
>
126
>
if (nth >= data.length) {
127
throw new TypeError('invalid index');
128
}
130
>
const pivotValue = data[Math.floor(data.length * Math.random())];
131
>
const lower: T[] = [];
132
>
const higher: T[] = [];
133
>
const pivots: T[] = [];
134
>
135
>
for (const value of data) {
136
>
const val = compare(value, pivotValue);
137
>
if (val < 0) {
138
>
lower.push(value);
139
>
} else if (val > 0) {
140
>
higher.push(value);
141
>
} else {
142
>
pivots.push(value);
143
>
}
144
>
}
145
>
146
>
if (nth < lower.length) {
147
>
return quickSelect(nth, lower, compare);
148
>
} else if (nth < lower.length + pivots.length) {
149
>
return pivots[0];
150
>
} else {
151
>
return quickSelect(nth - (lower.length + pivots.length), higher, compare);
152
>
}
153
>
}
155
>
export function groupBy<T>(data: ReadonlyArray<T>, compare: (a: T, b: T) => number): T[][] {
156
const result: T[][] = [];
157
let currentGroup: T[] | undefined = undefined;
158
for (const element of data.slice(0).sort(compare)) {
159
if (!currentGroup || compare(currentGroup[0], element) !== 0) {
160
currentGroup = [element];
161
result.push(currentGroup);
162
} else {
163
currentGroup.push(element);
164
}
165
}
166
return result;
167
}
169
>
/**
170
>
* Splits the given items into a list of (non-empty) groups.
171
>
* `shouldBeGrouped` is used to decide if two consecutive items should be in the same group.
172
>
* The order of the items is preserved.
173
>
*/
174
>
export function* groupAdjacentBy<T>(items: Iterable<T>, shouldBeGrouped: (item1: T, item2: T) => boolean): Iterable<T[]> {
176
>
let last: T | undefined;
177
>
for (const item of items) {
178
>
if (last !== undefined && shouldBeGrouped(last, item)) {
heuristicSequenceOptimizations.ts ×26
181
>
if (currentGroup) {
183
>
}
185
>
}
186
>
last = item;
187
>
}
190
>
}
193
>
export function forEachAdjacent<T>(arr: T[], f: (item1: T | undefined, item2: T | undefined) => void): void {
195
>
f(i === 0 ? undefined : arr[i - 1], i === arr.length ? undefined : arr[i]);
196
>
}
197
>
}
199
>
export function forEachWithNeighbors<T>(arr: T[], f: (before: T | undefined, element: T, after: T | undefined) => void): void {
201
>
f(i === 0 ? undefined : arr[i - 1], arr[i], i + 1 === arr.length ? undefined : arr[i + 1]);
202
>
}
203
>
}
205
>
export function concatArrays<T extends any[]>(...arrays: T): T[number][number][] {
206
return [].concat(...arrays);
207
}
209
>
interface IMutableSplice<T> extends ISplice<T> {
210
>
readonly toInsert: T[];
211
>
deleteCount: number;
212
>
}
213
>
214
>
/**
215
>
* Diffs two *sorted* arrays and computes the splices which apply the diff.
216
>
*/
217
>
export function sortedDiff<T>(before: ReadonlyArray<T>, after: ReadonlyArray<T>, compare: (a: T, b: T) => number): ISplice<T>[] {
219
>
220
>
function pushSplice(start: number, deleteCount: number, toInsert: T[]): void {
221
>
if (deleteCount === 0 && toInsert.length === 0) {
222
>
return;
223
>
}
224
>
225
>
const latest = result[result.length - 1];
226
>
227
>
if (latest && latest.start + latest.deleteCount === start) {
228
>
latest.deleteCount += deleteCount;
229
>
latest.toInsert.push(...toInsert);
230
>
} else {
231
>
result.push({ start, deleteCount, toInsert });
232
>
}
233
>
}
234
>
235
>
let beforeIdx = 0;
236
>
let afterIdx = 0;
237
>
238
>
while (true) {
239
>
if (beforeIdx === before.length) {
240
>
pushSplice(beforeIdx, 0, after.slice(afterIdx));
241
>
break;
242
>
}
243
>
if (afterIdx === after.length) {
244
>
pushSplice(beforeIdx, before.length - beforeIdx, []);
245
>
break;
246
>
}
247
>
248
>
const beforeElement = before[beforeIdx];
249
>
const afterElement = after[afterIdx];
250
>
const n = compare(beforeElement, afterElement);
251
>
if (n === 0) {
252
>
// equal
253
>
beforeIdx += 1;
254
>
afterIdx += 1;
255
>
} else if (n < 0) {
256
>
// beforeElement is smaller -> before element removed
257
>
pushSplice(beforeIdx, 1, []);
258
>
beforeIdx += 1;
259
>
} else if (n > 0) {
260
>
// beforeElement is greater -> after element added
261
>
pushSplice(beforeIdx, 0, [afterElement]);
262
>
afterIdx += 1;
263
>
}
264
>
}
265
>
266
>
return result;
267
>
}
269
>
/**
270
>
* Takes two *sorted* arrays and computes their delta (removed, added elements).
271
>
* Finishes in `Math.min(before.length, after.length)` steps.
272
>
*/
273
>
export function delta<T>(before: ReadonlyArray<T>, after: ReadonlyArray<T>, compare: (a: T, b: T) => number): { removed: T[]; added: T[] } {
275
>
const removed: T[] = [];
276
>
const added: T[] = [];
277
>
278
>
for (const splice of splices) {
279
>
removed.push(...before.slice(splice.start, splice.start + splice.deleteCount));
280
>
added.push(...splice.toInsert);
281
>
}
282
>
283
>
return { removed, added };
284
>
}
286
>
/**
287
>
* Returns the top N elements from the array.
288
>
*
289
>
* Faster than sorting the entire array when the array is a lot larger than N.
290
>
*
291
>
* @param array The unsorted array.
292
>
* @param compare A sort function for the elements.
293
>
* @param n The number of elements to return.
294
>
* @return The first n elements from array when sorted with compare.
295
>
*/
296
>
export function top<T>(array: ReadonlyArray<T>, compare: (a: T, b: T) => number, n: number): T[] {
298
>
return [];
299
>
}
300
>
const result = array.slice(0, n).sort(compare);
301
>
topStep(array, compare, result, n, array.length);
302
>
return result;
303
>
}
305
>
/**
306
>
* Asynchronous variant of `top()` allowing for splitting up work in batches between which the event loop can run.
307
>
*
308
>
* Returns the top N elements from the array.
309
>
*
310
>
* Faster than sorting the entire array when the array is a lot larger than N.
311
>
*
312
>
* @param array The unsorted array.
313
>
* @param compare A sort function for the elements.
314
>
* @param n The number of elements to return.
315
>
* @param batch The number of elements to examine before yielding to the event loop.
316
>
* @return The first n elements from array when sorted with compare.
317
>
*/
318
>
export function topAsync<T>(array: T[], compare: (a: T, b: T) => number, n: number, batch: number, token?: CancellationToken): Promise<T[]> {
320
>
return Promise.resolve([]);
321
>
}
322
>
323
>
return new Promise((resolve, reject) => {
324
>
(async () => {
325
>
const o = array.length;
326
>
const result = array.slice(0, n).sort(compare);
327
>
for (let i = n, m = Math.min(n + batch, o); i < o; i = m, m = Math.min(m + batch, o)) {
328
>
if (i > n) {
329
>
await new Promise(resolve => setTimeout(resolve)); // any other delay function would starve I/O
330
>
}
331
>
if (token && token.isCancellationRequested) {
332
throw new CancellationError();
333
}
335
>
}
336
>
return result;
337
>
})()
338
>
.then(resolve, reject);
339
>
});
340
>
}
342
>
function topStep<T>(array: ReadonlyArray<T>, compare: (a: T, b: T) => number, result: T[], i: number, m: number): void {
arrays.ts ×1
343
>
for (const n = result.length; i < m; i++) {
344
>
const element = array[i];
345
>
if (compare(element, result[n - 1]) < 0) {
346
>
result.pop();
347
>
const j = findFirstIdxMonotonousOrArrLen(result, e => compare(element, e) < 0);
348
>
result.splice(j, 0, element);
349
>
}
350
>
}
351
>
}
353
>
/**
354
>
* @returns New array with all falsy values removed. The original array IS NOT modified.
355
>
*/
356
>
export function coalesce<T>(array: ReadonlyArray<T | undefined | null>): T[] {
358
>
}
360
>
/**
361
>
* Remove all falsy values from `array`. The original array IS modified.
362
>
*/
363
>
export function coalesceInPlace<T>(array: Array<T | undefined | null>): asserts array is Array<T> {
365
>
for (let i = 0; i < array.length; i++) {
366
>
if (!!array[i]) {
367
>
array[to] = array[i];
368
>
to += 1;
369
>
}
370
>
}
371
>
array.length = to;
372
>
}
374
>
/**
375
>
* @deprecated Use `Array.copyWithin` instead
376
>
*/
377
>
export function move(array: unknown[], from: number, to: number): void {
378
array.splice(to, 0, array.splice(from, 1)[0]);
379
}
381
>
/**
382
>
* @returns false if the provided object is an array and not empty.
383
>
*/
384
>
export function isFalsyOrEmpty(obj: unknown): boolean {
386
>
}
388
>
/**
389
>
* @returns True if the provided object is an array and has at least one element.
390
>
*/
391
>
export function isNonEmptyArray<T>(obj: T[] | undefined | null): obj is T[];
392
>
export function isNonEmptyArray<T>(obj: readonly T[] | undefined | null): obj is readonly T[];
393
>
export function isNonEmptyArray<T>(obj: T[] | readonly T[] | undefined | null): obj is T[] | readonly T[] {
395
>
}
397
>
/**
398
>
* Removes duplicates from the given array. The optional keyFn allows to specify
399
>
* how elements are checked for equality by returning an alternate value for each.
400
>
*/
401
>
export function distinct<T>(array: ReadonlyArray<T>, keyFn: (value: T) => unknown = value => value): T[] {
403
>
404
>
return array.filter(element => {
406
>
if (seen.has(key)) {
408
>
}
410
>
return true;
412
>
}
414
>
export function uniqueFilter<T, R>(keyFn: (t: T) => R): (t: T) => boolean {
415
const seen = new Set<R>();
416
417
return element => {
418
const key = keyFn(element);
419
420
if (seen.has(key)) {
421
return false;
422
}
423
424
seen.add(key);
425
return true;
426
};
427
}
429
>
export function commonPrefixLength<T>(one: ReadonlyArray<T>, other: ReadonlyArray<T>, equals: (a: T, b: T) => boolean = (a, b) => a === b): number {
430
let result = 0;
431
432
for (let i = 0, len = Math.min(one.length, other.length); i < len && equals(one[i], other[i]); i++) {
433
result++;
434
}
435
436
return result;
437
}
439
>
export function range(to: number): number[];
440
>
export function range(from: number, to: number): number[];
441
>
export function range(arg: number, to?: number): number[] {
443
>
444
>
if (typeof to === 'number') {
445
from = arg;
447
>
from = 0;
448
>
to = arg;
449
>
}
450
>
451
>
const result: number[] = [];
452
>
453
>
if (from <= to) {
454
>
for (let i = from; i < to; i++) {
455
>
result.push(i);
456
>
}
457
>
} else {
458
for (let i = from; i > to; i--) {
459
result.push(i);
460
}
461
}
463
>
return result;
464
>
}
466
>
export function index<T>(array: ReadonlyArray<T>, indexer: (t: T) => string): { [key: string]: T };
467
>
export function index<T, R>(array: ReadonlyArray<T>, indexer: (t: T) => string, mapper: (t: T) => R): { [key: string]: R };
468
>
export function index<T, R>(array: ReadonlyArray<T>, indexer: (t: T) => string, mapper?: (t: T) => R): { [key: string]: R } {
469
return array.reduce((r, t) => {
470
r[indexer(t)] = mapper ? mapper(t) : t;
471
return r;
472
}, Object.create(null));
473
}
475
>
/**
476
>
* Inserts an element into an array. Returns a function which, when
477
>
* called, will remove that element from the array.
478
>
*
479
>
* @deprecated In almost all cases, use a `Set<T>` instead.
480
>
*/
481
>
export function insert<T>(array: T[], element: T): () => void {
483
>
484
>
return () => remove(array, element);
485
>
}
487
>
/**
488
>
* Removes an element from an array if it can be found.
489
>
*
490
>
* @deprecated In almost all cases, use a `Set<T>` instead.
491
>
*/
492
>
export function remove<T>(array: T[], element: T): T | undefined {
494
>
if (index > -1) {
495
>
array.splice(index, 1);
496
>
497
>
return element;
498
>
}
499
500
return undefined;
501
}
503
>
/**
504
>
* Insert `insertArr` inside `target` at `insertIndex`.
505
>
* Please don't touch unless you understand https://jsperf.com/inserting-an-array-within-an-array
506
>
*/
507
>
export function arrayInsert<T>(target: T[], insertIndex: number, insertArr: T[]): T[] {
509
>
const after = target.slice(insertIndex);
510
>
return before.concat(insertArr, after);
511
>
}
513
>
/**
514
>
* Uses Fisher-Yates shuffle to shuffle the given array
515
>
*/
516
>
export function shuffle<T>(array: T[], _seed?: number): void {
518
>
519
>
if (typeof _seed === 'number') {
520
let seed = _seed;
521
// Seeded random number generator in JS. Modified from:
522
// https://stackoverflow.com/questions/521295/seeding-the-random-number-generator-in-javascript
523
rand = () => {
524
const x = Math.sin(seed++) * 179426549; // throw away most significant digits and reduce any potential bias
525
return x - Math.floor(x);
526
};
528
>
rand = Math.random;
529
>
}
530
>
531
>
for (let i = array.length - 1; i > 0; i -= 1) {
533
>
const temp = array[i];
534
>
array[i] = array[j];
535
>
array[j] = temp;
536
>
}
539
>
/**
540
>
* Pushes an element to the start of the array, if found.
541
>
*/
542
>
export function pushToStart<T>(arr: T[], value: T): void {
543
const index = arr.indexOf(value);
544
545
if (index > -1) {
546
arr.splice(index, 1);
547
arr.unshift(value);
548
}
549
}
551
>
/**
552
>
* Pushes an element to the end of the array, if found.
553
>
*/
554
>
export function pushToEnd<T>(arr: T[], value: T): void {
555
const index = arr.indexOf(value);
556
557
if (index > -1) {
558
arr.splice(index, 1);
559
arr.push(value);
560
}
561
}
563
>
export function pushMany<T>(arr: T[], items: ReadonlyArray<T>): void {
566
>
}
569
>
export function mapArrayOrNot<T, U>(items: T | T[], fn: (_: T) => U): U | U[] {
575
>
export function mapFilter<T, U>(array: ReadonlyArray<T>, fn: (t: T) => U | undefined): U[] {
576
const result: U[] = [];
577
for (const item of array) {
578
const mapped = fn(item);
579
if (mapped !== undefined) {
580
result.push(mapped);
581
}
582
}
583
return result;
584
}
586
>
export function withoutDuplicates<T>(array: ReadonlyArray<T>): T[] {
587
const s = new Set(array);
588
return Array.from(s);
589
}
591
>
export function asArray<T>(x: T | T[]): T[];
592
>
export function asArray<T>(x: T | readonly T[]): readonly T[];
593
>
export function asArray<T>(x: T | T[]): T[] {
595
>
}
597
>
export function getRandomElement<T>(arr: T[]): T | undefined {
598
return arr[Math.floor(Math.random() * arr.length)];
599
}
601
>
/**
602
>
* Insert the new items in the array.
603
>
* @param array The original array.
604
>
* @param start The zero-based location in the array from which to start inserting elements.
605
>
* @param newItems The items to be inserted
606
>
*/
607
>
export function insertInto<T>(array: T[], start: number, newItems: T[]): void {
609
>
const originalLength = array.length;
610
>
const newItemsLength = newItems.length;
611
>
array.length = originalLength + newItemsLength;
612
>
// Move the items after the start index, start from the end so that we don't overwrite any value.
613
>
for (let i = originalLength - 1; i >= startIdx; i--) {
614
>
array[i + newItemsLength] = array[i];
615
>
}
616
>
617
>
for (let i = 0; i < newItemsLength; i++) {
618
>
array[i + startIdx] = newItems[i];
619
>
}
620
>
}
622
>
/**
623
>
* Removes elements from an array and inserts new elements in their place, returning the deleted elements. Alternative to the native Array.splice method, it
624
>
* can only support limited number of items due to the maximum call stack size limit.
625
>
* @param array The original array.
626
>
* @param start The zero-based location in the array from which to start removing elements.
627
>
* @param deleteCount The number of elements to remove.
628
>
* @returns An array containing the elements that were deleted.
629
>
*/
630
>
export function splice<T>(array: T[], start: number, deleteCount: number, newItems: T[]): T[] {
632
>
let result = array.splice(index, deleteCount);
633
>
if (result === undefined) {
634
// see https://bugs.webkit.org/show_bug.cgi?id=261140
635
result = [];
636
}
638
>
return result;
639
>
}
641
>
/**
642
>
* Determine the actual start index (same logic as the native splice() or slice())
643
>
* If greater than the length of the array, start will be set to the length of the array. In this case, no element will be deleted but the method will behave as an adding function, adding as many element as item[n*] provided.
644
>
* If negative, it will begin that many elements from the end of the array. (In this case, the origin -1, meaning -n is the index of the nth last element, and is therefore equivalent to the index of array.length - n.) If array.length + start is less than 0, it will begin from index 0.
645
>
* @param array The target array.
646
>
* @param start The operation index.
647
>
*/
649
>
return start < 0 ? Math.max(start + array.length, 0) : Math.min(start, array.length);
650
>
}
652
>
653
>
654
>
/**
655
>
* When comparing two values,
656
>
* a negative number indicates that the first value is less than the second,
657
>
* a positive number indicates that the first value is greater than the second,
658
>
* and zero indicates that neither is the case.
659
>
*/
660
>
export type CompareResult = number;
661
>
662
>
export namespace CompareResult {
663
>
export function isLessThan(result: CompareResult): boolean {
664
return result < 0;
665
}
667
>
export function isLessThanOrEqual(result: CompareResult): boolean {
668
return result <= 0;
669
}
671
>
export function isGreaterThan(result: CompareResult): boolean {
673
>
}
675
>
export function isNeitherLessOrGreaterThan(result: CompareResult): boolean {
677
>
}
679
>
export const greaterThan = 1;
680
>
export const lessThan = -1;
681
>
export const neitherLessOrGreaterThan = 0;
682
>
}
683
>
684
>
/**
685
>
* A comparator `c` defines a total order `<=` on `T` as following:
686
>
* `c(a, b) <= 0` iff `a` <= `b`.
687
>
* We also have `c(a, b) == 0` iff `c(b, a) == 0`.
688
>
*/
689
>
export type Comparator<T> = (a: T, b: T) => CompareResult;
690
>
691
>
export function compareBy<TItem, TCompareBy>(selector: (item: TItem) => TCompareBy, comparator: Comparator<TCompareBy>): Comparator<TItem> {
693
>
}
695
>
export function tieBreakComparators<TItem>(...comparators: Comparator<TItem>[]): Comparator<TItem> {
698
>
const result = comparator(item1, item2);
699
>
if (!CompareResult.isNeitherLessOrGreaterThan(result)) {
700
>
return result;
701
>
}
702
>
}
703
return CompareResult.neitherLessOrGreaterThan;
707
>
/**
708
>
* The natural order on numbers.
709
>
*/
710
>
export const numberComparator: Comparator<number> = (a, b) => a - b;
711
>
712
>
export const booleanComparator: Comparator<boolean> = (a, b) => numberComparator(a ? 1 : 0, b ? 1 : 0);
713
>
714
>
export function reverseOrder<TItem>(comparator: Comparator<TItem>): Comparator<TItem> {
716
>
}
718
>
/**
719
>
* Returns a new comparator that treats `undefined` as the smallest value.
720
>
* All other values are compared using the given comparator.
721
>
*/
722
>
export function compareUndefinedSmallest<T>(comparator: Comparator<T>): Comparator<T | undefined> {
723
return (a, b) => {
724
if (a === undefined) {
725
return b === undefined ? CompareResult.neitherLessOrGreaterThan : CompareResult.lessThan;
726
} else if (b === undefined) {
727
return CompareResult.greaterThan;
728
}
729
730
return comparator(a, b);
731
};
732
}
734
>
export class ArrayQueue<T> {
735
>
private readonly items: readonly T[];
736
>
private firstIdx = 0;
737
>
private lastIdx: number;
738
>
739
>
/**
740
>
* Constructs a queue that is backed by the given array. Runtime is O(1).
741
>
*/
742
>
constructor(items: readonly T[]) {
744
>
this.lastIdx = this.items.length - 1;
745
>
}
747
>
get length(): number {
749
>
}
751
>
/**
752
>
* Consumes elements from the beginning of the queue as long as the predicate returns true.
753
>
* If no elements were consumed, `null` is returned. Has a runtime of O(result.length).
754
>
*/
755
>
takeWhile(predicate: (value: T) => boolean): T[] | null {
757
>
// Find s := min { k | k >= this.firstIdx && !P(k) } and return this.data[this.firstIdx...s)
758
>
759
>
let startIdx = this.firstIdx;
760
>
while (startIdx < this.items.length && predicate(this.items[startIdx])) {
762
>
}
763
>
const result = startIdx === this.firstIdx ? null : this.items.slice(this.firstIdx, startIdx);
arrays.ts ×2
764
>
this.firstIdx = startIdx;
765
>
return result;
766
>
}
768
>
/**
769
>
* Consumes elements from the end of the queue as long as the predicate returns true.
770
>
* If no elements were consumed, `null` is returned.
771
>
* The result has the same order as the underlying array!
772
>
*/
773
>
takeFromEndWhile(predicate: (value: T) => boolean): T[] | null {
775
>
// Find s := max { k | k <= this.lastIdx && !P(k) } and return this.data(s...this.lastIdx]
776
>
777
>
let endIdx = this.lastIdx;
778
>
while (endIdx >= 0 && predicate(this.items[endIdx])) {
780
>
}
781
>
const result = endIdx === this.lastIdx ? null : this.items.slice(endIdx + 1, this.lastIdx + 1);
arrays.ts ×2
782
>
this.lastIdx = endIdx;
783
>
return result;
784
>
}
786
>
peek(): T | undefined {
787
if (this.length === 0) {
788
return undefined;
789
}
790
return this.items[this.firstIdx];
791
}
793
>
peekLast(): T | undefined {
794
if (this.length === 0) {
795
return undefined;
796
}
797
return this.items[this.lastIdx];
798
}
800
>
dequeue(): T | undefined {
802
>
this.firstIdx++;
803
>
return result;
804
>
}
806
>
removeLast(): T | undefined {
807
const result = this.items[this.lastIdx];
808
this.lastIdx--;
809
return result;
810
}
812
>
takeCount(count: number): T[] {
813
const result = this.items.slice(this.firstIdx, this.firstIdx + count);
814
this.firstIdx += count;
815
return result;
816
}
818
>
819
>
/**
820
>
* This class is faster than an iterator and array for lazy computed data.
821
>
*/
822
>
export class CallbackIterable<T> {
823
>
public static readonly empty = new CallbackIterable<never>(_callback => { });
824
>
825
>
constructor(
826
>
/**
827
>
* Calls the callback for every item.
828
>
* Stops when the callback returns false.
829
>
*/
830
>
public readonly iterate: (callback: (item: T) => boolean) => void
831
>
) {
832
>
}
833
>
834
>
forEach(handler: (item: T) => void) {
835
this.iterate(item => { handler(item); return true; });
836
}
838
>
toArray(): T[] {
840
>
this.iterate(item => { result.push(item); return true; });
841
>
return result;
842
>
}
844
>
filter(predicate: (item: T) => boolean): CallbackIterable<T> {
845
>
return new CallbackIterable(cb => this.iterate(item => predicate(item) ? cb(item) : true));
bracketPairsImpl.ts ×4
846
>
}
848
>
map<TResult>(mapFn: (item: T) => TResult): CallbackIterable<TResult> {
849
>
return new CallbackIterable<TResult>(cb => this.iterate(item => cb(mapFn(item))));
arrays.ts ×2
850
>
}
852
>
some(predicate: (item: T) => boolean): boolean {
853
let result = false;
854
this.iterate(item => { result = predicate(item); return !result; });
855
return result;
856
}
858
>
findFirst(predicate: (item: T) => boolean): T | undefined {
859
let result: T | undefined;
860
this.iterate(item => {
861
if (predicate(item)) {
862
result = item;
863
return false;
864
}
865
return true;
866
});
867
return result;
868
}
870
>
findLast(predicate: (item: T) => boolean): T | undefined {
871
let result: T | undefined;
872
this.iterate(item => {
873
if (predicate(item)) {
874
result = item;
875
}
876
return true;
877
});
878
return result;
879
}
881
>
findLastMaxBy(comparator: Comparator<T>): T | undefined {
883
>
let first = true;
884
>
this.iterate(item => {
886
>
first = false;
887
>
result = item;
888
>
}
889
>
return true;
891
>
return result;
892
>
}
894
>
895
>
/**
896
>
* Represents a re-arrangement of items in an array.
897
>
*/
898
>
export class Permutation {
899
>
constructor(private readonly _indexMap: readonly number[]) { }
900
>
901
>
/**
902
>
* Returns a permutation that sorts the given array according to the given compare function.
903
>
*/
904
>
public static createSortPermutation<T>(arr: readonly T[], compareFn: (a: T, b: T) => number): Permutation {
905
const sortIndices = Array.from(arr.keys()).sort((index1, index2) => compareFn(arr[index1], arr[index2]));
906
return new Permutation(sortIndices);
907
}
909
>
/**
910
>
* Returns a new array with the elements of the given array re-arranged according to this permutation.
911
>
*/
912
>
apply<T>(arr: readonly T[]): T[] {
913
return arr.map((_, index) => arr[this._indexMap[index]]);
914
}
916
>
/**
917
>
* Returns a new permutation that undoes the re-arrangement of this permutation.
918
>
*/
919
>
inverse(): Permutation {
920
const inverseIndexMap = this._indexMap.slice();
921
for (let i = 0; i < this._indexMap.length; i++) {
922
inverseIndexMap[this._indexMap[i]] = i;
923
}
924
return new Permutation(inverseIndexMap);
925
}
927
>
928
>
/**
929
>
* Asynchronous variant of `Array.find()`, returning the first element in
930
>
* the array for which the predicate returns true.
931
>
*
932
>
* This implementation does not bail early and waits for all promises to
933
>
* resolve before returning.
934
>
*/
935
export async function findAsync<T>(array: readonly T[], predicate: (element: T, index: number) => Promise<boolean>): Promise<T | undefined> {
936
const results = await Promise.all(array.map(
937
async (element, index) => ({ element, ok: await predicate(element, index) })
938
));
939
940
return results.find(r => r.ok)?.element;
941
}
943
>
export function sum(array: readonly number[]): number {
944
return array.reduce((acc, value) => acc + value, 0);
945
}
947
>
export function sumBy<T>(array: readonly T[], selector: (value: T) => number): number {
949
>
}