1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/lang/PersistentTreeMap.java	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,1003 @@
     1.4 +/**
     1.5 + *   Copyright (c) Rich Hickey. All rights reserved.
     1.6 + *   The use and distribution terms for this software are covered by the
     1.7 + *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
     1.8 + *   which can be found in the file epl-v10.html at the root of this distribution.
     1.9 + *   By using this software in any fashion, you are agreeing to be bound by
    1.10 + * 	 the terms of this license.
    1.11 + *   You must not remove this notice, or any other, from this software.
    1.12 + **/
    1.13 +
    1.14 +/* rich May 20, 2006 */
    1.15 +
    1.16 +package clojure.lang;
    1.17 +
    1.18 +import java.util.*;
    1.19 +
    1.20 +/**
    1.21 + * Persistent Red Black Tree
    1.22 + * Note that instances of this class are constant values
    1.23 + * i.e. add/remove etc return new values
    1.24 + * <p/>
    1.25 + * See Okasaki, Kahrs, Larsen et al
    1.26 + */
    1.27 +
    1.28 +public class PersistentTreeMap extends APersistentMap implements IObj, Reversible, Sorted{
    1.29 +
    1.30 +public final Comparator comp;
    1.31 +public final Node tree;
    1.32 +public final int _count;
    1.33 +final IPersistentMap _meta;
    1.34 +
    1.35 +final static public PersistentTreeMap EMPTY = new PersistentTreeMap();
    1.36 +
    1.37 +static public IPersistentMap create(Map other){
    1.38 +	IPersistentMap ret = EMPTY;
    1.39 +	for(Object o : other.entrySet())
    1.40 +		{
    1.41 +		Map.Entry e = (Entry) o;
    1.42 +		ret = ret.assoc(e.getKey(), e.getValue());
    1.43 +		}
    1.44 +	return ret;
    1.45 +}
    1.46 +
    1.47 +public PersistentTreeMap(){
    1.48 +	this(RT.DEFAULT_COMPARATOR);
    1.49 +}
    1.50 +
    1.51 +public PersistentTreeMap withMeta(IPersistentMap meta){
    1.52 +	return new PersistentTreeMap(meta, comp, tree, _count);
    1.53 +}
    1.54 +
    1.55 +private PersistentTreeMap(Comparator comp){
    1.56 +	this(null, comp);
    1.57 +}
    1.58 +
    1.59 +
    1.60 +public PersistentTreeMap(IPersistentMap meta, Comparator comp){
    1.61 +	this.comp = comp;
    1.62 +	this._meta = meta;
    1.63 +	tree = null;
    1.64 +	_count = 0;
    1.65 +}
    1.66 +
    1.67 +PersistentTreeMap(IPersistentMap meta, Comparator comp, Node tree, int _count){
    1.68 +	this._meta = meta;
    1.69 +	this.comp = comp;
    1.70 +	this.tree = tree;
    1.71 +	this._count = _count;
    1.72 +}
    1.73 +
    1.74 +static public PersistentTreeMap create(ISeq items){
    1.75 +	IPersistentMap ret = EMPTY;
    1.76 +	for(; items != null; items = items.next().next())
    1.77 +		{
    1.78 +		if(items.next() == null)
    1.79 +			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));
    1.80 +		ret = ret.assoc(items.first(), RT.second(items));
    1.81 +		}
    1.82 +	return (PersistentTreeMap) ret;
    1.83 +}
    1.84 +
    1.85 +static public PersistentTreeMap create(Comparator comp, ISeq items){
    1.86 +	IPersistentMap ret = new PersistentTreeMap(comp);
    1.87 +	for(; items != null; items = items.next().next())
    1.88 +		{
    1.89 +		if(items.next() == null)
    1.90 +			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));
    1.91 +		ret = ret.assoc(items.first(), RT.second(items));
    1.92 +		}
    1.93 +	return (PersistentTreeMap) ret;
    1.94 +}
    1.95 +
    1.96 +public boolean containsKey(Object key){
    1.97 +	return entryAt(key) != null;
    1.98 +}
    1.99 +
   1.100 +public PersistentTreeMap assocEx(Object key, Object val) throws Exception{
   1.101 +	Box found = new Box(null);
   1.102 +	Node t = add(tree, key, val, found);
   1.103 +	if(t == null)   //null == already contains key
   1.104 +		{
   1.105 +		throw new Exception("Key already present");
   1.106 +		}
   1.107 +	return new PersistentTreeMap(comp, t.blacken(), _count + 1, meta());
   1.108 +}
   1.109 +
   1.110 +public PersistentTreeMap assoc(Object key, Object val){
   1.111 +	Box found = new Box(null);
   1.112 +	Node t = add(tree, key, val, found);
   1.113 +	if(t == null)   //null == already contains key
   1.114 +		{
   1.115 +		Node foundNode = (Node) found.val;
   1.116 +		if(foundNode.val() == val)  //note only get same collection on identity of val, not equals()
   1.117 +			return this;
   1.118 +		return new PersistentTreeMap(comp, replace(tree, key, val), _count, meta());
   1.119 +		}
   1.120 +	return new PersistentTreeMap(comp, t.blacken(), _count + 1, meta());
   1.121 +}
   1.122 +
   1.123 +
   1.124 +public PersistentTreeMap without(Object key){
   1.125 +	Box found = new Box(null);
   1.126 +	Node t = remove(tree, key, found);
   1.127 +	if(t == null)
   1.128 +		{
   1.129 +		if(found.val == null)//null == doesn't contain key
   1.130 +			return this;
   1.131 +		//empty
   1.132 +		return new PersistentTreeMap(meta(), comp);
   1.133 +		}
   1.134 +	return new PersistentTreeMap(comp, t.blacken(), _count - 1, meta());
   1.135 +}
   1.136 +
   1.137 +public ISeq seq(){
   1.138 +	if(_count > 0)
   1.139 +		return Seq.create(tree, true, _count);
   1.140 +	return null;
   1.141 +}
   1.142 +
   1.143 +public IPersistentCollection empty(){
   1.144 +	return new PersistentTreeMap(meta(), comp);	
   1.145 +}
   1.146 +
   1.147 +public ISeq rseq() throws Exception{
   1.148 +	if(_count > 0)
   1.149 +		return Seq.create(tree, false, _count);
   1.150 +	return null;
   1.151 +}
   1.152 +
   1.153 +public Comparator comparator(){
   1.154 +	return comp;
   1.155 +}
   1.156 +
   1.157 +public Object entryKey(Object entry){
   1.158 +	return ((IMapEntry) entry).key();
   1.159 +}
   1.160 +
   1.161 +public ISeq seq(boolean ascending){
   1.162 +	if(_count > 0)
   1.163 +		return Seq.create(tree, ascending, _count);
   1.164 +	return null;
   1.165 +}
   1.166 +
   1.167 +public ISeq seqFrom(Object key, boolean ascending){
   1.168 +	if(_count > 0)
   1.169 +		{
   1.170 +		ISeq stack = null;
   1.171 +		Node t = tree;
   1.172 +		while(t != null)
   1.173 +			{
   1.174 +			int c = doCompare(key, t.key);
   1.175 +			if(c == 0)
   1.176 +				{
   1.177 +				stack = RT.cons(t, stack);
   1.178 +				return new Seq(stack, ascending);
   1.179 +				}
   1.180 +			else if(ascending)
   1.181 +				{
   1.182 +				if(c < 0)
   1.183 +					{
   1.184 +					stack = RT.cons(t, stack);
   1.185 +					t = t.left();
   1.186 +					}
   1.187 +				else
   1.188 +					t = t.right();
   1.189 +				}
   1.190 +			else
   1.191 +				{
   1.192 +				if(c > 0)
   1.193 +					{
   1.194 +					stack = RT.cons(t, stack);
   1.195 +					t = t.right();
   1.196 +					}
   1.197 +				else
   1.198 +					t = t.left();
   1.199 +				}
   1.200 +			}
   1.201 +		if(stack != null)
   1.202 +			return new Seq(stack, ascending);
   1.203 +		}
   1.204 +	return null;
   1.205 +}
   1.206 +
   1.207 +public NodeIterator iterator(){
   1.208 +	return new NodeIterator(tree, true);
   1.209 +}
   1.210 +
   1.211 +public NodeIterator reverseIterator(){
   1.212 +	return new NodeIterator(tree, false);
   1.213 +}
   1.214 +
   1.215 +public Iterator keys(){
   1.216 +	return keys(iterator());
   1.217 +}
   1.218 +
   1.219 +public Iterator vals(){
   1.220 +	return vals(iterator());
   1.221 +}
   1.222 +
   1.223 +public Iterator keys(NodeIterator it){
   1.224 +	return new KeyIterator(it);
   1.225 +}
   1.226 +
   1.227 +public Iterator vals(NodeIterator it){
   1.228 +	return new ValIterator(it);
   1.229 +}
   1.230 +
   1.231 +public Object minKey(){
   1.232 +	Node t = min();
   1.233 +	return t != null ? t.key : null;
   1.234 +}
   1.235 +
   1.236 +public Node min(){
   1.237 +	Node t = tree;
   1.238 +	if(t != null)
   1.239 +		{
   1.240 +		while(t.left() != null)
   1.241 +			t = t.left();
   1.242 +		}
   1.243 +	return t;
   1.244 +}
   1.245 +
   1.246 +public Object maxKey(){
   1.247 +	Node t = max();
   1.248 +	return t != null ? t.key : null;
   1.249 +}
   1.250 +
   1.251 +public Node max(){
   1.252 +	Node t = tree;
   1.253 +	if(t != null)
   1.254 +		{
   1.255 +		while(t.right() != null)
   1.256 +			t = t.right();
   1.257 +		}
   1.258 +	return t;
   1.259 +}
   1.260 +
   1.261 +public int depth(){
   1.262 +	return depth(tree);
   1.263 +}
   1.264 +
   1.265 +int depth(Node t){
   1.266 +	if(t == null)
   1.267 +		return 0;
   1.268 +	return 1 + Math.max(depth(t.left()), depth(t.right()));
   1.269 +}
   1.270 +
   1.271 +public Object valAt(Object key, Object notFound){
   1.272 +	Node n = entryAt(key);
   1.273 +	return (n != null) ? n.val() : notFound;
   1.274 +}
   1.275 +
   1.276 +public Object valAt(Object key){
   1.277 +	return valAt(key, null);
   1.278 +}
   1.279 +
   1.280 +public int capacity(){
   1.281 +	return _count;
   1.282 +}
   1.283 +
   1.284 +public int count(){
   1.285 +	return _count;
   1.286 +}
   1.287 +
   1.288 +public Node entryAt(Object key){
   1.289 +	Node t = tree;
   1.290 +	while(t != null)
   1.291 +		{
   1.292 +		int c = doCompare(key, t.key);
   1.293 +		if(c == 0)
   1.294 +			return t;
   1.295 +		else if(c < 0)
   1.296 +			t = t.left();
   1.297 +		else
   1.298 +			t = t.right();
   1.299 +		}
   1.300 +	return t;
   1.301 +}
   1.302 +
   1.303 +public int doCompare(Object k1, Object k2){
   1.304 +//	if(comp != null)
   1.305 +		return comp.compare(k1, k2);
   1.306 +//	return ((Comparable) k1).compareTo(k2);
   1.307 +}
   1.308 +
   1.309 +Node add(Node t, Object key, Object val, Box found){
   1.310 +	if(t == null)
   1.311 +		{
   1.312 +		if(val == null)
   1.313 +			return new Red(key);
   1.314 +		return new RedVal(key, val);
   1.315 +		}
   1.316 +	int c = doCompare(key, t.key);
   1.317 +	if(c == 0)
   1.318 +		{
   1.319 +		found.val = t;
   1.320 +		return null;
   1.321 +		}
   1.322 +	Node ins = c < 0 ? add(t.left(), key, val, found) : add(t.right(), key, val, found);
   1.323 +	if(ins == null) //found below
   1.324 +		return null;
   1.325 +	if(c < 0)
   1.326 +		return t.addLeft(ins);
   1.327 +	return t.addRight(ins);
   1.328 +}
   1.329 +
   1.330 +Node remove(Node t, Object key, Box found){
   1.331 +	if(t == null)
   1.332 +		return null; //not found indicator
   1.333 +	int c = doCompare(key, t.key);
   1.334 +	if(c == 0)
   1.335 +		{
   1.336 +		found.val = t;
   1.337 +		return append(t.left(), t.right());
   1.338 +		}
   1.339 +	Node del = c < 0 ? remove(t.left(), key, found) : remove(t.right(), key, found);
   1.340 +	if(del == null && found.val == null) //not found below
   1.341 +		return null;
   1.342 +	if(c < 0)
   1.343 +		{
   1.344 +		if(t.left() instanceof Black)
   1.345 +			return balanceLeftDel(t.key, t.val(), del, t.right());
   1.346 +		else
   1.347 +			return red(t.key, t.val(), del, t.right());
   1.348 +		}
   1.349 +	if(t.right() instanceof Black)
   1.350 +		return balanceRightDel(t.key, t.val(), t.left(), del);
   1.351 +	return red(t.key, t.val(), t.left(), del);
   1.352 +//		return t.removeLeft(del);
   1.353 +//	return t.removeRight(del);
   1.354 +}
   1.355 +
   1.356 +static Node append(Node left, Node right){
   1.357 +	if(left == null)
   1.358 +		return right;
   1.359 +	else if(right == null)
   1.360 +		return left;
   1.361 +	else if(left instanceof Red)
   1.362 +		{
   1.363 +		if(right instanceof Red)
   1.364 +			{
   1.365 +			Node app = append(left.right(), right.left());
   1.366 +			if(app instanceof Red)
   1.367 +				return red(app.key, app.val(),
   1.368 +				           red(left.key, left.val(), left.left(), app.left()),
   1.369 +				           red(right.key, right.val(), app.right(), right.right()));
   1.370 +			else
   1.371 +				return red(left.key, left.val(), left.left(), red(right.key, right.val(), app, right.right()));
   1.372 +			}
   1.373 +		else
   1.374 +			return red(left.key, left.val(), left.left(), append(left.right(), right));
   1.375 +		}
   1.376 +	else if(right instanceof Red)
   1.377 +		return red(right.key, right.val(), append(left, right.left()), right.right());
   1.378 +	else //black/black
   1.379 +		{
   1.380 +		Node app = append(left.right(), right.left());
   1.381 +		if(app instanceof Red)
   1.382 +			return red(app.key, app.val(),
   1.383 +			           black(left.key, left.val(), left.left(), app.left()),
   1.384 +			           black(right.key, right.val(), app.right(), right.right()));
   1.385 +		else
   1.386 +			return balanceLeftDel(left.key, left.val(), left.left(), black(right.key, right.val(), app, right.right()));
   1.387 +		}
   1.388 +}
   1.389 +
   1.390 +static Node balanceLeftDel(Object key, Object val, Node del, Node right){
   1.391 +	if(del instanceof Red)
   1.392 +		return red(key, val, del.blacken(), right);
   1.393 +	else if(right instanceof Black)
   1.394 +		return rightBalance(key, val, del, right.redden());
   1.395 +	else if(right instanceof Red && right.left() instanceof Black)
   1.396 +		return red(right.left().key, right.left().val(),
   1.397 +		           black(key, val, del, right.left().left()),
   1.398 +		           rightBalance(right.key, right.val(), right.left().right(), right.right().redden()));
   1.399 +	else
   1.400 +		throw new UnsupportedOperationException("Invariant violation");
   1.401 +}
   1.402 +
   1.403 +static Node balanceRightDel(Object key, Object val, Node left, Node del){
   1.404 +	if(del instanceof Red)
   1.405 +		return red(key, val, left, del.blacken());
   1.406 +	else if(left instanceof Black)
   1.407 +		return leftBalance(key, val, left.redden(), del);
   1.408 +	else if(left instanceof Red && left.right() instanceof Black)
   1.409 +		return red(left.right().key, left.right().val(),
   1.410 +		           leftBalance(left.key, left.val(), left.left().redden(), left.right().left()),
   1.411 +		           black(key, val, left.right().right(), del));
   1.412 +	else
   1.413 +		throw new UnsupportedOperationException("Invariant violation");
   1.414 +}
   1.415 +
   1.416 +static Node leftBalance(Object key, Object val, Node ins, Node right){
   1.417 +	if(ins instanceof Red && ins.left() instanceof Red)
   1.418 +		return red(ins.key, ins.val(), ins.left().blacken(), black(key, val, ins.right(), right));
   1.419 +	else if(ins instanceof Red && ins.right() instanceof Red)
   1.420 +		return red(ins.right().key, ins.right().val(),
   1.421 +		           black(ins.key, ins.val(), ins.left(), ins.right().left()),
   1.422 +		           black(key, val, ins.right().right(), right));
   1.423 +	else
   1.424 +		return black(key, val, ins, right);
   1.425 +}
   1.426 +
   1.427 +
   1.428 +static Node rightBalance(Object key, Object val, Node left, Node ins){
   1.429 +	if(ins instanceof Red && ins.right() instanceof Red)
   1.430 +		return red(ins.key, ins.val(), black(key, val, left, ins.left()), ins.right().blacken());
   1.431 +	else if(ins instanceof Red && ins.left() instanceof Red)
   1.432 +		return red(ins.left().key, ins.left().val(),
   1.433 +		           black(key, val, left, ins.left().left()),
   1.434 +		           black(ins.key, ins.val(), ins.left().right(), ins.right()));
   1.435 +	else
   1.436 +		return black(key, val, left, ins);
   1.437 +}
   1.438 +
   1.439 +Node replace(Node t, Object key, Object val){
   1.440 +	int c = doCompare(key, t.key);
   1.441 +	return t.replace(t.key,
   1.442 +	                 c == 0 ? val : t.val(),
   1.443 +	                 c < 0 ? replace(t.left(), key, val) : t.left(),
   1.444 +	                 c > 0 ? replace(t.right(), key, val) : t.right());
   1.445 +}
   1.446 +
   1.447 +PersistentTreeMap(Comparator comp, Node tree, int count, IPersistentMap meta){
   1.448 +	this._meta = meta;
   1.449 +	this.comp = comp;
   1.450 +	this.tree = tree;
   1.451 +	this._count = count;
   1.452 +}
   1.453 +
   1.454 +static Red red(Object key, Object val, Node left, Node right){
   1.455 +	if(left == null && right == null)
   1.456 +		{
   1.457 +		if(val == null)
   1.458 +			return new Red(key);
   1.459 +		return new RedVal(key, val);
   1.460 +		}
   1.461 +	if(val == null)
   1.462 +		return new RedBranch(key, left, right);
   1.463 +	return new RedBranchVal(key, val, left, right);
   1.464 +}
   1.465 +
   1.466 +static Black black(Object key, Object val, Node left, Node right){
   1.467 +	if(left == null && right == null)
   1.468 +		{
   1.469 +		if(val == null)
   1.470 +			return new Black(key);
   1.471 +		return new BlackVal(key, val);
   1.472 +		}
   1.473 +	if(val == null)
   1.474 +		return new BlackBranch(key, left, right);
   1.475 +	return new BlackBranchVal(key, val, left, right);
   1.476 +}
   1.477 +
   1.478 +public IPersistentMap meta(){
   1.479 +	return _meta;
   1.480 +}
   1.481 +
   1.482 +static abstract class Node extends AMapEntry{
   1.483 +	final Object key;
   1.484 +
   1.485 +	Node(Object key){
   1.486 +		this.key = key;
   1.487 +	}
   1.488 +
   1.489 +	public Object key(){
   1.490 +		return key;
   1.491 +	}
   1.492 +
   1.493 +	public Object val(){
   1.494 +		return null;
   1.495 +	}
   1.496 +
   1.497 +	public Object getKey(){
   1.498 +		return key();
   1.499 +	}
   1.500 +
   1.501 +	public Object getValue(){
   1.502 +		return val();
   1.503 +	}
   1.504 +
   1.505 +	Node left(){
   1.506 +		return null;
   1.507 +	}
   1.508 +
   1.509 +	Node right(){
   1.510 +		return null;
   1.511 +	}
   1.512 +
   1.513 +	abstract Node addLeft(Node ins);
   1.514 +
   1.515 +	abstract Node addRight(Node ins);
   1.516 +
   1.517 +	abstract Node removeLeft(Node del);
   1.518 +
   1.519 +	abstract Node removeRight(Node del);
   1.520 +
   1.521 +	abstract Node blacken();
   1.522 +
   1.523 +	abstract Node redden();
   1.524 +
   1.525 +	Node balanceLeft(Node parent){
   1.526 +		return black(parent.key, parent.val(), this, parent.right());
   1.527 +	}
   1.528 +
   1.529 +	Node balanceRight(Node parent){
   1.530 +		return black(parent.key, parent.val(), parent.left(), this);
   1.531 +	}
   1.532 +
   1.533 +	abstract Node replace(Object key, Object val, Node left, Node right);
   1.534 +
   1.535 +}
   1.536 +
   1.537 +static class Black extends Node{
   1.538 +	public Black(Object key){
   1.539 +		super(key);
   1.540 +	}
   1.541 +
   1.542 +	Node addLeft(Node ins){
   1.543 +		return ins.balanceLeft(this);
   1.544 +	}
   1.545 +
   1.546 +	Node addRight(Node ins){
   1.547 +		return ins.balanceRight(this);
   1.548 +	}
   1.549 +
   1.550 +	Node removeLeft(Node del){
   1.551 +		return balanceLeftDel(key, val(), del, right());
   1.552 +	}
   1.553 +
   1.554 +	Node removeRight(Node del){
   1.555 +		return balanceRightDel(key, val(), left(), del);
   1.556 +	}
   1.557 +
   1.558 +	Node blacken(){
   1.559 +		return this;
   1.560 +	}
   1.561 +
   1.562 +	Node redden(){
   1.563 +		return new Red(key);
   1.564 +	}
   1.565 +
   1.566 +	Node replace(Object key, Object val, Node left, Node right){
   1.567 +		return black(key, val, left, right);
   1.568 +	}
   1.569 +
   1.570 +}
   1.571 +
   1.572 +static class BlackVal extends Black{
   1.573 +	final Object val;
   1.574 +
   1.575 +	public BlackVal(Object key, Object val){
   1.576 +		super(key);
   1.577 +		this.val = val;
   1.578 +	}
   1.579 +
   1.580 +	public Object val(){
   1.581 +		return val;
   1.582 +	}
   1.583 +
   1.584 +	Node redden(){
   1.585 +		return new RedVal(key, val);
   1.586 +	}
   1.587 +
   1.588 +}
   1.589 +
   1.590 +static class BlackBranch extends Black{
   1.591 +	final Node left;
   1.592 +
   1.593 +	final Node right;
   1.594 +
   1.595 +	public BlackBranch(Object key, Node left, Node right){
   1.596 +		super(key);
   1.597 +		this.left = left;
   1.598 +		this.right = right;
   1.599 +	}
   1.600 +
   1.601 +	public Node left(){
   1.602 +		return left;
   1.603 +	}
   1.604 +
   1.605 +	public Node right(){
   1.606 +		return right;
   1.607 +	}
   1.608 +
   1.609 +	Node redden(){
   1.610 +		return new RedBranch(key, left, right);
   1.611 +	}
   1.612 +
   1.613 +}
   1.614 +
   1.615 +static class BlackBranchVal extends BlackBranch{
   1.616 +	final Object val;
   1.617 +
   1.618 +	public BlackBranchVal(Object key, Object val, Node left, Node right){
   1.619 +		super(key, left, right);
   1.620 +		this.val = val;
   1.621 +	}
   1.622 +
   1.623 +	public Object val(){
   1.624 +		return val;
   1.625 +	}
   1.626 +
   1.627 +	Node redden(){
   1.628 +		return new RedBranchVal(key, val, left, right);
   1.629 +	}
   1.630 +
   1.631 +}
   1.632 +
   1.633 +static class Red extends Node{
   1.634 +	public Red(Object key){
   1.635 +		super(key);
   1.636 +	}
   1.637 +
   1.638 +	Node addLeft(Node ins){
   1.639 +		return red(key, val(), ins, right());
   1.640 +	}
   1.641 +
   1.642 +	Node addRight(Node ins){
   1.643 +		return red(key, val(), left(), ins);
   1.644 +	}
   1.645 +
   1.646 +	Node removeLeft(Node del){
   1.647 +		return red(key, val(), del, right());
   1.648 +	}
   1.649 +
   1.650 +	Node removeRight(Node del){
   1.651 +		return red(key, val(), left(), del);
   1.652 +	}
   1.653 +
   1.654 +	Node blacken(){
   1.655 +		return new Black(key);
   1.656 +	}
   1.657 +
   1.658 +	Node redden(){
   1.659 +		throw new UnsupportedOperationException("Invariant violation");
   1.660 +	}
   1.661 +
   1.662 +	Node replace(Object key, Object val, Node left, Node right){
   1.663 +		return red(key, val, left, right);
   1.664 +	}
   1.665 +
   1.666 +}
   1.667 +
   1.668 +static class RedVal extends Red{
   1.669 +	final Object val;
   1.670 +
   1.671 +	public RedVal(Object key, Object val){
   1.672 +		super(key);
   1.673 +		this.val = val;
   1.674 +	}
   1.675 +
   1.676 +	public Object val(){
   1.677 +		return val;
   1.678 +	}
   1.679 +
   1.680 +	Node blacken(){
   1.681 +		return new BlackVal(key, val);
   1.682 +	}
   1.683 +
   1.684 +}
   1.685 +
   1.686 +static class RedBranch extends Red{
   1.687 +	final Node left;
   1.688 +
   1.689 +	final Node right;
   1.690 +
   1.691 +	public RedBranch(Object key, Node left, Node right){
   1.692 +		super(key);
   1.693 +		this.left = left;
   1.694 +		this.right = right;
   1.695 +	}
   1.696 +
   1.697 +	public Node left(){
   1.698 +		return left;
   1.699 +	}
   1.700 +
   1.701 +	public Node right(){
   1.702 +		return right;
   1.703 +	}
   1.704 +
   1.705 +	Node balanceLeft(Node parent){
   1.706 +		if(left instanceof Red)
   1.707 +			return red(key, val(), left.blacken(), black(parent.key, parent.val(), right, parent.right()));
   1.708 +		else if(right instanceof Red)
   1.709 +			return red(right.key, right.val(), black(key, val(), left, right.left()),
   1.710 +			           black(parent.key, parent.val(), right.right(), parent.right()));
   1.711 +		else
   1.712 +			return super.balanceLeft(parent);
   1.713 +
   1.714 +	}
   1.715 +
   1.716 +	Node balanceRight(Node parent){
   1.717 +		if(right instanceof Red)
   1.718 +			return red(key, val(), black(parent.key, parent.val(), parent.left(), left), right.blacken());
   1.719 +		else if(left instanceof Red)
   1.720 +			return red(left.key, left.val(), black(parent.key, parent.val(), parent.left(), left.left()),
   1.721 +			           black(key, val(), left.right(), right));
   1.722 +		else
   1.723 +			return super.balanceRight(parent);
   1.724 +	}
   1.725 +
   1.726 +	Node blacken(){
   1.727 +		return new BlackBranch(key, left, right);
   1.728 +	}
   1.729 +
   1.730 +}
   1.731 +
   1.732 +
   1.733 +static class RedBranchVal extends RedBranch{
   1.734 +	final Object val;
   1.735 +
   1.736 +	public RedBranchVal(Object key, Object val, Node left, Node right){
   1.737 +		super(key, left, right);
   1.738 +		this.val = val;
   1.739 +	}
   1.740 +
   1.741 +	public Object val(){
   1.742 +		return val;
   1.743 +	}
   1.744 +
   1.745 +	Node blacken(){
   1.746 +		return new BlackBranchVal(key, val, left, right);
   1.747 +	}
   1.748 +}
   1.749 +
   1.750 +
   1.751 +static public class Seq extends ASeq{
   1.752 +	final ISeq stack;
   1.753 +	final boolean asc;
   1.754 +	final int cnt;
   1.755 +
   1.756 +	public Seq(ISeq stack, boolean asc){
   1.757 +		this.stack = stack;
   1.758 +		this.asc = asc;
   1.759 +		this.cnt = -1;
   1.760 +	}
   1.761 +
   1.762 +	public Seq(ISeq stack, boolean asc, int cnt){
   1.763 +		this.stack = stack;
   1.764 +		this.asc = asc;
   1.765 +		this.cnt = cnt;
   1.766 +	}
   1.767 +
   1.768 +	Seq(IPersistentMap meta, ISeq stack, boolean asc, int cnt){
   1.769 +		super(meta);
   1.770 +		this.stack = stack;
   1.771 +		this.asc = asc;
   1.772 +		this.cnt = cnt;
   1.773 +	}
   1.774 +
   1.775 +	static Seq create(Node t, boolean asc, int cnt){
   1.776 +		return new Seq(push(t, null, asc), asc, cnt);
   1.777 +	}
   1.778 +
   1.779 +	static ISeq push(Node t, ISeq stack, boolean asc){
   1.780 +		while(t != null)
   1.781 +			{
   1.782 +			stack = RT.cons(t, stack);
   1.783 +			t = asc ? t.left() : t.right();
   1.784 +			}
   1.785 +		return stack;
   1.786 +	}
   1.787 +
   1.788 +	public Object first(){
   1.789 +		return stack.first();
   1.790 +	}
   1.791 +
   1.792 +	public ISeq next(){
   1.793 +		Node t = (Node) stack.first();
   1.794 +		ISeq nextstack = push(asc ? t.right() : t.left(), stack.next(), asc);
   1.795 +		if(nextstack != null)
   1.796 +			{
   1.797 +			return new Seq(nextstack, asc, cnt - 1);
   1.798 +			}
   1.799 +		return null;
   1.800 +	}
   1.801 +
   1.802 +	public int count(){
   1.803 +		if(cnt < 0)
   1.804 +			return super.count();
   1.805 +		return cnt;
   1.806 +	}
   1.807 +
   1.808 +	public Obj withMeta(IPersistentMap meta){
   1.809 +		return new Seq(meta, stack, asc, cnt);
   1.810 +	}
   1.811 +}
   1.812 +
   1.813 +static public class NodeIterator implements Iterator{
   1.814 +	Stack stack = new Stack();
   1.815 +	boolean asc;
   1.816 +
   1.817 +	NodeIterator(Node t, boolean asc){
   1.818 +		this.asc = asc;
   1.819 +		push(t);
   1.820 +	}
   1.821 +
   1.822 +	void push(Node t){
   1.823 +		while(t != null)
   1.824 +			{
   1.825 +			stack.push(t);
   1.826 +			t = asc ? t.left() : t.right();
   1.827 +			}
   1.828 +	}
   1.829 +
   1.830 +	public boolean hasNext(){
   1.831 +		return !stack.isEmpty();
   1.832 +	}
   1.833 +
   1.834 +	public Object next(){
   1.835 +		Node t = (Node) stack.pop();
   1.836 +		push(asc ? t.right() : t.left());
   1.837 +		return t;
   1.838 +	}
   1.839 +
   1.840 +	public void remove(){
   1.841 +		throw new UnsupportedOperationException();
   1.842 +	}
   1.843 +}
   1.844 +
   1.845 +static class KeyIterator implements Iterator{
   1.846 +	NodeIterator it;
   1.847 +
   1.848 +	KeyIterator(NodeIterator it){
   1.849 +		this.it = it;
   1.850 +	}
   1.851 +
   1.852 +	public boolean hasNext(){
   1.853 +		return it.hasNext();
   1.854 +	}
   1.855 +
   1.856 +	public Object next(){
   1.857 +		return ((Node) it.next()).key;
   1.858 +	}
   1.859 +
   1.860 +	public void remove(){
   1.861 +		throw new UnsupportedOperationException();
   1.862 +	}
   1.863 +}
   1.864 +
   1.865 +static class ValIterator implements Iterator{
   1.866 +	NodeIterator it;
   1.867 +
   1.868 +	ValIterator(NodeIterator it){
   1.869 +		this.it = it;
   1.870 +	}
   1.871 +
   1.872 +	public boolean hasNext(){
   1.873 +		return it.hasNext();
   1.874 +	}
   1.875 +
   1.876 +	public Object next(){
   1.877 +		return ((Node) it.next()).val();
   1.878 +	}
   1.879 +
   1.880 +	public void remove(){
   1.881 +		throw new UnsupportedOperationException();
   1.882 +	}
   1.883 +}
   1.884 +/*
   1.885 +static public void main(String args[]){
   1.886 +	if(args.length != 1)
   1.887 +		System.err.println("Usage: RBTree n");
   1.888 +	int n = Integer.parseInt(args[0]);
   1.889 +	Integer[] ints = new Integer[n];
   1.890 +	for(int i = 0; i < ints.length; i++)
   1.891 +		{
   1.892 +		ints[i] = i;
   1.893 +		}
   1.894 +	Collections.shuffle(Arrays.asList(ints));
   1.895 +	//force the ListMap class loading now
   1.896 +//	try
   1.897 +//		{
   1.898 +//
   1.899 +//		//PersistentListMap.EMPTY.assocEx(1, null).assocEx(2,null).assocEx(3,null);
   1.900 +//		}
   1.901 +//	catch(Exception e)
   1.902 +//		{
   1.903 +//		e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
   1.904 +//		}
   1.905 +	System.out.println("Building set");
   1.906 +	//IPersistentMap set = new PersistentArrayMap();
   1.907 +	//IPersistentMap set = new PersistentHashtableMap(1001);
   1.908 +	IPersistentMap set = PersistentHashMap.EMPTY;
   1.909 +	//IPersistentMap set = new ListMap();
   1.910 +	//IPersistentMap set = new ArrayMap();
   1.911 +	//IPersistentMap set = new PersistentTreeMap();
   1.912 +//	for(int i = 0; i < ints.length; i++)
   1.913 +//		{
   1.914 +//		Integer anInt = ints[i];
   1.915 +//		set = set.add(anInt);
   1.916 +//		}
   1.917 +	long startTime = System.nanoTime();
   1.918 +	for(Integer anInt : ints)
   1.919 +		{
   1.920 +		set = set.assoc(anInt, anInt);
   1.921 +		}
   1.922 +	//System.out.println("_count = " + set.count());
   1.923 +
   1.924 +//	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
   1.925 +//	                   + ", depth: " + set.depth());
   1.926 +	for(Object aSet : set)
   1.927 +		{
   1.928 +		IMapEntry o = (IMapEntry) aSet;
   1.929 +		if(!set.contains(o.key()))
   1.930 +			System.err.println("Can't find: " + o.key());
   1.931 +		//else if(n < 2000)
   1.932 +		//	System.out.print(o.key().toString() + ",");
   1.933 +		}
   1.934 +
   1.935 +	Random rand = new Random(42);
   1.936 +	for(int i = 0; i < ints.length / 2; i++)
   1.937 +		{
   1.938 +		Integer anInt = ints[rand.nextInt(n)];
   1.939 +		set = set.without(anInt);
   1.940 +		}
   1.941 +
   1.942 +	long estimatedTime = System.nanoTime() - startTime;
   1.943 +	System.out.println();
   1.944 +
   1.945 +	System.out.println("_count = " + set.count() + ", time: " + estimatedTime / 1000000);
   1.946 +
   1.947 +	System.out.println("Building ht");
   1.948 +	Hashtable ht = new Hashtable(1001);
   1.949 +	startTime = System.nanoTime();
   1.950 +//	for(int i = 0; i < ints.length; i++)
   1.951 +//		{
   1.952 +//		Integer anInt = ints[i];
   1.953 +//		ht.put(anInt,null);
   1.954 +//		}
   1.955 +	for(Integer anInt : ints)
   1.956 +		{
   1.957 +		ht.put(anInt, anInt);
   1.958 +		}
   1.959 +	//System.out.println("size = " + ht.size());
   1.960 +	//Iterator it = ht.entrySet().iterator();
   1.961 +	for(Object o1 : ht.entrySet())
   1.962 +		{
   1.963 +		Map.Entry o = (Map.Entry) o1;
   1.964 +		if(!ht.containsKey(o.getKey()))
   1.965 +			System.err.println("Can't find: " + o);
   1.966 +		//else if(n < 2000)
   1.967 +		//	System.out.print(o.toString() + ",");
   1.968 +		}
   1.969 +
   1.970 +	rand = new Random(42);
   1.971 +	for(int i = 0; i < ints.length / 2; i++)
   1.972 +		{
   1.973 +		Integer anInt = ints[rand.nextInt(n)];
   1.974 +		ht.remove(anInt);
   1.975 +		}
   1.976 +	estimatedTime = System.nanoTime() - startTime;
   1.977 +	System.out.println();
   1.978 +	System.out.println("size = " + ht.size() + ", time: " + estimatedTime / 1000000);
   1.979 +
   1.980 +	System.out.println("set lookup");
   1.981 +	startTime = System.nanoTime();
   1.982 +	int c = 0;
   1.983 +	for(Integer anInt : ints)
   1.984 +		{
   1.985 +		if(!set.contains(anInt))
   1.986 +			++c;
   1.987 +		}
   1.988 +	estimatedTime = System.nanoTime() - startTime;
   1.989 +	System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);
   1.990 +
   1.991 +	System.out.println("ht lookup");
   1.992 +	startTime = System.nanoTime();
   1.993 +	c = 0;
   1.994 +	for(Integer anInt : ints)
   1.995 +		{
   1.996 +		if(!ht.containsKey(anInt))
   1.997 +			++c;
   1.998 +		}
   1.999 +	estimatedTime = System.nanoTime() - startTime;
  1.1000 +	System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);
  1.1001 +
  1.1002 +//	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
  1.1003 +//	                   + ", depth: " + set.depth());
  1.1004 +}
  1.1005 +*/
  1.1006 +}