-
-
Notifications
You must be signed in to change notification settings - Fork 2
/
RBTreeMultiDict.ts
126 lines (120 loc) · 4.05 KB
/
RBTreeMultiDict.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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import { MultiDictBase } from "./MultiDictBase";
import { isEqual, isIterable, ResolveAction } from "./util";
import { TreeDictOptions } from "./TreeDict";
import { RBTreeIndex } from "./RBTreeIndex";
/**
* A tree-based dictionary that can store multile items with the same key, but
* only if the values differ.
*
* ```ts
* import { TreeMultiDict } from "scl"
* ```
*
* The following table summarises the worst-case time complexity of the most
* commonly used properies of this class. For more information, see the
* documentation of the respective property.
*
* | Property name | Worst case |
* |----------------------------------------|--------------|
* | {@link TreeDict.add add()} | `O(log(n))` |
* | {@link TreeDict.clear clear()} | `O(1)` |
* | {@link TreeDict.equalKeys equalKeys()} | `O(n)` |
* | {@link TreeDict.delete delete()} | `O(log(n))` |
* | {@link TreeDict.deleteAll deleteAll()} | `O(n)` |
* | {@link TreeDict.deleteAt deleteAt()} | `O(log(n))` |
* | {@link TreeDict.size size} | `O(1)` |
*
* When a new entry is added with a key and value that is already taken, the
* dictionary will replace the corresponding entry with the new one.
*
* ```ts
* const d = new TreeMultiDict<number, string>()
* d.emplace(1, 'foo') // ok
* assert.strictEqual(d.getValues(1), 'foo')
* d.emplace(1, 'bar') // ok
* d.emplace(1, 'foo') // ok
* const values = [...d.getValues(1)]
* assert.lengthOf(values, 3)
* assert.deepInclude(value, [1, 'foo']) // appears two times
* assert.deepInclude(value, [1, 'bar'])
* ```
*
* If you need to throw an error when a key is already taken, simply use
* {@link TreeDict.has has()}.
*
* The items in a tree-based dictionary are guaranteed to be sorted on their
* keys. This is not true for values with the same, which generally appear in
* the order by which they were inserted.
*
* ```ts
* const d = new TreeMultiDict<number, string>()
* d.emplace(2, 'two')
* d.emplace(1, 'one')
* d.emplace(3, 'three')
* assert.deepEqual([...d], [[1, 'one'], [2, 'two'], [3, 'three']])
* ```
*
* @see [[HashMultiDict]] for a fast, unordered version of this collection.
* @see [[TreeDict]] when you need your keys to be unique.
* @see [[TreeManyDict]] when you want the values to be unique but not the keys.
*
* @typeparam K The type of key of a given entry.
* @typeparam V The type of value associated with the given key.
*/
export class RBTreeMultiDict<K, V> extends MultiDictBase<K, V> {
/**
* Construct a new tree-based dictionary.
*
* ```ts
* const d = new TreeMultiDict<number, string>()
* ```
*
* Similar to JavaScript's built-in [map type][1], the constructor accepts a
* list of key-value pairs that will immediately be added to the resulting
* dictionary.
*
* ```ts
* const d = new TreeMultiDict<number, string>([
* [1, 'one'],
* [2, 'two']
* ])
* ```
*
* The dictionary can be tweaked by providing a [[TreeDictOptions]]-object,
* which allows to configure things like the default compare function and
* value equality.
*
* ```ts
* const d = new TreeMultiDict<number, string>({
* compare: (a, b) => a < b,
* valuesEqual: (a, b) => a === b,
* elements: [[1, 'one'], [2, 'two']]
* })
* ```
*
* [1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
*/
constructor(opts: Iterable<[K, V]> | RBTreeIndex<[K, V], K> | TreeDictOptions<K, V> = {}) {
if (opts instanceof RBTreeIndex) {
super(opts);
} else {
if (isIterable(opts)) {
opts = { elements: opts }
}
const valuesEqual = opts.valuesEqual ?? isEqual;
super(
new RBTreeIndex({
getKey: pair => pair[0],
isEqual: (a, b) => valuesEqual(a[1], b[1]),
onDuplicateKeys: ResolveAction.Insert,
onDuplicateElements: ResolveAction.Insert,
...opts
})
);
}
}
public clone() {
return new RBTreeMultiDict(this.index)
}
}
export default RBTreeMultiDict;