From 7e9b97b213b0214238c244eff9389554adcba54e Mon Sep 17 00:00:00 2001 From: Rich Hickey Date: Fri, 4 Aug 2006 23:16:49 +0000 Subject: got rid of identity maps --- src/cli/runtime/PersistentArrayIdentityMap.cs | 50 --- src/cli/runtime/PersistentHashtableIdentityMap.cs | 111 ------- src/cli/runtime/PersistentListIdentityMap.cs | 384 ---------------------- 3 files changed, 545 deletions(-) delete mode 100644 src/cli/runtime/PersistentArrayIdentityMap.cs delete mode 100644 src/cli/runtime/PersistentHashtableIdentityMap.cs delete mode 100644 src/cli/runtime/PersistentListIdentityMap.cs (limited to 'src/cli') diff --git a/src/cli/runtime/PersistentArrayIdentityMap.cs b/src/cli/runtime/PersistentArrayIdentityMap.cs deleted file mode 100644 index 93fe2a15..00000000 --- a/src/cli/runtime/PersistentArrayIdentityMap.cs +++ /dev/null @@ -1,50 +0,0 @@ -/** - * 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. - **/ - -using System; - -namespace clojure.lang -{ -/** - * ArrayMap using identity (==) comparison instead of equals - */ -public class PersistentArrayIdentityMap : PersistentArrayMap { - -new public static PersistentArrayIdentityMap EMPTY = new PersistentArrayIdentityMap(); - -override public IPersistentMap empty() { - return EMPTY; -} - -PersistentArrayIdentityMap() { -} - -override internal PersistentArrayMap create(params Object[] init) - { - PersistentArrayIdentityMap ret = new PersistentArrayIdentityMap(init); - ret._meta = _meta; - return ret; - } - -override internal IPersistentMap createHT(Object[] init){ - PersistentHashtableIdentityMap ret = new PersistentHashtableIdentityMap(init); - ret._meta = _meta; - return ret; -} - -public PersistentArrayIdentityMap(params Object[] init) :base(init) { -} - -internal override bool equalKey(Object k1, Object k2) { - return k1 == k2; -} -} - -} \ No newline at end of file diff --git a/src/cli/runtime/PersistentHashtableIdentityMap.cs b/src/cli/runtime/PersistentHashtableIdentityMap.cs deleted file mode 100644 index 5ea01457..00000000 --- a/src/cli/runtime/PersistentHashtableIdentityMap.cs +++ /dev/null @@ -1,111 +0,0 @@ -/** - * 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. - **/ - -using System; -using System.Collections; - -namespace clojure.lang - { - -public class PersistentHashtableIdentityMap : PersistentHashtableMap { - -public PersistentHashtableIdentityMap(int initialCapacity) : base(initialCapacity) { -} - -public PersistentHashtableIdentityMap(Object[] init) : base(init){ -} - -PersistentHashtableIdentityMap(int count, PersistentArray array) : base(count, array) { -} - -PersistentHashtableIdentityMap(int i, PersistentArray newArray, int growAtCount):base(i,newArray,growAtCount){ -} - - -override public IEnumerator GetEnumerator() - { - return new Iter2(array); - } - - -internal class Iter2 : IEnumerator - { - PersistentArray buckets; - int b; - Object e; - - internal Iter2(PersistentArray buckets) - { - this.buckets = buckets; - this.b = -1; - } - - private void nextBucket() - { - e = null; - for (b = b + 1; b < buckets.length(); b++) - { - Object a = buckets.get(b); - if (a != null && a != PersistentListIdentityMap.EMPTY) - { - e = a; - break; - } - } - } - - #region IEnumerator Members - - public object Current - { - get { return e; } - } - - public bool MoveNext() - { - if (e == null || (e = ((PersistentListIdentityMap)e).next()) == PersistentListIdentityMap.EMPTY) - nextBucket(); - return e != null; - } - - public void Reset() - { - throw new Exception("The method or operation is not implemented."); - } - - #endregion - } - - -internal override IPersistentMap create(int capacity) { - PersistentHashtableIdentityMap ret = new PersistentHashtableIdentityMap(capacity); - ret._meta = _meta; - return ret; - } - -internal override IPersistentMap create(int count, PersistentArray array) { - PersistentHashtableIdentityMap ret = new PersistentHashtableIdentityMap(count, array); - ret._meta = _meta; - return ret; - } - -internal override IPersistentMap create(int i, PersistentArray newArray, int growAtCount){ - PersistentHashtableIdentityMap ret = new PersistentHashtableIdentityMap(i, newArray, growAtCount); - ret._meta = _meta; - return ret; - } - -internal override IPersistentMap createListMap(Object key, Object val){ - return PersistentListIdentityMap.create(key,val); -} - -} - -} diff --git a/src/cli/runtime/PersistentListIdentityMap.cs b/src/cli/runtime/PersistentListIdentityMap.cs deleted file mode 100644 index 6a84c000..00000000 --- a/src/cli/runtime/PersistentListIdentityMap.cs +++ /dev/null @@ -1,384 +0,0 @@ -/** - * 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 clojure.lang - { - /** - * 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 : Obj, IPersistentMap, IMapEntry, ISeq, IPersistentCollection - { - - static public PersistentListIdentityMap EMPTY = new PersistentListIdentityMap(); - - static public PersistentListIdentityMap create(Object key, Object val) - { - return new Tail(key, val,null); - } - - public override Obj withMeta(IPersistentMap meta) - { - Obj ret = (Obj)MemberwiseClone(); - ret._meta = meta; - return ret; - } - - public virtual Object key() - { - return null; - } - - public virtual Object val() - { - return null; - } - - internal virtual PersistentListIdentityMap next() - { - 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, Object val) - { - return put(key, val); - } - - public virtual IPersistentMap put(Object key, Object val) - { - return new Tail(key, val, _meta); - } - - public virtual IPersistentMap remove(Object key) - { - return this; - } - - public virtual Object get(Object key) - { - return null; - } - - public virtual int capacity() - { - return 0; - } - - virtual public Object first() - { - return null; - } - - virtual public ISeq rest() - { - return null; - } - - virtual public ISeq seq() - { - return null; - } - - 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.next(); - return e.count() > 0; - } - - 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, IPersistentMap meta) - { - this._key = key; - this._val = val; - this._meta = meta; - } - - override internal PersistentListIdentityMap next() - { - 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 add(Object key, Object val) - { - if ((key == _key)) - { - throw new Exception("Key already present"); - } - return new Link(key, val, this, _meta); - } - - override public IPersistentMap put(Object key, Object val) - { - if ((key == _key)) //replace - { - if (val == _val) - return this; - return new Tail(key, val, _meta); - } - return new Link(key, val, this, _meta); - } - - override public IPersistentMap remove(Object key) - { - if ((key == _key)) - { - if (_meta == null) - return EMPTY; - return (IPersistentMap)EMPTY.withMeta(_meta); - } - return this; - } - - override public Object first() - { - return this; - } - - override public ISeq rest() - { - return null; - } - - override public ISeq seq() - { - return this; - } - } - - internal class Link : PersistentListIdentityMap - { - readonly Object _key; - readonly Object _val; - readonly PersistentListIdentityMap _rest; - - internal Link(Object key, Object val, PersistentListIdentityMap next, IPersistentMap meta) - { - this._key = key; - this._val = val; - this._rest = next; - this._meta = meta; - } - - override public Object key() - { - return _key; - } - - override public Object val() - { - return _val; - } - - override internal PersistentListIdentityMap next() - { - 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 add(Object key, Object val) - { - IMapEntry e = find(key); - if (e != null) - { - throw new Exception("Key already present"); - } - return new Link(key, val, this, _meta); - } - - 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, _meta); - } - - override public IPersistentMap remove(Object key) - { - if ((key == _key)) - { - if (_rest._meta == _meta) - return _rest; - return (IPersistentMap)_rest.withMeta(_meta); - } - 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(); - } - - override public Object first() - { - return this; - } - - override public ISeq rest() - { - return _rest; - } - - override public ISeq seq() - { - return this; - } - - PersistentListIdentityMap create(Object k, Object v, IPersistentMap r) - { - if (r == EMPTY) - return new Tail(k, v, _meta); - return new Link(k, v, (PersistentListIdentityMap)r, _meta); - } - - } - - } - - } -- cgit v1.2.3-70-g09d2