1
>
/*---------------------------------------------------------------------------------------------
smallImmutableSet.ts
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
>
const emptyArr: number[] = [];
7
>
8
>
/**
9
>
* Represents an immutable set that works best for a small number of elements (less than 32).
10
>
* It uses bits to encode element membership efficiently.
11
>
*/
12
>
export class SmallImmutableSet<T> {
13
>
// eslint-disable-next-line @typescript-eslint/no-explicit-any
14
>
private static cache = new Array<SmallImmutableSet<any>>(129);
15
>
16
>
private static create<T>(items: number, additionalItems: readonly number[]): SmallImmutableSet<T> {
17
>
if (items <= 128 && additionalItems.length === 0) {
18
>
// We create a cache of 128=2^7 elements to cover all sets with up to 7 (dense) elements.
19
>
let cached = SmallImmutableSet.cache[items];
20
>
if (!cached) {
21
>
cached = new SmallImmutableSet(items, additionalItems);
22
>
SmallImmutableSet.cache[items] = cached;
23
>
}
24
>
return cached;
25
>
}
26
27
return new SmallImmutableSet(items, additionalItems);
29
>
30
>
// eslint-disable-next-line @typescript-eslint/no-explicit-any
31
>
private static empty = SmallImmutableSet.create<any>(0, emptyArr);
32
>
public static getEmpty<T>(): SmallImmutableSet<T> {
33
return this.empty;
34
}
36
>
private constructor(
37
>
private readonly items: number,
38
>
private readonly additionalItems: readonly number[]
39
>
) {
40
>
}
41
>
42
>
public add(value: T, keyProvider: IDenseKeyProvider<T>): SmallImmutableSet<T> {
43
const key = keyProvider.getKey(value);
44
let idx = key >> 5; // divided by 32