Mercurial > lasercutter

annotate src/clojure/lang/PersistentTreeMap.java @ 10:ef7dbbd6452c

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