1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 | "use strict";
|
7 |
|
8 | const { first } = require("./SetHelpers");
|
9 | const SortableSet = require("./SortableSet");
|
10 |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 | class LazyBucketSortedSet {
|
24 | |
25 |
|
26 |
|
27 |
|
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 |
|
35 | this._map = new Map();
|
36 | this._unsortedItems = new Set();
|
37 | this.size = 0;
|
38 | }
|
39 |
|
40 | |
41 |
|
42 |
|
43 |
|
44 | add(item) {
|
45 | this.size++;
|
46 | this._unsortedItems.add(item);
|
47 | }
|
48 |
|
49 | |
50 |
|
51 |
|
52 |
|
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 (LazyBucketSortedSet)(...this._innerArgs);
|
60 | this._keys.add(key);
|
61 | this._map.set(key, entry);
|
62 | }
|
63 | entry.add(item);
|
64 | }
|
65 |
|
66 | |
67 |
|
68 |
|
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 |
|
86 |
|
87 |
|
88 | _deleteKey(key) {
|
89 | this._keys.delete(key);
|
90 | this._map.delete(key);
|
91 | }
|
92 |
|
93 | |
94 |
|
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 = (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 = (entry);
|
120 | const item = nodeEntry.popFirst();
|
121 | if (nodeEntry.size === 0) {
|
122 | this._deleteKey(key);
|
123 | }
|
124 | return item;
|
125 | }
|
126 | }
|
127 |
|
128 | |
129 |
|
130 |
|
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 = (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 |
|
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 = (
|
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 |
|
196 |
|
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 = (entry);
|
205 | const iterator = leafEntry[Symbol.iterator]();
|
206 | iterators.push(iterator);
|
207 | } else {
|
208 | const nodeEntry = (entry);
|
209 | nodeEntry._appendIterators(iterators);
|
210 | }
|
211 | }
|
212 | }
|
213 |
|
214 | |
215 |
|
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;
|