interim checkin

4 files changed, 255 insertions, 16 deletions

diff --git a/src/org/clojure/runtime/ArrayMap.java b/src/org/clojure/runtime/ArrayMap.java
index 45bde6b0..49dec167 100644
--- a/src/org/clojure/runtime/ArrayMap.java
+++ b/src/org/clojure/runtime/ArrayMap.java
@@ -23,7 +23,7 @@ import java.util.Iterator;
  * 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{

+public class ArrayMap implements IMap {

 

 final Object[] array;

 

diff --git a/src/org/clojure/runtime/HashtableMap.java b/src/org/clojure/runtime/HashtableMap.java
index 52119123..0bb1c53a 100644
--- a/src/org/clojure/runtime/HashtableMap.java
+++ b/src/org/clojure/runtime/HashtableMap.java
@@ -48,6 +48,12 @@ HashtableMap(int count,PersistentArray array) {
     this.growAtCount = (int) (this.array.length()*FILL_FACTOR);

 }

 

+HashtableMap(int count,PersistentArray array,int growAt) {

+    this._count = count;

+    this.array = array;

+    this.growAtCount = growAt;

+}

+

 int calcPrimeCapacity(int capacity) {

     return BigInteger.valueOf((long) (capacity/FILL_FACTOR)).nextProbablePrime().intValue();

 }

@@ -82,7 +88,7 @@ public IMap put(Object key, Object val) {
         return this;

     if(array.get(i) != null && ((IMap)newArray.get(i)).count() == ((IMap)array.get(i)).count()) //key already there, no growth

         incr = 0;

-    return create(_count + incr, newArray);

+    return create(_count + incr, newArray, growAtCount);

 }

 

 PersistentArray doPut(int i,Object key,Object val,PersistentArray array){

@@ -95,7 +101,8 @@ PersistentArray doPut(int i,Object key,Object val,PersistentArray array){
             return array;

         }

     else

-        newEntries = createArrayMap(new Object[]{key, val});

+	    newEntries = createListMap(key, val);

+		//newEntries = createArrayMap(new Object[]{key, val});

 

     return array.set(i, newEntries);

 }

@@ -139,22 +146,27 @@ IMap grow(){
     return create(_count,newArray);

 }

 

+/*

 static class Iter implements Iterator, IMapEntry{

-    PersistentArray buckets;

-    int b;

-    Object[] nextEntries;

-    int nextE;

+	PersistentArray buckets;

+

+	int b;

 

-    Object[] entries;

-    int e;

+	Object[] nextEntries;

 

-    Iter(PersistentArray buckets){

+	int nextE;

+

+	Object[] entries;

+

+	int e;

+

+	Iter(PersistentArray buckets){

         this.buckets = buckets;

         this.b = -1;

         nextBucket();

     }

 

-    private void nextBucket() {

+	private void nextBucket() {

         nextEntries = null;

         nextE = 0;

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

@@ -168,11 +180,11 @@ static class Iter implements Iterator, IMapEntry{
             }

     }

 

-    public boolean hasNext() {

+	public boolean hasNext() {

         return nextEntries != null;

     }

 

-    public Object next() {

+	public Object next() {

         entries = nextEntries;

         e = nextE;

         nextE += 2;

@@ -181,17 +193,59 @@ static class Iter implements Iterator, IMapEntry{
         return this;

     }

 

-    public void remove() {

+	public void remove() {

         throw new UnsupportedOperationException();

     }

 

-    public Object key() {

+	public Object key() {

         return entries[e];

     }

 

-    public Object val() {

+	public Object val() {

         return entries[e+1];

     }

+

+}

+*/

+static class Iter implements Iterator{

+	PersistentArray buckets;

+	int b;

+	ListMap.Entry e;

+

+		Iter(PersistentArray buckets){

+        this.buckets = buckets;

+        this.b = -1;

+        nextBucket();

+    }

+

+	private void nextBucket() {

+        e = null;

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

+            {

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

+            if(a != null)

+                {

+                e = a.entries;

+                break;

+                }

+            }

+    }

+

+	public boolean hasNext() {

+        return e != null;

+    }

+

+	public Object next() {

+		ListMap.Entry ret = e;

+        e = e.rest();

+        if(e == null)

+            nextBucket();

+        return ret;

+    }

+

+	public void remove() {

+        throw new UnsupportedOperationException();

+    }

 }

 

 IMap entriesFor(Object key){

@@ -210,8 +264,17 @@ IMap create(int count,PersistentArray array) {
     return new HashtableMap(count, array);

 }

 

+private IMap create(int i, PersistentArray newArray, int growAtCount){

+	return new HashtableMap(i, newArray, growAtCount);

+}

+

+

 IMap createArrayMap(Object[] init) {

     return new ArrayMap(init);

 }

 

+private IMap createListMap(Object key, Object val){

+	return new ListMap(key,val);

+}

+

 }

diff --git a/src/org/clojure/runtime/ListMap.java b/src/org/clojure/runtime/ListMap.java
new file mode 100644
index 00000000..18b17ee3
--- /dev/null
+++ b/src/org/clojure/runtime/ListMap.java
@@ -0,0 +1,173 @@
+/**
+ *   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 */
+
+package org.clojure.runtime;
+
+import java.util.Iterator;
+
+public class ListMap implements IMap
+{
+final Entry entries;
+final int _count;
+
+public ListMap(){
+	this.entries = null;
+	this._count = 0;
+}
+
+public ListMap(Object key, Object val){
+	this.entries = Entry.create(key, val, null);
+	this._count = 1;
+}
+
+ListMap(int count, Entry entries){
+	this._count = count;
+	this.entries = entries;
+}
+
+
+
+static class Entry implements IMapEntry{
+	final Object _key;
+	final Object _val;
+
+	Entry(Object key,Object val){
+		this._key = key;
+		this._val = val;
+		}
+
+    Entry rest(){
+        return null;
+    }
+
+    static Entry create(Object key,Object val,Entry rest){
+        if(rest == null)
+            return new Entry(key,val);
+        return new EntryLink(key, val, rest);
+    }
+
+	public Object key(){
+		return _key;
+	}
+
+	public Object val(){
+		return _val;
+	}
+}
+
+static class EntryLink extends Entry{
+	final Entry _rest;
+
+	EntryLink(Object key,Object val,Entry rest){
+        super(key,val);
+		this._rest = rest;
+		}
+
+    Entry rest(){
+        return _rest;
+    }
+}
+
+public int count(){
+	return _count;
+}
+
+public boolean contains(Object key){
+	return find(key) != null;
+}
+
+public Entry find(Object key){
+	for(Entry e = entries;e != null;e = e.rest())
+		{
+		if(equalKey(key,e._key))
+			return e;
+		}
+	return null;
+}
+
+public IMap add(Object key){
+	return put(key, null);
+}
+
+public IMap put(Object key, Object val){
+	Entry remEntries = doRemove(entries, key);
+	int incr = (remEntries == entries) ? 1 : 0;
+	return new ListMap(_count + incr, Entry.create(key, val, remEntries));
+}
+
+Entry doRemove(Entry e, Object key){
+	if(e == null)
+		return null;
+	else if(equalKey(key,e._key))
+		{
+		return e.rest();
+		}
+	else
+		{
+		Entry er = doRemove(e.rest(), key);
+		if(er != e.rest()) //removed in tail
+			return Entry.create(e._key, e._val, er);
+		return e;
+		}
+}
+
+public IMap remove(Object key){
+	Entry remEntries = doRemove(entries, key);
+	if(remEntries == entries) //didn't have key
+		return this;
+	return new ListMap(_count - 1, remEntries);
+}
+
+public Object get(Object key){
+	Entry e = find(key);
+	if(e != null)
+		return e._val;
+	return null;
+}
+
+public int capacity(){
+	return count();
+}
+
+static class Iter implements Iterator{
+	Entry e;
+
+	Iter(Entry e)
+	{
+	this.e = e;
+	}
+
+	public boolean hasNext(){
+		return e != null;
+	}
+
+	public Object next(){
+		Entry ret = e;
+		e = e.rest();
+		return ret;
+	}
+
+	public void remove(){
+		throw new UnsupportedOperationException();
+	}
+}
+
+public Iterator iterator(){
+	return new Iter(entries);
+}
+
+boolean equalKey(Object k1,Object k2){
+    if(k1 == null)
+        return k2 == null;
+    return k1.equals(k2);
+}
+}
diff --git a/src/org/clojure/runtime/RBTree.java b/src/org/clojure/runtime/RBTree.java
index 400b6283..af311db4 100644
--- a/src/org/clojure/runtime/RBTree.java
+++ b/src/org/clojure/runtime/RBTree.java
@@ -676,7 +676,10 @@ static public void main(String args[]){
 		}
 	Collections.shuffle(Arrays.asList(ints));
 	System.out.println("Building set");
+	//IMap set = new PersistentHashMap(1);
 	IMap set = new HashtableMap(1001);
+	//IMap set = new ListMap();
+	//IMap set = new RBTree();
 	for(int i = 0; i < ints.length; i++)
 		{
 		Integer anInt = ints[i];