src/vs/base/common/arraysFind.ts
226 LOC · 172 covered · 54 uncovered · 40 ranges · 20961 concepts · 16 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 { Comparator } from './arrays.js';
7
>
8
>
export function findLast<T, R extends T>(array: readonly T[], predicate: (item: T, index: number) => item is R, fromIndex?: number): R | undefined;
9
>
export function findLast<T>(array: readonly T[], predicate: (item: T, index: number) => unknown, fromIndex?: number): T | undefined;
10
>
export function findLast<T>(array: readonly T[], predicate: (item: T, index: number) => unknown, fromIndex = array.length - 1): T | undefined {
12
>
if (idx === -1) {
14
>
}
16
>
}
18
>
export function findLastIdx<T>(array: readonly T[], predicate: (item: T, index: number) => unknown, fromIndex = array.length - 1): number {
21
>
22
>
if (predicate(element, i)) {
23
>
return i;
24
>
}
25
>
}
27
>
return -1;
28
>
}
30
>
export function findFirst<T, R extends T>(array: readonly T[], predicate: (item: T, index: number) => item is R, fromIndex?: number): R | undefined;
31
>
export function findFirst<T>(array: readonly T[], predicate: (item: T, index: number) => unknown, fromIndex?: number): T | undefined;
32
>
export function findFirst<T>(array: readonly T[], predicate: (item: T, index: number) => unknown, fromIndex = 0): T | undefined {
33
const idx = findFirstIdx(array, predicate, fromIndex);
34
if (idx === -1) {
35
return undefined;
36
}
37
return array[idx];
38
}
40
>
export function findFirstIdx<T>(array: readonly T[], predicate: (item: T, index: number) => unknown, fromIndex = 0): number {
41
for (let i = fromIndex; i < array.length; i++) {
42
const element = array[i];
43
44
if (predicate(element, i)) {
45
return i;
46
}
47
}
48
49
return -1;
50
}
52
>
/**
53
>
* Finds the last item where predicate is true using binary search.
54
>
* `predicate` must be monotonous, i.e. `arr.map(predicate)` must be like `[true, ..., true, false, ..., false]`!
55
>
*
56
>
* @returns `undefined` if no item matches, otherwise the last item that matches the predicate.
57
>
*/
58
>
export function findLastMonotonous<T>(array: readonly T[], predicate: (item: T) => boolean): T | undefined {
60
>
return idx === -1 ? undefined : array[idx];
61
>
}
63
>
/**
64
>
* Finds the last item where predicate is true using binary search.
65
>
* `predicate` must be monotonous, i.e. `arr.map(predicate)` must be like `[true, ..., true, false, ..., false]`!
66
>
*
67
>
* @returns `startIdx - 1` if predicate is false for all items, otherwise the index of the last item that matches the predicate.
68
>
*/
69
>
export function findLastIdxMonotonous<T>(array: readonly T[], predicate: (item: T) => boolean, startIdx = 0, endIdxEx = array.length): number {
71
>
let j = endIdxEx;
72
>
while (i < j) {
73
>
const k = Math.floor((i + j) / 2);
74
>
if (predicate(array[k])) {
75
>
i = k + 1;
76
>
} else {
78
>
}
80
>
return i - 1;
81
>
}
83
>
/**
84
>
* Finds the first item where predicate is true using binary search.
85
>
* `predicate` must be monotonous, i.e. `arr.map(predicate)` must be like `[false, ..., false, true, ..., true]`!
86
>
*
87
>
* @returns `undefined` if no item matches, otherwise the first item that matches the predicate.
88
>
*/
89
>
export function findFirstMonotonous<T>(array: readonly T[], predicate: (item: T) => boolean): T | undefined {
91
>
return idx === array.length ? undefined : array[idx];
92
>
}
94
>
/**
95
>
* Finds the first item where predicate is true using binary search.
96
>
* `predicate` must be monotonous, i.e. `arr.map(predicate)` must be like `[false, ..., false, true, ..., true]`!
97
>
*
98
>
* @returns `endIdxEx` if predicate is false for all items, otherwise the index of the first item that matches the predicate.
99
>
*/
100
>
export function findFirstIdxMonotonousOrArrLen<T>(array: readonly T[], predicate: (item: T) => boolean, startIdx = 0, endIdxEx = array.length): number {
102
>
let j = endIdxEx;
103
>
while (i < j) {
104
>
const k = Math.floor((i + j) / 2);
105
>
if (predicate(array[k])) {
109
>
}
111
>
return i;
112
>
}
114
>
export function findFirstIdxMonotonous<T>(array: readonly T[], predicate: (item: T) => boolean, startIdx = 0, endIdxEx = array.length): number {
115
const idx = findFirstIdxMonotonousOrArrLen(array, predicate, startIdx, endIdxEx);
116
return idx === array.length ? -1 : idx;
117
}
119
>
/**
120
>
* Use this when
121
>
* * You have a sorted array
122
>
* * You query this array with a monotonous predicate to find the last item that has a certain property.
123
>
* * You query this array multiple times with monotonous predicates that get weaker and weaker.
124
>
*/
125
>
export class MonotonousArray<T> {
126
>
public static assertInvariants = false;
127
>
128
>
private _findLastMonotonousLastIdx = 0;
129
>
private _prevFindLastPredicate: ((item: T) => boolean) | undefined;
130
>
131
>
constructor(private readonly _array: readonly T[]) {
134
>
/**
135
>
* The predicate must be monotonous, i.e. `arr.map(predicate)` must be like `[true, ..., true, false, ..., false]`!
136
>
* For subsequent calls, current predicate must be weaker than (or equal to) the previous predicate, i.e. more entries must be `true`.
137
>
*/
138
>
findLastMonotonous(predicate: (item: T) => boolean): T | undefined {
140
if (this._prevFindLastPredicate) {
141
for (const item of this._array) {
142
if (this._prevFindLastPredicate(item) && !predicate(item)) {
143
throw new Error('MonotonousArray: current predicate must be weaker than (or equal to) the previous predicate.');
144
}
145
}
146
}
147
this._prevFindLastPredicate = predicate;
148
}
150
>
const idx = findLastIdxMonotonous(this._array, predicate, this._findLastMonotonousLastIdx);
151
>
this._findLastMonotonousLastIdx = idx + 1;
152
>
return idx === -1 ? undefined : this._array[idx];
153
>
}
155
>
156
>
/**
157
>
* Returns the first item that is equal to or greater than every other item.
158
>
*/
159
>
export function findFirstMax<T>(array: readonly T[], comparator: Comparator<T>): T | undefined {
161
return undefined;
162
}
164
>
let max = array[0];
165
>
for (let i = 1; i < array.length; i++) {
166
>
const item = array[i];
167
>
if (comparator(item, max) > 0) {
168
>
max = item;
169
>
}
170
>
}
171
>
return max;
172
>
}
174
>
/**
175
>
* Returns the last item that is equal to or greater than every other item.
176
>
*/
177
>
export function findLastMax<T>(array: readonly T[], comparator: Comparator<T>): T | undefined {
179
return undefined;
180
}
182
>
let max = array[0];
183
>
for (let i = 1; i < array.length; i++) {
184
>
const item = array[i];
185
>
if (comparator(item, max) >= 0) {
186
>
max = item;
187
>
}
188
>
}
189
>
return max;
190
>
}
192
>
/**
193
>
* Returns the first item that is equal to or less than every other item.
194
>
*/
195
>
export function findFirstMin<T>(array: readonly T[], comparator: Comparator<T>): T | undefined {
197
>
}
199
>
export function findMaxIdx<T>(array: readonly T[], comparator: Comparator<T>): number {
200
if (array.length === 0) {
201
return -1;
202
}
203
204
let maxIdx = 0;
205
for (let i = 1; i < array.length; i++) {
206
const item = array[i];
207
if (comparator(item, array[maxIdx]) > 0) {
208
maxIdx = i;
209
}
210
}
211
return maxIdx;
212
}
214
>
/**
215
>
* Returns the first mapped value of the array which is not undefined.
216
>
*/
217
>
export function mapFindFirst<T, R>(items: Iterable<T>, mapFn: (value: T) => R | undefined): R | undefined {
218
for (const value of items) {
219
const mapped = mapFn(value);
220
if (mapped !== undefined) {
221
return mapped;
222
}
223
}
224
225
return undefined;
226
}