Mercurial > projects > ldc

comparison tango/tango/util/collection/TreeBag.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
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 }