Algorithmen & Datenstrukturen mit Java: Beispielklasse für Verzeichnisse als Rot-Schwarz-Bäume
| Algorithmen & Datenstrukturen mit Java: Beispielklasse für Verzeichnisse als Rot-Schwarz-Bäume |
|
1package ds.interfaces;
2
3/** Simple interface for maps
4 */
5
6import java.util.Iterator;
7
8import ds.util.Invariant;
9import ds.util.Function2;
10
11import ds.util.K; // example class for keys
12import ds.util.V; // example class for values
13import ds.util.KV; // key value pair
14
15public
16 interface Map
17 extends Iterable<KV>,
18 Invariant {
19
20 boolean isEmpty();
21 boolean member(K k);
22 V lookup(K k);
23 int size();
24 KV findMin();
25 KV findMax();
26 Map insert(K k, V v);
27 Map remove(K k);
28 Map union(Map m2);
29 Map difference(Map m2);
30 Map unionWith(Function2<V,V,V> op, Map m2);
31 Map differenceWith(Function2<V,V,V> op, Map m2);
32 Map copy();
33
34 // inherited
35
36 // public Iterator<KV> iterator();
37 // public inv();
38}
1package ds.persistent.map;
2
3/** This is a translation of a Haskell implementation
4 for red-black trees from
5 http://matt.might.net/articles/red-black-delete/
6 The Haskell source can be found under
7 http://matt.might.net/articles/red-black-delete/code/RedBlackSet.hs
8
9 This Java implementation is a PERSISTENT one and
10 it supports deletion.
11*/
12
13import ds.interfaces.Map;
14
15import ds.util.K; // example class for keys
16import ds.util.V; // example class for values
17import ds.util.KV; // key value pair
18import ds.util.Queue; // used by iterators
19import ds.util.Function2;
20import ds.util.NullIterator;
21
22import static ds.util.KV.mkPair;
23import static ds.util.Boolean.toInt;
24import static ds.util.Integer.max;
25import static ds.util.Integer.min;
26import static ds.util.Undef.undefined;
27
28import java.util.Iterator;
29
30import static java.lang.Integer.signum;
31
32//----------------------------------------
33
34public abstract
35 class RedBlackTree
36 implements Map {
37
38 /* trc *
39 static void msg(String s) {
40 System.out.println(s);
41 }
42
43 static RedBlackTree trc(String s, RedBlackTree t) {
44 msg(s + " " + t);
45 return t;
46 }
47 /**/
48
49 //----------------------------------------
50 // the smart constructors
51
52 // empty tree
53 public static
54 RedBlackTree empty() {
55 return
56 EMPTY;
57 }
58
59 // singleton tree
60 public static
61 RedBlackTree singleton(K k, V v) {
62 return
63 empty().insert(k, v);
64 }
65
66 // build search tree from arbitrary sequence (iterator)
67 public static
68 RedBlackTree fromIterator(Iterator<KV> elems) {
69
70 RedBlackTree res = empty();
71 while ( elems.hasNext() ) {
72 KV p = elems.next();
73 res = res.insert(p.fst, p.snd);
74 }
75 return
76 res;
77 }
78
79 public RedBlackTree
80 union(Map m2) {
81 return
82 unionWith(const2, m2);
83 }
84
85 // general unionWith by iterating over m2
86 public RedBlackTree
87 unionWith(Function2<V,V,V> op,
88 Map m2) {
89 Iterator<KV> i = m2.iterator();
90 RedBlackTree res = this;
91
92 while ( i.hasNext() ) {
93 KV kv2 = i.next();
94 K k2 = kv2.fst;
95 V v2 = kv2.snd;
96 V v1 = res.lookup(k2);
97 V vr = v1 == null ? v2 : op.apply(v1, v2);
98 res = res.insert(k2, vr);
99 }
100 return
101 res;
102 }
103
104 public RedBlackTree
105 difference(Map m2) {
106 return
107 differenceWith(null2, m2);
108 }
109
110 // general differenceWith by iterating over m2
111 public RedBlackTree
112 differenceWith(Function2<V,V,V> op,
113 Map m2) {
114
115 Iterator<KV> i = m2.iterator();
116 RedBlackTree res = this;
117
118 while ( i.hasNext() ) {
119 KV kv2 = i.next();
120 K k2 = kv2.fst;
121 V v2 = kv2.snd;
122 V v1 = res.lookup(k2);
123
124 if ( v1 != null ) { // key found in res
125 V vr = op.apply(v1, v2);
126 if ( vr == null )
127 res = res.remove(k2);
128 else
129 res = res.insert(k2, vr);
130 }
131 }
132 return
133 res;
134 }
135
136 public RedBlackTree copy() {
137 return
138 this;
139 }
140
141 //----------------------------------------
142 // special binary tree methods
143
144 abstract public int depth();
145 abstract public int minDepth();
146
147 public boolean member(K k) {
148 return
149 lookup(k) != null;
150 }
151
152 //----------------------------------------
153 // internal methods
154
155 // getter
156 Node node() { return nodeExpected(); }
157 int color() { return nodeExpected(); }
158 K key() { return nodeExpected(); }
159 V value() { return nodeExpected(); }
160 RedBlackTree left() { return nodeExpected(); }
161 RedBlackTree right() { return nodeExpected(); }
162
163 // tree manipulation
164 public RedBlackTree insert(K k, V v) {
165 assert k != null;
166
167 return
168 insert1(k, v).paintItBlack();
169 }
170
171 public RedBlackTree remove(K k) {
172 assert k != null;
173
174 return
175 remove1(k).paintItBlack();
176 }
177
178 // 2. iterator for descending enumeration
179
180 abstract public Iterator<KV> iteratorDesc();
181
182 public String toString() {
183 return
184 iterator().toString();
185 }
186
187 public boolean inv() {
188 return
189 invOrdered()
190 &&
191 invRedWithBlackChildren()
192 &&
193 noOfBlackNodes() != -1
194 &&
195 isBlack();
196 }
197
198
199 //----------------------------------------
200 // internal methods
201
202 abstract RedBlackTree insert1(K k, V v);
203 abstract RedBlackTree remove1(K k);
204
205 abstract boolean invRedWithBlackChildren();
206 abstract int noOfBlackNodes();
207 abstract boolean invOrdered();
208 abstract boolean allLS(K k);
209 abstract boolean allGT(K k);
210
211 // helper for ***With functions
212 private static <A> A nodeExpected() {
213 return
214 undefined("Node expected");
215 }
216
217 private static Function2<V,V,V> const2
218 = new Function2<V,V,V>() {
219 public V apply(V x, V y) {
220 return y;
221 }
222 };
223
224 private static Function2<V,V,V> null2
225 = new Function2<V,V,V>() {
226 public V apply(V x, V y) {
227 return null;
228 }
229 };
230
231 //----------------------------------------
232 // coloring
233
234 static final int NEGATIVE_BLACK = -1;
235 static final int RED = 0;
236 static final int BLACK = 1;
237 static final int DOUBLE_BLACK = 2;
238
239 static int blacker(int c) {
240 assert c < DOUBLE_BLACK;
241 return
242 c + 1;
243 }
244
245 static int redder(int c) {
246 assert c > NEGATIVE_BLACK;
247 return
248 c - 1;
249 }
250
251 boolean isRed() { return color() == RED; }
252 boolean isBlack() { return color() == BLACK; }
253 boolean isDoubleBlack() { return color() == DOUBLE_BLACK; }
254 boolean isNegativeBlack() { return color() == NEGATIVE_BLACK; }
255 boolean isEmptyDoubleBlack() { return false; }
256
257 abstract RedBlackTree paintItRed();
258 abstract RedBlackTree paintItBlack();
259
260 abstract RedBlackTree blacker();
261 abstract RedBlackTree redder();
262
263 //----------------------------------------
264 // the empty tree implemented by applying the singleton design pattern
265
266 // the "generic" empty list object (with a raw type)
267
268 private static final RedBlackTree EMPTY
269 = new Empty();
270
271 // the singleton class for the empty list object
272
273 private static
274 class Empty extends RedBlackTree {
275
276 public boolean isEmpty() {
277 return true;
278 }
279
280 public int size() {
281 return 0;
282 }
283
284 public int depth() {
285 return 0;
286 }
287
288 public int minDepth() {
289 return 0;
290 }
291
292 public V lookup(K k) {
293 return null;
294 }
295
296 public KV findMin() {
297 return nodeExpected();
298 }
299
300 public KV findMax() {
301 return nodeExpected();
302 }
303
304 public Iterator<KV> iterator() {
305 ++cntIter;
306 return
307 new NullIterator<KV>();
308 }
309 public Iterator<KV> iteratorDesc() {
310 return
311 iterator();
312 }
313
314 /* *
315 public String toString() {
316 return
317 ".";
318 }
319 /* */
320
321 //----------------------------------------
322 // not public stuff
323
324 Empty() { }
325
326 boolean invRedWithBlackChildren() { return true; }
327 int noOfBlackNodes() { return 1; }
328 boolean invOrdered() { return true; }
329 boolean allLS(K k) { return true; }
330 boolean allGT(K k) { return true; }
331
332 int color() {
333 return BLACK;
334 }
335
336 RedBlackTree insert1(K k, V v) {
337 return
338 new Node(k, v, RED, EMPTY, EMPTY);
339 }
340 RedBlackTree remove1(K k) {
341 return
342 this;
343 }
344 RedBlackTree paintItBlack() {
345 return
346 empty(); // works also for DoubleEmpty
347 }
348 RedBlackTree paintItRed() {
349 return
350 undefined("paintItRed on empty tree");
351 }
352 RedBlackTree blacker() {
353 return
354 doubleEmpty();
355 }
356 RedBlackTree redder() {
357 return
358 undefined("redder of empty tree");
359 }
360
361 }
362
363 //----------------------------------------
364 // double black empty tree
365 // helper for deletion
366
367 private static
368 RedBlackTree doubleEmpty() {
369 return
370 DOUBLE_EMPTY;
371 }
372
373 private static final RedBlackTree DOUBLE_EMPTY
374 = new DoubleEmpty();
375
376 // the singleton class for the double black empty tree
377
378 private static final
379 class DoubleEmpty extends Empty {
380
381 /* *
382 public String toString() {
383 return
384 "!";
385 }
386 /* */
387
388 DoubleEmpty() { }
389
390 int color() {
391 return DOUBLE_BLACK;
392 }
393
394 boolean isEmptyDoubleBlack() {
395 return true;
396 }
397
398 RedBlackTree blacker() {
399 return
400 undefined("blacker of double black");
401 }
402 RedBlackTree redder() {
403 return
404 empty();
405 }
406 }
407
408 //----------------------------------------
409 // the node class for none empty trees
410
411 private static final
412 class Node extends RedBlackTree {
413
414 /* persistent */
415 final K k;
416 final V v;
417 final int c; // the color
418 final RedBlackTree l;
419 final RedBlackTree r;
420
421 /* destructive *
422 K k;
423 V v;
424 int c;
425 RedBlackTree l;
426 RedBlackTree r;
427 /**/
428
429 Node(K k, V v, int c, RedBlackTree l, RedBlackTree r) {
430 assert k != null;
431
432 this.k = k;
433 this.v = v;
434 this.c = c;
435 this.l = l;
436 this.r = r;
437 ++cntNode;
438 }
439
440 /* destructive *
441 public RedBlackTree copy() {
442 return
443 new Node(k, v, c, l, r);
444 }
445 /**/
446
447 /* trc *
448 String toString() {
449 return
450 "(" + l + " " + k + "," + v + "," + c2s(c) + " " + r + ")";
451 }
452 /**/
453
454 private static String c2s(int c) {
455 switch ( c ) {
456 case NEGATIVE_BLACK: return "N";
457 case RED: return "R";
458 case BLACK: return "B";
459 case DOUBLE_BLACK: return "D";
460 }
461 return "";
462 }
463
464 //----------------------------------------
465 // predicates and attributes
466
467 public boolean isEmpty() {
468 return false;
469 }
470
471 public int size() {
472 return
473 1 + l.size() + r.size();
474 }
475
476 public int depth() {
477 return
478 1 + max(l.depth(), r.depth());
479 }
480
481 public int minDepth() {
482 return
483 1 + min(l.minDepth(), r.minDepth());
484 }
485
486 public V lookup(K k) {
487 assert k != null;
488
489 switch (signum(k.compareTo(this.k))) {
490 case -1:
491 return
492 l.lookup(k);
493 case 0:
494 return
495 v;
496 case +1:
497 return
498 r.lookup(k);
499 }
500 // never executed, but required
501 return
502 null;
503 }
504
505 //----------------------------------------
506 // getter
507
508 Node node() { return this; }
509 int color() { return c; }
510 K key() { return k; }
511 V value() { return v; }
512 RedBlackTree left() { return l; }
513 RedBlackTree right() { return r; }
514
515 public KV findMin() {
516 if ( l.isEmpty() )
517 return
518 mkPair(k, v);
519 return
520 l.findMin();
521 }
522
523 public KV findMax() {
524 if ( r.isEmpty() )
525 return
526 mkPair(k, v);
527 return
528 r.findMax();
529 }
530
531 public Iterator<KV> iterator() {
532 ++cntIter;
533 return
534 new NodeIterator(this);
535 }
536
537 public Iterator<KV> iteratorDesc() {
538 ++cntIter;
539 return
540 new NodeIteratorDescending(this);
541 }
542
543 //----------------------------------------
544 // invariant helpers
545
546 boolean invRedWithBlackChildren() {
547 return
548 ( ! isRed()
549 ||
550 ( l.isBlack() && r.isBlack() ) )
551 &&
552 l.invRedWithBlackChildren()
553 &&
554 r.invRedWithBlackChildren();
555 }
556
557 // -1 indicates # of black nodes differ
558 int noOfBlackNodes() {
559 int nl = l.noOfBlackNodes();
560 int nr = r.noOfBlackNodes();
561 return
562 (nl == nr && nl != -1)
563 ? nl + toInt(isBlack())
564 : -1;
565 }
566
567 boolean invOrdered() {
568 return
569 l.allLS(k)
570 &&
571 r.allGT(k)
572 &&
573 l.invOrdered()
574 &&
575 r.invOrdered();
576 }
577
578 boolean allLS(K k) {
579 return
580 this.k.compareTo(k) < 0
581 &&
582 r.allLS(k)
583 // && // redundant if only
584 // l.allLS(k) // used by inv
585 ;
586 }
587 boolean allGT(K k) {
588 return
589 this.k.compareTo(k) > 0
590 &&
591 l.allGT(k)
592 // && // redundant if only
593 // r.allGT(k) // used by inv
594 ;
595 }
596
597
598 //----------------------------------------
599 // getter
600
601 //----------------------------------------
602 // recoloring
603
604 RedBlackTree paintItBlack() {
605 return
606 setColor(BLACK);
607 }
608 RedBlackTree paintItRed() {
609 return
610 setColor(RED);
611 }
612 RedBlackTree blacker() {
613 return
614 setColor(blacker(color()));
615 }
616 RedBlackTree redder() {
617 return
618 setColor(redder(color()));
619 }
620
621 //----------------------------------------
622 // balancing
623
624 Node balance(int c, RedBlackTree t1, K k, V v, RedBlackTree t2) {
625 if ( c == BLACK )
626 return
627 balanceBlack(t1, k, v, t2);
628
629 // DOUBLE_BLACK only used in remove1
630 if ( c == DOUBLE_BLACK )
631 return
632 balanceDoubleBlack(t1, k, v, t2);
633
634 // no balancing at red nodes
635 return
636 set(k, v, c, t1, t2);
637 }
638
639 // Okasaki's rules for insertion balancing
640
641 Node balanceBlack(RedBlackTree l, K k, V v, RedBlackTree r) {
642 // pattern matching with java is pain in the ass
643
644 if ( l.isRed() ) {
645 Node ln = l.node();
646 if ( ln.l.isRed() ) {
647 Node lln = ln.l.node();
648 return
649 build3(RED, lln.l, lln.k, lln.v,
650 lln.r, ln.k, ln.v,
651 ln.r, k, v, r, ln, lln);
652 }
653 if ( ln.r.isRed() ) {
654 Node lrn = ln.r.node();
655 return
656 build3(RED, ln.l, ln.k, ln.v,
657 lrn.l, lrn.k, lrn.v,
658 lrn.r, k, v, r, ln, lrn);
659 }
660 }
661 if ( r.isRed() ) {
662 Node rn = r.node();
663 if ( rn.l.isRed() ) {
664 Node rln = rn.l.node();
665 return
666 build3(RED,
667 l, k, v,
668 rln.l, rln.k, rln.v,
669 rln.r, rn.k, rn.v,
670 rn.r,
671 rln, rn);
672 }
673 if ( rn.r.isRed() ) {
674 Node rrn = rn.r.node();
675 return
676 build3(RED,
677 l, k, v,
678 rn.l, rn.k, rn.v,
679 rrn.l, rrn.k, rrn.v,
680 rrn.r,
681 rrn, rn);
682 }
683 }
684 return
685 set(k, v, BLACK, l, r);
686 }
687
688 Node balanceDoubleBlack(RedBlackTree l, K k, V v, RedBlackTree r) {
689 // same rules as in balanceBlack, double black is absorbed
690
691 if ( l.isRed() ) {
692 Node ln = l.node();
693 if ( ln.l.isRed() ) {
694 Node lln = ln.l.node();
695 return
696 build3(BLACK,
697 lln.l, lln.k, lln.v,
698 lln.r, ln.k, ln.v,
699 ln.r, k, v,
700 r,
701 ln, lln);
702 }
703 if ( ln.r.isRed() ) {
704 Node lrn = ln.r.node();
705 return
706 build3(BLACK,
707 ln.l, ln.k, ln.v,
708 lrn.l, lrn.k, lrn.v,
709 lrn.r, k, v,
710 r,
711 ln, lrn);
712 }
713 }
714 if ( r.isRed() ) {
715 Node rn = r.node();
716 if ( rn.l.isRed() ) {
717 Node rln = rn.l.node();
718 return
719 build3(BLACK,
720 l, k, v,
721 rln.l, rln.k, rln.v,
722 rln.r, rn.k, rn.v,
723 rn.r,
724 rln, rn);
725 }
726 if ( rn.r.isRed() ) {
727 Node rrn = rn.r.node();
728 return
729 build3(BLACK,
730 l, k, v,
731 rn.l, rn.k, rn.v,
732 rrn.l, rrn.k, rrn.v,
733 rrn.r,
734 rrn, rn);
735 }
736 }
737
738 // extra rules for negative black none empty trees
739 if ( r.isNegativeBlack() ) {
740 Node rn = r.node();
741 if ( rn.l.isBlack()
742 &&
743 rn.r.isBlack() ) {
744 Node rln = rn.l.node();
745 return
746 rln.set(rln.k, rln.v, BLACK,
747 set(k, v, BLACK, l, rln.l),
748 rn.balanceBlack(rln.r, rn.k, rn.v, rn.r.paintItRed()));
749 }
750 }
751 if ( l.isNegativeBlack() ) {
752 Node ln = l.node();
753 if ( ln.l.isBlack()
754 &&
755 ln.r.isBlack() ) {
756 Node lrn = ln.r.node();
757 return
758 lrn.set(lrn.k, lrn.v, BLACK,
759 ln.balanceBlack(ln.l.paintItRed(), ln.k, ln.v, lrn.l),
760 set(k, v, BLACK, l, lrn.r));
761 }
762 }
763 return
764 set(k, v, DOUBLE_BLACK, l, r);
765 }
766
767 Node bubble(int c, RedBlackTree l, K k, V v, RedBlackTree r) {
768 if ( l.isDoubleBlack()
769 ||
770 r.isDoubleBlack() ) {
771 return
772 balance(blacker(c), l.redder(), k, v, r.redder());
773 }
774 return
775 balance(c, l, k, v, r);
776 }
777
778 // build 3 nodes from a b c and d with labels x y z
779 // when a destrutive set is used
780 // the root is stored in this
781 // the left node is stored in l
782 // the right node in r
783
784 Node build3(int rootColor,
785 RedBlackTree a, K xk, V xv,
786 RedBlackTree b, K yk, V yv,
787 RedBlackTree c, K zk, V zv,
788 RedBlackTree d,
789 Node l, Node r) {
790 return
791 set(yk, yv, rootColor,
792 l.set(xk, xv, BLACK, a, b),
793 r.set(zk, zv, BLACK, c, d));
794 }
795
796 //----------------------------------------
797 // setter
798
799 private Node set(K k, V v, int c,
800 RedBlackTree l,
801 RedBlackTree r) {
802 /* persistent */
803 if ( k == this.k && v == this.v
804 &&
805 c == this.c
806 &&
807 l == this.l && r == this.r )
808 return
809 this;
810 return
811 new Node(k, v, c, l, r);
812
813 /* destructive *
814 this.k = k;
815 this.v = v;
816 this.c = c;
817 this.l = l;
818 this.r = r;
819 return
820 this;
821 /**/
822 }
823 private Node setV(V v) {
824 /* persistent */
825 return
826 ( v == this.v )
827 ? this
828 : new Node(this.k, v, this.c, this.l, this.r);
829
830 /* destructive *
831 this.v = v;
832 return
833 this;
834 /**/
835 }
836
837 private Node setColor(int c) {
838 /* persistent */
839 return
840 c == this.c
841 ? this
842 : new Node(this.k, this.v, c, this.l, this.r);
843
844 /* destructive *
845 this.c = c;
846 return
847 this;
848 /**/
849 }
850
851 //----------------------------------------
852 // tree manipulation
853
854 RedBlackTree insert1(K k, V v) {
855 switch ( signum(k.compareTo(this.k)) ) {
856 case -1:
857 return
858 balance(c, l.insert1(k, v), this.k, this.v, r);
859 case 0:
860 return
861 setV(v);
862 case +1:
863 return
864 balance(c, l, this.k, this.v, r.insert1(k, v));
865 }
866 // never executed, but required
867 return
868 null;
869 }
870
871 RedBlackTree remove1(K k) {
872 switch ( signum(k.compareTo(this.k)) ) {
873 case -1:
874 return
875 bubble(c, l.remove1(k), this.k, this.v, r);
876 case 0:
877 return
878 removeRoot();
879 //trc("removeRoot",removeRoot());
880 case +1:
881 return
882 bubble(c, l, this.k, this.v, r.remove1(k));
883 }
884 // never executed, but required
885 return
886 null;
887 }
888
889 RedBlackTree removeRoot() {
890 if ( isRed()
891 &&
892 l.isEmpty()
893 &&
894 r.isEmpty()
895 )
896 return
897 empty();
898 if ( isBlack() ) {
899 if ( l.isEmpty()
900 &&
901 r.isEmpty() )
902 return
903 doubleEmpty();
904 if ( l.isRed()
905 &&
906 r.isEmpty() )
907 return
908 l.blacker();
909 if ( r.isRed()
910 &&
911 l.isEmpty() )
912 return
913 r.blacker();
914 }
915 KV p = l.findMax();
916 return
917 bubble(c, l.node().removeMax(), p.fst, p.snd, r);
918 }
919
920 RedBlackTree removeMax() {
921 if ( r.isEmpty() )
922 return
923 removeRoot();
924 return
925 bubble(c, l, k, v, r.node().removeMax());
926 }
927
928 //----------------------------------------
929 // iterators
930
931 // ascending enumeration
932
933 private static
934 class NodeIterator
935 extends ds.util.Iterator<KV> {
936
937 Queue queue;
938
939 NodeIterator(Node n) {
940 queue = Queue.empty();
941 add(n);
942 ++cntIter;
943 }
944
945 void add(Node n) {
946 queue = queue.cons(n);
947 if ( ! n.l.isEmpty() )
948 add(n.l.node()); // downcast
949 }
950
951 void addSubNodes(Node n) {
952 if ( ! n.r.isEmpty() )
953 add(n.r.node());
954 }
955
956 public boolean hasNext() {
957 return
958 ! queue.isEmpty();
959 }
960
961 public KV next() {
962 if ( queue.isEmpty() )
963 return
964 undefined("empty tree");
965
966 Node n = (Node)queue.head();
967 queue = queue.tail();
968 addSubNodes(n);
969 return
970 mkPair(n.k, n.v);
971 }
972 }
973
974 // descending enumeration
975
976 private
977 class NodeIteratorDescending
978 extends NodeIterator {
979
980 NodeIteratorDescending(Node n) {
981 super(n);
982 }
983
984 void add(Node n) {
985 queue = queue.cons(n);
986 if ( ! n.r.isEmpty() )
987 add(n.r.node()); // downcast
988 }
989
990 void addSubNodes(Node n) {
991 if ( ! n.l.isEmpty() )
992 add(n.l.node());
993 }
994 }
995 }
996
997 //----------------------------------------
998 // profiling
999
1000 private static int cntNode = 0;
1001 private static int cntIter = 0;
1002
1003 public static String stats() {
1004 return
1005 "stats for ds.persistent.map.RedBlackTree:\n" +
1006 "# new Node() : " + cntNode + "\n" +
1007 "# new Iterator() : " + cntIter + "\n";
1008 }
1009
1010 public String objStats() {
1011 int s = size();
1012 int o = s;
1013 int f = 5 * s;
1014 int m = o + f;
1015
1016 return
1017 "mem stats for ds.persistent.map.RedBlackTree object:\n" +
1018 "# elements (size) : " + s + "\n" +
1019 "# objects : " + o + "\n" +
1020 "# fields : " + f + "\n" +
1021 "# mem words : " + m + "\n";
1022 }
1023}
|
| Letzte Änderung: 05.11.2015 | © Prof. Dr. Uwe Schmidt |
