diff options
author | Rich Hickey <richhickey@gmail.com> | 2006-06-06 01:31:35 +0000 |
---|---|---|
committer | Rich Hickey <richhickey@gmail.com> | 2006-06-06 01:31:35 +0000 |
commit | 2c46259efd90f7c28a51cf7638f3dbbecc5f90a4 (patch) | |
tree | 07f4b5a2f2039438a27ab50432c9cb694e20b17b | |
parent | b61885dee76bfa7ae6f64c0ef620be5f2fdc8f64 (diff) |
interim checkin
-rw-r--r-- | src/org/clojure/runtime/ArrayMap.java | 7 | ||||
-rw-r--r-- | src/org/clojure/runtime/HashtableMap.java | 217 | ||||
-rw-r--r-- | src/org/clojure/runtime/IMap.java | 4 | ||||
-rw-r--r-- | src/org/clojure/runtime/IdentityArrayMap.java | 6 | ||||
-rw-r--r-- | src/org/clojure/runtime/IdentityHashtableMap.java | 38 | ||||
-rw-r--r-- | src/org/clojure/runtime/PersistentHashMap.java | 100 | ||||
-rw-r--r-- | src/org/clojure/runtime/RBTree.java | 24 |
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()); } } |