renamed to PersistentTree

1 files changed, 789 insertions, 0 deletions

diff --git a/src/cli/runtime/PersistentTree.cs b/src/cli/runtime/PersistentTree.cs
new file mode 100644
index 00000000..3ed31f41
--- /dev/null
+++ b/src/cli/runtime/PersistentTree.cs
@@ -0,0 +1,789 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
+ *   which can be found in the file CPL.TXT 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 */
+
+using System;

+using System.Collections;

+using System.Collections.Specialized;

+
+namespace org.clojure.runtime

+{
+
+/**
+ * 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 PersistentTree : IPersistentMap{
+
+public readonly IComparer comp;
+public readonly Node tree;
+public readonly int _count;
+
+public PersistentTree():this(null){
+}
+
+public PersistentTree(IComparer comp){
+	this.comp = comp;
+	tree = null;
+	_count = 0;
+}
+
+public int count(){
+	return _count;
+	}
+
+public int capacity(){
+	return _count;
+	}
+	
+public bool contains(Object key){
+	return find(key) != null;
+}

+

+	public IPersistentMap add(Object key)

+		{
+	return put(key, null);
+}
+
+public IPersistentMap put(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 PersistentTree(comp, replace(tree, key, val), _count);
+		}
+	return new PersistentTree(comp, t.blacken(), _count + 1);
+}
+
+
+public IPersistentMap remove(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 PersistentTree(comp);
+		}
+	return new PersistentTree(comp, t.blacken(), _count - 1);
+}
+
+
+public IEnumerator GetEnumerator(){
+	return new NodeIEnumerator(tree, true);
+}
+
+public NodeIEnumerator reverseIEnumerator(){
+	return new NodeIEnumerator(tree, false);
+}
+
+public IEnumerator keys(){

+return keys((NodeIEnumerator)GetEnumerator());
+}
+
+public IEnumerator vals(){

+return vals((NodeIEnumerator)GetEnumerator());
+}
+
+public IEnumerator keys(NodeIEnumerator it){
+	return new KeyIEnumerator(it);
+}
+
+public IEnumerator vals(NodeIEnumerator it){
+	return new ValIEnumerator(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 get(Object key){
+	Node n = (Node)find(key);
+	return (n != null) ? n.val() : null;
+}
+
+public IMapEntry find(Object key){
+	Node t = tree;
+	while(t != null)
+		{
+		int c = compare(key, t._key);
+		if(c == 0)
+			return t;
+		else if(c < 0)
+			t = t.left();
+		else
+			t = t.right();
+		}
+	return t;
+}
+
+int compare(Object k1, Object k2){
+	if(comp != null)
+		return comp.Compare(k1, k2);
+	return ((IComparable) 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 = compare(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 = compare(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() is Black)
+			return balanceLeftDel(t._key, t.val(), del, t.right());
+		else
+			return red(t._key, t.val(), del, t.right());
+		}
+	if(t.right() is 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 is Red)
+		{
+		if(right is Red)
+			{
+			Node app = append(left.right(), right.left());
+			if(app is 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 is 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 is 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 is Red)
+		return red(key, val, del.blacken(), right);
+	else if(right is Black)
+		return rightBalance(key, val, del, right.redden());
+	else if(right is Red && right.left() is 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 InvalidOperationException("Invariant violation");
+}
+
+static Node balanceRightDel(Object key, Object val, Node left, Node del){
+	if(del is Red)
+		return red(key, val, left, del.blacken());
+	else if(left is Black)
+		return leftBalance(key, val, left.redden(), del);
+	else if(left is Red && left.right() is 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 InvalidOperationException("Invariant violation");
+}
+
+static Node leftBalance(Object key, Object val, Node ins, Node right){
+	if(ins is Red && ins.left() is Red)
+		return red(ins._key, ins.val(), ins.left().blacken(), black(key, val, ins.right(), right));
+	else if(ins is Red && ins.right() is 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 is Red && ins.right() is Red)
+		return red(ins._key, ins.val(), black(key, val, left, ins.left()), ins.right().blacken());
+	else if(ins is Red && ins.left() is 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 = compare(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());
+}
+
+PersistentTree(IComparer comp, Node tree, int count){
+	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 abstract class Node : IMapEntry{
+	internal readonly Object _key;
+
+	internal Node(Object key){
+		this._key = key;
+	}
+
+	public Object key(){
+		return _key;
+	}
+
+	virtual public Object val(){
+		return null;
+	}

+

+    internal virtual Node left()

+        {
+		return null;
+	}

+

+    internal virtual Node right()

+        {
+		return null;
+	}
+
+	internal abstract Node addLeft(Node ins);

+

+    internal abstract Node addRight(Node ins);

+

+    internal abstract Node removeLeft(Node del);

+

+    internal abstract Node removeRight(Node del);

+

+    internal abstract Node blacken();

+

+    internal abstract Node redden();

+

+    internal virtual Node balanceLeft(Node parent)

+        {
+		return black(parent._key, parent.val(), this, parent.right());
+	}

+

+    internal virtual Node balanceRight(Node parent)

+        {
+		return black(parent._key, parent.val(), parent.left(), this);
+	}

+

+    internal abstract Node replace(Object key, Object val, Node left, Node right);
+}
+
+class Black : Node{
+	public Black(Object key):base(key){
+	}
+
+	internal override Node addLeft(Node ins){
+		return ins.balanceLeft(this);
+	}

+

+    internal override Node addRight(Node ins)

+        {
+		return ins.balanceRight(this);
+	}

+

+    internal override Node removeLeft(Node del)

+        {
+		return balanceLeftDel(_key, val(), del, right());
+	}

+

+    internal override Node removeRight(Node del)

+        {
+		return balanceRightDel(_key, val(), left(), del);
+	}

+

+    internal override Node blacken()

+        {
+		return this;
+	}

+

+    internal override Node redden()

+        {
+		return new Red(_key);
+	}

+

+    internal override Node replace(Object key, Object val, Node left, Node right)

+        {
+		return black(key, val, left, right);
+	}
+}
+
+class BlackVal : Black{
+	readonly Object _val;
+
+	public BlackVal(Object key, Object val):base(key){
+		this._val = val;
+	}
+
+	override public Object val(){
+		return _val;
+	}

+

+    internal override Node redden()

+        {
+		return new RedVal(_key, _val);
+	}
+
+}
+
+class BlackBranch : Black{
+	internal readonly Node _left;
+	internal readonly Node _right;
+
+	public BlackBranch(Object key, Node left, Node right):base(key){
+		this._left = left;
+		this._right = right;
+	}

+

+    internal override Node left()

+        {
+		return _left;
+	}

+

+    internal override Node right()

+        {
+		return _right;
+	}

+

+    internal override Node redden()

+        {
+		return new RedBranch(_key, _left, _right);
+	}
+
+}
+
+class BlackBranchVal : BlackBranch{
+	readonly Object _val;
+
+	public BlackBranchVal(Object key, Object val, Node left, Node right): base(key, left, right){
+		this._val = val;
+	}
+
+	override public Object val(){
+		return _val;
+	}

+

+    internal override Node redden()

+        {
+		return new RedBranchVal(_key, _val, _left, _right);
+	}
+
+}
+
+class Red : Node{
+	public Red(Object key):base(key){
+	}

+

+    internal override Node addLeft(Node ins)

+        {
+		return red(_key, val(), ins, right());
+	}

+

+    internal override Node addRight(Node ins)

+        {
+		return red(_key, val(), left(), ins);
+	}

+

+    internal override Node removeLeft(Node del)

+        {
+		return red(_key, val(), del, right());
+	}

+

+    internal override Node removeRight(Node del)

+        {
+		return red(_key, val(), left(), del);
+	}

+

+    internal override Node blacken()

+        {
+		return new Black(_key);
+	}

+

+    internal override Node redden()

+        {
+		throw new InvalidOperationException("Invariant violation");
+	}

+

+    internal override Node replace(Object key, Object val, Node left, Node right)

+        {
+		return red(key, val, left, right);
+	}
+}
+
+class RedVal : Red{
+	readonly Object _val;
+
+	public RedVal(Object key, Object val):base(key){
+		this._val = val;
+	}
+
+	override public Object val(){
+		return _val;
+	}

+

+    internal override Node blacken()

+        {
+		return new BlackVal(_key, _val);
+	}
+}
+
+class RedBranch : Red{
+	internal readonly Node _left;
+	internal readonly Node _right;
+
+	public RedBranch(Object key, Node left, Node right):base(key){
+		this._left = left;
+		this._right = right;
+	}

+

+    internal override Node left()

+        {
+		return _left;
+	}

+

+    internal override Node right()

+        {
+		return _right;
+	}

+

+    internal override Node balanceLeft(Node parent)

+        {
+		if(_left is Red)
+			return red(_key, val(), _left.blacken(), black(parent._key, parent.val(), _right, parent.right()));
+		else if(_right is Red)
+			return red(_right._key, _right.val(), black(_key, val(), _left, _right.left()),
+			           black(parent._key, parent.val(), _right.right(), parent.right()));
+		else
+			return base.balanceLeft(parent);
+
+	}

+

+    internal override Node balanceRight(Node parent)

+        {
+		if(_right is Red)
+			return red(_key, val(), black(parent._key, parent.val(), parent.left(), _left), _right.blacken());
+		else if(_left is Red)
+			return red(_left._key, _left.val(), black(parent._key, parent.val(), parent.left(), _left.left()),
+			           black(_key, val(), _left.right(), _right));
+		else
+			return base.balanceRight(parent);
+	}

+

+    internal override Node blacken()

+        {
+		return new BlackBranch(_key, _left, _right);
+	}
+}
+
+class RedBranchVal : RedBranch{
+	readonly Object _val;
+
+	public RedBranchVal(Object key, Object val, Node left, Node right):base(key, left, right){
+		
+		this._val = val;
+	}
+
+	override public Object val(){
+		return _val;
+	}

+

+    internal override Node blacken()

+        {
+		return new BlackBranchVal(_key, _val, _left, _right);
+	}
+}
+
+public class NodeIEnumerator : IEnumerator{
+	Stack stack = new Stack();
+	bool asc;

+    object curr;
+
+	internal NodeIEnumerator(Node t, bool asc){
+		this.asc = asc;
+		push(t);
+	}
+
+	void push(Node t){
+		while(t != null)
+			{
+			stack.Push(t);
+			t = asc ? t.left() : t.right();
+			}
+	}
+
+	bool hasNext(){
+		return !(stack.Count == 0);
+	}
+
+	Object next(){
+		Node t = (Node) stack.Pop();
+		push(asc ? t.right() : t.left());
+		return t;
+	}
+
+	public void remove(){
+		throw new InvalidOperationException();
+	}

+

+#region IEnumerator Members

+

+public object Current

+    {

+    get { return curr; }

+    }

+

+public bool MoveNext()

+    {

+    if (hasNext())

+        {

+        curr = next();

+        return true;

+        }

+    return false;

+    }

+

+public void Reset()

+    {

+    throw new Exception("The method or operation is not implemented.");

+    }

+

+#endregion

+    }
+
+class KeyIEnumerator : IEnumerator{
+	NodeIEnumerator it;
+
+	internal KeyIEnumerator(NodeIEnumerator it){
+		this.it = it;
+	}
+

+#region IEnumerator Members

+

+public object  Current

+{

+get { return ((Node)it.Current)._key; }

+}

+

+public bool  MoveNext()

+{

+return it.MoveNext();

+}

+

+public void  Reset()

+{

+ 	throw new Exception("The method or operation is not implemented.");

+}

+

+#endregion

+}
+
+class ValIEnumerator : IEnumerator{
+	NodeIEnumerator it;
+
+	internal ValIEnumerator(NodeIEnumerator it){
+		this.it = it;
+	}

+

+#region IEnumerator Members

+

+public object Current

+    {

+    get { return ((Node)it.Current).val(); }

+    }

+

+public bool MoveNext()

+    {

+    return it.MoveNext();

+    }

+

+public void Reset()

+    {

+    throw new Exception("The method or operation is not implemented.");

+    }

+

+#endregion

+    }
+
+    /*

+	[STAThread]
+static public void Main(String[] args){
+	if(args.Length != 1)
+		Console.Error.WriteLine("Usage: RBTree n");
+	int n = Int32.Parse(args[0]);
+	Object[] ints = new Object[n];
+	for(int i = 0; i < ints.Length; i++)
+		{
+		ints[i] = i;
+		}
+	//Collections.shuffle(Arrays.asList(ints));

+    Array.Reverse(ints);
+	Console.WriteLine("Building set");
+	RBTree set = new RBTree();
+    //for(int i = 0; i < ints.Length; i++)
+    //    {
+    //    Object anInt = ints[i];
+    //    set = set.add(anInt);
+    //    }
+	for(int i = 0; i < ints.Length; i++)
+		{
+		Object anInt = ints[i];
+		set = set.put(anInt, anInt);
+		}

+    Console.WriteLine("Building SortedList");

+    SortedList od = new SortedList();

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

+        {

+        Object anInt = ints[i];

+        od.Add(anInt, anInt);

+        }

+
+	Console.Error.WriteLine("count = " + set.count + ", min: " + set.minKey() + ", max: " + set.maxKey()
+	                   + ", depth: " + set.depth());
+	IEnumerator it = set.keys();
+	while(it.MoveNext())
+		{
+		Object o = it.Current;
+		if(!set.contains(o))
+			Console.Error.WriteLine("Can't find: " + o);
+		else if(n < 2000)
+			Console.Write(o.ToString() + ",");
+		}
+
+	for(int i = 0; i < ints.Length/2; i++)
+		{
+		Object anInt = ints[i];
+		set = set.remove(anInt);
+		}
+
+	Console.Error.WriteLine();
+	Console.Error.WriteLine("count = " + set.count + ", min: " + set.minKey() + ", max: " + set.maxKey()
+	                   + ", depth: " + set.depth());
+}
+     //*/
+}
+    }