-
-
Notifications
You must be signed in to change notification settings - Fork 2
/
TreeIndex.ts
101 lines (89 loc) · 2.23 KB
/
TreeIndex.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import { RBTreeIndex } from "./RBTreeIndex"
export interface TreeIndexOptions<T, K = T> {
/**
* An iterable that will be consumed to fill the collection.
*/
elements?: Iterable<T>;
/**
* Compares two keys and returns whether the first key is less than the
* second.
*
* If left unspecified, a default function will be chosen that works on most
* keys.
*/
compareKeys?: (a: K, b: K) => boolean;
/**
* Exctracts the key part of the element.
*/
getKey?: (elements: T) => K;
/**
* Used for checking two elements with the same key in the collection.
*/
isEqual?: (a: T, b: T) => boolean;
/**
* Set to `false` to prevent an element with the same key for which
* [[isEqual]] returns true to be added to the collection.
*/
allowDuplicates?: boolean;
}
/**
* An [[Index | indexed collection]] that is backed by the recommended
* implementation that strikes a balance between fast storage and fast
* retrieval of elements. You may assume that most operations are at least
* within `O(log(n))` and that all elements are ordered from smallest to
* largest.
*
* ```
* import { TreeIndex } from "scl";
*
* interface Person {
* firstName: string
* email: string,
* age: number,
* }
*
* const personsSortedByAge = new TreeIndex<Person, number>([
* {
* firstName: 'Jack',
* email: 'jack.smith@gmail.com',
* age: 34
* },
* {
* firstName: 'Bob',
* email: 'thebobman@gmail.com',
* age: 17
* },
* {
* firstName: 'Jessie',
* email: 'jessie@gmail.com',
* age: 25
* },
* {
* firstName: 'Anna',
* email: 'anna@outlook.com',
* age: 58
* }
* ]);
*
* const jack = personsSortedByAge.findKey(34);
*
* // The following will return Jessie (aged 25)
* const oldestPersonYoungerThan30 = personsSortedByAge.lowerKey(30)
*
* // This will print names in the following order:
* // Bob (aged 17)
* // Jessie (aged 25)
* // Jack (aged 34)
* // Anna (aged 58)
* for (const person of personsSortedByAge) {
* console.log(person.fullName);
* }
* ```
*
* @see AVLTreeIndex
*/
export class TreeIndex<T, K = T> extends RBTreeIndex<T, K> {
constructor(opts: Iterable<T> | TreeIndexOptions<T, K> = {}) {
super(opts);
}
}