path: root/src/cli/runtime/PersistentTreeMap.cs

/**
 *   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 clojure.lang
{

/**
 * 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 : APersistentMap{

public readonly IComparer comp;
public readonly Node tree;
public readonly int _count;

public PersistentTreeMap():this(null){
}

public PersistentTreeMap(IComparer comp){
	this.comp = comp;
	tree = null;
	_count = 0;
}

override public int count(){
	return _count;
	}
	
override public bool contains(Object key){
	return find(key) != null;
}

override public IPersistentMap assocEx(Object key,Object val){
	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);
}

override public Associative 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);
}


override public IPersistentMap 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
		PersistentTreeMap ret = new PersistentTreeMap(comp);
		ret._meta = _meta;
		return ret;
		}
	return new PersistentTreeMap(comp, t.blacken(), _count - 1, _meta);
}

override public ISeq seq() {
    if(_count > 0)
        return Seq.create(tree, true);
    return null;
}

public ISeq rseq() {
    if(_count > 0)
        return Seq.create(tree, false);
    return null;
}

override 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()));
}

override public Object get(Object key){
	Node n = (Node)find(key);
	return (n != null) ? n.val() : null;
}

override public IMapEntry find(Object key){
	Node t = tree;
	while(t != null)
		{
		int c