|
132
|
1 /*
|
|
|
2 File: TreeBag.d
|
|
|
3
|
|
|
4 Originally written by Doug Lea and released into the public domain.
|
|
|
5 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
|
|
|
6 Inc, Loral, and everyone contributing, testing, and using this code.
|
|
|
7
|
|
|
8 History:
|
|
|
9 Date Who What
|
|
|
10 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file
|
|
|
11 13Oct95 dl Changed protection statuses
|
|
|
12
|
|
|
13 */
|
|
|
14
|
|
|
15
|
|
|
16 module tango.util.collection.TreeBag;
|
|
|
17
|
|
|
18 private import tango.util.collection.model.Iterator,
|
|
|
19 tango.util.collection.model.Comparator,
|
|
|
20 tango.util.collection.model.SortedValues,
|
|
|
21 tango.util.collection.model.GuardIterator;
|
|
|
22
|
|
|
23 private import tango.util.collection.impl.RBCell,
|
|
|
24 tango.util.collection.impl.BagCollection,
|
|
|
25 tango.util.collection.impl.AbstractIterator,
|
|
|
26 tango.util.collection.impl.DefaultComparator;
|
|
|
27
|
|
|
28 /**
|
|
|
29 * RedBlack trees.
|
|
|
30 * author: Doug Lea
|
|
|
31 **/
|
|
|
32
|
|
|
33 public class TreeBag(T) : BagCollection!(T), SortedValues!(T)
|
|
|
34 {
|
|
|
35 alias RBCell!(T) RBCellT;
|
|
|
36 alias Comparator!(T) ComparatorT;
|
|
|
37
|
|
|
38 alias BagCollection!(T).remove remove;
|
|
|
39 alias BagCollection!(T).removeAll removeAll;
|
|
|
40
|
|
|
41
|
|
|
42 // instance variables
|
|
|
43
|
|
|
44 /**
|
|
|
45 * The root of the tree. Null if empty.
|
|
|
46 **/
|
|
|
47
|
|
|
48 package RBCellT tree;
|
|
|
49
|
|
|
50 /**
|
|
|
51 * The comparator to use for ordering.
|
|
|
52 **/
|
|
|
53 protected ComparatorT cmp_;
|
|
|
54
|
|
|
55 // constructors
|
|
|
56
|
|
|
57 /**
|
|
|
58 * Make an empty tree.
|
|
|
59 * Initialize to use DefaultComparator for ordering
|
|
|
60 **/
|
|
|
61 public this ()
|
|
|
62 {
|
|
|
63 this(null, null, null, 0);
|
|
|
64 }
|
|
|
65
|
|
|
66 /**
|
|
|
67 * Make an empty tree, using the supplied element screener.
|
|
|
68 * Initialize to use DefaultComparator for ordering
|
|
|
69 **/
|
|
|
70
|
|
|
71 public this (Predicate s)
|
|
|
72 {
|
|
|
73 this(s, null, null, 0);
|
|
|
74 }
|
|
|
75
|
|
|
76 /**
|
|
|
77 * Make an empty tree, using the supplied element comparator for ordering.
|
|
|
78 **/
|
|
|
79 public this (ComparatorT c)
|
|
|
80 {
|
|
|
81 this(null, c, null, 0);
|
|
|
82 }
|
|
|
83
|
|
|
84 /**
|
|
|
85 * Make an empty tree, using the supplied element screener and comparator
|
|
|
86 **/
|
|
|
87 public this (Predicate s, ComparatorT c)
|
|
|
88 {
|
|
|
89 this(s, c, null, 0);
|
|
|
90 }
|
|
|
91
|
|
|
92 /**
|
|
|
93 * Special version of constructor needed by clone()
|
|
|
94 **/
|
|
|
95
|
|
|
96 protected this (Predicate s, ComparatorT cmp, RBCellT t, int n)
|
|
|
97 {
|
|
|
98 super(s);
|
|
|
99 count = n;
|
|
|
100 tree = t;
|
|
|
101 if (cmp !is null)
|
|
|
102 cmp_ = cmp;
|
|
|
103 else
|
|
|
104 cmp_ = new DefaultComparator!(T);
|
|
|
105 }
|
|
|
106
|
|
|
107 /**
|
|
|
108 * Make an independent copy of the tree. Does not clone elements.
|
|
|
109 **/
|
|
|
110
|
|
|
111 public TreeBag duplicate()
|
|
|
112 {
|
|
|
113 if (count is 0)
|
|
|
114 return new TreeBag!(T)(screener, cmp_);
|
|
|
115 else
|
|
|
116 return new TreeBag!(T)(screener, cmp_, tree.copyTree(), count);
|
|
|
117 }
|
|
|
118
|
|
|
119
|
|
|
120
|
|
|
121 // Collection methods
|
|
|
122
|
|
|
123 /**
|
|
|
124 * Implements tango.util.collection.impl.Collection.Collection.contains
|
|
|
125 * Time complexity: O(log n).
|
|
|
126 * See_Also: tango.util.collection.impl.Collection.Collection.contains
|
|
|
127 **/
|
|
|
128 public final bool contains(T element)
|
|
|
129 {
|
|
|
130 if (!isValidArg(element) || count is 0)
|
|
|
131 return false;
|
|
|
132
|
|
|
133 return tree.find(element, cmp_) !is null;
|
|
|
134 }
|
|
|
135
|
|
|
136 /**
|
|
|
137 * Implements tango.util.collection.impl.Collection.Collection.instances
|
|
|
138 * Time complexity: O(log n).
|
|
|
139 * See_Also: tango.util.collection.impl.Collection.Collection.instances
|
|
|
140 **/
|
|
|
141 public final uint instances(T element)
|
|
|
142 {
|
|
|
143 if (!isValidArg(element) || count is 0)
|
|
|
144 return 0;
|
|
|
145
|
|
|
146 return tree.count(element, cmp_);
|
|
|
147 }
|
|
|
148
|
|
|
149 /**
|
|
|
150 * Implements tango.util.collection.impl.Collection.Collection.elements
|
|
|
151 * Time complexity: O(1).
|
|
|
152 * See_Also: tango.util.collection.impl.Collection.Collection.elements
|
|
|
153 **/
|
|
|
154 public final GuardIterator!(T) elements()
|
|
|
155 {
|
|
|
156 return new CellIterator!(T)(this);
|
|
|
157 }
|
|
|
158
|
|
|
159 /**
|
|
|
160 * Implements tango.util.collection.model.View.View.opApply
|
|
|
161 * Time complexity: O(n).
|
|
|
162 * See_Also: tango.util.collection.model.View.View.opApply
|
|
|
163 **/
|
|
|
164 int opApply (int delegate (inout T value) dg)
|
|
|
165 {
|
|
|
166 auto scope iterator = new CellIterator!(T)(this);
|
|
|
167 return iterator.opApply (dg);
|
|
|
168 }
|
|
|
169
|
|
|
170
|
|
|
171 // ElementSortedCollection methods
|
|
|
172
|
|
|
173
|
|
|
174 /**
|
|
|
175 * Implements tango.util.collection.ElementSortedCollection.comparator
|
|
|
176 * Time complexity: O(1).
|
|
|
177 * See_Also: tango.util.collection.ElementSortedCollection.comparator
|
|
|
178 **/
|
|
|
179 public final ComparatorT comparator()
|
|
|
180 {
|
|
|
181 return cmp_;
|
|
|
182 }
|
|
|
183
|
|
|
184 /**
|
|
|
185 * Reset the comparator. Will cause a reorganization of the tree.
|
|
|
186 * Time complexity: O(n log n).
|
|
|
187 **/
|
|
|
188 public final void comparator(ComparatorT cmp)
|
|
|
189 {
|
|
|
190 if (cmp !is cmp_)
|
|
|
191 {
|
|
|
192 if (cmp !is null)
|
|
|
193 cmp_ = cmp;
|
|
|
194 else
|
|
|
195 cmp_ = new DefaultComparator!(T);
|
|
|
196
|
|
|
197 if (count !is 0)
|
|
|
198 { // must rebuild tree!
|
|
|
199 incVersion();
|
|
|
200 RBCellT t = tree.leftmost();
|
|
|
201 tree = null;
|
|
|
202 count = 0;
|
|
|
203 while (t !is null)
|
|
|
204 {
|
|
|
205 add_(t.element(), false);
|
|
|
206 t = t.successor();
|
|
|
207 }
|
|
|
208 }
|
|
|
209 }
|
|
|
210 }
|
|
|
211
|
|
|
212
|
|
|
213 // MutableCollection methods
|
|
|
214
|
|
|
215 /**
|
|
|
216 * Implements tango.util.collection.impl.Collection.Collection.clear.
|
|
|
217 * Time complexity: O(1).
|
|
|
218 * See_Also: tango.util.collection.impl.Collection.Collection.clear
|
|
|
219 **/
|
|
|
220 public final void clear()
|
|
|
221 {
|
|
|
222 setCount(0);
|
|
|
223 tree = null;
|
|
|
224 }
|
|
|
225
|
|
|
226 /**
|
|
|
227 * Implements tango.util.collection.impl.Collection.Collection.removeAll.
|
|
|
228 * Time complexity: O(log n * instances(element)).
|
|
|
229 * See_Also: tango.util.collection.impl.Collection.Collection.removeAll
|
|
|
230 **/
|
|
|
231 public final void removeAll(T element)
|
|
|
232 {
|
|
|
233 remove_(element, true);
|
|
|
234 }
|
|
|
235
|
|
|
236
|
|
|
237 /**
|
|
|
238 * Implements tango.util.collection.impl.Collection.Collection.removeOneOf.
|
|
|
239 * Time complexity: O(log n).
|
|
|
240 * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf
|
|
|
241 **/
|
|
|
242 public final void remove(T element)
|
|
|
243 {
|
|
|
244 remove_(element, false);
|
|
|
245 }
|
|
|
246
|
|
|
247 /**
|
|
|
248 * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf
|
|
|
249 * Time complexity: O(log n).
|
|
|
250 * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf
|
|
|
251 **/
|
|
|
252 public final void replace(T oldElement, T newElement)
|
|
|
253 {
|
|
|
254 replace_(oldElement, newElement, false);
|
|
|
255 }
|
|
|
256
|
|
|
257 /**
|
|
|
258 * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf.
|
|
|
259 * Time complexity: O(log n * instances(oldElement)).
|
|
|
260 * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf
|
|
|
261 **/
|
|
|
262 public final void replaceAll(T oldElement, T newElement)
|
|
|
263 {
|
|
|
264 replace_(oldElement, newElement, true);
|
|
|
265 }
|
|
|
266
|
|
|
267 /**
|
|
|
268 * Implements tango.util.collection.impl.Collection.Collection.take.
|
|
|
269 * Time complexity: O(log n).
|
|
|
270 * Takes the least element.
|
|
|
271 * See_Also: tango.util.collection.impl.Collection.Collection.take
|
|
|
272 **/
|
|
|
273 public final T take()
|
|
|
274 {
|
|
|
275 if (count !is 0)
|
|
|
276 {
|
|
|
277 RBCellT p = tree.leftmost();
|
|
|
278 T v = p.element();
|
|
|
279 tree = p.remove(tree);
|
|
|
280 decCount();
|
|
|
281 return v;
|
|
|
282 }
|
|
|
283
|
|
|
284 checkIndex(0);
|
|
|
285 return T.init; // not reached
|
|
|
286 }
|
|
|
287
|
|
|
288
|
|
|
289 // MutableBag methods
|
|
|
290
|
|
|
291 /**
|
|
|
292 * Implements tango.util.collection.MutableBag.addIfAbsent
|
|
|
293 * Time complexity: O(log n).
|
|
|
294 * See_Also: tango.util.collection.MutableBag.addIfAbsent
|
|
|
295 **/
|
|
|
296 public final void addIf (T element)
|
|
|
297 {
|
|
|
298 add_(element, true);
|
|
|
299 }
|
|
|
300
|
|
|
301
|
|
|
302 /**
|
|
|
303 * Implements tango.util.collection.MutableBag.add.
|
|
|
304 * Time complexity: O(log n).
|
|
|
305 * See_Also: tango.util.collection.MutableBag.add
|
|
|
306 **/
|
|
|
307 public final void add (T element)
|
|
|
308 {
|
|
|
309 add_(element, false);
|
|
|
310 }
|
|
|
311
|
|
|
312
|
|
|
313 // helper methods
|
|
|
314
|
|
|
315 private final void add_(T element, bool checkOccurrence)
|
|
|
316 {
|
|
|
317 checkElement(element);
|
|
|
318
|
|
|
319 if (tree is null)
|
|
|
320 {
|
|
|
321 tree = new RBCellT(element);
|
|
|
322 incCount();
|
|
|
323 }
|
|
|
324 else
|
|
|
325 {
|
|
|
326 RBCellT t = tree;
|
|
|
327
|
|
|
328 for (;;)
|
|
|
329 {
|
|
|
330 int diff = cmp_.compare(element, t.element());
|
|
|
331 if (diff is 0 && checkOccurrence)
|
|
|
332 return ;
|
|
|
333 else
|
|
|
334 if (diff <= 0)
|
|
|
335 {
|
|
|
336 if (t.left() !is null)
|
|
|
337 t = t.left();
|
|
|
338 else
|
|
|
339 {
|
|
|
340 tree = t.insertLeft(new RBCellT(element), tree);
|
|
|
341 incCount();
|
|
|
342 return ;
|
|
|
343 }
|
|
|
344 }
|
|
|
345 else
|
|
|
346 {
|
|
|
347 if (t.right() !is null)
|
|
|
348 t = t.right();
|
|
|
349 else
|
|
|
350 {
|
|
|
351 tree = t.insertRight(new RBCellT(element), tree);
|
|
|
352 incCount();
|
|
|
353 return ;
|
|
|
354 }
|
|
|
355 }
|
|
|
356 }
|
|
|
357 }
|
|
|
358 }
|
|
|
359
|
|
|
360
|
|
|
361 private final void remove_(T element, bool allOccurrences)
|
|
|
362 {
|
|
|
363 if (!isValidArg(element))
|
|
|
364 return ;
|
|
|
365
|
|
|
366 while (count > 0)
|
|
|
367 {
|
|
|
368 RBCellT p = tree.find(element, cmp_);
|
|
|
369
|
|
|
370 if (p !is null)
|
|
|
371 {
|
|
|
372 tree = p.remove(tree);
|
|
|
373 decCount();
|
|
|
374 if (!allOccurrences)
|
|
|
375 return ;
|
|
|
376 }
|
|
|
377 else
|
|
|
378 break;
|
|
|
379 }
|
|
|
380 }
|
|
|
381
|
|
|
382 private final void replace_(T oldElement, T newElement, bool allOccurrences)
|
|
|
383 {
|
|
|
384 if (!isValidArg(oldElement) || count is 0 || oldElement == newElement)
|
|
|
385 return ;
|
|
|
386
|
|
|
387 while (contains(oldElement))
|
|
|
388 {
|
|
|
389 remove(oldElement);
|
|
|
390 add (newElement);
|
|
|
391 if (!allOccurrences)
|
|
|
392 return ;
|
|
|
393 }
|
|
|
394 }
|
|
|
395
|
|
|
396 // ImplementationCheckable methods
|
|
|
397
|
|
|
398 /**
|
|
|
399 * Implements tango.util.collection.model.View.View.checkImplementation.
|
|
|
400 * See_Also: tango.util.collection.model.View.View.checkImplementation
|
|
|
401 **/
|
|
|
402 public override void checkImplementation()
|
|
|
403 {
|
|
|
404
|
|
|
405 super.checkImplementation();
|
|
|
406 assert(cmp_ !is null);
|
|
|
407 assert(((count is 0) is (tree is null)));
|
|
|
408 assert((tree is null || tree.size() is count));
|
|
|
409
|
|
|
410 if (tree !is null)
|
|
|
411 {
|
|
|
412 tree.checkImplementation();
|
|
|
413 T last = T.init;
|
|
|
414 RBCellT t = tree.leftmost();
|
|
|
415 while (t !is null)
|
|
|
416 {
|
|
|
417 T v = t.element();
|
|
|
418 if (last !is T.init)
|
|
|
419 assert(cmp_.compare(last, v) <= 0);
|
|
|
420 last = v;
|
|
|
421 t = t.successor();
|
|
|
422 }
|
|
|
423 }
|
|
|
424 }
|
|
|
425
|
|
|
426
|
|
|
427 /***********************************************************************
|
|
|
428
|
|
|
429 opApply() has migrated here to mitigate the virtual call
|
|
|
430 on method get()
|
|
|
431
|
|
|
432 ************************************************************************/
|
|
|
433
|
|
|
434 private static class CellIterator(T) : AbstractIterator!(T)
|
|
|
435 {
|
|
|
436 private RBCellT cell;
|
|
|
437
|
|
|
438 public this (TreeBag bag)
|
|
|
439 {
|
|
|
440 super(bag);
|
|
|
441
|
|
|
442 if (bag.tree)
|
|
|
443 cell = bag.tree.leftmost;
|
|
|
444 }
|
|
|
445
|
|
|
446 public final T get()
|
|
|
447 {
|
|
|
448 decRemaining();
|
|
|
449 auto v = cell.element();
|
|
|
450 cell = cell.successor();
|
|
|
451 return v;
|
|
|
452 }
|
|
|
453
|
|
|
454 int opApply (int delegate (inout T value) dg)
|
|
|
455 {
|
|
|
456 int result;
|
|
|
457
|
|
|
458 for (auto i=remaining(); i--;)
|
|
|
459 {
|
|
|
460 auto value = get();
|
|
|
461 if ((result = dg(value)) != 0)
|
|
|
462 break;
|
|
|
463 }
|
|
|
464 return result;
|
|
|
465 }
|
|
|
466 }
|
|
|
467 }
|
|
|
468
|
|
|
469
|
|
|
470
|
|
|
471 debug (Test)
|
|
|
472 {
|
|
|
473 import tango.io.Console;
|
|
|
474
|
|
|
475 void main()
|
|
|
476 {
|
|
|
477 auto bag = new TreeBag!(char[]);
|
|
|
478 bag.add ("bar");
|
|
|
479 bag.add ("barrel");
|
|
|
480 bag.add ("foo");
|
|
|
481
|
|
|
482 foreach (value; bag.elements) {}
|
|
|
483
|
|
|
484 auto elements = bag.elements();
|
|
|
485 while (elements.more)
|
|
|
486 auto v = elements.get();
|
|
|
487
|
|
|
488 foreach (value; bag.elements)
|
|
|
489 Cout (value).newline;
|
|
|
490
|
|
|
491 bag.checkImplementation();
|
|
|
492 }
|
|
|
493 }
|
