summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRich Hickey <richhickey@gmail.com>2006-06-06 01:31:35 +0000
committerRich Hickey <richhickey@gmail.com>2006-06-06 01:31:35 +0000
commit2c46259efd90f7c28a51cf7638f3dbbecc5f90a4 (patch)
tree07f4b5a2f2039438a27ab50432c9cb694e20b17b
parentb61885dee76bfa7ae6f64c0ef620be5f2fdc8f64 (diff)
interim checkin
-rw-r--r--src/org/clojure/runtime/ArrayMap.java7
-rw-r--r--src/org/clojure/runtime/HashtableMap.java217
-rw-r--r--src/org/clojure/runtime/IMap.java4
-rw-r--r--src/org/clojure/runtime/IdentityArrayMap.java6
-rw-r--r--src/org/clojure/runtime/IdentityHashtableMap.java38
-rw-r--r--src/org/clojure/runtime/PersistentHashMap.java100
-rw-r--r--src/org/clojure/runtime/RBTree.java24
7 files changed, 384 insertions, 12 deletions
diff --git a/src/org/clojure/runtime/ArrayMap.java b/src/org/clojure/runtime/ArrayMap.java
index 89e95e38..45bde6b0 100644
--- a/src/org/clojure/runtime/ArrayMap.java
+++ b/src/org/clojure/runtime/ArrayMap.java
@@ -25,7 +25,7 @@ import java.util.Iterator;
public class ArrayMap implements IMap, Iterable{
-Object[] array;
+final Object[] array;
public ArrayMap(){
this.array = RT.EMPTY_ARRAY;
@@ -107,6 +107,10 @@ public Object get(Object key) {
return null;
}
+public int capacity() {
+ return count();
+}
+
int indexOf(Object key){
for(int i=0;i<array.length;i+=2)
{
@@ -133,7 +137,6 @@ static class Iter implements Iterator,IMapEntry{
//for iterator
Iter(Object[] array){
this(array,-2);
-
}
//for find
diff --git a/src/org/clojure/runtime/HashtableMap.java b/src/org/clojure/runtime/HashtableMap.java
new file mode 100644
index 00000000..52119123
--- /dev/null
+++ b/src/org/clojure/runtime/HashtableMap.java
@@ -0,0 +1,217 @@
+/**
+ * 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;
+import java.math.BigInteger;
+
+public class HashtableMap implements IMap, Iterable {
+
+static final float FILL_FACTOR = 0.75f;
+
+final PersistentArray array;
+final int _count;
+final int growAtCount;
+
+public HashtableMap(int initialCapacity) {
+ array = new PersistentArray(calcPrimeCapacity(initialCapacity));
+ _count = 0;
+ this.growAtCount = (int) (this.array.length()*FILL_FACTOR);
+}
+
+/**
+ * @param init {key1,val1,key2,val2,...}
+ */
+public HashtableMap(Object[] init){
+ //start halfway to a rehash
+ PersistentArray narray = new PersistentArray(calcPrimeCapacity(init.length));
+ for(int i=0;i<init.length;i+=2)
+ {
+ narray = doPut(bucketFor(init[i],narray),init[i], init[i + 1],narray);
+ }
+ this.array = narray;
+ this._count = init.length/2; //hmmm... presumes no dupe keys in init
+ this.growAtCount = (int) (this.array.length()*FILL_FACTOR);
+}
+
+HashtableMap(int count,PersistentArray array) {
+ this._count = count;
+ this.array = array;
+ this.growAtCount = (int) (this.array.length()*FILL_FACTOR);
+}
+
+int calcPrimeCapacity(int capacity) {
+ return BigInteger.valueOf((long) (capacity/FILL_FACTOR)).nextProbablePrime().intValue();
+}
+
+public int count() {
+ return _count;
+}
+
+public boolean contains(Object key) {
+ IMap entries = entriesFor(key);
+ return entries != null && entries.contains(key);
+}
+
+public IMapEntry find(Object key) {
+ IMap entries = entriesFor(key);
+ if(entries != null)
+ return entries.find(key);
+ return null;
+}
+
+public IMap add(Object key) {
+ return put(key, null);
+}
+
+public IMap put(Object key, Object val) {
+ if(_count > growAtCount)
+ return grow().put(key, val);
+ int i = bucketFor(key,array);
+ int incr = 1;
+ PersistentArray newArray = doPut(i, key, val, array);
+ if(newArray == array)
+ 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);
+}
+
+PersistentArray doPut(int i,Object key,Object val,PersistentArray array){
+ IMap entries = (IMap) array.get(i);
+ IMap newEntries;
+ if (entries != null)
+ {
+ newEntries = entries.put(key, val);
+ if(newEntries == entries) //already there with same value, no op
+ return array;
+ }
+ else
+ newEntries = createArrayMap(new Object[]{key, val});
+
+ return array.set(i, newEntries);
+}
+
+public IMap remove(Object key) {
+ int i = bucketFor(key,array);
+ IMap entries = (IMap) array.get(i);
+ if (entries != null)
+ {
+ IMap newEntries = entries.remove(key);
+ if (newEntries != entries)
+ return create(_count - 1, array.set(i, newEntries));
+ }
+ //not there, no op
+ return this;
+}
+
+public Object get(Object key) {
+ IMap entries = entriesFor(key);
+ if(entries != null)
+ return entries.get(key);
+ return null;
+}
+
+public int capacity() {
+ return array.length();
+}
+
+public Iterator<IMapEntry> iterator() {
+ return new Iter(array);
+}
+
+
+IMap grow(){
+ PersistentArray newArray = new PersistentArray(calcPrimeCapacity(_count * 2));
+ for (Object o : this)
+ {
+ IMapEntry e = (IMapEntry) o;
+ newArray = doPut(bucketFor(e.key(),newArray),e.key(), e.val(),newArray);
+ }
+ 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 Object val() {
+ return entries[e+1];
+ }
+}
+
+IMap entriesFor(Object key){
+ return (IMap) array.get(bucketFor(key,array));
+}
+
+static int bucketFor(Object key, PersistentArray array) {
+ return (key.hashCode() & 0x7fffffff)%array.length();
+}
+
+IMap create(int capacity) {
+ return new HashtableMap(capacity);
+}
+
+IMap create(int count,PersistentArray array) {
+ return new HashtableMap(count, array);
+}
+
+IMap createArrayMap(Object[] init) {
+ return new ArrayMap(init);
+}
+
+}
diff --git a/src/org/clojure/runtime/IMap.java b/src/org/clojure/runtime/IMap.java
index 86b54144..015df00d 100644
--- a/src/org/clojure/runtime/IMap.java
+++ b/src/org/clojure/runtime/IMap.java
@@ -11,7 +11,7 @@
package org.clojure.runtime;
-public interface IMap {
+public interface IMap extends Iterable {
int count();
@@ -26,4 +26,6 @@ IMap put(Object key, Object val);
IMap remove(Object key);
Object get(Object key);
+
+int capacity();
}
diff --git a/src/org/clojure/runtime/IdentityArrayMap.java b/src/org/clojure/runtime/IdentityArrayMap.java
index 0c4991de..ed0c7106 100644
--- a/src/org/clojure/runtime/IdentityArrayMap.java
+++ b/src/org/clojure/runtime/IdentityArrayMap.java
@@ -14,6 +14,12 @@ package org.clojure.runtime;
* ArrayMap using identity (==) comparison instead of equals
*/
public class IdentityArrayMap extends ArrayMap{
+public IdentityArrayMap() {
+}
+
+public IdentityArrayMap(Object[] init) {
+ super(init);
+}
boolean equalKey(Object k1, Object k2) {
return k1 == k2;
diff --git a/src/org/clojure/runtime/IdentityHashtableMap.java b/src/org/clojure/runtime/IdentityHashtableMap.java
new file mode 100644
index 00000000..71d93eeb
--- /dev/null
+++ b/src/org/clojure/runtime/IdentityHashtableMap.java
@@ -0,0 +1,38 @@
+/**
+ * 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 IdentityHashtableMap extends HashtableMap{
+
+public IdentityHashtableMap(int initialCapacity) {
+ super(initialCapacity);
+}
+
+public IdentityHashtableMap(Object[] init) {
+ super(init);
+}
+
+IdentityHashtableMap(int count, PersistentArray array) {
+ super(count, array);
+}
+
+IMap create(int capacity) {
+ return new IdentityHashtableMap(capacity);
+}
+
+IMap create(int count, PersistentArray array) {
+ return new IdentityHashtableMap(count, array);
+}
+
+IMap createArrayMap(Object[] init) {
+ return new IdentityArrayMap(init);
+}
+}
diff --git a/src/org/clojure/runtime/PersistentHashMap.java b/src/org/clojure/runtime/PersistentHashMap.java
new file mode 100644
index 00000000..40fb50dc
--- /dev/null
+++ b/src/org/clojure/runtime/PersistentHashMap.java
@@ -0,0 +1,100 @@
+/**
+ * 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;
+
+public class PersistentHashMap implements IMap, Iterable{
+
+IMap impl;
+static final int CAPACITY_THRESHOLD = 10;
+
+public PersistentHashMap(Object[] init){
+ if(init.length/2 < CAPACITY_THRESHOLD)
+ impl = createArrayMap(init);
+ impl = createHashtableMap(init);
+}
+
+public PersistentHashMap(int initialCapacity){
+ if(initialCapacity < CAPACITY_THRESHOLD)
+ impl = createArrayMap();
+ impl = createHashtableMap(initialCapacity);
+}
+
+PersistentHashMap(IMap impl){
+ this.impl = impl;
+}
+
+public int count() {
+ return impl.count();
+}
+
+public boolean contains(Object key) {
+ return impl.contains(key);
+}
+
+public IMapEntry find(Object key) {
+ return impl.find(key);
+}
+
+public IMap add(Object key) {
+ return put(key, null);
+}
+
+public IMap put(Object key, Object val) {
+ IMap newImpl = impl.put(key,val);
+ if(newImpl.capacity() == CAPACITY_THRESHOLD)
+ {
+ newImpl = createHashtableMap(((ArrayMap)newImpl).array);
+ }
+ return create(newImpl);
+}
+
+public IMap remove(Object key) {
+ IMap newImpl = impl.remove(key);
+ if(newImpl != impl)
+ return create(newImpl);
+ return this;
+}
+
+public Object get(Object key) {
+ return impl.get(key);
+}
+
+public int capacity() {
+ return impl.capacity();
+}
+
+public Iterator iterator() {
+ return ((Iterable)impl).iterator();
+}
+
+public IMap create(IMap impl) {
+ return new PersistentHashMap(impl);
+}
+
+public ArrayMap createArrayMap(Object[] init) {
+ return new ArrayMap(init);
+}
+
+private IMap createArrayMap() {
+ return new ArrayMap();
+}
+
+private IMap createHashtableMap(Object[] init) {
+ return new HashtableMap(init);
+}
+
+private IMap createHashtableMap(int initialCapacity) {
+ return new HashtableMap(initialCapacity);
+}
+
+}
diff --git a/src/org/clojure/runtime/RBTree.java b/src/org/clojure/runtime/RBTree.java
index dc82c112..400b6283 100644
--- a/src/org/clojure/runtime/RBTree.java
+++ b/src/org/clojure/runtime/RBTree.java
@@ -143,6 +143,10 @@ public Object get(Object key){
return (n != null) ? n.val() : null;
}
+public int capacity() {
+ return _count;
+}
+
public int count() {
return _count;
}
@@ -672,7 +676,7 @@ static public void main(String args[]){
}
Collections.shuffle(Arrays.asList(ints));
System.out.println("Building set");
- RBTree set = new RBTree();
+ IMap set = new HashtableMap(1001);
for(int i = 0; i < ints.length; i++)
{
Integer anInt = ints[i];
@@ -683,16 +687,17 @@ 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()
- + ", depth: " + set.depth());
- Iterator it = set.keys();
+ System.out.println("_count = " + set.count());
+// System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
+// + ", depth: " + set.depth());
+ Iterator it = set.iterator();
while(it.hasNext())
{
- Object o = it.next();
- if(!set.contains(o))
+ IMapEntry o = (IMapEntry) it.next();
+ if(!set.contains(o.key()))
System.err.println("Can't find: " + o);
else if(n < 2000)
- System.out.print(o.toString() + ",");
+ System.out.print(o.key().toString() + ",");
}
for(int i = 0; i < ints.length/2; i++)
@@ -702,7 +707,8 @@ static public void main(String args[]){
}
System.out.println();
- System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
- + ", depth: " + set.depth());
+ System.out.println("_count = " + set.count());
+// System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
+// + ", depth: " + set.depth());
}
}