/**

  *   Copyright (c) Rich Hickey. All rights reserved.

  *   The use and distribution terms for this software are covered by the

  *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)

  *   which can be found in the file epl-v10.html at the root of this distribution.

  *   By using this software in any fashion, you are agreeing to be bound by

  * 	 the terms of this license.

  *   You must not remove this notice, or any other, from this software.

  **/

 

 /* rich May 20, 2006 */

 

 package clojure.lang;

 

 import java.util.*;

 

 /**

  * Persistent Red Black Tree

  * Note that instances of this class are constant values

  * i.e. add/remove etc return new values

  * <p/>

  * See Okasaki, Kahrs, Larsen et al

  */

 

 public class PersistentTreeMap extends APersistentMap implements IObj, Reversible, Sorted{

 

 public final Comparator comp;

 public final Node tree;

 public final int _count;

 final IPersistentMap _meta;

 

 final static public PersistentTreeMap EMPTY = new PersistentTreeMap();

 

 static public IPersistentMap create(Map other){

 	IPersistentMap ret = EMPTY;

 	for(Object o : other.entrySet())

 		{

 		Map.Entry e = (Entry) o;

 		ret = ret.assoc(e.getKey(), e.getValue());

 		}

 	return ret;

 }

 

 public PersistentTreeMap(){

 	this(RT.DEFAULT_COMPARATOR);

 }

 

 public PersistentTreeMap withMeta(IPersistentMap meta){

 	return new PersistentTreeMap(meta, comp, tree, _count);

 }

 

 private PersistentTreeMap(Comparator comp){

 	this(null, comp);

 }

 

 

 public PersistentTreeMap(IPersistentMap meta, Comparator comp){

 	this.comp = comp;

 	this._meta = meta;

 	tree = null;

 	_count = 0;

 }

 

 PersistentTreeMap(IPersistentMap meta, Comparator comp, Node tree, int _count){

 	this._meta = meta;

 	this.comp = comp;

 	this.tree = tree;

 	this._count = _count;

 }

 

 static public PersistentTreeMap create(ISeq items){

 	IPersistentMap ret = EMPTY;

 	for(; items != null; items = items.next().next())

 		{

 		if(items.next() == null)

 			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));

 		ret = ret.assoc(items.first(), RT.second(items));

 		}

 	return (PersistentTreeMap) ret;

 }

 

 static public PersistentTreeMap create(Comparator comp, ISeq items){

 	IPersistentMap ret = new PersistentTreeMap(comp);

 	for(; items != null; items = items.next().next())

 		{

 		if(items.next() == null)

 			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));

 		ret = ret.assoc(items.first(), RT.second(items));

 		}

 	return (PersistentTreeMap) ret;

 }

 

 public boolean containsKey(Object key){

 	return entryAt(key) != null;

 }

 

 public PersistentTreeMap assocEx(Object key, Object val) throws Exception{

 	Box found = new Box(null);

 	Node t = add(tree, key, val, found);

 	if(t == null)   //null == already contains key

 		{

 		throw new Exception("Key already present");

 		}

 	return new PersistentTreeMap(comp, t.blacken(), _count + 1, meta());

 }

 

 public PersistentTreeMap assoc(Object key, Object val){

 	Box found = new Box(null);

 	Node t = add(tree, key, val, found);

 	if(t == null)   //null == already contains key

 		{

 		Node foundNode = (Node) found.val;

 		if(foundNode.val() == val)  //note only get same collection on identity of val, not equals()

 			return this;

 		return new PersistentTreeMap(comp, replace(tree, key, val), _count, meta());

 		}

 	return new PersistentTreeMap(comp, t.blacken(), _count + 1, meta());

 }

 

 

 public PersistentTreeMap without(Object key){

 	Box found = new Box(null);

 	Node t = remove(tree, key, found);

 	if(t == null)

 		{

 		if(found.val == null)//null == doesn't contain key

 			return this;

 		//empty

 		return new PersistentTreeMap(meta(), comp);

 		}

 	return new PersistentTreeMap(comp, t.blacken(), _count - 1, meta());

 }

 

 public ISeq seq(){

 	if(_count > 0)

 		return Seq.create(tree, true, _count);

 	return null;

 }

 

 public IPersistentCollection empty(){

 	return new PersistentTreeMap(meta(), comp);	

 }

 

 public ISeq rseq() throws Exception{

 	if(_count > 0)

 		return Seq.create(tree, false, _count);

 	return null;

 }

 

 public Comparator comparator(){

 	return comp;

 }

 

 public Object entryKey(Object entry){

 	return ((IMapEntry) entry).key();

 }

 

 public ISeq seq(boolean ascending){

 	if(_count > 0)

 		return Seq.create(tree, ascending, _count);

 	return null;

 }

 

 public ISeq seqFrom(Object key, boolean ascending){

 	if(_count > 0)

 		{

 		ISeq stack = null;

 		Node t = tree;

 		while(t != null)

 			{

 			int c = doCompare(key, t.key);

 			if(c == 0)

 				{

 				stack = RT.cons(t, stack);

 				return new Seq(stack, ascending);

 				}

 			else if(ascending)

 				{

 				if(c < 0)

 					{

 					stack = RT.cons(t, stack);

 					t = t.left();

 					}

 				else

 					t = t.right();

 				}

 			else

 				{

 				if(c > 0)

 					{

 					stack = RT.cons(t, stack);

 					t = t.right();

 					}

 				else

 					t = t.left();

 				}

 			}

 		if(stack != null)

 			return new Seq(stack, ascending);

 		}

 	return null;

 }

 

 public NodeIterator iterator(){

 	return new NodeIterator(tree, true);

 }

 

 public NodeIterator reverseIterator(){

 	return new NodeIterator(tree, false);

 }

 

 public Iterator keys(){

 	return keys(iterator());

 }

 

 public Iterator vals(){

 	return vals(iterator());

 }

 

 public Iterator keys(NodeIterator it){

 	return new KeyIterator(it);

 }

 

 public Iterator vals(NodeIterator it){

 	return new ValIterator(it);

 }

 

 public Object minKey(){

 	Node t = min();

 	return t != null ? t.key : null;

 }

 

 public Node min(){

 	Node t = tree;

 	if(t != null)

 		{

 		while(t.left() != null)

 			t = t.left();

 		}

 	return t;

 }

 

 public Object maxKey(){

 	Node t = max();

 	return t != null ? t.key : null;

 }

 

 public Node max(){

 	Node t = tree;

 	if(t != null)

 		{

 		while(t.right() != null)

 			t = t.right();

 		}

 	return t;

 }

 

 public int depth(){

 	return depth(tree);

 }

 

 int depth(Node t){

 	if(t == null)

 		return 0;

 	return 1 + Math.max(depth(t.left()), depth(t.right()));

 }

 

 public Object valAt(Object key, Object notFound){

 	Node n = entryAt(key);

 	return (n != null) ? n.val() : notFound;

 }

 

 public Object valAt(Object key){

 	return valAt(key, null);

 }

 

 public int capacity(){

 	return _count;

 }

 

 public int count(){

 	return _count;

 }

 

 public Node entryAt(Object key){

 	Node t = tree;

 	while(t != null)

 		{

 		int c = doCompare(key, t.key);

 		if(c == 0)

 			return t;

 		else if(c < 0)

 			t = t.left();

 		else

 			t = t.right();

 		}

 	return t;

 }

 

 public int doCompare(Object k1, Object k2){

 //	if(comp != null)

 		return comp.compare(k1, k2);

 //	return ((Comparable) k1).compareTo(k2);

 }

 

 Node add(Node t, Object key, Object val, Box found){

 	if(t == null)

 		{

 		if(val == null)

 			return new Red(key);

 		return new RedVal(key, val);

 		}

 	int c = doCompare(key, t.key);

 	if(c == 0)

 		{

 		found.val = t;

 		return null;

 		}

 	Node ins = c < 0 ? add(t.left(), key, val, found) : add(t.right(), key, val, found);

 	if(ins == null) //found below

 		return null;

 	if(c < 0)

 		return t.addLeft(ins);

 	return t.addRight(ins);

 }

 

 Node remove(Node t, Object key, Box found){

 	if(t == null)

 		return null; //not found indicator

 	int c = doCompare(key, t.key);

 	if(c == 0)

 		{

 		found.val = t;

 		return append(t.left(), t.right());

 		}

 	Node del = c < 0 ? remove(t.left(), key, found) : remove(t.right(), key, found);

 	if(del == null && found.val == null) //not found below

 		return null;

 	if(c < 0)

 		{

 		if(t.left() instanceof Black)

 			return balanceLeftDel(t.key, t.val(), del, t.right());

 		else

 			return red(t.key, t.val(), del, t.right());

 		}

 	if(t.right() instanceof Black)

 		return balanceRightDel(t.key, t.val(), t.left(), del);

 	return red(t.key, t.val(), t.left(), del);

 //		return t.removeLeft(del);

 //	return t.removeRight(del);

 }

 

 static Node append(Node left, Node right){

 	if(left == null)

 		return right;

 	else if(right == null)

 		return left;

 	else if(left instanceof Red)

 		{

 		if(right instanceof Red)

 			{

 			Node app = append(left.right(), right.left());

 			if(app instanceof Red)

 				return red(app.key, app.val(),

 				           red(left.key, left.val(), left.left(), app.left()),

 				           red(right.key, right.val(), app.right(), right.right()));

 			else

 				return red(left.key, left.val(), left.left(), red(right.key, right.val(), app, right.right()));

 			}

 		else

 			return red(left.key, left.val(), left.left(), append(left.right(), right));

 		}

 	else if(right instanceof Red)

 		return red(right.key, right.val(), append(left, right.left()), right.right());

 	else //black/black

 		{

 		Node app = append(left.right(), right.left());

 		if(app instanceof Red)

 			return red(app.key, app.val(),

 			           black(left.key, left.val(), left.left(), app.left()),

 			           black(right.key, right.val(), app.right(), right.right()));

 		else

 			return balanceLeftDel(left.key, left.val(), left.left(), black(right.key, right.val(), app, right.right()));

 		}

 }

 

 static Node balanceLeftDel(Object key, Object val, Node del, Node right){

 	if(del instanceof Red)

 		return red(key, val, del.blacken(), right);

 	else if(right instanceof Black)

 		return rightBalance(key, val, del, right.redden());

 	else if(right instanceof Red && right.left() instanceof Black)

 		return red(right.left().key, right.left().val(),

 		           black(key, val, del, right.left().left()),

 		           rightBalance(right.key, right.val(), right.left().right(), right.right().redden()));

 	else

 		throw new UnsupportedOperationException("Invariant violation");

 }

 

 static Node balanceRightDel(Object key, Object val, Node left, Node del){

 	if(del instanceof Red)

 		return red(key, val, left, del.blacken());

 	else if(left instanceof Black)

 		return leftBalance(key, val, left.redden(), del);

 	else if(left instanceof Red && left.right() instanceof Black)

 		return red(left.right().key, left.right().val(),

 		           leftBalance(left.key, left.val(), left.left().redden(), left.right().left()),

 		           black(key, val, left.right().right(), del));

 	else

 		throw new UnsupportedOperationException("Invariant violation");

 }

 

 static Node leftBalance(Object key, Object val, Node ins, Node right){

 	if(ins instanceof Red && ins.left() instanceof Red)

 		return red(ins.key, ins.val(), ins.left().blacken(), black(key, val, ins.right(), right));

 	else if(ins instanceof Red && ins.right() instanceof Red)

 		return red(ins.right().key, ins.right().val(),

 		           black(ins.key, ins.val(), ins.left(), ins.right().left()),

 		           black(key, val, ins.right().right(), right));

 	else

 		return black(key, val, ins, right);

 }

 

 

 static Node rightBalance(Object key, Object val, Node left, Node ins){

 	if(ins instanceof Red && ins.right() instanceof Red)

 		return red(ins.key, ins.val(), black(key, val, left, ins.left()), ins.right().blacken());

 	else if(ins instanceof Red && ins.left() instanceof Red)

 		return red(ins.left().key, ins.left().val(),

 		           black(key, val, left, ins.left().left()),

 		           black(ins.key, ins.val(), ins.left().right(), ins.right()));

 	else

 		return black(key, val, left, ins);

 }

 

 Node replace(Node t, Object key, Object val){

 	int c = doCompare(key, t.key);

 	return t.replace(t.key,

 	                 c == 0 ? val : t.val(),

 	                 c < 0 ? replace(t.left(), key, val) : t.left(),

 	                 c > 0 ? replace(t.right(), key, val) : t.right());

 }

 

 PersistentTreeMap(Comparator comp, Node tree, int count, IPersistentMap meta){

 	this._meta = meta;

 	this.comp = comp;

 	this.tree = tree;

 	this._count = count;

 }

 

 static Red red(Object key, Object val, Node left, Node right){

 	if(left == null && right == null)

 		{

 		if(val == null)

 			return new Red(key);

 		return new RedVal(key, val);

 		}

 	if(val == null)

 		return new RedBranch(key, left, right);

 	return new RedBranchVal(key, val, left, right);

 }

 

 static Black black(Object key, Object val, Node left, Node right){

 	if(left == null && right == null)

 		{

 		if(val == null)

 			return new Black(key);

 		return new BlackVal(key, val);

 		}

 	if(val == null)

 		return new BlackBranch(key, left, right);

 	return new BlackBranchVal(key, val, left, right);

 }

 

 public IPersistentMap meta(){

 	return _meta;

 }

 

 static abstract class Node extends AMapEntry{

 	final Object key;

 

 	Node(Object key){

 		this.key = key;

 	}

 

 	public Object key(){

 		return key;

 	}

 

 	public Object val(){

 		return null;

 	}

 

 	public Object getKey(){

 		return key();

 	}

 

 	public Object getValue(){

 		return val();

 	}

 

 	Node left(){

 		return null;

 	}

 

 	Node right(){

 		return null;

 	}

 

 	abstract Node addLeft(Node ins);

 

 	abstract Node addRight(Node ins);

 

 	abstract Node removeLeft(Node del);

 

 	abstract Node removeRight(Node del);

 

 	abstract Node blacken();

 

 	abstract Node redden();

 

 	Node balanceLeft(Node parent){

 		return black(parent.key, parent.val(), this, parent.right());

 	}

 

 	Node balanceRight(Node parent){

 		return black(parent.key, parent.val(), parent.left(), this);

 	}

 

 	abstract Node replace(Object key, Object val, Node left, Node right);

 

 }

 

 static class Black extends Node{

 	public Black(Object key){

 		super(key);

 	}

 

 	Node addLeft(Node ins){

 		return ins.balanceLeft(this);

 	}

 

 	Node addRight(Node ins){

 		return ins.balanceRight(this);

 	}

 

 	Node removeLeft(Node del){

 		return balanceLeftDel(key, val(), del, right());

 	}

 

 	Node removeRight(Node del){

 		return balanceRightDel(key, val(), left(), del);

 	}

 

 	Node blacken(){

 		return this;

 	}

 

 	Node redden(){

 		return new Red(key);

 	}

 

 	Node replace(Object key, Object val, Node left, Node right){

 		return black(key, val, left, right);

 	}

 

 }

 

 static class BlackVal extends Black{

 	final Object val;

 

 	public BlackVal(Object key, Object val){

 		super(key);

 		this.val = val;

 	}

 

 	public Object val(){

 		return val;

 	}

 

 	Node redden(){

 		return new RedVal(key, val);

 	}

 

 }

 

 static class BlackBranch extends Black{

 	final Node left;

 

 	final Node right;

 

 	public BlackBranch(Object key, Node left, Node right){

 		super(key);

 		this.left = left;

 		this.right = right;

 	}

 

 	public Node left(){

 		return left;

 	}

 

 	public Node right(){

 		return right;

 	}

 

 	Node redden(){

 		return new RedBranch(key, left, right);

 	}

 

 }

 

 static class BlackBranchVal extends BlackBranch{

 	final Object val;

 

 	public BlackBranchVal(Object key, Object val, Node left, Node right){

 		super(key, left, right);

 		this.val = val;

 	}

 

 	public Object val(){

 		return val;

 	}

 

 	Node redden(){

 		return new RedBranchVal(key, val, left, right);

 	}

 

 }

 

 static class Red extends Node{

 	public Red(Object key){

 		super(key);

 	}

 

 	Node addLeft(Node ins){

 		return red(key, val(), ins, right());

 	}

 

 	Node addRight(Node ins){

 		return red(key, val(), left(), ins);

 	}

 

 	Node removeLeft(Node del){

 		return red(key, val(), del, right());

 	}

 

 	Node removeRight(Node del){

 		return red(key, val(), left(), del);

 	}

 

 	Node blacken(){

 		return new Black(key);

 	}

 

 	Node redden(){

 		throw new UnsupportedOperationException("Invariant violation");

 	}

 

 	Node replace(Object key, Object val, Node left, Node right){

 		return red(key, val, left, right);

 	}

 

 }

 

 static class RedVal extends Red{

 	final Object val;

 

 	public RedVal(Object key, Object val){

 		super(key);

 		this.val = val;

 	}

 

 	public Object val(){

 		return val;

 	}

 

 	Node blacken(){

 		return new BlackVal(key, val);

 	}

 

 }

 

 static class RedBranch extends Red{

 	final Node left;

 

 	final Node right;

 

 	public RedBranch(Object key, Node left, Node right){

 		super(key);

 		this.left = left;

 		this.right = right;

 	}

 

 	public Node left(){

 		return left;

 	}

 

 	public Node right(){

 		return right;

 	}

 

 	Node balanceLeft(Node parent){

 		if(left instanceof Red)

 			return red(key, val(), left.blacken(), black(parent.key, parent.val(), right, parent.right()));

 		else if(right instanceof Red)

 			return red(right.key, right.val(), black(key, val(), left, right.left()),

 			           black(parent.key, parent.val(), right.right(), parent.right()));

 		else

 			return super.balanceLeft(parent);

 

 	}

 

 	Node balanceRight(Node parent){

 		if(right instanceof Red)

 			return red(key, val(), black(parent.key, parent.val(), parent.left(), left), right.blacken());

 		else if(left instanceof Red)

 			return red(left.key, left.val(), black(parent.key, parent.val(), parent.left(), left.left()),

 			           black(key, val(), left.right(), right));

 		else

 			return super.balanceRight(parent);

 	}

 

 	Node blacken(){

 		return new BlackBranch(key, left, right);

 	}

 

 }

 

 

 static class RedBranchVal extends RedBranch{

 	final Object val;

 

 	public RedBranchVal(Object key, Object val, Node left, Node right){

 		super(key, left, right);

 		this.val = val;

 	}

 

 	public Object val(){

 		return val;

 	}

 

 	Node blacken(){

 		return new BlackBranchVal(key, val, left, right);

 	}

 }

 

 

 static public class Seq extends ASeq{

 	final ISeq stack;

 	final boolean asc;

 	final int cnt;

 

 	public Seq(ISeq stack, boolean asc){

 		this.stack = stack;

 		this.asc = asc;

 		this.cnt = -1;

 	}

 

 	public Seq(ISeq stack, boolean asc, int cnt){

 		this.stack = stack;

 		this.asc = asc;

 		this.cnt = cnt;

 	}

 

 	Seq(IPersistentMap meta, ISeq stack, boolean asc, int cnt){

 		super(meta);

 		this.stack = stack;

 		this.asc = asc;

 		this.cnt = cnt;

 	}

 

 	static Seq create(Node t, boolean asc, int cnt){

 		return new Seq(push(t, null, asc), asc, cnt);

 	}

 

 	static ISeq push(Node t, ISeq stack, boolean asc){

 		while(t != null)

 			{

 			stack = RT.cons(t, stack);

 			t = asc ? t.left() : t.right();

 			}

 		return stack;

 	}

 

 	public Object first(){

 		return stack.first();

 	}

 

 	public ISeq next(){

 		Node t = (Node) stack.first();

 		ISeq nextstack = push(asc ? t.right() : t.left(), stack.next(), asc);

 		if(nextstack != null)

 			{

 			return new Seq(nextstack, asc, cnt - 1);

 			}

 		return null;

 	}

 

 	public int count(){

 		if(cnt < 0)

 			return super.count();

 		return cnt;

 	}

 

 	public Obj withMeta(IPersistentMap meta){

 		return new Seq(meta, stack, asc, cnt);

 	}

 }

 

 static public class NodeIterator implements Iterator{

 	Stack stack = new Stack();

 	boolean asc;

 

 	NodeIterator(Node t, boolean asc){

 		this.asc = asc;

 		push(t);

 	}

 

 	void push(Node t){

 		while(t != null)

 			{

 			stack.push(t);

 			t = asc ? t.left() : t.right();

 			}

 	}

 

 	public boolean hasNext(){

 		return !stack.isEmpty();

 	}

 

 	public Object next(){

 		Node t = (Node) stack.pop();

 		push(asc ? t.right() : t.left());

 		return t;

 	}

 

 	public void remove(){

 		throw new UnsupportedOperationException();

 	}

 }

 

 static class KeyIterator implements Iterator{

 	NodeIterator it;

 

 	KeyIterator(NodeIterator it){

 		this.it = it;

 	}

 

 	public boolean hasNext(){

 		return it.hasNext();

 	}

 

 	public Object next(){

 		return ((Node) it.next()).key;

 	}

 

 	public void remove(){

 		throw new UnsupportedOperationException();

 	}

 }

 

 static class ValIterator implements Iterator{

 	NodeIterator it;

 

 	ValIterator(NodeIterator it){

 		this.it = it;

 	}

 

 	public boolean hasNext(){

 		return it.hasNext();

 	}

 

 	public Object next(){

 		return ((Node) it.next()).val();

 	}

 

 	public void remove(){

 		throw new UnsupportedOperationException();

 	}

 }

 /*

 static public void main(String args[]){

 	if(args.length != 1)

 		System.err.println("Usage: RBTree n");

 	int n = Integer.parseInt(args[0]);

 	Integer[] ints = new Integer[n];

 	for(int i = 0; i < ints.length; i++)

 		{

 		ints[i] = i;

 		}

 	Collections.shuffle(Arrays.asList(ints));

 	//force the ListMap class loading now

 //	try

 //		{

 //

 //		//PersistentListMap.EMPTY.assocEx(1, null).assocEx(2,null).assocEx(3,null);

 //		}

 //	catch(Exception e)

 //		{

 //		e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.

 //		}

 	System.out.println("Building set");

 	//IPersistentMap set = new PersistentArrayMap();

 	//IPersistentMap set = new PersistentHashtableMap(1001);

 	IPersistentMap set = PersistentHashMap.EMPTY;

 	//IPersistentMap set = new ListMap();

 	//IPersistentMap set = new ArrayMap();

 	//IPersistentMap set = new PersistentTreeMap();

 //	for(int i = 0; i < ints.length; i++)

 //		{

 //		Integer anInt = ints[i];

 //		set = set.add(anInt);

 //		}

 	long startTime = System.nanoTime();

 	for(Integer anInt : ints)

 		{

 		set = set.assoc(anInt, anInt);

 		}

 	//System.out.println("_count = " + set.count());

 

 //	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()

 //	                   + ", depth: " + set.depth());

 	for(Object aSet : set)

 		{

 		IMapEntry o = (IMapEntry) aSet;

 		if(!set.contains(o.key()))

 			System.err.println("Can't find: " + o.key());

 		//else if(n < 2000)

 		//	System.out.print(o.key().toString() + ",");

 		}

 

 	Random rand = new Random(42);

 	for(int i = 0; i < ints.length / 2; i++)

 		{

 		Integer anInt = ints[rand.nextInt(n)];

 		set = set.without(anInt);

 		}

 

 	long estimatedTime = System.nanoTime() - startTime;

 	System.out.println();

 

 	System.out.println("_count = " + set.count() + ", time: " + estimatedTime / 1000000);

 

 	System.out.println("Building ht");

 	Hashtable ht = new Hashtable(1001);

 	startTime = System.nanoTime();

 //	for(int i = 0; i < ints.length; i++)

 //		{

 //		Integer anInt = ints[i];

 //		ht.put(anInt,null);

 //		}

 	for(Integer anInt : ints)

 		{

 		ht.put(anInt, anInt);

 		}

 	//System.out.println("size = " + ht.size());

 	//Iterator it = ht.entrySet().iterator();

 	for(Object o1 : ht.entrySet())

 		{

 		Map.Entry o = (Map.Entry) o1;

 		if(!ht.containsKey(o.getKey()))

 			System.err.println("Can't find: " + o);

 		//else if(n < 2000)

 		//	System.out.print(o.toString() + ",");

 		}

 

 	rand = new Random(42);

 	for(int i = 0; i < ints.length / 2; i++)

 		{

 		Integer anInt = ints[rand.nextInt(n)];

 		ht.remove(anInt);

 		}

 	estimatedTime = System.nanoTime() - startTime;

 	System.out.println();

 	System.out.println("size = " + ht.size() + ", time: " + estimatedTime / 1000000);

 

 	System.out.println("set lookup");

 	startTime = System.nanoTime();

 	int c = 0;

 	for(Integer anInt : ints)

 		{

 		if(!set.contains(anInt))

 			++c;

 		}

 	estimatedTime = System.nanoTime() - startTime;

 	System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);

 

 	System.out.println("ht lookup");

 	startTime = System.nanoTime();

 	c = 0;

 	for(Integer anInt : ints)

 		{

 		if(!ht.containsKey(anInt))

 			++c;

 		}

 	estimatedTime = System.nanoTime() - startTime;

 	System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);

 

 //	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()

 //	                   + ", depth: " + set.depth());

 }

 */

 }