Added IMap, IMapEntry, ArrayMaps

5 files changed, 257 insertions, 22 deletions

diff --git a/src/org/clojure/runtime/ArrayMap.java b/src/org/clojure/runtime/ArrayMap.java
new file mode 100644
index 00000000..9087d1f1
--- /dev/null
+++ b/src/org/clojure/runtime/ArrayMap.java
@@ -0,0 +1,164 @@
+/**

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

+

+/**

+ * Simple implementation of persistent map on an array

+

+ * Note that instances of this class are constant values

+ * i.e. add/remove etc return new values

+ *

+ * Copies array on every change, so only appropriate for _very_small_ maps

+ *

+ * null keys and values are ok, but you won't be able to distinguish a null value via get - use contains/find

+ */

+

+public class ArrayMap implements IMap, Iterable{

+

+Object[] array;

+

+public ArrayMap(){

+    this.array = RT.EMPTY_ARRAY;

+}

+

+/**

+ * This ctor captures/aliases the passed array, so do not modify later

+ * @param init {key1,val1,key2,val2,...}

+ */

+public ArrayMap(Object[] init){

+    this.array = init;

+}

+

+public int count() {

+    return array.length/2;

+}

+

+public boolean contains(Object key){

+	return indexOf(key) >= 0;

+}

+

+public IMapEntry find(Object key) {

+    int i = indexOf(key);

+    if(i >= 0)

+        return new Iter(array,i);

+    return null;

+}

+

+public IMap add(Object key) {

+

+    return put(key,null);

+}

+

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

+    int i = indexOf(key);

+    Object[] newArray;

+    if(i >= 0) //already have key, same-sized replacement

+        {

+        if(array[i+1] == val) //no change, no op

+            return this;

+        newArray = array.clone();

+        newArray[i+1] = val;

+        }

+    else //didn't have key, grow

+        {

+        newArray = new Object[array.length + 2];

+        newArray[array.length] = key;

+        newArray[array.length + 1] = val;

+        }

+    return new ArrayMap(newArray);

+}

+

+public IMap remove(Object key) {

+    int i = indexOf(key);

+    if(i >= 0) //have key, will remove

+        {

+        Object[] newArray = new Object[array.length - 2];

+        for(int s=0,d=0;s<array.length;s += 2)

+            {

+            if(!equalKey(array[s],key)) //skip removal key

+                {

+                newArray[d] = array[s];

+                newArray[d+1] = array[s+1];

+                d += 2;

+                }

+            }

+        return new ArrayMap(newArray);

+        }

+    //don't have key, no op

+    return this;

+}

+

+public Object get(Object key) {

+    int i = indexOf(key);

+    if(i >= 0)

+        return array[i + 1];

+    return null;

+}

+

+int indexOf(Object key){

+    for(int i=0;i<array.length;i+=2)

+        {

+        if(equalKey(array[i],key))

+            return i;

+        }

+    return -1;

+}

+

+boolean equalKey(Object k1,Object k2){

+    if(k1 == null)

+        return k2 == null;

+    return k1.equals(k2);

+}

+

+public Iterator iterator() {

+    return new Iter(array);

+}

+

+static class Iter implements Iterator,IMapEntry{

+    Object[] array;

+    int i;

+

+    //for iterator

+    Iter(Object[] array){

+        this(array,-2);

+

+    }

+

+    //for find

+    Iter(Object[] array, int i){

+        this.array = array;

+        this.i = i;

+    }

+

+    public boolean hasNext() {

+        return i < array.length - 2;

+    }

+

+    public Object next() {

+        i+=2;

+        return this;

+    }

+

+    public void remove() {

+        throw new UnsupportedOperationException();

+    }

+

+    public Object key() {

+        return array[i];

+    }

+

+    public Object val() {

+        return array[i+1];

+    }

+}

+}

diff --git a/src/org/clojure/runtime/IMap.java b/src/org/clojure/runtime/IMap.java
new file mode 100644
index 00000000..86b54144
--- /dev/null
+++ b/src/org/clojure/runtime/IMap.java
@@ -0,0 +1,29 @@
+/**

+ * 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 interface IMap {

+

+int count();

+

+boolean contains(Object key);

+

+IMapEntry find(Object key);

+

+IMap add(Object key);

+

+IMap put(Object key, Object val);

+

+IMap remove(Object key);

+

+Object get(Object key);

+}

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

+ * 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 interface IMapEntry {

+Object key();

+

+Object val();

+}

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

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

+

+/**

+ * ArrayMap using identity (==) comparison instead of equals

+ */

+public class IdentityArrayMap extends ArrayMap{

+

+boolean equalKey(Object k1, Object k2) {

+    return k1 == k2;

+}

+}

diff --git a/src/org/clojure/runtime/RBTree.java b/src/org/clojure/runtime/RBTree.java
index c43245cc..dc82c112 100644
--- a/src/org/clojure/runtime/RBTree.java
+++ b/src/org/clojure/runtime/RBTree.java
@@ -22,11 +22,11 @@ import java.util.*;
  * See Okasaki, Kahrs, Larsen et al
  */
 
-public class RBTree implements Iterable{
+public class RBTree implements Iterable, IMap {
 
 public final Comparator comp;
 public final Node tree;
-public final int count;
+public final int _count;
 
 public RBTree(){
 	this(null);
@@ -35,7 +35,7 @@ public RBTree(){
 public RBTree(Comparator comp){
 	this.comp = comp;
 	tree = null;
-	count = 0;
+	_count = 0;
 }
 
 public boolean contains(Object key){
@@ -54,9 +54,9 @@ public RBTree put(Object key, Object val){
 		Node foundNode = (Node) found.val;
 		if(foundNode.val() == val)  //note only get same collection on identity of val, not equals()
 			return this;
-		return new RBTree(comp, replace(tree, key, val), count);
+		return new RBTree(comp, replace(tree, key, val), _count);
 		}
-	return new RBTree(comp, t.blacken(), count + 1);
+	return new RBTree(comp, t.blacken(), _count + 1);
 }
 
 
@@ -70,7 +70,7 @@ public RBTree remove(Object key){
 		//empty
 		return new RBTree(comp);
 		}
-	return new RBTree(comp, t.blacken(), count - 1);
+	return new RBTree(comp, t.blacken(), _count - 1);
 }
 
 
@@ -143,19 +143,23 @@ public Object get(Object key){
 	return (n != null) ? n.val() : null;
 }
 
+public int count() {
+    return _count;
+}
+
 public Node 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;
+    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){
@@ -305,7 +309,7 @@ Node replace(Node t, Object key, Object val){
 RBTree(Comparator comp, Node tree, int count){
 	this.comp = comp;
 	this.tree = tree;
-	this.count = count;
+	this._count = count;
 }
 
 static Red red(Object key, Object val, Node left, Node right){
@@ -333,7 +337,7 @@ static Black black(Object key, Object val, Node left, Node right){
 }
 
 
-static abstract class Node{
+static abstract class Node implements IMapEntry {
 	final Object key;
 
 	Node(Object key){
@@ -679,7 +683,7 @@ static public void main(String args[]){
 		Integer anInt = ints[i];
 		set = set.put(anInt, anInt);
 		}
-	System.out.println("count = " + set.count + ", min: " + set.minKey() + ", max: " + set.maxKey()
+	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
 	                   + ", depth: " + set.depth());
 	Iterator it = set.keys();
 	while(it.hasNext())
@@ -698,7 +702,7 @@ static public void main(String args[]){
 		}
 
 	System.out.println();
-	System.out.println("count = " + set.count + ", min: " + set.minKey() + ", max: " + set.maxKey()
+	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
 	                   + ", depth: " + set.depth());
 }
 }