1 | /*
|
---|
2 | MIT License http://www.opensource.org/licenses/mit-license.php
|
---|
3 | Author Tobias Koppers @sokra
|
---|
4 | */
|
---|
5 |
|
---|
6 | "use strict";
|
---|
7 |
|
---|
8 | const { first } = require("./SetHelpers");
|
---|
9 | const SortableSet = require("./SortableSet");
|
---|
10 |
|
---|
11 | /**
|
---|
12 | * Multi layer bucket sorted set:
|
---|
13 | * Supports adding non-existing items (DO NOT ADD ITEM TWICE),
|
---|
14 | * Supports removing exiting items (DO NOT REMOVE ITEM NOT IN SET),
|
---|
15 | * Supports popping the first items according to defined order,
|
---|
16 | * Supports iterating all items without order,
|
---|
17 | * Supports updating an item in an efficient way,
|
---|
18 | * Supports size property, which is the number of items,
|
---|
19 | * Items are lazy partially sorted when needed
|
---|
20 | * @template T
|
---|
21 | * @template K
|
---|
22 | */
|
---|
23 | class LazyBucketSortedSet {
|
---|
24 | /**
|
---|
25 | * @param {function(T): K} getKey function to get key from item
|
---|
26 | * @param {function(K, K): number} comparator comparator to sort keys
|
---|
27 | * @param {...((function(T): any) | (function(any, any): number))} args more pairs of getKey and comparator plus optional final comparator for the last layer
|
---|
28 | */
|
---|
29 | constructor(getKey, comparator, ...args) {
|
---|
30 | this._getKey = getKey;
|
---|
31 | this._innerArgs = args;
|
---|
32 | this._leaf = args.length <= 1;
|
---|
33 | this._keys = new SortableSet(undefined, comparator);
|
---|
34 | /** @type {Map<K, LazyBucketSortedSet<T, any> | SortableSet<T>>} */
|
---|
35 | this._map = new Map();
|
---|
36 | this._unsortedItems = new Set();
|
---|
37 | this.size = 0;
|
---|
38 | }
|
---|
39 |
|
---|
40 | /**
|
---|
41 | * @param {T} item an item
|
---|
42 | * @returns {void}
|
---|
43 | */
|
---|
44 | add(item) {
|
---|
45 | this.size++;
|
---|
46 | this._unsortedItems.add(item);
|
---|
47 | }
|
---|
48 |
|
---|
49 | /**
|
---|
50 | * @param {K} key key of item
|
---|
51 | * @param {T} item the item
|
---|
52 | * @returns {void}
|
---|
53 | */
|
---|
54 | _addInternal(key, item) {
|
---|
55 | let entry = this._map.get(key);
|
---|
56 | if (entry === undefined) {
|
---|
57 | entry = this._leaf
|
---|
58 | ? new SortableSet(undefined, this._innerArgs[0])
|
---|
59 | : new /** @type {any} */ (LazyBucketSortedSet)(...this._innerArgs);
|
---|
60 | this._keys.add(key);
|
---|
61 | this._map.set(key, entry);
|
---|
62 | }
|
---|
63 | entry.add(item);
|
---|
64 | }
|
---|
65 |
|
---|
66 | /**
|
---|
67 | * @param {T} item an item
|
---|
68 | * @returns {void}
|
---|
69 | */
|
---|
70 | delete(item) {
|
---|
71 | this.size--;
|
---|
72 | if (this._unsortedItems.has(item)) {
|
---|
73 | this._unsortedItems.delete(item);
|
---|
74 | return;
|
---|
75 | }
|
---|
76 | const key = this._getKey(item);
|
---|
77 | const entry = this._map.get(key);
|
---|
78 | entry.delete(item);
|
---|
79 | if (entry.size === 0) {
|
---|
80 | this._deleteKey(key);
|
---|
81 | }
|
---|
82 | }
|
---|
83 |
|
---|
84 | /**
|
---|
85 | * @param {K} key key to be removed
|
---|
86 | * @returns {void}
|
---|
87 | */
|
---|
88 | _deleteKey(key) {
|
---|
89 | this._keys.delete(key);
|
---|
90 | this._map.delete(key);
|
---|
91 | }
|
---|
92 |
|
---|
93 | /**
|
---|
94 | * @returns {T | undefined} an item
|
---|
95 | */
|
---|
96 | popFirst() {
|
---|
97 | if (this.size === 0) return undefined;
|
---|
98 | this.size--;
|
---|
99 | if (this._unsortedItems.size > 0) {
|
---|
100 | for (const item of this._unsortedItems) {
|
---|
101 | const key = this._getKey(item);
|
---|
102 | this._addInternal(key, item);
|
---|
103 | }
|
---|
104 | this._unsortedItems.clear();
|
---|
105 | }
|
---|
106 | this._keys.sort();
|
---|
107 | const key = first(this._keys);
|
---|
108 | const entry = this._map.get(key);
|
---|
109 | if (this._leaf) {
|
---|
110 | const leafEntry = /** @type {SortableSet<T>} */ (entry);
|
---|
111 | leafEntry.sort();
|
---|
112 | const item = first(leafEntry);
|
---|
113 | leafEntry.delete(item);
|
---|
114 | if (leafEntry.size === 0) {
|
---|
115 | this._deleteKey(key);
|
---|
116 | }
|
---|
117 | return item;
|
---|
118 | } else {
|
---|
119 | const nodeEntry = /** @type {LazyBucketSortedSet<T, any>} */ (entry);
|
---|
120 | const item = nodeEntry.popFirst();
|
---|
121 | if (nodeEntry.size === 0) {
|
---|
122 | this._deleteKey(key);
|
---|
123 | }
|
---|
124 | return item;
|
---|
125 | }
|
---|
126 | }
|
---|
127 |
|
---|
128 | /**
|
---|
129 | * @param {T} item to be updated item
|
---|
130 | * @returns {function(true=): void} finish update
|
---|
131 | */
|
---|
132 | startUpdate(item) {
|
---|
133 | if (this._unsortedItems.has(item)) {
|
---|
134 | return remove => {
|
---|
135 | if (remove) {
|
---|
136 | this._unsortedItems.delete(item);
|
---|
137 | this.size--;
|
---|
138 | return;
|
---|
139 | }
|
---|
140 | };
|
---|
141 | }
|
---|
142 | const key = this._getKey(item);
|
---|
143 | if (this._leaf) {
|
---|
144 | const oldEntry = /** @type {SortableSet<T>} */ (this._map.get(key));
|
---|
145 | return remove => {
|
---|
146 | if (remove) {
|
---|
147 | this.size--;
|
---|
148 | oldEntry.delete(item);
|
---|
149 | if (oldEntry.size === 0) {
|
---|
150 | this._deleteKey(key);
|
---|
151 | }
|
---|
152 | return;
|
---|
153 | }
|
---|
154 | const newKey = this._getKey(item);
|
---|
155 | if (key === newKey) {
|
---|
156 | // This flags the sortable set as unordered
|
---|
157 | oldEntry.add(item);
|
---|
158 | } else {
|
---|
159 | oldEntry.delete(item);
|
---|
160 | if (oldEntry.size === 0) {
|
---|
161 | this._deleteKey(key);
|
---|
162 | }
|
---|
163 | this._addInternal(newKey, item);
|
---|
164 | }
|
---|
165 | };
|
---|
166 | } else {
|
---|
167 | const oldEntry = /** @type {LazyBucketSortedSet<T, any>} */ (
|
---|
168 | this._map.get(key)
|
---|
169 | );
|
---|
170 | const finishUpdate = oldEntry.startUpdate(item);
|
---|
171 | return remove => {
|
---|
172 | if (remove) {
|
---|
173 | this.size--;
|
---|
174 | finishUpdate(true);
|
---|
175 | if (oldEntry.size === 0) {
|
---|
176 | this._deleteKey(key);
|
---|
177 | }
|
---|
178 | return;
|
---|
179 | }
|
---|
180 | const newKey = this._getKey(item);
|
---|
181 | if (key === newKey) {
|
---|
182 | finishUpdate();
|
---|
183 | } else {
|
---|
184 | finishUpdate(true);
|
---|
185 | if (oldEntry.size === 0) {
|
---|
186 | this._deleteKey(key);
|
---|
187 | }
|
---|
188 | this._addInternal(newKey, item);
|
---|
189 | }
|
---|
190 | };
|
---|
191 | }
|
---|
192 | }
|
---|
193 |
|
---|
194 | /**
|
---|
195 | * @param {Iterator<T>[]} iterators list of iterators to append to
|
---|
196 | * @returns {void}
|
---|
197 | */
|
---|
198 | _appendIterators(iterators) {
|
---|
199 | if (this._unsortedItems.size > 0)
|
---|
200 | iterators.push(this._unsortedItems[Symbol.iterator]());
|
---|
201 | for (const key of this._keys) {
|
---|
202 | const entry = this._map.get(key);
|
---|
203 | if (this._leaf) {
|
---|
204 | const leafEntry = /** @type {SortableSet<T>} */ (entry);
|
---|
205 | const iterator = leafEntry[Symbol.iterator]();
|
---|
206 | iterators.push(iterator);
|
---|
207 | } else {
|
---|
208 | const nodeEntry = /** @type {LazyBucketSortedSet<T, any>} */ (entry);
|
---|
209 | nodeEntry._appendIterators(iterators);
|
---|
210 | }
|
---|
211 | }
|
---|
212 | }
|
---|
213 |
|
---|
214 | /**
|
---|
215 | * @returns {Iterator<T>} the iterator
|
---|
216 | */
|
---|
217 | [Symbol.iterator]() {
|
---|
218 | const iterators = [];
|
---|
219 | this._appendIterators(iterators);
|
---|
220 | iterators.reverse();
|
---|
221 | let currentIterator = iterators.pop();
|
---|
222 | return {
|
---|
223 | next: () => {
|
---|
224 | const res = currentIterator.next();
|
---|
225 | if (res.done) {
|
---|
226 | if (iterators.length === 0) return res;
|
---|
227 | currentIterator = iterators.pop();
|
---|
228 | return currentIterator.next();
|
---|
229 | }
|
---|
230 | return res;
|
---|
231 | }
|
---|
232 | };
|
---|
233 | }
|
---|
234 | }
|
---|
235 |
|
---|
236 | module.exports = LazyBucketSortedSet;
|
---|