Mercurial > lasercutter
comparison src/clojure/lang/PersistentTreeMap.java @ 10:ef7dbbd6452c
added clojure source goodness
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 21 Aug 2010 06:25:44 -0400 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
9:35cf337adfcf | 10:ef7dbbd6452c |
---|---|
1 /** | |
2 * Copyright (c) Rich Hickey. All rights reserved. | |
3 * The use and distribution terms for this software are covered by the | |
4 * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) | |
5 * which can be found in the file epl-v10.html at the root of this distribution. | |
6 * By using this software in any fashion, you are agreeing to be bound by | |
7 * the terms of this license. | |
8 * You must not remove this notice, or any other, from this software. | |
9 **/ | |
10 | |
11 /* rich May 20, 2006 */ | |
12 | |
13 package clojure.lang; | |
14 | |
15 import java.util.*; | |
16 | |
17 /** | |
18 * Persistent Red Black Tree | |
19 * Note that instances of this class are constant values | |
20 * i.e. add/remove etc return new values | |
21 * <p/> | |
22 * See Okasaki, Kahrs, Larsen et al | |
23 */ | |
24 | |
25 public class PersistentTreeMap extends APersistentMap implements IObj, Reversible, Sorted{ | |
26 | |
27 public final Comparator comp; | |
28 public final Node tree; | |
29 public final int _count; | |
30 final IPersistentMap _meta; | |
31 | |
32 final static public PersistentTreeMap EMPTY = new PersistentTreeMap(); | |
33 | |
34 static public IPersistentMap create(Map other){ | |
35 IPersistentMap ret = EMPTY; | |
36 for(Object o : other.entrySet()) | |
37 { | |
38 Map.Entry e = (Entry) o; | |
39 ret = ret.assoc(e.getKey(), e.getValue()); | |
40 } | |
41 return ret; | |
42 } | |
43 | |
44 public PersistentTreeMap(){ | |
45 this(RT.DEFAULT_COMPARATOR); | |
46 } | |
47 | |
48 public PersistentTreeMap withMeta(IPersistentMap meta){ | |
49 return new PersistentTreeMap(meta, comp, tree, _count); | |
50 } | |
51 | |
52 private PersistentTreeMap(Comparator comp){ | |
53 this(null, comp); | |
54 } | |
55 | |
56 | |
57 public PersistentTreeMap(IPersistentMap meta, Comparator comp){ | |
58 this.comp = comp; | |
59 this._meta = meta; | |
60 tree = null; | |
61 _count = 0; | |
62 } | |
63 | |
64 PersistentTreeMap(IPersistentMap meta, Comparator comp, Node tree, int _count){ | |
65 this._meta = meta; | |
66 this.comp = comp; | |
67 this.tree = tree; | |
68 this._count = _count; | |
69 } | |
70 | |
71 static public PersistentTreeMap create(ISeq items){ | |
72 IPersistentMap ret = EMPTY; | |
73 for(; items != null; items = items.next().next()) | |
74 { | |
75 if(items.next() == null) | |
76 throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); | |
77 ret = ret.assoc(items.first(), RT.second(items)); | |
78 } | |
79 return (PersistentTreeMap) ret; | |
80 } | |
81 | |
82 static public PersistentTreeMap create(Comparator comp, ISeq items){ | |
83 IPersistentMap ret = new PersistentTreeMap(comp); | |
84 for(; items != null; items = items.next().next()) | |
85 { | |
86 if(items.next() == null) | |
87 throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); | |
88 ret = ret.assoc(items.first(), RT.second(items)); | |
89 } | |
90 return (PersistentTreeMap) ret; | |
91 } | |
92 | |
93 public boolean containsKey(Object key){ | |
94 return entryAt(key) != null; | |
95 } | |
96 | |
97 public PersistentTreeMap assocEx(Object key, Object val) throws Exception{ | |
98 Box found = new Box(null); | |
99 Node t = add(tree, key, val, found); | |
100 if(t == null) //null == already contains key | |
101 { | |
102 throw new Exception("Key already present"); | |
103 } | |
104 return new PersistentTreeMap(comp, t.blacken(), _count + 1, meta()); | |
105 } | |
106 | |
107 public PersistentTreeMap assoc(Object key, Object val){ | |
108 Box found = new Box(null); | |
109 Node t = add(tree, key, val, found); | |
110 if(t == null) //null == already contains key | |
111 { | |
112 Node foundNode = (Node) found.val; | |
113 if(foundNode.val() == val) //note only get same collection on identity of val, not equals() | |
114 return this; | |
115 return new PersistentTreeMap(comp, replace(tree, key, val), _count, meta()); | |
116 } | |
117 return new PersistentTreeMap(comp, t.blacken(), _count + 1, meta()); | |
118 } | |
119 | |
120 | |
121 public PersistentTreeMap without(Object key){ | |
122 Box found = new Box(null); | |
123 Node t = remove(tree, key, found); | |
124 if(t == null) | |
125 { | |
126 if(found.val == null)//null == doesn't contain key | |
127 return this; | |
128 //empty | |
129 return new PersistentTreeMap(meta(), comp); | |
130 } | |
131 return new PersistentTreeMap(comp, t.blacken(), _count - 1, meta()); | |
132 } | |
133 | |
134 public ISeq seq(){ | |
135 if(_count > 0) | |
136 return Seq.create(tree, true, _count); | |
137 return null; | |
138 } | |
139 | |
140 public IPersistentCollection empty(){ | |
141 return new PersistentTreeMap(meta(), comp); | |
142 } | |
143 | |
144 public ISeq rseq() throws Exception{ | |
145 if(_count > 0) | |
146 return Seq.create(tree, false, _count); | |
147 return null; | |
148 } | |
149 | |
150 public Comparator comparator(){ | |
151 return comp; | |
152 } | |
153 | |
154 public Object entryKey(Object entry){ | |
155 return ((IMapEntry) entry).key(); | |
156 } | |
157 | |
158 public ISeq seq(boolean ascending){ | |
159 if(_count > 0) | |
160 return Seq.create(tree, ascending, _count); | |
161 return null; | |
162 } | |
163 | |
164 public ISeq seqFrom(Object key, boolean ascending){ | |
165 if(_count > 0) | |
166 { | |
167 ISeq stack = null; | |
168 Node t = tree; | |
169 while(t != null) | |
170 { | |
171 int c = doCompare(key, t.key); | |
172 if(c == 0) | |
173 { | |
174 stack = RT.cons(t, stack); | |
175 return new Seq(stack, ascending); | |
176 } | |
177 else if(ascending) | |
178 { | |
179 if(c < 0) | |
180 { | |
181 stack = RT.cons(t, stack); | |
182 t = t.left(); | |
183 } | |
184 else | |
185 t = t.right(); | |
186 } | |
187 else | |
188 { | |
189 if(c > 0) | |
190 { | |
191 stack = RT.cons(t, stack); | |
192 t = t.right(); | |
193 } | |
194 else | |
195 t = t.left(); | |
196 } | |
197 } | |
198 if(stack != null) | |
199 return new Seq(stack, ascending); | |
200 } | |
201 return null; | |
202 } | |
203 | |
204 public NodeIterator iterator(){ | |
205 return new NodeIterator(tree, true); | |
206 } | |
207 | |
208 public NodeIterator reverseIterator(){ | |
209 return new NodeIterator(tree, false); | |
210 } | |
211 | |
212 public Iterator keys(){ | |
213 return keys(iterator()); | |
214 } | |
215 | |
216 public Iterator vals(){ | |
217 return vals(iterator()); | |
218 } | |
219 | |
220 public Iterator keys(NodeIterator it){ | |
221 return new KeyIterator(it); | |
222 } | |
223 | |
224 public Iterator vals(NodeIterator it){ | |
225 return new ValIterator(it); | |
226 } | |
227 | |
228 public Object minKey(){ | |
229 Node t = min(); | |
230 return t != null ? t.key : null; | |
231 } | |
232 | |
233 public Node min(){ | |
234 Node t = tree; | |
235 if(t != null) | |
236 { | |
237 while(t.left() != null) | |
238 t = t.left(); | |
239 } | |
240 return t; | |
241 } | |
242 | |
243 public Object maxKey(){ | |
244 Node t = max(); | |
245 return t != null ? t.key : null; | |
246 } | |
247 | |
248 public Node max(){ | |
249 Node t = tree; | |
250 if(t != null) | |
251 { | |
252 while(t.right() != null) | |
253 t = t.right(); | |
254 } | |
255 return t; | |
256 } | |
257 | |
258 public int depth(){ | |
259 return depth(tree); | |
260 } | |
261 | |
262 int depth(Node t){ | |
263 if(t == null) | |
264 return 0; | |
265 return 1 + Math.max(depth(t.left()), depth(t.right())); | |
266 } | |
267 | |
268 public Object valAt(Object key, Object notFound){ | |
269 Node n = entryAt(key); | |
270 return (n != null) ? n.val() : notFound; | |
271 } | |
272 | |
273 public Object valAt(Object key){ | |
274 return valAt(key, null); | |
275 } | |
276 | |
277 public int capacity(){ | |
278 return _count; | |
279 } | |
280 | |
281 public int count(){ | |
282 return _count; | |
283 } | |
284 | |
285 public Node entryAt(Object key){ | |
286 Node t = tree; | |
287 while(t != null) | |
288 { | |
289 int c = doCompare(key, t.key); | |
290 if(c == 0) | |
291 return t; | |
292 else if(c < 0) | |
293 t = t.left(); | |
294 else | |
295 t = t.right(); | |
296 } | |
297 return t; | |
298 } | |
299 | |
300 public int doCompare(Object k1, Object k2){ | |
301 // if(comp != null) | |
302 return comp.compare(k1, k2); | |
303 // return ((Comparable) k1).compareTo(k2); | |
304 } | |
305 | |
306 Node add(Node t, Object key, Object val, Box found){ | |
307 if(t == null) | |
308 { | |
309 if(val == null) | |
310 return new Red(key); | |
311 return new RedVal(key, val); | |
312 } | |
313 int c = doCompare(key, t.key); | |
314 if(c == 0) | |
315 { | |
316 found.val = t; | |
317 return null; | |
318 } | |
319 Node ins = c < 0 ? add(t.left(), key, val, found) : add(t.right(), key, val, found); | |
320 if(ins == null) //found below | |
321 return null; | |
322 if(c < 0) | |
323 return t.addLeft(ins); | |
324 return t.addRight(ins); | |
325 } | |
326 | |
327 Node remove(Node t, Object key, Box found){ | |
328 if(t == null) | |
329 return null; //not found indicator | |
330 int c = doCompare(key, t.key); | |
331 if(c == 0) | |
332 { | |
333 found.val = t; | |
334 return append(t.left(), t.right()); | |
335 } | |
336 Node del = c < 0 ? remove(t.left(), key, found) : remove(t.right(), key, found); | |
337 if(del == null && found.val == null) //not found below | |
338 return null; | |
339 if(c < 0) | |
340 { | |
341 if(t.left() instanceof Black) | |
342 return balanceLeftDel(t.key, t.val(), del, t.right()); | |
343 else | |
344 return red(t.key, t.val(), del, t.right()); | |
345 } | |
346 if(t.right() instanceof Black) | |
347 return balanceRightDel(t.key, t.val(), t.left(), del); | |
348 return red(t.key, t.val(), t.left(), del); | |
349 // return t.removeLeft(del); | |
350 // return t.removeRight(del); | |
351 } | |
352 | |
353 static Node append(Node left, Node right){ | |
354 if(left == null) | |
355 return right; | |
356 else if(right == null) | |
357 return left; | |
358 else if(left instanceof Red) | |
359 { | |
360 if(right instanceof Red) | |
361 { | |
362 Node app = append(left.right(), right.left()); | |
363 if(app instanceof Red) | |
364 return red(app.key, app.val(), | |
365 red(left.key, left.val(), left.left(), app.left()), | |
366 red(right.key, right.val(), app.right(), right.right())); | |
367 else | |
368 return red(left.key, left.val(), left.left(), red(right.key, right.val(), app, right.right())); | |
369 } | |
370 else | |
371 return red(left.key, left.val(), left.left(), append(left.right(), right)); | |
372 } | |
373 else if(right instanceof Red) | |
374 return red(right.key, right.val(), append(left, right.left()), right.right()); | |
375 else //black/black | |
376 { | |
377 Node app = append(left.right(), right.left()); | |
378 if(app instanceof Red) | |
379 return red(app.key, app.val(), | |
380 black(left.key, left.val(), left.left(), app.left()), | |
381 black(right.key, right.val(), app.right(), right.right())); | |
382 else | |
383 return balanceLeftDel(left.key, left.val(), left.left(), black(right.key, right.val(), app, right.right())); | |
384 } | |
385 } | |
386 | |
387 static Node balanceLeftDel(Object key, Object val, Node del, Node right){ | |
388 if(del instanceof Red) | |
389 return red(key, val, del.blacken(), right); | |
390 else if(right instanceof Black) | |
391 return rightBalance(key, val, del, right.redden()); | |
392 else if(right instanceof Red && right.left() instanceof Black) | |
393 return red(right.left().key, right.left().val(), | |
394 black(key, val, del, right.left().left()), | |
395 rightBalance(right.key, right.val(), right.left().right(), right.right().redden())); | |
396 else | |
397 throw new UnsupportedOperationException("Invariant violation"); | |
398 } | |
399 | |
400 static Node balanceRightDel(Object key, Object val, Node left, Node del){ | |
401 if(del instanceof Red) | |
402 return red(key, val, left, del.blacken()); | |
403 else if(left instanceof Black) | |
404 return leftBalance(key, val, left.redden(), del); | |
405 else if(left instanceof Red && left.right() instanceof Black) | |
406 return red(left.right().key, left.right().val(), | |
407 leftBalance(left.key, left.val(), left.left().redden(), left.right().left()), | |
408 black(key, val, left.right().right(), del)); | |
409 else | |
410 throw new UnsupportedOperationException("Invariant violation"); | |
411 } | |
412 | |
413 static Node leftBalance(Object key, Object val, Node ins, Node right){ | |
414 if(ins instanceof Red && ins.left() instanceof Red) | |
415 return red(ins.key, ins.val(), ins.left().blacken(), black(key, val, ins.right(), right)); | |
416 else if(ins instanceof Red && ins.right() instanceof Red) | |
417 return red(ins.right().key, ins.right().val(), | |
418 black(ins.key, ins.val(), ins.left(), ins.right().left()), | |
419 black(key, val, ins.right().right(), right)); | |
420 else | |
421 return black(key, val, ins, right); | |
422 } | |
423 | |
424 | |
425 static Node rightBalance(Object key, Object val, Node left, Node ins){ | |
426 if(ins instanceof Red && ins.right() instanceof Red) | |
427 return red(ins.key, ins.val(), black(key, val, left, ins.left()), ins.right().blacken()); | |
428 else if(ins instanceof Red && ins.left() instanceof Red) | |
429 return red(ins.left().key, ins.left().val(), | |
430 black(key, val, left, ins.left().left()), | |
431 black(ins.key, ins.val(), ins.left().right(), ins.right())); | |
432 else | |
433 return black(key, val, left, ins); | |
434 } | |
435 | |
436 Node replace(Node t, Object key, Object val){ | |
437 int c = doCompare(key, t.key); | |
438 return t.replace(t.key, | |
439 c == 0 ? val : t.val(), | |
440 c < 0 ? replace(t.left(), key, val) : t.left(), | |
441 c > 0 ? replace(t.right(), key, val) : t.right()); | |
442 } | |
443 | |
444 PersistentTreeMap(Comparator comp, Node tree, int count, IPersistentMap meta){ | |
445 this._meta = meta; | |
446 this.comp = comp; | |
447 this.tree = tree; | |
448 this._count = count; | |
449 } | |
450 | |
451 static Red red(Object key, Object val, Node left, Node right){ | |
452 if(left == null && right == null) | |
453 { | |
454 if(val == null) | |
455 return new Red(key); | |
456 return new RedVal(key, val); | |
457 } | |
458 if(val == null) | |
459 return new RedBranch(key, left, right); | |
460 return new RedBranchVal(key, val, left, right); | |
461 } | |
462 | |
463 static Black black(Object key, Object val, Node left, Node right){ | |
464 if(left == null && right == null) | |
465 { | |
466 if(val == null) | |
467 return new Black(key); | |
468 return new BlackVal(key, val); | |
469 } | |
470 if(val == null) | |
471 return new BlackBranch(key, left, right); | |
472 return new BlackBranchVal(key, val, left, right); | |
473 } | |
474 | |
475 public IPersistentMap meta(){ | |
476 return _meta; | |
477 } | |
478 | |
479 static abstract class Node extends AMapEntry{ | |
480 final Object key; | |
481 | |
482 Node(Object key){ | |
483 this.key = key; | |
484 } | |
485 | |
486 public Object key(){ | |
487 return key; | |
488 } | |
489 | |
490 public Object val(){ | |
491 return null; | |
492 } | |
493 | |
494 public Object getKey(){ | |
495 return key(); | |
496 } | |
497 | |
498 public Object getValue(){ | |
499 return val(); | |
500 } | |
501 | |
502 Node left(){ | |
503 return null; | |
504 } | |
505 | |
506 Node right(){ | |
507 return null; | |
508 } | |
509 | |
510 abstract Node addLeft(Node ins); | |
511 | |
512 abstract Node addRight(Node ins); | |
513 | |
514 abstract Node removeLeft(Node del); | |
515 | |
516 abstract Node removeRight(Node del); | |
517 | |
518 abstract Node blacken(); | |
519 | |
520 abstract Node redden(); | |
521 | |
522 Node balanceLeft(Node parent){ | |
523 return black(parent.key, parent.val(), this, parent.right()); | |
524 } | |
525 | |
526 Node balanceRight(Node parent){ | |
527 return black(parent.key, parent.val(), parent.left(), this); | |
528 } | |
529 | |
530 abstract Node replace(Object key, Object val, Node left, Node right); | |
531 | |
532 } | |
533 | |
534 static class Black extends Node{ | |
535 public Black(Object key){ | |
536 super(key); | |
537 } | |
538 | |
539 Node addLeft(Node ins){ | |
540 return ins.balanceLeft(this); | |
541 } | |
542 | |
543 Node addRight(Node ins){ | |
544 return ins.balanceRight(this); | |
545 } | |
546 | |
547 Node removeLeft(Node del){ | |
548 return balanceLeftDel(key, val(), del, right()); | |
549 } | |
550 | |
551 Node removeRight(Node del){ | |
552 return balanceRightDel(key, val(), left(), del); | |
553 } | |
554 | |
555 Node blacken(){ | |
556 return this; | |
557 } | |
558 | |
559 Node redden(){ | |
560 return new Red(key); | |
561 } | |
562 | |
563 Node replace(Object key, Object val, Node left, Node right){ | |
564 return black(key, val, left, right); | |
565 } | |
566 | |
567 } | |
568 | |
569 static class BlackVal extends Black{ | |
570 final Object val; | |
571 | |
572 public BlackVal(Object key, Object val){ | |
573 super(key); | |
574 this.val = val; | |
575 } | |
576 | |
577 public Object val(){ | |
578 return val; | |
579 } | |
580 | |
581 Node redden(){ | |
582 return new RedVal(key, val); | |
583 } | |
584 | |
585 } | |
586 | |
587 static class BlackBranch extends Black{ | |
588 final Node left; | |
589 | |
590 final Node right; | |
591 | |
592 public BlackBranch(Object key, Node left, Node right){ | |
593 super(key); | |
594 this.left = left; | |
595 this.right = right; | |
596 } | |
597 | |
598 public Node left(){ | |
599 return left; | |
600 } | |
601 | |
602 public Node right(){ | |
603 return right; | |
604 } | |
605 | |
606 Node redden(){ | |
607 return new RedBranch(key, left, right); | |
608 } | |
609 | |
610 } | |
611 | |
612 static class BlackBranchVal extends BlackBranch{ | |
613 final Object val; | |
614 | |
615 public BlackBranchVal(Object key, Object val, Node left, Node right){ | |
616 super(key, left, right); | |
617 this.val = val; | |
618 } | |
619 | |
620 public Object val(){ | |
621 return val; | |
622 } | |
623 | |
624 Node redden(){ | |
625 return new RedBranchVal(key, val, left, right); | |
626 } | |
627 | |
628 } | |
629 | |
630 static class Red extends Node{ | |
631 public Red(Object key){ | |
632 super(key); | |
633 } | |
634 | |
635 Node addLeft(Node ins){ | |
636 return red(key, val(), ins, right()); | |
637 } | |
638 | |
639 Node addRight(Node ins){ | |
640 return red(key, val(), left(), ins); | |
641 } | |
642 | |
643 Node removeLeft(Node del){ | |
644 return red(key, val(), del, right()); | |
645 } | |
646 | |
647 Node removeRight(Node del){ | |
648 return red(key, val(), left(), del); | |
649 } | |
650 | |
651 Node blacken(){ | |
652 return new Black(key); | |
653 } | |
654 | |
655 Node redden(){ | |
656 throw new UnsupportedOperationException("Invariant violation"); | |
657 } | |
658 | |
659 Node replace(Object key, Object val, Node left, Node right){ | |
660 return red(key, val, left, right); | |
661 } | |
662 | |
663 } | |
664 | |
665 static class RedVal extends Red{ | |
666 final Object val; | |
667 | |
668 public RedVal(Object key, Object val){ | |
669 super(key); | |
670 this.val = val; | |
671 } | |
672 | |
673 public Object val(){ | |
674 return val; | |
675 } | |
676 | |
677 Node blacken(){ | |
678 return new BlackVal(key, val); | |
679 } | |
680 | |
681 } | |
682 | |
683 static class RedBranch extends Red{ | |
684 final Node left; | |
685 | |
686 final Node right; | |
687 | |
688 public RedBranch(Object key, Node left, Node right){ | |
689 super(key); | |
690 this.left = left; | |
691 this.right = right; | |
692 } | |
693 | |
694 public Node left(){ | |
695 return left; | |
696 } | |
697 | |
698 public Node right(){ | |
699 return right; | |
700 } | |
701 | |
702 Node balanceLeft(Node parent){ | |
703 if(left instanceof Red) | |
704 return red(key, val(), left.blacken(), black(parent.key, parent.val(), right, parent.right())); | |
705 else if(right instanceof Red) | |
706 return red(right.key, right.val(), black(key, val(), left, right.left()), | |
707 black(parent.key, parent.val(), right.right(), parent.right())); | |
708 else | |
709 return super.balanceLeft(parent); | |
710 | |
711 } | |
712 | |
713 Node balanceRight(Node parent){ | |
714 if(right instanceof Red) | |
715 return red(key, val(), black(parent.key, parent.val(), parent.left(), left), right.blacken()); | |
716 else if(left instanceof Red) | |
717 return red(left.key, left.val(), black(parent.key, parent.val(), parent.left(), left.left()), | |
718 black(key, val(), left.right(), right)); | |
719 else | |
720 return super.balanceRight(parent); | |
721 } | |
722 | |
723 Node blacken(){ | |
724 return new BlackBranch(key, left, right); | |
725 } | |
726 | |
727 } | |
728 | |
729 | |
730 static class RedBranchVal extends RedBranch{ | |
731 final Object val; | |
732 | |
733 public RedBranchVal(Object key, Object val, Node left, Node right){ | |
734 super(key, left, right); | |
735 this.val = val; | |
736 } | |
737 | |
738 public Object val(){ | |
739 return val; | |
740 } | |
741 | |
742 Node blacken(){ | |
743 return new BlackBranchVal(key, val, left, right); | |
744 } | |
745 } | |
746 | |
747 | |
748 static public class Seq extends ASeq{ | |
749 final ISeq stack; | |
750 final boolean asc; | |
751 final int cnt; | |
752 | |
753 public Seq(ISeq stack, boolean asc){ | |
754 this.stack = stack; | |
755 this.asc = asc; | |
756 this.cnt = -1; | |
757 } | |
758 | |
759 public Seq(ISeq stack, boolean asc, int cnt){ | |
760 this.stack = stack; | |
761 this.asc = asc; | |
762 this.cnt = cnt; | |
763 } | |
764 | |
765 Seq(IPersistentMap meta, ISeq stack, boolean asc, int cnt){ | |
766 super(meta); | |
767 this.stack = stack; | |
768 this.asc = asc; | |
769 this.cnt = cnt; | |
770 } | |
771 | |
772 static Seq create(Node t, boolean asc, int cnt){ | |
773 return new Seq(push(t, null, asc), asc, cnt); | |
774 } | |
775 | |
776 static ISeq push(Node t, ISeq stack, boolean asc){ | |
777 while(t != null) | |
778 { | |
779 stack = RT.cons(t, stack); | |
780 t = asc ? t.left() : t.right(); | |
781 } | |
782 return stack; | |
783 } | |
784 | |
785 public Object first(){ | |
786 return stack.first(); | |
787 } | |
788 | |
789 public ISeq next(){ | |
790 Node t = (Node) stack.first(); | |
791 ISeq nextstack = push(asc ? t.right() : t.left(), stack.next(), asc); | |
792 if(nextstack != null) | |
793 { | |
794 return new Seq(nextstack, asc, cnt - 1); | |
795 } | |
796 return null; | |
797 } | |
798 | |
799 public int count(){ | |
800 if(cnt < 0) | |
801 return super.count(); | |
802 return cnt; | |
803 } | |
804 | |
805 public Obj withMeta(IPersistentMap meta){ | |
806 return new Seq(meta, stack, asc, cnt); | |
807 } | |
808 } | |
809 | |
810 static public class NodeIterator implements Iterator{ | |
811 Stack stack = new Stack(); | |
812 boolean asc; | |
813 | |
814 NodeIterator(Node t, boolean asc){ | |
815 this.asc = asc; | |
816 push(t); | |
817 } | |
818 | |
819 void push(Node t){ | |
820 while(t != null) | |
821 { | |
822 stack.push(t); | |
823 t = asc ? t.left() : t.right(); | |
824 } | |
825 } | |
826 | |
827 public boolean hasNext(){ | |
828 return !stack.isEmpty(); | |
829 } | |
830 | |
831 public Object next(){ | |
832 Node t = (Node) stack.pop(); | |
833 push(asc ? t.right() : t.left()); | |
834 return t; | |
835 } | |
836 | |
837 public void remove(){ | |
838 throw new UnsupportedOperationException(); | |
839 } | |
840 } | |
841 | |
842 static class KeyIterator implements Iterator{ | |
843 NodeIterator it; | |
844 | |
845 KeyIterator(NodeIterator it){ | |
846 this.it = it; | |
847 } | |
848 | |
849 public boolean hasNext(){ | |
850 return it.hasNext(); | |
851 } | |
852 | |
853 public Object next(){ | |
854 return ((Node) it.next()).key; | |
855 } | |
856 | |
857 public void remove(){ | |
858 throw new UnsupportedOperationException(); | |
859 } | |
860 } | |
861 | |
862 static class ValIterator implements Iterator{ | |
863 NodeIterator it; | |
864 | |
865 ValIterator(NodeIterator it){ | |
866 this.it = it; | |
867 } | |
868 | |
869 public boolean hasNext(){ | |
870 return it.hasNext(); | |
871 } | |
872 | |
873 public Object next(){ | |
874 return ((Node) it.next()).val(); | |
875 } | |
876 | |
877 public void remove(){ | |
878 throw new UnsupportedOperationException(); | |
879 } | |
880 } | |
881 /* | |
882 static public void main(String args[]){ | |
883 if(args.length != 1) | |
884 System.err.println("Usage: RBTree n"); | |
885 int n = Integer.parseInt(args[0]); | |
886 Integer[] ints = new Integer[n]; | |
887 for(int i = 0; i < ints.length; i++) | |
888 { | |
889 ints[i] = i; | |
890 } | |
891 Collections.shuffle(Arrays.asList(ints)); | |
892 //force the ListMap class loading now | |
893 // try | |
894 // { | |
895 // | |
896 // //PersistentListMap.EMPTY.assocEx(1, null).assocEx(2,null).assocEx(3,null); | |
897 // } | |
898 // catch(Exception e) | |
899 // { | |
900 // e.printStackTrace(); //To change body of catch statement use File | Settings | File Templates. | |
901 // } | |
902 System.out.println("Building set"); | |
903 //IPersistentMap set = new PersistentArrayMap(); | |
904 //IPersistentMap set = new PersistentHashtableMap(1001); | |
905 IPersistentMap set = PersistentHashMap.EMPTY; | |
906 //IPersistentMap set = new ListMap(); | |
907 //IPersistentMap set = new ArrayMap(); | |
908 //IPersistentMap set = new PersistentTreeMap(); | |
909 // for(int i = 0; i < ints.length; i++) | |
910 // { | |
911 // Integer anInt = ints[i]; | |
912 // set = set.add(anInt); | |
913 // } | |
914 long startTime = System.nanoTime(); | |
915 for(Integer anInt : ints) | |
916 { | |
917 set = set.assoc(anInt, anInt); | |
918 } | |
919 //System.out.println("_count = " + set.count()); | |
920 | |
921 // System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey() | |
922 // + ", depth: " + set.depth()); | |
923 for(Object aSet : set) | |
924 { | |
925 IMapEntry o = (IMapEntry) aSet; | |
926 if(!set.contains(o.key())) | |
927 System.err.println("Can't find: " + o.key()); | |
928 //else if(n < 2000) | |
929 // System.out.print(o.key().toString() + ","); | |
930 } | |
931 | |
932 Random rand = new Random(42); | |
933 for(int i = 0; i < ints.length / 2; i++) | |
934 { | |
935 Integer anInt = ints[rand.nextInt(n)]; | |
936 set = set.without(anInt); | |
937 } | |
938 | |
939 long estimatedTime = System.nanoTime() - startTime; | |
940 System.out.println(); | |
941 | |
942 System.out.println("_count = " + set.count() + ", time: " + estimatedTime / 1000000); | |
943 | |
944 System.out.println("Building ht"); | |
945 Hashtable ht = new Hashtable(1001); | |
946 startTime = System.nanoTime(); | |
947 // for(int i = 0; i < ints.length; i++) | |
948 // { | |
949 // Integer anInt = ints[i]; | |
950 // ht.put(anInt,null); | |
951 // } | |
952 for(Integer anInt : ints) | |
953 { | |
954 ht.put(anInt, anInt); | |
955 } | |
956 //System.out.println("size = " + ht.size()); | |
957 //Iterator it = ht.entrySet().iterator(); | |
958 for(Object o1 : ht.entrySet()) | |
959 { | |
960 Map.Entry o = (Map.Entry) o1; | |
961 if(!ht.containsKey(o.getKey())) | |
962 System.err.println("Can't find: " + o); | |
963 //else if(n < 2000) | |
964 // System.out.print(o.toString() + ","); | |
965 } | |
966 | |
967 rand = new Random(42); | |
968 for(int i = 0; i < ints.length / 2; i++) | |
969 { | |
970 Integer anInt = ints[rand.nextInt(n)]; | |
971 ht.remove(anInt); | |
972 } | |
973 estimatedTime = System.nanoTime() - startTime; | |
974 System.out.println(); | |
975 System.out.println("size = " + ht.size() + ", time: " + estimatedTime / 1000000); | |
976 | |
977 System.out.println("set lookup"); | |
978 startTime = System.nanoTime(); | |
979 int c = 0; | |
980 for(Integer anInt : ints) | |
981 { | |
982 if(!set.contains(anInt)) | |
983 ++c; | |
984 } | |
985 estimatedTime = System.nanoTime() - startTime; | |
986 System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); | |
987 | |
988 System.out.println("ht lookup"); | |
989 startTime = System.nanoTime(); | |
990 c = 0; | |
991 for(Integer anInt : ints) | |
992 { | |
993 if(!ht.containsKey(anInt)) | |
994 ++c; | |
995 } | |
996 estimatedTime = System.nanoTime() - startTime; | |
997 System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); | |
998 | |
999 // System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey() | |
1000 // + ", depth: " + set.depth()); | |
1001 } | |
1002 */ | |
1003 } |