From 800a956ffed030dbce4ec2bf394a331ec6dbc83b Mon Sep 17 00:00:00 2001
From: Rich Hickey <richhickey@gmail.com>
Date: Tue, 6 Jun 2006 15:35:19 +0000
Subject: interim checkin

---
 src/org/clojure/runtime/ArrayMap.java     |   2 +-
 src/org/clojure/runtime/HashtableMap.java |  93 +++++++++++++---
 src/org/clojure/runtime/ListMap.java      | 173 ++++++++++++++++++++++++++++++
 src/org/clojure/runtime/RBTree.java       |   3 +
 4 files changed, 255 insertions(+), 16 deletions(-)
 create mode 100644 src/org/clojure/runtime/ListMap.java

(limited to 'src/org')

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];
-- 
cgit v1.2.3-70-g09d2