fixed up identity versions

6 files changed, 357 insertions, 76 deletions

diff --git a/src/org/clojure/runtime/PersistentHashtableMap.java b/src/org/clojure/runtime/PersistentHashtableMap.java
index 7047afa3..7a6b5f21 100644
--- a/src/org/clojure/runtime/PersistentHashtableMap.java
+++ b/src/org/clojure/runtime/PersistentHashtableMap.java
@@ -131,11 +131,6 @@ public int capacity() {
     return array.length();

 }

 

-public Iterator<IMapEntry> iterator() {

-    return new Iter(array);

-}

-

-

 IPersistentMap grow(){

     PersistentArray newArray = new PersistentArray(calcPrimeCapacity(_count * 2));

     for (Object o : this)

@@ -146,67 +141,11 @@ IPersistentMap grow(){
     return create(_count,newArray);

 }

 

-/*

-static class Iter implements Iterator, IMapEntry{

-	PersistentArray buckets;

-

-	int b;

-

-	Object[] nextEntries;

-

-	int nextE;

-

-	Object[] entries;

-

-	int e;

-

-	Iter(PersistentArray buckets){

-        this.buckets = buckets;

-        this.b = -1;

-        nextBucket();

-    }

-

-	private void nextBucket() {

-        nextEntries = null;

-        nextE = 0;

-        for(b = b+1;b<buckets.length();b++)

-            {

-            ArrayMap a = (ArrayMap) buckets.get(b);

-            if(a != null)

-                {

-                nextEntries = a.array;

-                break;

-                }

-            }

-    }

-

-	public boolean hasNext() {

-        return nextEntries != null;

-    }

-

-	public Object next() {

-        entries = nextEntries;

-        e = nextE;

-        nextE += 2;

-        if(nextE >= nextEntries.length)

-            nextBucket();

-        return this;

-    }

-

-	public void remove() {

-        throw new UnsupportedOperationException();

-    }

-

-	public Object key() {

-        return entries[e];

-    }

+public Iterator<IMapEntry> iterator() {

+    return new Iter(array);

+}

 

-	public Object val() {

-        return entries[e+1];

-    }

 

-}

-*/

 static class Iter implements Iterator{

 	PersistentArray buckets;

 	int b;

@@ -264,16 +203,12 @@ IPersistentMap create(int count,PersistentArray array) {
     return new PersistentHashtableMap(count, array);

 }

 

-private IPersistentMap create(int i, PersistentArray newArray, int growAtCount){

+IPersistentMap create(int i, PersistentArray newArray, int growAtCount){

 	return new PersistentHashtableMap(i, newArray, growAtCount);

 }

 

 

-IPersistentMap createArrayMap(Object[] init) {

-    return new PersistentArrayMap(init);

-}

-

-private IPersistentMap createListMap(Object key, Object val){

+IPersistentMap createListMap(Object key, Object val){

 	return PersistentListMap.create(key,val);

 }

 

diff --git a/src/org/clojure/runtime/PersistentHybridIdentityMap.java b/src/org/clojure/runtime/PersistentHybridIdentityMap.java
new file mode 100644
index 00000000..d3d6b743
--- /dev/null
+++ b/src/org/clojure/runtime/PersistentHybridIdentityMap.java
@@ -0,0 +1,47 @@
+/**

+ *   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.

+ **/

+

+package org.clojure.runtime;

+

+public class PersistentHybridIdentityMap extends PersistentHybridMap{

+

+public PersistentHybridIdentityMap(Object[] init) {

+    super(init);

+}

+

+public PersistentHybridIdentityMap(int initialCapacity) {

+    super(initialCapacity);

+}

+

+PersistentHybridIdentityMap(IPersistentMap impl) {

+    super(impl);

+}

+

+public IPersistentMap create(IPersistentMap impl) {

+    return new PersistentHybridIdentityMap(impl);

+}

+

+public PersistentArrayMap createArrayMap(Object[] init) {

+    return new PersistentIdentityArrayMap(init);

+}

+

+IPersistentMap createArrayMap() {

+    return new PersistentIdentityArrayMap();

+}

+

+IPersistentMap createHashtableMap(Object[] init) {

+    return new PersistentIdentityHashtableMap(init);

+}

+

+IPersistentMap createHashtableMap(int initialCapacity) {

+    return new PersistentIdentityHashtableMap(initialCapacity);

+}

+

+}

diff --git a/src/org/clojure/runtime/PersistentHybridMap.java b/src/org/clojure/runtime/PersistentHybridMap.java
index 215b13c0..0779a09a 100644
--- a/src/org/clojure/runtime/PersistentHybridMap.java
+++ b/src/org/clojure/runtime/PersistentHybridMap.java
@@ -86,15 +86,15 @@ public PersistentArrayMap createArrayMap(Object[] init) {
     return new PersistentArrayMap(init);

 }

 

-private IPersistentMap createArrayMap() {

+IPersistentMap createArrayMap() {

     return new PersistentArrayMap();

 }

 

-private IPersistentMap createHashtableMap(Object[] init) {

+IPersistentMap createHashtableMap(Object[] init) {

     return new PersistentHashtableMap(init);

 }

 

-private IPersistentMap createHashtableMap(int initialCapacity) {

+IPersistentMap createHashtableMap(int initialCapacity) {

     return new PersistentHashtableMap(initialCapacity);

 }

 

diff --git a/src/org/clojure/runtime/PersistentIdentityHashtableMap.java b/src/org/clojure/runtime/PersistentIdentityHashtableMap.java
index 190fcb74..1cbf2749 100644
--- a/src/org/clojure/runtime/PersistentIdentityHashtableMap.java
+++ b/src/org/clojure/runtime/PersistentIdentityHashtableMap.java
@@ -10,6 +10,8 @@
 

 package org.clojure.runtime;

 

+import java.util.Iterator;

+

 public class PersistentIdentityHashtableMap extends PersistentHashtableMap {

 

 public PersistentIdentityHashtableMap(int initialCapacity) {

@@ -24,6 +26,53 @@ PersistentIdentityHashtableMap(int count, PersistentArray array) {
     super(count, array);

 }

 

+

+public Iterator<IMapEntry> iterator() {

+    return new Iter(array);

+}

+

+

+static class Iter implements Iterator{

+    PersistentArray buckets;

+    int b;

+    PersistentIdentityListMap e;

+

+    Iter(PersistentArray buckets){

+        this.buckets = buckets;

+        this.b = -1;

+        nextBucket();

+    }

+

+    private void nextBucket() {

+        e = null;

+        for(b = b+1;b<buckets.length();b++)

+            {

+            PersistentIdentityListMap a = (PersistentIdentityListMap) buckets.get(b);

+            if(a != null && a != PersistentIdentityListMap.EMPTY)

+                {

+                e = a;

+                break;

+                }

+            }

+    }

+

+    public boolean hasNext() {

+        return e != null;

+    }

+

+    public Object next() {

+        PersistentIdentityListMap ret = e;

+        e = e.rest();

+        if(e == PersistentIdentityListMap.EMPTY)

+            nextBucket();

+        return ret;

+    }

+

+    public void remove() {

+        throw new UnsupportedOperationException();

+    }

+}

+

 IPersistentMap create(int capacity) {

     return new PersistentIdentityHashtableMap(capacity);

 }

@@ -32,7 +81,8 @@ IPersistentMap create(int count, PersistentArray array) {
     return new PersistentIdentityHashtableMap(count, array);

 }

 

-IPersistentMap createArrayMap(Object[] init) {

-    return new PersistentIdentityArrayMap(init);

+IPersistentMap createListMap(Object key, Object val){

+    return PersistentIdentityListMap.create(key,val);

 }

+

 }

diff --git a/src/org/clojure/runtime/PersistentIdentityListMap.java b/src/org/clojure/runtime/PersistentIdentityListMap.java
new file mode 100644
index 00000000..36d77336
--- /dev/null
+++ b/src/org/clojure/runtime/PersistentIdentityListMap.java
@@ -0,0 +1,249 @@
+/**

+ *   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.

+ **/

+

+package org.clojure.runtime;

+

+import java.util.Iterator;

+

+/**

+ * Immplementation 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 PersistentIdentityListMap implements IPersistentMap, IMapEntry

+{

+

+static public PersistentIdentityListMap EMPTY = new PersistentIdentityListMap();

+

+static public PersistentIdentityListMap create(Object key, Object val){

+	return new Tail(key, val);

+}

+

+public Object key(){

+	return null;

+}

+

+public Object val(){

+	return null;

+}

+

+PersistentIdentityListMap rest(){

+    return this;

+    }

+

+public int count(){

+	return 0;

+}

+

+public boolean contains(Object key){

+	return false;

+}

+

+public IMapEntry find(Object key){

+	return null;

+}

+

+public IPersistentMap add(Object key){

+	return put(key, null);

+}

+

+public PersistentIdentityListMap put(Object key, Object val){

+	return new Tail(key, val);

+}

+

+public PersistentIdentityListMap remove(Object key){

+	return this;

+}

+

+public Object get(Object key){

+	return null;

+}

+

+public int capacity(){

+	return 0;

+}

+

+static class Iter implements Iterator{

+	PersistentIdentityListMap e;

+

+	Iter(PersistentIdentityListMap e)

+	{

+	this.e = e;

+	}

+

+	public boolean hasNext(){

+		return e != EMPTY;

+	}

+

+	public Object next(){

+		PersistentIdentityListMap ret = e;

+		e = e.rest();

+		return ret;

+	}

+

+	public void remove(){

+		throw new UnsupportedOperationException();

+	}

+}

+

+public Iterator iterator(){

+	return new Iter(this);

+}

+

+static class Tail extends PersistentIdentityListMap {

+	final Object _key;

+	final Object _val;

+

+	Tail(Object key,Object val){

+		this._key = key;

+		this._val = val;

+		}

+

+    PersistentIdentityListMap rest(){

+        return EMPTY;

+    }

+

+	public int count(){

+		return 1;

+	}

+

+	public Object get(Object key){

+		if(key ==_key)

+			return _val;

+		return null;

+	}

+

+	public int capacity(){

+		return 1;

+	}

+

+	public Object key(){

+		return _key;

+	}

+

+	public Object val(){

+		return _val;

+	}

+

+	public boolean contains(Object key){

+		return key ==_key;

+	}

+

+	public IMapEntry find(Object key){

+		if(key ==_key)

+			return this;

+		return null;

+	}

+

+	public PersistentIdentityListMap 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);

+	}

+

+	public PersistentIdentityListMap remove(Object key){

+		if(key == _key)

+			return EMPTY;

+		return this;

+	}

+}

+

+static class Link extends PersistentIdentityListMap {

+	final Object _key;

+	final Object _val;

+	final PersistentIdentityListMap _rest;

+

+	Link(Object key,Object val,PersistentIdentityListMap rest){

+		this._key = key;

+		this._val = val;

+		this._rest = rest;

+		}

+

+	public Object key(){

+		return _key;

+	}

+

+	public Object val(){

+		return _val;

+	}

+

+	PersistentIdentityListMap rest(){

+        return _rest;

+        }

+

+	public int count(){

+		return 1 + _rest.count();

+	}

+

+	public boolean contains(Object key){

+		return find(key) != null;

+	}

+

+	public IMapEntry find(Object key){

+		if(key ==_key)

+			return this;

+		return _rest.find(key);

+	}

+

+	public PersistentIdentityListMap 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);

+	}

+

+	public PersistentIdentityListMap remove(Object key){

+		if(key == _key)

+			return _rest;

+		PersistentIdentityListMap r = _rest.remove(key);

+		if(r == _rest)  //not there

+			return this;

+		return create(_key,_val,r);

+	}

+

+	public Object get(Object key){

+		IMapEntry e = find(key);

+		if(e != null)

+			return e.val();

+		return null;

+	}

+

+	public int capacity(){

+		return count();

+	}

+

+	PersistentIdentityListMap create(Object k,Object v,PersistentIdentityListMap r){

+		if(r == EMPTY)

+			return new Tail(k,v);

+		return new Link(k, v, r);

+	}

+

+}

+

+}

diff --git a/src/org/clojure/runtime/PersistentListMap.java b/src/org/clojure/runtime/PersistentListMap.java
index cbe772d4..b6f13c73 100644
--- a/src/org/clojure/runtime/PersistentListMap.java
+++ b/src/org/clojure/runtime/PersistentListMap.java
@@ -21,7 +21,7 @@ import java.util.Iterator;
  * i.e. add/remove etc return new values
  *
  * Lookups/changes are linear, so only appropriate for _very_small_ maps
- * ArrayMap is generally faster, but this class avoids the double allocation,
+ * 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