Replaced PersistentHashMap by PersistentHashMap2

Signed-off-by: Rich Hickey <richhickey@gmail.com>

2 files changed, 607 insertions, 1601 deletions

diff --git a/src/jvm/clojure/lang/PersistentHashMap.java b/src/jvm/clojure/lang/PersistentHashMap.java
index ecfbeca1..101a6df9 100644
--- a/src/jvm/clojure/lang/PersistentHashMap.java
+++ b/src/jvm/clojure/lang/PersistentHashMap.java
@@ -32,16 +32,14 @@
  POSSIBILITY OF SUCH DAMAGE.
  **/
 
-/* rich Jun 18, 2007 */
-
 package clojure.lang;
 
-import java.util.*;
-//this stuff is just for the test main()
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
 import java.util.concurrent.atomic.AtomicReference;
 
-import clojure.lang.PersistentVector.Node;
-
 /*
  A persistent rendition of Phil Bagwell's Hash Array Mapped Trie
 
@@ -56,8 +54,11 @@ public class PersistentHashMap extends APersistentMap implements IEditableCollec
 
 final int count;
 final INode root;
+final boolean hasNull;
+final Object nullValue;
 
-final public static PersistentHashMap EMPTY = new PersistentHashMap(0, new EmptyNode());
+final public static PersistentHashMap EMPTY = new PersistentHashMap(0, null, false, null);
+final private static Object NOT_FOUND = new Object();
 
 static public IPersistentMap create(Map other){
 	ITransientMap ret = EMPTY.asTransient();
@@ -112,39 +113,51 @@ public static PersistentHashMap create(IPersistentMap meta, Object... init){
 	return create(init).withMeta(meta);
 }
 
-PersistentHashMap(int count, INode root){
+PersistentHashMap(int count, INode root, boolean hasNull, Object nullValue){
 	this.count = count;
 	this.root = root;
+	this.hasNull = hasNull;
+	this.nullValue = nullValue;
 }
 
-
-public PersistentHashMap(IPersistentMap meta, int count, INode root){
+public PersistentHashMap(IPersistentMap meta, int count, INode root, boolean hasNull, Object nullValue){
 	super(meta);
 	this.count = count;
 	this.root = root;
+	this.hasNull = hasNull;
+	this.nullValue = nullValue;
 }
 
 public boolean containsKey(Object key){
-	return entryAt(key) != null;
+	if(key == null)
+		return hasNull;
+	return (root != null) ? root.find(0, Util.hash(key), key, NOT_FOUND) != NOT_FOUND : false;
 }
 
 public IMapEntry entryAt(Object key){
-	return root.find(Util.hash(key), key);
+	if(key == null)
+		return hasNull ? new MapEntry(null, nullValue) : null;
+	return (root != null) ? root.find(0, Util.hash(key), key) : null;
 }
 
 public IPersistentMap assoc(Object key, Object val){
+	if(key == null) {
+		if(hasNull && val == nullValue)
+			return this;
+		return new PersistentHashMap(meta(), hasNull ? count : count + 1, root, true, val);
+	}
 	Box addedLeaf = new Box(null);
-	INode newroot = root.assoc(0, Util.hash(key), key, val, addedLeaf);
+	INode newroot = (root == null ? BitmapIndexedNode.EMPTY : root) 
+			.assoc(0, Util.hash(key), key, val, addedLeaf);
 	if(newroot == root)
 		return this;
-	return new PersistentHashMap(meta(), addedLeaf.val == null ? count : count + 1, newroot);
+	return new PersistentHashMap(meta(), addedLeaf.val == null ? count : count + 1, newroot, hasNull, nullValue);
 }
 
 public Object valAt(Object key, Object notFound){
-	IMapEntry e = entryAt(key);
-	if(e != null)
-		return e.val();
-	return notFound;
+	if(key == null)
+		return hasNull ? nullValue : notFound;
+	return root != null ? root.find(0, Util.hash(key), key, notFound) : notFound;
 }
 
 public Object valAt(Object key){
@@ -158,12 +171,14 @@ public IPersistentMap assocEx(Object key, Object val) throws Exception{
 }
 
 public IPersistentMap without(Object key){
-	INode newroot = root.without(Util.hash(key), key);
+	if(key == null)
+		return hasNull ? new PersistentHashMap(meta(), count - 1, root, false, null) : this;
+	if(root == null)
+		return this;
+	INode newroot = root.without(0, Util.hash(key), key);
 	if(newroot == root)
 		return this;
-	if(newroot == null)
-		return EMPTY.withMeta(meta());
-	return new PersistentHashMap(meta(), count - 1, newroot);
+	return new PersistentHashMap(meta(), count - 1, newroot, hasNull, nullValue); 
 }
 
 public Iterator iterator(){
@@ -175,7 +190,8 @@ public int count(){
 }
 
 public ISeq seq(){
-	return root.nodeSeq();
+	ISeq s = root != null ? root.nodeSeq() : null; 
+	return hasNull ? new Cons(new MapEntry(null, nullValue), s) : s;
 }
 
 public IPersistentCollection empty(){
@@ -188,7 +204,7 @@ static int mask(int hash, int shift){
 }
 
 public PersistentHashMap withMeta(IPersistentMap meta){
-	return new PersistentHashMap(meta, count, root);
+	return new PersistentHashMap(meta, count, root, hasNull, nullValue);
 }
 
 public TransientHashMap asTransient() {
@@ -199,46 +215,72 @@ static final class TransientHashMap extends ATransientMap {
 	AtomicReference<Thread> edit;
 	INode root;
 	int count;
+	boolean hasNull;
+	Object nullValue;
+	
 	
 	TransientHashMap(PersistentHashMap m) {
-		this(new AtomicReference<Thread>(Thread.currentThread()), m.root, m.count);
+		this(new AtomicReference<Thread>(Thread.currentThread()), m.root, m.count, m.hasNull, m.nullValue);
 	}
 	
-	TransientHashMap(AtomicReference<Thread> edit, INode root, int count) {
+	TransientHashMap(AtomicReference<Thread> edit, INode root, int count, boolean hasNull, Object nullValue) {
 		this.edit = edit;
 		this.root = root; 
 		this.count = count; 
+		this.hasNull = hasNull;
+		this.nullValue = nullValue;
 	}
 
 	ITransientMap doAssoc(Object key, Object val) {
+		if (key == null) {
+			if (this.nullValue != val)
+				this.nullValue = val;
+			if (!hasNull) {
+				this.count++;
+				this.hasNull = true;
+			}
+			return this;
+		}
 		Box addedLeaf = new Box(null);
-		this.root = root.assoc(edit, 0, Util.hash(key), key, val, addedLeaf);
-		if (addedLeaf.val != null) this.count++;
+		INode n = (root == null ? BitmapIndexedNode.EMPTY : root)
+			.assoc(edit, 0, Util.hash(key), key, val, addedLeaf);
+		if (n != this.root)
+			this.root = n; 
+		if(addedLeaf.val != null) this.count++;
 		return this;
 	}
 
 	ITransientMap doWithout(Object key) {
+		if (key == null) {
+			if (!hasNull) return this;
+			hasNull = false;
+			nullValue = null;
+			this.count--;
+			return this;
+		}
+		if (root == null) return this;
 		Box removedLeaf = new Box(null);
-		INode newroot = root.without(edit, Util.hash(key), key, removedLeaf);
-		this.root = newroot == null ? EMPTY.root : newroot;
-		if (removedLeaf.val != null) this.count--;
+		INode n = root.without(edit, 0, Util.hash(key), key, removedLeaf);
+		if (n != root)
+			this.root = n;
+		if(removedLeaf.val != null) this.count--;
 		return this;
 	}
 
 	IPersistentMap doPersistent() {
 		edit.set(null);
-		return new PersistentHashMap(count, root);
-	}
-
-	private IMapEntry entryAt(Object key){
-		return root.find(Util.hash(key), key);
+		return new PersistentHashMap(count, root, hasNull, nullValue);
 	}
 
 	Object doValAt(Object key, Object notFound) {
-		IMapEntry e = entryAt(key);
-		if(e != null)
-			return e.val();
-		return notFound;
+		if (key == null)
+			if (hasNull)
+				return nullValue;
+			else
+				return notFound;
+		if (root == null)
+			return null;
+		return root.find(0, Util.hash(key), key, notFound);
 	}
 
 	int doCount() {
@@ -255,537 +297,422 @@ static final class TransientHashMap extends ATransientMap {
 	}
 }
 
-/*
-final static int[] pathmasks = new int[32];
-static{
-	pathmasks[0] = 0;
-	for(int i=1;i<32;i++)
-		pathmasks[i] = 0x80000000 >> (i - 1);
-}
-//final static int pathmask(int hash, int shift){
-//	//return hash & (0x80000000 >> (shift - 1));
-//	return hash & pathmasks[shift];
-//	}
-
-static boolean diffPath(int shift, int hash1, int hash2){
-	return shift > 0 && ((hash1^hash2) & pathmasks[shift]) != 0;
-	//return shift > 0 && pathmask(hash1^hash2,shift) != 0;
-}
-*/
 static interface INode{
 	INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf);
 
-	INode without(int hash, Object key);
+	INode without(int shift, int hash, Object key);
 
-	LeafNode find(int hash, Object key);
+	IMapEntry find(int shift, int hash, Object key);
 
-	ISeq nodeSeq();
+	Object find(int shift, int hash, Object key, Object notFound);
 
-	int getHash();
+	ISeq nodeSeq();
 
 	INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf);
 
-	INode without(AtomicReference<Thread> edit, int hash, Object key, Box removedLeaf);
+	INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf);
 }
 
-/*
-static interface ILeaf extends INode{
-	int getHash();
-}
-*/
+final static class ArrayNode implements INode{
+	int count;
+	final INode[] array;
+	final AtomicReference<Thread> edit;
 
-final static class EmptyNode implements INode{
+	ArrayNode(AtomicReference<Thread> edit, int count, INode[] array){
+		this.array = array;
+		this.edit = edit;
+		this.count = count;
+	}
 
 	public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){
-		INode ret = new LeafNode(null, hash, key, val);
-		addedLeaf.val = ret;
-		return ret;
+		int idx = mask(hash, shift);
+		INode node = array[idx];
+		if(node == null)
+			return new ArrayNode(null, count + 1, cloneAndSet(array, idx, BitmapIndexedNode.EMPTY.assoc(shift + 5, hash, key, val, addedLeaf)));			
+		INode n = node.assoc(shift + 5, hash, key, val, addedLeaf);
+		if(n == node)
+			return this;
+		return new ArrayNode(null, count, cloneAndSet(array, idx, n));
 	}
 
-	public INode without(int hash, Object key){
-		return this;
+	public INode without(int shift, int hash, Object key){
+		int idx = mask(hash, shift);
+		INode node = array[idx];
+		if(node == null)
+			return this;
+		INode n = node.without(shift + 5, hash, key);
+		if(n == node)
+			return this;
+		if (n == null) {
+			if (count <= 8) // shrink
+				return pack(null, idx);
+			return new ArrayNode(null, count - 1, cloneAndSet(array, idx, n));
+		} else 
+			return new ArrayNode(null, count, cloneAndSet(array, idx, n));
 	}
 
-	public LeafNode find(int hash, Object key){
-		return null;
+	public IMapEntry find(int shift, int hash, Object key){
+		int idx = mask(hash, shift);
+		INode node = array[idx];
+		if(node == null)
+			return null;
+		return node.find(shift + 5, hash, key); 
 	}
 
+	public Object find(int shift, int hash, Object key, Object notFound){
+		int idx = mask(hash, shift);
+		INode node = array[idx];
+		if(node == null)
+			return notFound;
+		return node.find(shift + 5, hash, key, notFound); 
+	}
+	
 	public ISeq nodeSeq(){
-		return null;
+		return Seq.create(array);
 	}
 
-	public int getHash(){
-		return 0;
+	private ArrayNode ensureEditable(AtomicReference<Thread> edit){
+		if(this.edit == edit)
+			return this;
+		return new ArrayNode(edit, count, this.array.clone());
 	}
 	
-	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
-		return assoc(shift, hash, key, val, addedLeaf);
-	}	
-
-	public INode without(AtomicReference<Thread> edit, int hash, Object key, Box removedLeaf){
-		return this;
+	private ArrayNode editAndSet(AtomicReference<Thread> edit, int i, INode n){
+		ArrayNode editable = ensureEditable(edit);
+		editable.array[i] = n;
+		return editable;
 	}
-}
 
-final static class FullNode implements INode{
-	final INode[] nodes;
-	final int shift;
-	final int _hash;
-	final AtomicReference<Thread> edit;
 
-	static int bitpos(int hash, int shift){
-		return 1 << mask(hash, shift);
-	}
-
-	FullNode(AtomicReference<Thread> edit, INode[] nodes, int shift){
-		this.nodes = nodes;
-		this.shift = shift;
-		this._hash = nodes[0].getHash();
-		this.edit = edit;
+	private INode pack(AtomicReference<Thread> edit, int idx) {
+		Object[] newArray = new Object[2*(count - 1)];
+		int j = 1;
+		int bitmap = 0;
+		for(int i = 0; i < idx; i++)
+			if (array[i] != null) {
+				newArray[j] = array[i];
+				bitmap |= 1 << i;
+				j += 2;
+			}
+		for(int i = idx + 1; i < array.length; i++)
+			if (array[i] != null) {
+				newArray[j] = array[i];
+				bitmap |= 1 << i;
+				j += 2;
+			}
+		return new BitmapIndexedNode(edit, bitmap, newArray);
 	}
 
-	public INode assoc(int levelShift, int hash, Object key, Object val, Box addedLeaf){
-//		if(levelShift < shift && diffPath(shift,hash,_hash))
-//			return BitmapIndexedNode.create(levelShift, this, hash, key, val, addedLeaf);
+	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
 		int idx = mask(hash, shift);
-
-		INode n = nodes[idx].assoc(shift + 5, hash, key, val, addedLeaf);
-		if(n == nodes[idx])
+		INode node = array[idx];
+		if(node == null) {
+			ArrayNode editable = editAndSet(edit, idx, BitmapIndexedNode.EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf));
+			editable.count++;
+			return editable;			
+		}
+		INode n = node.assoc(edit, shift + 5, hash, key, val, addedLeaf);
+		if(n == node)
 			return this;
-		else
-			{
-			INode[] newnodes = nodes.clone();
-			newnodes[idx] = n;
-			return new FullNode(null, newnodes, shift);
-			}
-	}
+		return editAndSet(edit, idx, n);
+	}	
 
-	public INode without(int hash, Object key){
-//		if(diffPath(shift,hash,_hash))
-//			return this;
+	public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){
 		int idx = mask(hash, shift);
-		INode n = nodes[idx].without(hash, key);
-		if(n != nodes[idx])
-			{
-			if(n == null)
-				{
-				INode[] newnodes = new INode[nodes.length - 1];
-				System.arraycopy(nodes, 0, newnodes, 0, idx);
-				System.arraycopy(nodes, idx + 1, newnodes, idx, nodes.length - (idx + 1));
-				return new BitmapIndexedNode(null, ~bitpos(hash, shift), newnodes, shift);
-				}
-			INode[] newnodes = nodes.clone();
-			newnodes[idx] = n;
-			return new FullNode(null, newnodes, shift);
-			}
-		return this;
-	}
-
-	public LeafNode find(int hash, Object key){
-//		if(diffPath(shift,hash,_hash))
-//			return null;
-		return nodes[mask(hash, shift)].find(hash, key);
-	}
-
-	public ISeq nodeSeq(){
-		return Seq.create(this, 0);
-	}
-
-	public int getHash(){
-		return _hash;
+		INode node = array[idx];
+		if(node == null)
+			return this;
+		INode n = node.without(edit, shift + 5, hash, key, removedLeaf);
+		if(n == node)
+			return this;
+		if(n == null) {
+			if (count <= 8) // shrink
+				return pack(edit, idx);
+			ArrayNode editable = editAndSet(edit, idx, n);
+			editable.count--;
+			return editable;
+		}
+		return editAndSet(edit, idx, n);
 	}
-
-	static class Seq extends ASeq{
-		final ISeq s;
+	
+	static class Seq extends ASeq {
+		final INode[] nodes;
 		final int i;
-		final FullNode node;
-
-		Seq(ISeq s, int i, FullNode node){
-			this.s = s;
-			this.i = i;
-			this.node = node;
+		final ISeq s; 
+		
+		static ISeq create(INode[] nodes) {
+			return create(null, nodes, 0, null);
 		}
-
-		Seq(IPersistentMap meta, ISeq s, int i, FullNode node){
+		
+		private static ISeq create(IPersistentMap meta, INode[] nodes, int i, ISeq s) {
+			if (s != null)
+				return new Seq(meta, nodes, i, s);
+			for(int j = i; j < nodes.length; j++)
+				if (nodes[j] != null) {
+					ISeq ns = nodes[j].nodeSeq();
+					if (ns != null)
+						return new Seq(meta, nodes, j + 1, ns);
+				}
+			return null;
+		}
+		
+		private Seq(IPersistentMap meta, INode[] nodes, int i, ISeq s) {
 			super(meta);
-			this.s = s;
+			this.nodes = nodes;
 			this.i = i;
-			this.node = node;
+			this.s = s;
 		}
 
-		static ISeq create(FullNode node, int i){
-			if(i >= node.nodes.length)
-				return null;
-			return new Seq(node.nodes[i].nodeSeq(), i, node);
+		public Obj withMeta(IPersistentMap meta) {
+			return new Seq(meta, nodes, i, s);
 		}
 
-		public Object first(){
+		public Object first() {
 			return s.first();
 		}
 
-		public ISeq next(){
-			ISeq nexts = s.next();
-			if(nexts != null)
-				return new Seq(nexts, i, node);
-			return create(node, i + 1);
+		public ISeq next() {
+			return create(null, nodes, i, s.next());
 		}
-
-		public Seq withMeta(IPersistentMap meta){
-			return new Seq(meta, s, i, node);
-		}
-    }
-
-	FullNode ensureEditable(AtomicReference<Thread> edit){
-		if(this.edit == edit)
-			return this;
-		return new FullNode(edit, this.nodes.clone(), shift);
-	}
-
-	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
-		int idx = mask(hash, shift);
-
-		INode n = nodes[idx].assoc(edit, shift + 5, hash, key, val, addedLeaf);
-		if(n == nodes[idx])
-			return this;
-		else
-			{
-			FullNode node = this.ensureEditable(edit);
-			node.nodes[idx] = n;
-			return node;
-			}
-	}	
-
-	public INode without(AtomicReference<Thread> edit, int hash, Object key, Box removedLeaf){
-		int idx = mask(hash, shift);
-		INode n = nodes[idx].without(edit, hash, key, removedLeaf);
-		if(n != nodes[idx])
-			{
-			if(n == null)
-				{
-				INode[] newnodes = new INode[nodes.length - 1];
-				System.arraycopy(nodes, 0, newnodes, 0, idx);
-				System.arraycopy(nodes, idx + 1, newnodes, idx, nodes.length - (idx + 1));
-				return new BitmapIndexedNode(edit, ~bitpos(hash, shift), newnodes, shift);
-				}
-			FullNode node = ensureEditable(edit);
-			node.nodes[idx] = n;
-			return node;
-			}
-		return this;
+		
 	}
 }
 
 final static class BitmapIndexedNode implements INode{
-	final int bitmap;
-	final INode[] nodes;
-	final int shift;
-	final int _hash;
+	static final BitmapIndexedNode EMPTY = new BitmapIndexedNode(null, 0, new Object[0]);
+	
+	int bitmap;
+	Object[] array;
 	final AtomicReference<Thread> edit;
 
-	static int bitpos(int hash, int shift){
-		return 1 << mask(hash, shift);
-	}
-
 	final int index(int bit){
 		return Integer.bitCount(bitmap & (bit - 1));
 	}
 
-	BitmapIndexedNode(AtomicReference<Thread> edit, int bitmap, INode[] nodes, int shift){
+	BitmapIndexedNode(AtomicReference<Thread> edit, int bitmap, Object[] array){
 		this.bitmap = bitmap;
-		this.nodes = nodes;
-		this.shift = shift;
-		this._hash = nodes[0].getHash();
+		this.array = array;
 		this.edit = edit;
 	}
 
-	static INode create(AtomicReference<Thread> edit, int bitmap, INode[] nodes, int shift){
-		if(bitmap == -1)
-			return new FullNode(edit, nodes, shift);
-		return new BitmapIndexedNode(edit, bitmap, nodes, shift);
-	}
-
-	static INode create(AtomicReference<Thread> edit, int shift, INode branch, int hash, Object key, Object val, Box addedLeaf){
-//		int hx = branch.getHash()^hash;
-//		while(mask(hx,shift) == 0)
-//			shift += 5;
-//		if(mask(branch.getHash(),shift) == mask(hash,shift))
-//			return create(shift+5,branch,hash,key,val,addedLeaf);
-		BitmapIndexedNode node = new BitmapIndexedNode(edit, bitpos(branch.getHash(), shift), new INode[]{branch}, shift); 
-		return edit == null ? node.assoc(shift, hash, key, val, addedLeaf) : node.assoc(edit, shift, hash, key, val, addedLeaf);
-	}
-
-	public INode assoc(int levelShift, int hash, Object key, Object val, Box addedLeaf){
-//		if(levelShift < shift && diffPath(shift,hash,_hash))
-//			return create(levelShift, this, hash, key, val, addedLeaf);
+	public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){
 		int bit = bitpos(hash, shift);
 		int idx = index(bit);
-		if((bitmap & bit) != 0)
-			{
-			INode n = nodes[idx].assoc(shift + 5, hash, key, val, addedLeaf);
-			if(n == nodes[idx])
-				return this;
-			else
-				{
-				INode[] newnodes = nodes.clone();
-				newnodes[idx] = n;
-				return new BitmapIndexedNode(null, bitmap, newnodes, shift);
-				}
-			}
-		else
-			{
-			INode[] newnodes = new INode[nodes.length + 1];
-			System.arraycopy(nodes, 0, newnodes, 0, idx);
-			addedLeaf.val = newnodes[idx] = new LeafNode(null, hash, key, val);
-			System.arraycopy(nodes, idx, newnodes, idx + 1, nodes.length - idx);
-			return create(null, bitmap | bit, newnodes, shift);
-			}
-	}
-
-	public INode without(int hash, Object key){
-//		if(diffPath(shift,hash,_hash))
-//			return this;
-		int bit = bitpos(hash, shift);
-		if((bitmap & bit) != 0)
-			{
-			int idx = index(bit);
-			INode n = nodes[idx].without(hash, key);
-			if(n != nodes[idx])
-				{
-				if(n == null)
-					{
-					if(bitmap == bit)
-						return null;
-//					if(nodes.length == 2)
-//						return nodes[idx == 0?1:0];
-					INode[] newnodes = new INode[nodes.length - 1];
-					System.arraycopy(nodes, 0, newnodes, 0, idx);
-					System.arraycopy(nodes, idx + 1, newnodes, idx, nodes.length - (idx + 1));
-					return new BitmapIndexedNode(null, bitmap & ~bit, newnodes, shift);
+		if((bitmap & bit) != 0) {
+			Object keyOrNull = array[2*idx];
+			Object valOrNode = array[2*idx+1];
+			if(keyOrNull == null) {
+				INode n = ((INode) valOrNode).assoc(shift + 5, hash, key, val, addedLeaf);
+				if(n == valOrNode)
+					return this;
+				return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n));
+			} 
+			if(Util.equals(key, keyOrNull)) {
+				if(val == valOrNode)
+					return this;
+				return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, val));
+			} 
+			addedLeaf.val = val;
+			return new BitmapIndexedNode(null, bitmap, 
+					cloneAndSet(array, 
+							2*idx, null, 
+							2*idx+1, createNode(shift + 5, keyOrNull, valOrNode, hash, key, val)));
+		} else {
+			int n = Integer.bitCount(bitmap);
+			if(n >= 16) {
+				INode[] nodes = new INode[32];
+				int jdx = mask(hash, shift);
+				nodes[jdx] = EMPTY.assoc(shift + 5, hash, key, val, addedLeaf);  
+				int j = 0;
+				for(int i = 0; i < 32; i++)
+					if(((bitmap >>> i) & 1) != 0) {
+						if (array[j] == null)
+							nodes[i] = (INode) array[j+1];
+						else
+							nodes[i] = EMPTY.assoc(shift + 5, Util.hash(array[j]), array[j], array[j+1], addedLeaf);
+						j += 2;
 					}
-				INode[] newnodes = nodes.clone();
-				newnodes[idx] = n;
-				return new BitmapIndexedNode(null, bitmap, newnodes, shift);
-				}
+				return new ArrayNode(null, n + 1, nodes);
+			} else {
+				Object[] newArray = new Object[2*(n+1)];
+				System.arraycopy(array, 0, newArray, 0, 2*idx);
+				newArray[2*idx] = key;
+				addedLeaf.val = newArray[2*idx+1] = val;
+				System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx));
+				return new BitmapIndexedNode(null, bitmap | bit, newArray);
 			}
-		return this;
-	}
-
-	public LeafNode find(int hash, Object key){
-//		if(diffPath(shift,hash,_hash))
-//			return null;
-		int bit = bitpos(hash, shift);
-		if((bitmap & bit) != 0)
-			{
-			return nodes[index(bit)].find(hash, key);
-			}
-		else
-			return null;
-	}
-
-	public int getHash(){
-		return _hash;
-	}
-
-	public ISeq nodeSeq(){
-		return Seq.create(this, 0);
-	}
-
-	static class Seq extends ASeq{
-		final ISeq s;
-		final int i;
-		final BitmapIndexedNode node;
-
-
-		Seq(ISeq s, int i, BitmapIndexedNode node){
-			this.s = s;
-			this.i = i;
-			this.node = node;
-		}
-
-		Seq(IPersistentMap meta, ISeq s, int i, BitmapIndexedNode node){
-			super(meta);
-			this.s = s;
-			this.i = i;
-			this.node = node;
-		}
-
-		static ISeq create(BitmapIndexedNode node, int i){
-			if(i >= node.nodes.length)
-				return null;
-			return new Seq(node.nodes[i].nodeSeq(), i, node);
 		}
-
-		public Object first(){
-			return s.first();
-		}
-
-		public ISeq next(){
-			ISeq nexts = s.next();
-			if(nexts != null)
-				return new Seq(nexts, i, node);
-			return create(node, i + 1);
-		}
-
-		public Seq withMeta(IPersistentMap meta){
-			return new Seq(meta, s, i, node);
-		}
-    }
-	
-	BitmapIndexedNode ensureEditable(AtomicReference<Thread> edit){
-		if(this.edit == edit)
-			return this;
-		return new BitmapIndexedNode(edit, bitmap, nodes.clone(), shift);
 	}
 
-	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
+	public INode without(int shift, int hash, Object key){
 		int bit = bitpos(hash, shift);
+		if((bitmap & bit) == 0)
+			return this;
 		int idx = index(bit);
-		if((bitmap & bit) != 0)
-			{
-			INode n = nodes[idx].assoc(shift + 5, hash, key, val, addedLeaf);
-			if(n == nodes[idx])
+		Object keyOrNull = array[2*idx];
+		Object valOrNode = array[2*idx+1];
+		if(keyOrNull == null) {
+			INode n = ((INode) valOrNode).without(shift + 5, hash, key);
+			if (n == valOrNode)
 				return this;
-			else
-				{
-				BitmapIndexedNode node = ensureEditable(edit);
-				node.nodes[idx] = n;
-				return node;
-				}
-			}
-		else
-			{
-			// TODO can do better
-			INode[] newnodes = new INode[nodes.length + 1];
-			System.arraycopy(nodes, 0, newnodes, 0, idx);
-			addedLeaf.val = newnodes[idx] = new LeafNode(null, hash, key, val);
-			System.arraycopy(nodes, idx, newnodes, idx + 1, nodes.length - idx);
-			return create(edit, bitmap | bit, newnodes, shift);
-			}
-	}
-
-	public INode without(AtomicReference<Thread> edit, int hash, Object key, Box removedLeaf){
-		int bit = bitpos(hash, shift);
-		if((bitmap & bit) != 0)
-			{
-			int idx = index(bit);
-			INode n = nodes[idx].without(edit, hash, key, removedLeaf);
-			if(n != nodes[idx])
-				{
-				if(n == null)
-					{
-					if(bitmap == bit)
-						return null;
-					INode[] newnodes = new INode[nodes.length - 1];
-					System.arraycopy(nodes, 0, newnodes, 0, idx);
-					System.arraycopy(nodes, idx + 1, newnodes, idx, nodes.length - (idx + 1));
-					return new BitmapIndexedNode(edit, bitmap & ~bit, newnodes, shift);
-					}
-				BitmapIndexedNode node = ensureEditable(edit);
-				node.nodes[idx] = n;
-				return node;
-				}
-			}
+			if (n != null)
+				return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n));
+			if (bitmap == bit) 
+				return null;
+			return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx));
+		}
+		if(Util.equals(key, keyOrNull))
+			// TODO: collapse
+			return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx));
 		return this;
 	}
-}
-
-final static class LeafNode extends AMapEntry implements INode{
-	final int hash;
-	final Object key;
-	Object val;
-	final AtomicReference<Thread> edit; 
-
-	public LeafNode(AtomicReference<Thread> edit, int hash, Object key, Object val){
-		this.edit = edit;
-		this.hash = hash;
-		this.key = key;
-		this.val = val;
-	}
-
-	public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){
-		if(hash == this.hash)
-			{
-			if(Util.equals(key, this.key))
-				{
-				if(val == this.val)
-					return this;
-				//note  - do not set addedLeaf, since we are replacing
-				return new LeafNode(null, hash, key, val);
-				}
-			//hash collision - same hash, different keys
-			LeafNode newLeaf = new LeafNode(null, hash, key, val);
-			addedLeaf.val = newLeaf;
-			return new HashCollisionNode(null, hash, this, newLeaf);
-			}
-		return BitmapIndexedNode.create(null, shift, this, hash, key, val, addedLeaf);
-	}
-
-	public INode without(int hash, Object key){
-		if(hash == this.hash && Util.equals(key, this.key))
+	
+	public IMapEntry find(int shift, int hash, Object key){
+		int bit = bitpos(hash, shift);
+		if((bitmap & bit) == 0)
 			return null;
-		return this;
-	}
-
-	public LeafNode find(int hash, Object key){
-		if(hash == this.hash && Util.equals(key, this.key))
-			return this;
+		int idx = index(bit);
+		Object keyOrNull = array[2*idx];
+		Object valOrNode = array[2*idx+1];
+		if(keyOrNull == null)
+			return ((INode) valOrNode).find(shift + 5, hash, key);
+		if(Util.equals(key, keyOrNull))
+			return new MapEntry(keyOrNull, valOrNode);
 		return null;
 	}
 
-	public ISeq nodeSeq(){
-		return RT.cons(this, null);
+	public Object find(int shift, int hash, Object key, Object notFound){
+		int bit = bitpos(hash, shift);
+		if((bitmap & bit) == 0)
+			return notFound;
+		int idx = index(bit);
+		Object keyOrNull = array[2*idx];
+		Object valOrNode = array[2*idx+1];
+		if(keyOrNull == null)
+			return ((INode) valOrNode).find(shift + 5, hash, key, notFound);
+		if(Util.equals(key, keyOrNull))
+			return valOrNode;
+		return notFound;
 	}
 
-	public int getHash(){
-		return hash;
+	public ISeq nodeSeq(){
+		return NodeSeq.create(array);
 	}
 
-	public Object key(){
-		return this.key;
+	private BitmapIndexedNode ensureEditable(AtomicReference<Thread> edit){
+		if(this.edit == edit)
+			return this;
+		int n = Integer.bitCount(bitmap);
+		Object[] newArray = new Object[n >= 0 ? 2*(n+1) : 4]; // make room for next assoc
+		System.arraycopy(array, 0, newArray, 0, 2*n);
+		return new BitmapIndexedNode(edit, bitmap, newArray);
 	}
-
-	public Object val(){
-		return this.val;
+	
+	private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a) {
+		BitmapIndexedNode editable = ensureEditable(edit);
+		editable.array[i] = a;
+		return editable;
 	}
 
-	public Object getKey(){
-		return this.key;
+	private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) {
+		BitmapIndexedNode editable = ensureEditable(edit);
+		editable.array[i] = a;
+		editable.array[j] = b;
+		return editable;
 	}
 
-	public Object getValue(){
-		return this.val;
-	}
-	
-	LeafNode ensureEditable(AtomicReference<Thread> edit){
-		if(this.edit == edit)
-			return this;
-		return new LeafNode(edit, this.hash, this.key, this.val);
+	private BitmapIndexedNode editAndRemovePair(AtomicReference<Thread> edit, int bit, int i) {
+		if (bitmap == bit) 
+			return null;
+		BitmapIndexedNode editable = ensureEditable(edit);
+		editable.bitmap ^= bit;
+		System.arraycopy(editable.array, 2*(i+1), editable.array, 2*i, editable.array.length - 2*(i+1));
+		editable.array[editable.array.length - 2] = null;
+		editable.array[editable.array.length - 1] = null;
+		return editable;
 	}
 
 	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
-		if(hash == this.hash)
-			{
-			if(Util.equals(key, this.key))
-				{
-				if(val == this.val)
+		int bit = bitpos(hash, shift);
+		int idx = index(bit);
+		if((bitmap & bit) != 0) {
+			Object keyOrNull = array[2*idx];
+			Object valOrNode = array[2*idx+1];
+			if(keyOrNull == null) {
+				INode n = ((INode) valOrNode).assoc(edit, shift + 5, hash, key, val, addedLeaf);
+				if(n == valOrNode)
 					return this;
-				LeafNode node = ensureEditable(edit);
-				node.val = val;
-				//note  - do not set addedLeaf, since we are replacing
-				return node;
-				}
-			//hash collision - same hash, different keys
-			LeafNode newLeaf = new LeafNode(edit, hash, key, val);
-			addedLeaf.val = newLeaf;
-			return new HashCollisionNode(edit, hash, this, newLeaf);
+				return editAndSet(edit, 2*idx+1, n);
+			} 
+			if(Util.equals(key, keyOrNull)) {
+				if(val == valOrNode)
+					return this;
+				return editAndSet(edit, 2*idx+1, val);
+			} 
+			addedLeaf.val = val;
+			return editAndSet(edit, 2*idx, null, 2*idx+1, 
+					createNode(edit, shift + 5, keyOrNull, valOrNode, hash, key, val)); 
+		} else {
+			int n = Integer.bitCount(bitmap);
+			if(n*2 < array.length) {
+				addedLeaf.val = val;
+				BitmapIndexedNode editable = ensureEditable(edit);
+				System.arraycopy(editable.array, 2*idx, editable.array, 2*(idx+1), 2*(n-idx));
+				editable.array[2*idx] = key;
+				editable.array[2*idx+1] = val;
+				editable.bitmap |= bit;
+				return editable;
 			}
-		return BitmapIndexedNode.create(edit, shift, this, hash, key, val, addedLeaf);
-	}	
+			if(n >= 16) {
+				INode[] nodes = new INode[32];
+				int jdx = mask(hash, shift);
+				nodes[jdx] = EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf);  
+				int j = 0;
+				for(int i = 0; i < 32; i++)
+					if(((bitmap >>> i) & 1) != 0) {
+						if (array[j] == null)
+							nodes[i] = (INode) array[j+1];
+						else
+							nodes[i] = EMPTY.assoc(edit, shift + 5, Util.hash(array[j]), array[j], array[j+1], addedLeaf);
+						j += 2;
+					}
+				return new ArrayNode(edit, n + 1, nodes);
+			} else {
+				Object[] newArray = new Object[2*(n+2)];
+				System.arraycopy(array, 0, newArray, 0, 2*idx);
+				newArray[2*idx] = key;
+				addedLeaf.val = newArray[2*idx+1] = val;
+				System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx));
+				BitmapIndexedNode editable = ensureEditable(edit);
+				editable.array = newArray;
+				editable.bitmap |= bit;
+				return editable;
+			}
+		}
+	}
 
-	public INode without(AtomicReference<Thread> edit, int hash, Object key, Box removedLeaf){
-		if(hash == this.hash && Util.equals(key, this.key)) {
-			removedLeaf.val = this;
-			return null;
+	public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){
+		int bit = bitpos(hash, shift);
+		if((bitmap & bit) == 0)
+			return this;
+		int idx = index(bit);
+		Object keyOrNull = array[2*idx];
+		Object valOrNode = array[2*idx+1];
+		if(keyOrNull == null) {
+			INode n = ((INode) valOrNode).without(edit, shift + 5, hash, key, removedLeaf);
+			if (n == valOrNode)
+				return this;
+			if (n != null)
+				return editAndSet(edit, 2*idx+1, n); 
+			if (bitmap == bit) 
+				return null;
+			removedLeaf.val = valOrNode;
+			return editAndRemovePair(edit, bit, idx); 
+		}
+		if(Util.equals(key, keyOrNull)) {
+			removedLeaf.val = key; // key can't be null
+			// TODO: collapse
+			return editAndRemovePair(edit, bit, idx); 			
 		}
 		return this;
 	}
@@ -794,113 +721,140 @@ final static class LeafNode extends AMapEntry implements INode{
 final static class HashCollisionNode implements INode{
 
 	final int hash;
-	final LeafNode[] leaves;
+	int count;
+	Object[] array;
 	final AtomicReference<Thread> edit;
 
-	public HashCollisionNode(AtomicReference<Thread> edit, int hash, LeafNode... leaves){
+	HashCollisionNode(AtomicReference<Thread> edit, int hash, int count, Object... array){
 		this.edit = edit;
 		this.hash = hash;
-		this.leaves = leaves;
+		this.count = count;
+		this.array = array;
 	}
 
 	public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){
-		if(hash == this.hash)
-			{
-			int idx = findIndex(hash, key);
-			if(idx != -1)
-				{