ported PersistentListMap, PersistentListIdentityMap

author: Rich Hickey <richhickey@gmail.com> 2006-06-07 19:41:23 +0000
committer: Rich Hickey <richhickey@gmail.com> 2006-06-07 19:41:23 +0000
commit: 4e6dd0d78a9705f8be56be8145546ab9d512f961 (patch)
tree: fbaf9d794ce37fe90d70c971a4bb21e3714938f8 /src
parent: 2023e999fa999c25acbbb212a9197eed6dce956c (diff)
2 files changed, 579 insertions, 0 deletions
diff --git a/src/cli/runtime/PersistentListIdentityMap.cs b/src/cli/runtime/PersistentListIdentityMap.cs
new file mode 100644
index 00000000..8ec09759
--- /dev/null
+++ b/src/cli/runtime/PersistentListIdentityMap.cs
@@ -0,0 +1,303 @@
+/**
+ *   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 Jun 6, 2006 */
+
+using System;
+using System.Collections;
+
+namespace org.clojure.runtime
+	{
+	/**
+	 * Implementation of persistent map on a linked list
+	 * Uses identity (==) comparison, vs equals() of PersistentListMap
+
+	 * Note that instances of this class are constant values
+	 * i.e. add/remove etc return new values
+	 *
+	 * Lookups/changes are linear, so only appropriate for _very_small_ maps
+	 * PersistentArrayMap is generally faster, but this class avoids the double allocation,
+	 * and so is better/faster as a bucket for hash tables
+	 *
+	 * null keys and values are ok, but you won't be able to distinguish a null value via get - use contains/find
+	 *
+	 * code duplication here is kind of gross, but most efficient
+	 */
+	 
+	public class PersistentListIdentityMap : IPersistentMap, IMapEntry
+		{
+
+		static public PersistentListIdentityMap EMPTY = new PersistentListIdentityMap();
+
+		static public PersistentListIdentityMap create(Object key, Object val)
+			{
+			return new Tail(key, val);
+			}
+
+		public virtual Object key()
+			{
+			return null;
+			}
+
+		public virtual Object val()
+			{
+			return null;
+			}
+
+		internal virtual PersistentListIdentityMap rest()
+			{
+			return this;
+			}
+
+		public virtual int count()
+			{
+			return 0;
+			}
+
+		public virtual bool contains(Object key)
+			{
+			return false;
+			}
+
+		public virtual IMapEntry find(Object key)
+			{
+			return null;
+			}
+
+		public virtual IPersistentMap add(Object key)
+			{
+			return put(key, null);
+			}
+
+		public virtual IPersistentMap put(Object key, Object val)
+			{
+			return new Tail(key, val);
+			}
+
+		public virtual IPersistentMap remove(Object key)
+			{
+			return this;
+			}
+
+		public virtual Object get(Object key)
+			{
+			return null;
+			}
+
+		public virtual int capacity()
+			{
+			return 0;
+			}
+
+		internal class Iter : IEnumerator
+			{
+			PersistentListIdentityMap e;
+			bool first = true;
+
+			internal Iter(PersistentListIdentityMap e)
+				{
+				this.e = e;
+				}
+
+			#region IEnumerator Members
+
+			public object Current
+				{
+				get { return e; }
+				}
+
+			public bool MoveNext()
+				{
+				if (first)
+					first = false;
+				else
+					e = e.rest();
+				return e != EMPTY;
+				}
+
+			public void Reset()
+				{
+				throw new Exception("The method or operation is not implemented.");
+				}
+
+			#endregion
+			}
+
+		public IEnumerator GetEnumerator()
+			{
+			return new Iter(this);
+			}
+
+		internal class Tail : PersistentListIdentityMap
+			{
+			readonly Object _key;
+			readonly Object _val;
+
+			internal Tail(Object key, Object val)
+				{
+				this._key = key;
+				this._val = val;
+				}
+
+			override internal PersistentListIdentityMap rest()
+				{
+				return EMPTY;
+				}
+
+			override public int count()
+				{
+				return 1;
+				}
+
+			override public Object get(Object key)
+				{
+				if (key == _key)
+					return _val;
+				return null;
+				}
+
+			override public int capacity()
+				{
+				return 1;
+				}
+
+			override public Object key()
+				{
+				return _key;
+				}
+
+			override public Object val()
+				{
+				return _val;
+				}
+
+			override public bool contains(Object key)
+				{
+				return (key == _key);
+				}
+
+			override public IMapEntry find(Object key)
+				{
+				if ((key == _key))
+					return this;
+				return null;
+				}
+
+			override public IPersistentMap put(Object key, Object val)
+				{
+				if ((key == _key))  //replace
+					{
+					if (val == _val)
+						return this;
+					return new Tail(key, val);
+					}
+				return new Link(key, val, this);
+				}
+
+			override public IPersistentMap remove(Object key)
+				{
+				if ((key == _key))
+					return EMPTY;
+				return this;
+				}
+			}
+
+		internal class Link : PersistentListIdentityMap
+			{
+			readonly Object _key;
+			readonly Object _val;
+			readonly PersistentListIdentityMap _rest;
+
+			internal Link(Object key, Object val, PersistentListIdentityMap rest)
+				{
+				this._key = key;
+				this._val = val;
+				this._rest = rest;
+				}
+
+			override public Object key()
+				{
+				return _key;
+				}
+
+			override public Object val()
+				{
+				return _val;
+				}
+
+			override internal PersistentListIdentityMap rest()
+				{
+				return _rest;
+				}
+
+			override public int count()
+				{
+				return 1 + _rest.count();
+				}
+
+			override public bool contains(Object key)
+				{
+				return find(key) != null;
+				}
+
+			override public IMapEntry find(Object key)
+				{
+				if ((key == _key))
+					return this;
+				return _rest.find(key);
+				}
+
+			override public IPersistentMap put(Object key, Object val)
+				{
+				IMapEntry e = find(key);
+				if (e != null)
+					{
+					if (e.val() == val)
+						return this;
+					return create(_key, _val, remove(key));
+					}
+				return new Link(key, val, this);
+				}
+
+			override public IPersistentMap remove(Object key)
+				{
+				if ((key == _key))
+					return _rest;
+				PersistentListIdentityMap r = (PersistentListIdentityMap)_rest.remove(key);
+				if (r == _rest)  //not there
+					return this;
+				return create(_key, _val, r);
+				}
+
+			override public Object get(Object key)
+				{
+				IMapEntry e = find(key);
+				if (e != null)
+					return e.val();
+				return null;
+				}
+
+			override public int capacity()
+				{
+				return count();
+				}
+
+			PersistentListIdentityMap create(Object k, Object v, IPersistentMap r)
+				{
+				if (r == EMPTY)
+					return new Tail(k, v);
+				return new Link(k, v, (PersistentListIdentityMap)r);
+				}
+
+			}
+
+		}
+
+	}
diff --git a/src/cli/runtime/PersistentListMap.cs b/src/cli/runtime/PersistentListMap.cs
new file mode 100644
index 00000000..f6d19717
--- /dev/null
+++ b/src/cli/runtime/PersistentListMap.cs
@@ -0,0 +1,276 @@
+/**
+ *   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 Jun 6, 2006 */
+
+using System;
+using System.Collections;
+
+namespace org.clojure.runtime
+{
+/**
+ * Implementation of persistent map on a linked list
+
+ * Note that instances of this class are constant values
+ * i.e. add/remove etc return new values
+ *
+ * Lookups/changes are linear, so only appropriate for _very_small_ maps
+ * PersistentArrayMap is generally faster, but this class avoids the double allocation,
+ * and so is better/faster as a bucket for hash tables
+ *
+ * null keys and values are ok, but you won't be able to distinguish a null value via get - use contains/find
+ */
+public class PersistentListMap : IPersistentMap, IMapEntry
+{
+
+static public PersistentListMap EMPTY = new PersistentListMap();
+
+static public PersistentListMap create(Object key, Object val){
+	return new Tail(key, val);
+}
+
+public virtual Object key(){
+	return null;
+}
+
+public virtual Object val(){
+	return null;
+}
+
+internal virtual PersistentListMap rest(){
+    return this;
+    }
+
+public virtual int count(){
+	return 0;
+}
+
+public virtual bool contains(Object key){
+	return false;
+}
+
+public virtual IMapEntry find(Object key){
+	return null;
+}
+
+public virtual IPersistentMap add(Object key){
+	return put(key, null);
+}
+
+public virtual IPersistentMap put(Object key, Object val){
+	return new Tail(key, val);
+}
+
+public virtual IPersistentMap remove(Object key){
+	return this;
+}
+
+public virtual Object get(Object key){
+	return null;
+}
+
+public virtual int capacity(){
+	return 0;
+}
+
+internal class Iter : IEnumerator{
+	PersistentListMap e;
+	bool first = true;
+
+	internal Iter(PersistentListMap e)
+	{
+	this.e = e;
+	}
+
+#region IEnumerator Members
+
+public object Current
+	{
+	get { return e; }
+	}
+
+public bool MoveNext()
+	{
+	if(first)
+		first = false;
+	else
+		e = e.rest();
+	return e != EMPTY;
+	}
+
+public void Reset()
+	{
+	throw new Exception("The method or operation is not implemented.");
+	}
+
+#endregion
+	}
+
+public IEnumerator GetEnumerator(){
+	return new Iter(this);
+}
+
+internal class Tail : PersistentListMap {
+	readonly Object _key;
+	readonly Object _val;
+
+	internal Tail(Object key,Object val){
+		this._key = key;
+		this._val = val;
+		}
+
+    override internal PersistentListMap rest(){
+        return EMPTY;
+    }
+
+	override public int count()
+		{
+		return 1;
+	}
+
+	override public Object get(Object key)
+		{
+		if(equalKey(key,_key))
+			return _val;
+		return null;
+	}
+
+	override public int capacity()
+		{
+		return 1;
+	}
+
+	override public Object key()
+		{
+		return _key;
+	}
+
+	override public Object val()
+		{
+		return _val;
+	}
+
+	override public bool contains(Object key)
+		{
+		return equalKey(key,_key);
+	}
+
+	override public IMapEntry find(Object key)
+		{
+		if(equalKey(key,_key))
+			return this;
+		return null;
+	}
+
+	override public IPersistentMap put(Object key, Object val)
+		{
+		if(equalKey(key,_key))  //replace
+			{
+			if(val == _val)
+				return this;
+			return new Tail(key,val);
+			}
+		return new Link(key,val,this);
+	}
+
+	override public IPersistentMap remove(Object key){
+		if(equalKey(key,_key))
+			return EMPTY;
+		return this;
+	}
+}
+
+internal class Link : PersistentListMap {
+	readonly Object _key;
+	readonly Object _val;
+	readonly PersistentListMap _rest;
+
+	internal Link(Object key,Object val,PersistentListMap rest){
+		this._key = key;
+		this._val = val;
+		this._rest = rest;
+		}
+
+	override public Object key(){
+		return _key;
+	}
+
+	override public Object val(){
+		return _val;
+	}
+
+	override internal PersistentListMap rest(){
+        return _rest;
+        }
+
+	override public int count(){
+		return 1 + _rest.count();
+	}
+
+	override public bool contains(Object key){
+		return find(key) != null;
+	}
+
+	override public IMapEntry find(Object key){
+		if(equalKey(key,_key))
+			return this;
+		return _rest.find(key);
+	}
+
+	override public IPersistentMap put(Object key, Object val)
+		{
+		IMapEntry e = find(key);
+		if(e != null)
+			{
+			if(e.val() == val)
+				return this;
+			return create(_key,_val,remove(key));
+			}
+		return new Link(key,val,this);
+	}
+
+	override public IPersistentMap remove(Object key)
+		{
+		if(equalKey(key,_key))
+			return _rest;
+		PersistentListMap r = (PersistentListMap)_rest.remove(key);
+		if(r == _rest)  //not there
+			return this;
+		return create(_key,_val,r);
+	}
+
+	override public Object get(Object key){
+		IMapEntry e = find(key);
+		if(e != null)
+			return e.val();
+		return null;
+	}
+
+	override public int capacity(){
+		return count();
+	}
+
+	PersistentListMap create(Object k, Object v, IPersistentMap r)
+		{
+		if(r == EMPTY)
+			return new Tail(k,v);
+		return new Link(k, v, (PersistentListMap)r);
+	}
+
+}
+
+bool equalKey(Object k1,Object k2){
+    if(k1 == null)
+        return k2 == null;
+    return k1.Equals(k2);
+}
+}
+
+}
author	Rich Hickey <richhickey@gmail.com>	2006-06-07 19:41:23 +0000
committer	Rich Hickey <richhickey@gmail.com>	2006-06-07 19:41:23 +0000
commit	4e6dd0d78a9705f8be56be8145546ab9d512f961 (patch)
tree	fbaf9d794ce37fe90d70c971a4bb21e3714938f8 /src
parent	2023e999fa999c25acbbb212a9197eed6dce956c (diff)