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)
-				{
-				if(leaves[idx].val == val)
+		if(hash == this.hash) {
+			int idx = findIndex(key);
+			if(idx != -1) {
+				if(array[idx + 1] == val)
 					return this;
-				LeafNode[] newLeaves = leaves.clone();
-				//note  - do not set addedLeaf, since we are replacing
-				newLeaves[idx] = new LeafNode(null, hash, key, val);
-				return new HashCollisionNode(null, hash, newLeaves);
-				}
-			LeafNode[] newLeaves = new LeafNode[leaves.length + 1];
-			System.arraycopy(leaves, 0, newLeaves, 0, leaves.length);
-			addedLeaf.val = newLeaves[leaves.length] = new LeafNode(null, hash, key, val);
-			return new HashCollisionNode(null, hash, newLeaves);
+				return new HashCollisionNode(null, hash, count, cloneAndSet(array, idx + 1, val));
 			}
-		return BitmapIndexedNode.create(null, shift, this, hash, key, val, addedLeaf);
+			Object[] newArray = new Object[array.length + 2];
+			System.arraycopy(array, 0, newArray, 0, array.length);
+			newArray[array.length] = key;
+			newArray[array.length + 1] = val;
+			return new HashCollisionNode(edit, hash, count + 1, newArray);
+		}
+		// nest it in a bitmap node
+		return new BitmapIndexedNode(null, bitpos(this.hash, shift), new Object[] {this})
+			.assoc(shift, hash, key, val, addedLeaf);
 	}
 
-	public INode without(int hash, Object key){
-		int idx = findIndex(hash, key);
+	public INode without(int shift, int hash, Object key){
+		int idx = findIndex(key);
 		if(idx == -1)
 			return this;
-		if(leaves.length == 2)
-			return idx == 0 ? leaves[1] : leaves[0];
-		LeafNode[] newLeaves = new LeafNode[leaves.length - 1];
-		System.arraycopy(leaves, 0, newLeaves, 0, idx);
-		System.arraycopy(leaves, idx + 1, newLeaves, idx, leaves.length - (idx + 1));
-		return new HashCollisionNode(null, hash, newLeaves);
-	}
-
-	public LeafNode find(int hash, Object key){
-		int idx = findIndex(hash, key);
-		if(idx != -1)
-			return leaves[idx];
+		if(count == 1)
+			return null;
+		return new HashCollisionNode(null, hash, count - 1, removePair(array, idx/2));
+	}
+
+	public IMapEntry find(int shift, int hash, Object key){
+		int idx = findIndex(key);
+		if(idx < 0)
+			return null;
+		if(Util.equals(key, array[idx]))
+			return new MapEntry(array[idx], array[idx+1]);
 		return null;
 	}
 
+	public Object find(int shift, int hash, Object key, Object notFound){
+		int idx = findIndex(key);
+		if(idx < 0)
+			return notFound;
+		if(Util.equals(key, array[idx]))
+			return array[idx+1];
+		return notFound;
+	}
+
 	public ISeq nodeSeq(){
-		return ArraySeq.create((Object[]) leaves);
+		return NodeSeq.create(array);
 	}
 
-	int findIndex(int hash, Object key){
-		for(int i = 0; i < leaves.length; i++)
+	public int findIndex(Object key){
+		for(int i = 0; i < 2*count; i+=2)
 			{
-			if(leaves[i].find(hash, key) != null)
+			if(Util.equals(key, array[i]))
 				return i;
 			}
 		return -1;
 	}
 
-	public int getHash(){
-		return hash;
+	private HashCollisionNode ensureEditable(AtomicReference<Thread> edit){
+		if(this.edit == edit)
+			return this;
+		return new HashCollisionNode(edit, count, hash, array);
 	}
 
-	HashCollisionNode ensureEditable(AtomicReference<Thread> edit){
-		if(this.edit == edit)
+	private HashCollisionNode ensureEditable(AtomicReference<Thread> edit, int count, Object[] array){
+		if(this.edit == edit) {
+			this.array = array;
 			return this;
-		return new HashCollisionNode(edit, hash, leaves);
+		}
+		return new HashCollisionNode(edit, count, hash, array);
 	}
 
+	private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a) {
+		HashCollisionNode editable = ensureEditable(edit);
+		editable.array[i] = a;
+		return editable;
+	}
+
+	private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) {
+		HashCollisionNode editable = ensureEditable(edit);
+		editable.array[i] = a;
+		editable.array[j] = b;
+		return editable;
+	}
+
+
 	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
-		if(hash == this.hash)
-			{
-			int idx = findIndex(hash, key);
-			if(idx != -1)
-				{
-				if(leaves[idx].val == val)
-					return this;
-				LeafNode leaf = leaves[idx].ensureEditable(edit);
-				leaf.val = val;
-				if (leaves[idx] == leaf)
+		if(hash == this.hash) {
+			int idx = findIndex(key);
+			if(idx != -1) {
+				if(array[idx + 1] == val)
 					return this;
-				HashCollisionNode node = ensureEditable(edit);
-				node.leaves[idx] = leaf;
-				return node;
-				}
-			LeafNode[] newLeaves = new LeafNode[leaves.length + 1];
-			System.arraycopy(leaves, 0, newLeaves, 0, leaves.length);
-			addedLeaf.val = newLeaves[leaves.length] = new LeafNode(null, hash, key, val);
-			return new HashCollisionNode(edit, hash, newLeaves);
+				return editAndSet(edit, idx+1, val); 
+			}
+			if (array.length > 2*count) {
+				HashCollisionNode editable = editAndSet(edit, 2*count, key, 2*count+1, val);
+				editable.count++;
+				return editable;
 			}
-		return BitmapIndexedNode.create(edit, shift, this, hash, key, val, addedLeaf);
+			Object[] newArray = new Object[array.length + 2];
+			System.arraycopy(array, 0, newArray, 0, array.length);
+			newArray[array.length] = key;
+			newArray[array.length + 1] = val;
+			return ensureEditable(edit, count + 1, newArray);
+		}
+		// nest it in a bitmap node
+		return new BitmapIndexedNode(edit, bitpos(this.hash, shift), new Object[] {this})
+			.assoc(edit, shift, hash, key, val, addedLeaf);
 	}	
 
-	public INode without(AtomicReference<Thread> edit, int hash, Object key, Box removedLeaf){
-		int idx = findIndex(hash, key);
+	public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){
+		int idx = findIndex(key);
 		if(idx == -1)
 			return this;
-		removedLeaf.val = leaves[idx];
-		if(leaves.length == 2)
-			return idx == 0 ? leaves[1] : leaves[0];
-		LeafNode[] newLeaves = new LeafNode[leaves.length - 1];
-		System.arraycopy(leaves, 0, newLeaves, 0, idx);
-		System.arraycopy(leaves, idx + 1, newLeaves, idx, leaves.length - (idx + 1));
-		return new HashCollisionNode(edit, hash, newLeaves);
+		if(count == 1)
+			return null;
+		HashCollisionNode editable = ensureEditable(edit);
+		editable.array[idx] = editable.array[2*count-2];
+		editable.array[idx+1] = editable.array[2*count-1];
+		editable.array[2*count-2] = editable.array[2*count-1] = null;
+		editable.count--;
+		return editable;
 	}
 }
 
@@ -990,5 +944,109 @@ public static void main(String[] args){
 
 }
 */
+
+private static INode[] cloneAndSet(INode[] array, int i, INode a) {
+	INode[] clone = array.clone();
+	clone[i] = a;
+	return clone;
+}
+
+private static Object[] cloneAndSet(Object[] array, int i, Object a) {
+	Object[] clone = array.clone();
+	clone[i] = a;
+	return clone;
+}
+
+private static Object[] cloneAndSet(Object[] array, int i, Object a, int j, Object b) {
+	Object[] clone = array.clone();
+	clone[i] = a;
+	clone[j] = b;
+	return clone;
+}
+
+private static Object[] removePair(Object[] array, int i) {
+	Object[] newArray = new Object[array.length - 2];
+	System.arraycopy(array, 0, newArray, 0, 2*i);
+	System.arraycopy(array, 2*(i+1), newArray, 2*i, newArray.length - 2*i);
+	return newArray;
+}
+
+private static INode createNode(int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) {
+	int key1hash = Util.hash(key1);
+	if(key1hash == key2hash)
+		return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2});
+	Box _ = new Box(null);
+	AtomicReference<Thread> edit = new AtomicReference<Thread>();
+	return BitmapIndexedNode.EMPTY
+		.assoc(edit, shift, key1hash, key1, val1, _)
+		.assoc(edit, shift, key2hash, key2, val2, _);
+}
+
+private static INode createNode(AtomicReference<Thread> edit, int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) {
+	int key1hash = Util.hash(key1);
+	if(key1hash == key2hash)
+		return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2});
+	Box _ = new Box(null);
+	return BitmapIndexedNode.EMPTY
+		.assoc(edit, shift, key1hash, key1, val1, _)
+		.assoc(edit, shift, key2hash, key2, val2, _);
+}
+
+private static int bitpos(int hash, int shift){
+	return 1 << mask(hash, shift);
+}
+
+static final class NodeSeq extends ASeq {
+	final Object[] array;
+	final int i;
+	final ISeq s;
+	
+	NodeSeq(Object[] array, int i) {
+		this(null, array, i, null);
+	}
+
+	static ISeq create(Object[] array) {
+		return create(array, 0, null);
+	}
+
+	private static ISeq create(Object[] array, int i, ISeq s) {
+		if(s != null)
+			return new NodeSeq(null, array, i, s);
+		for(int j = i; j < array.length; j+=2) {
+			if(array[j] != null)
+				return new NodeSeq(null, array, j, null);
+			INode node = (INode) array[j+1];
+			if (node != null) {
+				ISeq nodeSeq = node.nodeSeq();
+				if(nodeSeq != null)
+					return new NodeSeq(null, array, j + 2, nodeSeq);
+			}
+		}
+		return null;
+	}
+	
+	NodeSeq(IPersistentMap meta, Object[] array, int i, ISeq s) {
+		super(meta);
+		this.array = array;
+		this.i = i;
+		this.s = s;
+	}
+
+	public Obj withMeta(IPersistentMap meta) {
+		return new NodeSeq(meta, array, i, s);
+	}
+
+	public Object first() {
+		if(s != null)
+			return s.first();
+		return new MapEntry(array[i], array[i+1]);
+	}
+
+	public ISeq next() {
+		if(s != null)
+			return create(array, i, s.next());
+		return create(array, i + 2, null);
+	}
 }
 
+}
\ No newline at end of file
diff --git a/src/jvm/clojure/lang/PersistentHashMap2.java b/src/jvm/clojure/lang/PersistentHashMap2.java
deleted file mode 100644
index 507a5add..00000000
--- a/src/jvm/clojure/lang/PersistentHashMap2.java
+++ /dev/null
@@ -1,1052 +0,0 @@
-/**
- Copyright (c) 2007-2008, Rich Hickey
- All rights reserved.
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
-
- * Redistributions of source code must retain the above copyright
-   notice, this list of conditions and the following disclaimer.
-
- * Redistributions in binary form must reproduce the above
-   copyright notice, this list of conditions and the following
-   disclaimer in the documentation and/or other materials provided
-   with the distribution.
-
- * Neither the name of Clojure nor the names of its contributors
-   may be used to endorse or promote products derived from this
-   software without specific prior written permission.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
- COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
- **/
-
-package clojure.lang;
-
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Map.Entry;
-import java.util.concurrent.atomic.AtomicReference;
-
-/*
- A persistent rendition of Phil Bagwell's Hash Array Mapped Trie
-
- Uses path copying for persistence
- HashCollision leaves vs. extended hashing
- Node polymorphism vs. conditionals
- No sub-tree pools or root-resizing
- Any errors are my own
- */
-
-public class PersistentHashMap2 extends APersistentMap implements IEditableCollection {
-
-final int count;
-final INode root;
-final boolean hasNull;
-final Object nullValue;
-
-final public static PersistentHashMap2 EMPTY = new PersistentHashMap2(0, null, false, null);
-final private static Object NOT_FOUND = new Object();
-
-static public IPersistentMap create(Map other){
-	ITransientMap ret = EMPTY.asTransient();
-	for(Object o : other.entrySet())
-		{
-		Map.Entry e = (Entry) o;
-		ret = ret.assoc(e.getKey(), e.getValue());
-		}
-	return ret.persistent();
-}
-
-/*
- * @param init {key1,val1,key2,val2,...}
- */
-public static PersistentHashMap2 create(Object... init){
-	ITransientMap ret = EMPTY.asTransient();
-	for(int i = 0; i < init.length; i += 2)
-		{
-		ret = ret.assoc(init[i], init[i + 1]);
-		}
-	return (PersistentHashMap2) ret.persistent();
-}
-
-public static PersistentHashMap2 create(List init){
-	ITransientMap ret = EMPTY.asTransient();
-	for(Iterator i = init.iterator(); i.hasNext();)
-		{
-		Object key = i.next();
-		if(!i.hasNext())
-			throw new IllegalArgumentException(String.format("No value supplied for key: %s", key));
-		Object val = i.next();
-		ret = ret.assoc(key, val);
-		}
-	return (PersistentHashMap2) ret.persistent();
-}
-
-static public PersistentHashMap2 create(ISeq items){
-	ITransientMap ret = EMPTY.asTransient();
-	for(; items != null; items = items.next().next())
-		{
-		if(items.next() == null)
-			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));
-		ret = ret.assoc(items.first(), RT.second(items));
-		}
-	return (PersistentHashMap2) ret.persistent();
-}
-
-/*
- * @param init {key1,val1,key2,val2,...}
- */
-public static PersistentHashMap2 create(IPersistentMap meta, Object... init){
-	return create(init).withMeta(meta);
-}
-
-PersistentHashMap2(int count, INode root, boolean hasNull, Object nullValue){
-	this.count = count;
-	this.root = root;
-	this.hasNull = hasNull;
-	this.nullValue = nullValue;
-}
-
-public PersistentHashMap2(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){
-	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){
-	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 PersistentHashMap2(meta(), hasNull ? count : count + 1, root, true, val);
-	}
-	Box addedLeaf = new Box(null);
-	INode newroot = (root == null ? BitmapIndexedNode.EMPTY : root) 
-			.assoc(0, Util.hash(key), key, val, addedLeaf);
-	if(newroot == root)
-		return this;
-	return new PersistentHashMap2(meta(), addedLeaf.val == null ? count : count + 1, newroot, hasNull, nullValue);
-}
-
-public Object valAt(Object key, Object 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){
-	return valAt(key, null);
-}
-
-public IPersistentMap assocEx(Object key, Object val) throws Exception{
-	if(containsKey(key))
-		throw new Exception("Key already present");
-	return assoc(key, val);
-}
-
-public IPersistentMap without(Object key){
-	if(key == null)
-		return hasNull ? new PersistentHashMap2(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;
-	return new PersistentHashMap2(meta(), count - 1, newroot, hasNull, nullValue); 
-}
-
-public Iterator iterator(){
-	return new SeqIterator(seq());
-}
-
-public int count(){
-	return count;
-}
-
-public ISeq seq(){
-	ISeq s = root != null ? root.nodeSeq() : null; 
-	return hasNull ? new Cons(new MapEntry(null, nullValue), s) : s;
-}
-
-public IPersistentCollection empty(){
-	return EMPTY.withMeta(meta());	
-}
-
-static int mask(int hash, int shift){
-	//return ((hash << shift) >>> 27);// & 0x01f;
-	return (hash >>> shift) & 0x01f;
-}
-
-public PersistentHashMap2 withMeta(IPersistentMap meta){
-	return new PersistentHashMap2(meta, count, root, hasNull, nullValue);
-}
-
-public TransientHashMap asTransient() {
-	return new TransientHashMap(this);
-}
-
-static final class TransientHashMap extends ATransientMap {
-	AtomicReference<Thread> edit;
-	INode root;
-	int count;
-	boolean hasNull;
-	Object nullValue;
-	
-	
-	TransientHashMap(PersistentHashMap2 m) {
-		this(new AtomicReference<Thread>(Thread.currentThread()), m.root, m.count, m.hasNull, m.nullValue);
-	}
-	
-	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);
-		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 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 PersistentHashMap2(count, root, hasNull, nullValue);
-	}
-
-	Object doValAt(Object key, Object 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() {
-		return count;
-	}
-	
-	void ensureEditable(){
-		Thread owner = edit.get();
-		if(owner == Thread.currentThread())
-			return;
-		if(owner != null)
-			throw new IllegalAccessError("Mutable used by non-owner thread");
-		throw new IllegalAccessError("Mutable used after immutable call");
-	}
-}
-
-static interface INode{
-	INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf);
-
-	INode without(int shift, int hash, Object key);
-
-	IMapEntry find(int shift, int hash, Object key);
-
-	Object find(int shift, int hash, Object key, Object notFound);
-
-	ISeq nodeSeq();
-
-	INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf);
-
-	INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf);
-}
-
-final static class ArrayNode implements INode{
-	int count;
-	final INode[] array;
-	final AtomicReference<Thread> edit;
-
-	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){
-		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 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 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 Seq.create(array);
-	}
-
-	private ArrayNode ensureEditable(AtomicReference<Thread> edit){
-		if(this.edit == edit)
-			return this;
-		return new ArrayNode(edit, count, this.array.clone());
-	}
-	
-	private ArrayNode editAndSet(AtomicReference<Thread> edit, int i, INode n){
-		ArrayNode editable = ensureEditable(edit);
-		editable.array[i] = n;
-		return editable;
-	}
-
-
-	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(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
-		int idx = mask(hash, shift);
-		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;
-		return editAndSet(edit, idx, n);
-	}	
-
-	public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){
-		int idx = mask(hash, shift);
-		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 INode[] nodes;
-		final int i;
-		final ISeq s; 
-		
-		static ISeq create(INode[] nodes) {
-			return create(null, nodes, 0, null);
-		}
-		
-		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.nodes = nodes;
-			this.i = i;
-			this.s = s;
-		}
-
-		public Obj withMeta(IPersistentMap meta) {
-			return new Seq(meta, nodes, i, s);
-		}
-
-		public Object first() {
-			return s.first();
-		}
-
-		public ISeq next() {
-			return create(null, nodes, i, s.next());
-		}
-		
-	}
-}
-
-final static class BitmapIndexedNode implements INode{
-	static final BitmapIndexedNode EMPTY = new BitmapIndexedNode(null, 0, new Object[0]);
-	
-	int bitmap;
-	Object[] array;
-	final AtomicReference<Thread> edit;
-
-	final int index(int bit){
-		return Integer.bitCount(bitmap & (bit - 1));
-	}
-
-	BitmapIndexedNode(AtomicReference<Thread> edit, int bitmap, Object[] array){
-		this.bitmap = bitmap;
-		this.array = array;
-		this.edit = edit;
-	}
-
-	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) {
-			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;
-					}
-				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);
-			}
-		}
-	}
-
-	public INode without(int shift, int hash, Object key){
-		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(shift + 5, hash, key);
-			if (n == valOrNode)
-				return this;
-			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;
-	}
-	
-	public IMapEntry find(int shift, int hash, Object key){
-		int bit = bitpos(hash, shift);
-		if((bitmap & bit) == 0)
-			return null;
-		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 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 ISeq nodeSeq(){
-		return NodeSeq.create(array);
-	}
-
-	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);
-	}
-	
-	private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a) {
-		BitmapIndexedNode editable = ensureEditable(edit);
-		editable.array[i] = a;
-		return editable;
-	}
-
-	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;
-	}
-
-	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){
-		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;
-				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;
-			}
-			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 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;
-	}
-}
-
-final static class HashCollisionNode implements INode{
-
-	final int hash;
-	int count;
-	Object[] array;
-	final AtomicReference<Thread> edit;
-
-	HashCollisionNode(AtomicReference<Thread> edit, int hash, int count, Object... array){
-		this.edit = edit;
-		this.hash = hash;
-		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(key);
-			if(idx != -1) {
-				if(array[idx + 1] == val)
-					return this;
-				return new HashCollisionNode(null, hash, count, cloneAndSet(array, idx + 1, val));
-			}
-			Object[] newArray = new Object[array.length + 2];
-			System.arraycopy(array, 0, newArray, 0, array.length);
-			newArray[array.length] = key;
-			newArray[array.length + 1] = val;
-			return new HashCollisionNode(edit, hash, count + 1, newArray);
-		}
-		// nest it in a bitmap node
-		return new BitmapIndexedNode(null, bitpos(this.hash, shift), new Object[] {this})
-			.assoc(shift, hash, key, val, addedLeaf);
-	}
-
-	public INode without(int shift, int hash, Object key){
-		int idx = findIndex(key);
-		if(idx == -1)
-			return this;
-		if(count == 1)
-			return null;
-		return new HashCollisionNode(null, hash, count - 1, removePair(array, idx/2));
-	}
-
-	public IMapEntry find(int shift, int hash, Object key){
-		int idx = findIndex(key);
-		if(idx < 0)
-			return null;
-		if(Util.equals(key, array[idx]))
-			return new MapEntry(array[idx], array[idx+1]);
-		return null;
-	}
-
-	public Object find(int shift, int hash, Object key, Object notFound){
-		int idx = findIndex(key);
-		if(idx < 0)
-			return notFound;
-		if(Util.equals(key, array[idx]))
-			return array[idx+1];
-		return notFound;
-	}
-
-	public ISeq nodeSeq(){
-		return NodeSeq.create(array);
-	}
-
-	public int findIndex(Object key){
-		for(int i = 0; i < 2*count; i+=2)
-			{
-			if(Util.equals(key, array[i]))
-				return i;
-			}
-		return -1;
-	}
-
-	private HashCollisionNode ensureEditable(AtomicReference<Thread> edit){
-		if(this.edit == edit)
-			return this;
-		return new HashCollisionNode(edit, count, hash, array);
-	}
-
-	private HashCollisionNode ensureEditable(AtomicReference<Thread> edit, int count, Object[] array){
-		if(this.edit == edit) {
-			this.array = array;
-			return this;
-		}
-		return new HashCollisionNode(edit, count, hash, array);
-	}
-
-	private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a) {
-		HashCollisionNode editable = ensureEditable(edit);
-		editable.array[i] = a;
-		return editable;
-	}
-
-	private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) {
-		HashCollisionNode editable = ensureEditable(edit);
-		editable.array[i] = a;
-		editable.array[j] = b;
-		return editable;
-	}
-
-
-	public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){
-		if(hash == this.hash) {
-			int idx = findIndex(key);
-			if(idx != -1) {
-				if(array[idx + 1] == val)
-					return this;
-				return editAndSet(edit, idx+1, val); 
-			}
-			if (array.length > 2*count) {
-				HashCollisionNode editable = editAndSet(edit, 2*count, key, 2*count+1, val);
-				editable.count++;
-				return editable;
-			}
-			Object[] newArray = new Object[array.length + 2];
-			System.arraycopy(array, 0, newArray, 0, array.length);
-			newArray[array.length] = key;
-			newArray[array.length + 1] = val;
-			return ensureEditable(edit, count + 1, newArray);
-		}
-		// nest it in a bitmap node
-		return new BitmapIndexedNode(edit, bitpos(this.hash, shift), new Object[] {this})
-			.assoc(edit, shift, hash, key, val, addedLeaf);
-	}	
-
-	public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){
-		int idx = findIndex(key);
-		if(idx == -1)
-			return this;
-		if(count == 1)
-			return null;
-		HashCollisionNode editable = ensureEditable(edit);
-		editable.array[idx] = editable.array[2*count-2];
-		editable.array[idx+1] = editable.array[2*count-1];
-		editable.array[2*count-2] = editable.array[2*count-1] = null;
-		editable.count--;
-		return editable;
-	}
-}
-
-/*
-public static void main(String[] args){
-	try
-		{
-		ArrayList words = new ArrayList();
-		Scanner s = new Scanner(new File(args[0]));
-		s.useDelimiter(Pattern.compile("\\W"));
-		while(s.hasNext())
-			{
-			String word = s.next();
-			words.add(word);
-			}
-		System.out.println("words: " + words.size());
-		IPersistentMap map = PersistentHashMap.EMPTY;
-		//IPersistentMap map = new PersistentTreeMap();
-		//Map ht = new Hashtable();
-		Map ht = new HashMap();
-		Random rand;
-
-		System.out.println("Building map");
-		long startTime = System.nanoTime();
-		for(Object word5 : words)
-			{
-			map = map.assoc(word5, word5);
-			}
-		rand = new Random(42);
-		IPersistentMap snapshotMap = map;
-		for(int i = 0; i < words.size() / 200; i++)
-			{
-			map = map.without(words.get(rand.nextInt(words.size() / 2)));
-			}
-		long estimatedTime = System.nanoTime() - startTime;
-		System.out.println("count = " + map.count() + ", time: " + estimatedTime / 1000000);
-
-		System.out.println("Building ht");
-		startTime = System.nanoTime();
-		for(Object word1 : words)
-			{
-			ht.put(word1, word1);
-			}
-		rand = new Random(42);
-		for(int i = 0; i < words.size() / 200; i++)
-			{
-			ht.remove(words.get(rand.nextInt(words.size() / 2)));
-			}
-		estimatedTime = System.nanoTime() - startTime;
-		System.out.println("count = " + ht.size() + ", time: " + estimatedTime / 1000000);
-
-		System.out.println("map lookup");
-		startTime = System.nanoTime();
-		int c = 0;
-		for(Object word2 : words)
-			{
-			if(!map.contains(word2))
-				++c;
-			}
-		estimatedTime = System.nanoTime() - startTime;
-		System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);
-		System.out.println("ht lookup");
-		startTime = System.nanoTime();
-		c = 0;
-		for(Object word3 : words)
-			{
-			if(!ht.containsKey(word3))
-				++c;
-			}
-		estimatedTime = System.nanoTime() - startTime;
-		System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);
-		System.out.println("snapshotMap lookup");
-		startTime = System.nanoTime();
-		c = 0;
-		for(Object word4 : words)
-			{
-			if(!snapshotMap.contains(word4))
-				++c;
-			}
-		estimatedTime = System.nanoTime() - startTime;
-		System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000);
-		}
-	catch(FileNotFoundException e)
-		{
-		e.printStackTrace();
-		}
-
-}
-*/
-
-private static INode[] cloneAndSet(INode[] array, int i, INode a) {
-	INode[] clone = array.clone();
-	clone[i] = a;
-	return clone;
-}
-
-private static Object[] cloneAndSet(Object[] array, int i, Object a) {
-	Object[] clone = array.clone();
-	clone[i] = a;
-	return clone;
-}
-
-private static Object[] cloneAndSet(Object[] array, int i, Object a, int j, Object b) {
-	Object[] clone = array.clone();
-	clone[i] = a;
-	clone[j] = b;
-	return clone;
-}
-
-private static Object[] removePair(Object[] array, int i) {
-	Object[] newArray = new Object[array.length - 2];
-	System.arraycopy(array, 0, newArray, 0, 2*i);
-	System.arraycopy(array, 2*(i+1), newArray, 2*i, newArray.length - 2*i);
-	return newArray;
-}
-
-private static INode createNode(int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) {
-	int key1hash = Util.hash(key1);
-	if(key1hash == key2hash)
-		return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2});
-	Box _ = new Box(null);
-	AtomicReference<Thread> edit = new AtomicReference<Thread>();
-	return BitmapIndexedNode.EMPTY
-		.assoc(edit, shift, key1hash, key1, val1, _)
-		.assoc(edit, shift, key2hash, key2, val2, _);
-}
-
-private static INode createNode(AtomicReference<Thread> edit, int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) {
-	int key1hash = Util.hash(key1);
-	if(key1hash == key2hash)
-		return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2});
-	Box _ = new Box(null);
-	return BitmapIndexedNode.EMPTY
-		.assoc(edit, shift, key1hash, key1, val1, _)
-		.assoc(edit, shift, key2hash, key2, val2, _);
-}
-
-private static int bitpos(int hash, int shift){
-	return 1 << mask(hash, shift);
-}
-
-static final class NodeSeq extends ASeq {
-	final Object[] array;
-	final int i;
-	final ISeq s;
-	
-	NodeSeq(Object[] array, int i) {
-		this(null, array, i, null);
-	}
-
-	static ISeq create(Object[] array) {
-		return create(array, 0, null);
-	}
-
-	private static ISeq create(Object[] array, int i, ISeq s) {
-		if(s != null)
-			return new NodeSeq(null, array, i, s);
-		for(int j = i; j < array.length; j+=2) {
-			if(array[j] != null)
-				return new NodeSeq(null, array, j, null);
-			INode node = (INode) array[j+1];
-			if (node != null) {
-				ISeq nodeSeq = node.nodeSeq();
-				if(nodeSeq != null)
-					return new NodeSeq(null, array, j + 2, nodeSeq);
-			}
-		}
-		return null;
-	}
-	
-	NodeSeq(IPersistentMap meta, Object[] array, int i, ISeq s) {
-		super(meta);
-		this.array = array;
-		this.i = i;
-		this.s = s;
-	}
-
-	public Obj withMeta(IPersistentMap meta) {
-		return new NodeSeq(meta, array, i, s);
-	}
-
-	public Object first() {
-		if(s != null)
-			return s.first();
-		return new MapEntry(array[i], array[i+1]);
-	}
-
-	public ISeq next() {
-		if(s != null)
-			return create(array, i, s.next());
-		return create(array, i + 2, null);
-	}
-}
-
-}
\ No newline at end of file