Merge branch 'chunks' into merge-chunks

10 files changed, 610 insertions, 257 deletions

diff --git a/src/clj/clojure/core.clj b/src/clj/clojure/core.clj
index 50e4d584..ef5f2482 100644
--- a/src/clj/clojure/core.clj
+++ b/src/clj/clojure/core.clj
@@ -251,7 +251,9 @@
 (defn vec
   "Creates a new vector containing the contents of coll."
   ([coll]
-   (. clojure.lang.LazilyPersistentVector (createOwning (to-array coll)))))
+   (if (instance? java.util.Collection coll)
+     (clojure.lang.LazilyPersistentVector/create coll)
+     (. clojure.lang.LazilyPersistentVector (createOwning (to-array coll))))))
 
 (defn hash-map
   "keyval => key val
@@ -4315,3 +4317,52 @@
   Delivers the supplied value to the promise, releasing any pending
   derefs. A subsequent call to deliver on a promise will throw an exception."  
   [promise val] (promise val))
+
+;;;;;;;;;;;;;;;;;;;;; editable collections ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+(defn mutable 
+  "Returns a new, mutable version of the collection, in constant time."
+  [#^clojure.lang.IEditableCollection coll] 
+  (.mutable coll))
+
+(defn immutable! 
+  "Returns a new, immutable version of the mutable collection, in constant time."
+  [#^clojure.lang.IMutableCollection coll] 
+  (.immutable coll))
+
+(defn conj!
+  "Adds x to the mutable collection, and return coll. The 'addition'
+  may happen at different 'places' depending on the concrete type."
+  [#^clojure.lang.IMutableCollection coll x]
+  (.conj coll x))
+
+(defn assoc!
+  "When applied to a mutable map, adds mapping of key(s) to
+  val(s). When applied to a mutable vector, sets the val at index.
+  Note - index must be <= (count vector). Returns coll."
+  ([#^clojure.lang.IMutableAssociative coll key val] (.assoc coll key val))
+  ([#^clojure.lang.IMutableAssociative coll key val & kvs]
+   (let [ret (.assoc coll key val)]
+     (if kvs
+       (recur ret (first kvs) (second kvs) (nnext kvs))
+       ret))))
+
+(defn pop!
+  "Removes the last item from a mutable vector. If
+  the collection is empty, throws an exception. Returns coll"
+  [#^clojure.lang.IMutableVector coll] 
+  (.pop coll)) 
+
+;redef into with batch support
+(defn into
+  "Returns a new coll consisting of to-coll with all of the items of
+  from-coll conjoined."
+  [to from]
+  (if (instance? clojure.lang.IEditableCollection to)
+    (#(loop [ret (mutable to) items (seq from)]
+        (if items
+          (recur (conj! ret (first items)) (next items))
+          (immutable! ret))))
+    (#(loop [ret to items (seq from)]
+        (if items
+          (recur (conj ret (first items)) (next items))
+          ret)))))
diff --git a/src/jvm/clojure/lang/Associative.java b/src/jvm/clojure/lang/Associative.java
index 891def5f..a2399946 100644
--- a/src/jvm/clojure/lang/Associative.java
+++ b/src/jvm/clojure/lang/Associative.java
@@ -9,14 +9,11 @@ package clojure.lang;
  * the terms of this license.

  * You must not remove this notice, or any other, from this software.

  */

-public interface Associative extends IPersistentCollection{

+public interface Associative extends IPersistentCollection, ILookup{

 boolean containsKey(Object key);

 

 IMapEntry entryAt(Object key);

 

 Associative assoc(Object key, Object val);

 

-Object valAt(Object key);

-

-Object valAt(Object key, Object notFound);

 }

diff --git a/src/jvm/clojure/lang/IEditableCollection.java b/src/jvm/clojure/lang/IEditableCollection.java
new file mode 100644
index 00000000..be447958
--- /dev/null
+++ b/src/jvm/clojure/lang/IEditableCollection.java
@@ -0,0 +1,17 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ *   which can be found in the file epl-v10.html at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IEditableCollection{
+IMutableCollection mutable();
+}
diff --git a/src/jvm/clojure/lang/ILookup.java b/src/jvm/clojure/lang/ILookup.java
new file mode 100644
index 00000000..b124955d
--- /dev/null
+++ b/src/jvm/clojure/lang/ILookup.java
@@ -0,0 +1,19 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ *   which can be found in the file epl-v10.html at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
+ **/
+
+/* rich Aug 2, 2009 */
+
+package clojure.lang;
+
+public interface ILookup{
+Object valAt(Object key);
+
+Object valAt(Object key, Object notFound);
+}
diff --git a/src/jvm/clojure/lang/IMutableAssociative.java b/src/jvm/clojure/lang/IMutableAssociative.java
new file mode 100644
index 00000000..1eef92c2
--- /dev/null
+++ b/src/jvm/clojure/lang/IMutableAssociative.java
@@ -0,0 +1,18 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ *   which can be found in the file epl-v10.html at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IMutableAssociative extends IMutableCollection, ILookup{
+
+IMutableAssociative assoc(Object key, Object val);
+}
diff --git a/src/jvm/clojure/lang/IMutableCollection.java b/src/jvm/clojure/lang/IMutableCollection.java
new file mode 100644
index 00000000..a41f1701
--- /dev/null
+++ b/src/jvm/clojure/lang/IMutableCollection.java
@@ -0,0 +1,20 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ *   which can be found in the file epl-v10.html at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IMutableCollection{
+
+IMutableCollection conj(Object val);
+
+IPersistentCollection immutable();
+}
diff --git a/src/jvm/clojure/lang/IMutableVector.java b/src/jvm/clojure/lang/IMutableVector.java
new file mode 100644
index 00000000..3deab315
--- /dev/null
+++ b/src/jvm/clojure/lang/IMutableVector.java
@@ -0,0 +1,20 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ *   which can be found in the file epl-v10.html at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IMutableVector extends IMutableAssociative, Indexed{
+
+IMutableVector assocN(int i, Object val);
+
+IMutableVector pop();
+}
diff --git a/src/jvm/clojure/lang/LazilyPersistentVector.java b/src/jvm/clojure/lang/LazilyPersistentVector.java
index f3562cae..44985467 100644
--- a/src/jvm/clojure/lang/LazilyPersistentVector.java
+++ b/src/jvm/clojure/lang/LazilyPersistentVector.java
@@ -14,141 +14,21 @@ package clojure.lang;
 
 import java.util.Collection;
 
-public class LazilyPersistentVector extends APersistentVector{
-final Object[] array;
-PersistentVector v = null;
+public class LazilyPersistentVector{
+
 
 static public IPersistentVector createOwning(Object... items){
 	if(items.length == 0)
 		return PersistentVector.EMPTY;
-	return new LazilyPersistentVector(null, items, null);
+	else if(items.length <= 32)
+		return new PersistentVector(items.length, 5, PersistentVector.EMPTY_NODE,items);
+	return PersistentVector.create(items);
 }
 
 static public IPersistentVector create(Collection coll){
-	return createOwning(coll.toArray());
-}
-
-LazilyPersistentVector(IPersistentMap meta, Object[] array, PersistentVector v){
-	super(meta);
-	this.array = array;
-	this.v = v;
-}
-
-public ISeq seq(){
-	if(array.length == 0)
-		return null;
-	return new ChunkedSeq(array);
-}
-
-static class ChunkedSeq extends ASeq implements IChunkedSeq, IndexedSeq{
-	final Object[] array;
-	final int offset;
-	final int end;
-	static final int BLOCK = 32;
-
-	ChunkedSeq(IPersistentMap meta, Object[] array, int offset, int end){
-		super(meta);
-		this.array = array;
-		this.offset = offset;
-		this.end = end;
-	}
-
-	ChunkedSeq(Object[] array){
-		this(array, 0);
-	}
-
-	ChunkedSeq(Object[] array, int offset){
-		this(array,offset,Math.min(offset + BLOCK, array.length));
-	}
-
-	ChunkedSeq(Object[] array, int offset, int end){
-		this.array = array;
-		this.offset = offset;
-		this.end = end;
-	}
-
-	public Obj withMeta(IPersistentMap meta){
-		if(meta != _meta)
-			return new ChunkedSeq(meta, array,offset,end);
-		return this;
-	}
-
-	public Object first(){
-		return array[offset];
-	}
-
-	public ISeq next(){
-		if(offset + 1 < end)
-			return new ChunkedSeq(array,offset + 1,end);
-		return chunkedNext();
-	}
-
-	public IChunk chunkedFirst(){
-		return new ArrayChunk(array, offset, end);
-	}
-
-	public ISeq chunkedNext(){
-		if(end < array.length)
-			return new ChunkedSeq(array,end);
-		return null;
-		}
-
-	public ISeq chunkedMore(){
-		ISeq s = chunkedNext();
-		if(s == null)
-			return PersistentList.EMPTY;
-		return s;
-	}
-
-	public int index(){
-		return offset;
-	}
-
-	public int count(){
-		return array.length - offset;
-	}
-}
-
-public Object[] toArray(){
-	return array.clone();
-}
-
-public Object nth(int i){
-	return array[i];
-}
-
-public IPersistentVector assocN(int i, Object val){
-	return (IPersistentVector) v().assoc(i, val);
-}
-
-public int count(){
-	return array.length;
-}
-
-public IPersistentVector cons(Object o){
-	return v().cons(o);
-}
-
-public IPersistentCollection empty(){
-	return PersistentVector.EMPTY.withMeta(meta());	
-}
-
-public IPersistentStack pop(){
-	return v().pop();
-}
-
-private synchronized IPersistentVector v(){
-	if(v == null)
-		{
-		v = PersistentVector.create(array);
-		}
-	return v;
-}
-
-public Obj withMeta(IPersistentMap meta){
-	if(meta != _meta)
-		return new LazilyPersistentVector(meta, array, v);
-	return this;
+	if(!(coll instanceof ISeq) && coll.size() <= 32)
+		return createOwning(coll.toArray());
+	return PersistentVector.create(RT.seq(coll));
 }
 
 }
diff --git a/src/jvm/clojure/lang/PersistentVector.java b/src/jvm/clojure/lang/PersistentVector.java
index 5c662556..752bccf8 100644
--- a/src/jvm/clojure/lang/PersistentVector.java
+++ b/src/jvm/clojure/lang/PersistentVector.java
@@ -1,35 +1,11 @@
 /**
- 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.
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ *   which can be found in the file epl-v10.html at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
  **/
 
 /* rich Jul 5, 2007 */
@@ -37,38 +13,57 @@
 package clojure.lang;
 
 import java.util.List;
+import java.util.concurrent.atomic.AtomicReference;
+
+public class PersistentVector extends APersistentVector implements IEditableCollection{
+
+static class Node{
+	final AtomicReference<Thread> edit;
+	final Object[] array;
+
+	Node(AtomicReference<Thread> edit, Object[] array){
+		this.edit = edit;
+		this.array = array;
+	}
+
+	Node(AtomicReference<Thread> edit){
+		this.edit = edit;
+		this.array = new Object[32];
+	}
+}
+
+final static AtomicReference<Thread> NOEDIT = new AtomicReference<Thread>(null);
+final static Node EMPTY_NODE = new Node(NOEDIT, new Object[32]);
 
-public class PersistentVector extends APersistentVector{
 final int cnt;
 final int shift;
-final Object[] root;
+final Node root;
 final Object[] tail;
 
-public final static PersistentVector EMPTY = new PersistentVector(0, 5, RT.EMPTY_ARRAY, RT.EMPTY_ARRAY);
-
+public final static PersistentVector EMPTY = new PersistentVector(0, 5, EMPTY_NODE, new Object[]{});
 
 static public PersistentVector create(ISeq items){
-	PersistentVector ret = EMPTY;
+	MutableVector ret = EMPTY.mutable();
 	for(; items != null; items = items.next())
-		ret = ret.cons(items.first());
-	return ret;
+		ret = ret.conj(items.first());
+	return ret.immutable();
 }
 
 static public PersistentVector create(List items){
-	PersistentVector ret = EMPTY;
+	MutableVector ret = EMPTY.mutable();
 	for(Object item : items)
-		ret = ret.cons(item);
-	return ret;
+		ret = ret.conj(item);
+	return ret.immutable();
 }
 
 static public PersistentVector create(Object... items){
-	PersistentVector ret = EMPTY;
+	MutableVector ret = EMPTY.mutable();
 	for(Object item : items)
-		ret = ret.cons(item);
-	return ret;
+		ret = ret.conj(item);
+	return ret.immutable();
 }
 
-PersistentVector(int cnt, int shift, Object[] root, Object[] tail){
+PersistentVector(int cnt, int shift, Node root, Object[] tail){
 	super(null);
 	this.cnt = cnt;
 	this.shift = shift;
@@ -77,7 +72,7 @@ PersistentVector(int cnt, int shift, Object[] root, Object[] tail){
 }
 
 
-PersistentVector(IPersistentMap meta, int cnt, int shift, Object[] root, Object[] tail){
+PersistentVector(IPersistentMap meta, int cnt, int shift, Node root, Object[] tail){
 	super(meta);
 	this.cnt = cnt;
 	this.shift = shift;
@@ -85,25 +80,31 @@ PersistentVector(IPersistentMap meta, int cnt, int shift, Object[] root, Object[
 	this.tail = tail;
 }
 
+public MutableVector mutable(){
+	return new MutableVector(this);
+}
+
 final int tailoff(){
-	return cnt - tail.length;
+	if(cnt < 32)
+		return 0;
+	return ((cnt - 1) >>> 5) << 5;
 }
 
-public Object[] nodeFor(int i){
+public Object[] arrayFor(int i){
 	if(i >= 0 && i < cnt)
 		{
 		if(i >= tailoff())
 			return tail;
-		Object[] arr = root;
+		Node node = root;
 		for(int level = shift; level > 0; level -= 5)
-			arr = (Object[]) arr[(i >>> level) & 0x01f];
-		return arr;
+			node = (Node) node.array[(i >>> level) & 0x01f];
+		return node.array;
 		}
 	throw new IndexOutOfBoundsException();
 }
 
 public Object nth(int i){
-	Object[] node = nodeFor(i);
+	Object[] node = arrayFor(i);
 	return node[i & 0x01f];
 }
 
@@ -126,16 +127,16 @@ public PersistentVector assocN(int i, Object val){
 	throw new IndexOutOfBoundsException();
 }
 
-private static Object[] doAssoc(int level, Object[] arr, int i, Object val){
-	Object[] ret = arr.clone();
+private static Node doAssoc(int level, Node node, int i, Object val){
+	Node ret = new Node(node.edit,node.array.clone());
 	if(level == 0)
 		{
-		ret[i & 0x01f] = val;
+		ret.array[i & 0x01f] = val;
 		}
 	else
 		{
 		int subidx = (i >>> level) & 0x01f;
-		ret[subidx] = doAssoc(level - 5, (Object[]) arr[subidx], i, val);
+		ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
 		}
 	return ret;
 }
@@ -150,24 +151,64 @@ public PersistentVector withMeta(IPersistentMap meta){
 
 
 public PersistentVector cons(Object val){
-	if(tail.length < 32)
+	int i = cnt;
+	//room in tail?
+//	if(tail.length < 32)
+	if(cnt - tailoff() < 32)
 		{
 		Object[] newTail = new Object[tail.length + 1];
 		System.arraycopy(tail, 0, newTail, 0, tail.length);
 		newTail[tail.length] = val;
 		return new PersistentVector(meta(), cnt + 1, shift, root, newTail);
 		}
-	Box expansion = new Box(null);
-	Object[] newroot = pushTail(shift - 5, root, tail, expansion);
+	//full tail, push into tree
+	Node newroot;
+	Node tailnode = new Node(root.edit,tail);
 	int newshift = shift;
-	if(expansion.val != null)
+	//overflow root?
+	if((cnt >>> 5) > (1 << shift))
 		{
-		newroot = new Object[]{newroot, expansion.val};
+		newroot = new Node(root.edit);
+		newroot.array[0] = root;
+		newroot.array[1] = newPath(root.edit,shift, tailnode);
 		newshift += 5;
 		}
+	else
+		newroot = pushTail(shift, root, tailnode);
 	return new PersistentVector(meta(), cnt + 1, newshift, newroot, new Object[]{val});
 }
 
+private Node pushTail(int level, Node parent, Node tailnode){
+	//if parent is leaf, insert node,
+	// else does it map to an existing child? -> nodeToInsert = pushNode one more level
+	// else alloc new path
+	//return  nodeToInsert placed in copy of parent
+	int subidx = ((cnt - 1) >>> level) & 0x01f;
+	Node ret = new Node(parent.edit, parent.array.clone());
+	Node nodeToInsert;
+	if(level == 5)
+		{
+		nodeToInsert = tailnode;
+		}
+	else
+		{
+		Node child = (Node) parent.array[subidx];
+		nodeToInsert = (child != null)?
+		                pushTail(level-5,child, tailnode)
+		                :newPath(root.edit,level-5, tailnode);
+		}
+	ret.array[subidx] = nodeToInsert;
+	return ret;
+}
+
+private static Node newPath(AtomicReference<Thread> edit,int level, Node node){
+	if(level == 0)
+		return node;
+	Node ret = new Node(edit);
+	ret.array[0] = newPath(edit, level - 5, node);
+	return ret;
+}
+
 public IChunkedSeq chunkedSeq(){
 	if(count() == 0)
 		return null;
@@ -189,7 +230,7 @@ static public final class ChunkedSeq extends ASeq implements IChunkedSeq{
 		this.vec = vec;
 		this.i = i;
 		this.offset = offset;
-		this.node = vec.nodeFor(i);
+		this.node = vec.arrayFor(i);
 	}
 
 	ChunkedSeq(IPersistentMap meta, PersistentVector vec, Object[] node, int i, int offset){
@@ -245,84 +286,361 @@ public IPersistentCollection empty(){
 	return EMPTY.withMeta(meta());
 }
 
-private Object[] pushTail(int level, Object[] arr, Object[] tailNode, Box expansion){
-	Object newchild;
-	if(level == 0)
-		{
-		newchild = tailNode;
-		}
-	else
-		{
-		newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
-		if(expansion.val == null)
-			{
-			Object[] ret = arr.clone();
-			ret[arr.length - 1] = newchild;
-			return ret;
-			}
-		else
-			newchild = expansion.val;
-		}
-	//expansion
-	if(arr.length == 32)
-		{
-		expansion.val = new Object[]{newchild};
-		return arr;
-		}
-	Object[] ret = new Object[arr.length + 1];
-	System.arraycopy(arr, 0, ret, 0, arr.length);
-	ret[arr.length] = newchild;
-	expansion.val = null;
-	return ret;
-}
+//private Node pushTail(int level, Node node, Object[] tailNode, Box expansion){
+//	Object newchild;
+//	if(level == 0)
+//		{
+//		newchild = tailNode;
+//		}
+//	else
+//		{
+//		newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
+//		if(expansion.val == null)
+//			{
+//			Object[] ret = arr.clone();
+//			ret[arr.length - 1] = newchild;
+//			return ret;
+//			}
+//		else
+//			newchild = expansion.val;
+//		}
+//	//expansion
+//	if(arr.length == 32)
+//		{
+//		expansion.val = new Object[]{newchild};
+//		return arr;
+//		}
+//	Object[] ret = new Object[arr.length + 1];
+//	System.arraycopy(arr, 0, ret, 0, arr.length);
+//	ret[arr.length] = newchild;
+//	expansion.val = null;
+//	return ret;
+//}
 
 public PersistentVector pop(){
 	if(cnt == 0)
 		throw new IllegalStateException("Can't pop empty vector");
 	if(cnt == 1)
 		return EMPTY.withMeta(meta());
-	if(tail.length > 1)
+	//if(tail.length > 1)
+	if(cnt-tailoff() > 1)
 		{
 		Object[] newTail = new Object[tail.length - 1];
 		System.arraycopy(tail, 0, newTail, 0, newTail.length);
 		return new PersistentVector(meta(), cnt - 1, shift, root, newTail);
 		}
-	Box ptail = new Box(null);
-	Object[] newroot = popTail(shift - 5, root, ptail);
+	Object[] newtail = arrayFor(cnt - 2);
+
+	Node newroot = popTail(shift, root);
 	int newshift = shift;
 	if(newroot == null)
 		{
-		newroot = RT.EMPTY_ARRAY;
+		newroot = EMPTY_NODE;
 		}
-	if(shift > 5 && newroot.length == 1)
+	if(shift > 5 && newroot.array[1] == null)
 		{
-		newroot = (Object[]) newroot[0];
+		newroot = (Node) newroot.array[0];
 		newshift -= 5;
 		}
-	return new PersistentVector(meta(), cnt - 1, newshift, newroot, (Object[]) ptail.val);
+	return new PersistentVector(meta(), cnt - 1, newshift, newroot, newtail);
 }
 
-private Object[] popTail(int shift, Object[] arr, Box ptail){
-	if(shift > 0)
+private Node popTail(int level, Node node){
+	int subidx = ((cnt-2) >>> level) & 0x01f;
+	if(level > 5)
 		{
-		Object[] newchild = popTail(shift - 5, (Object[]) arr[arr.length - 1], ptail);
-		if(newchild != null)
+		Node newchild = popTail(level - 5, (Node) node.array[subidx]);
+		if(newchild == null && subidx == 0)
+			return null;
+		else
 			{
-			Object[] ret = arr.clone();
-			ret[arr.length - 1] = newchild;
+			Node ret = new Node(root.edit, node.array.clone());
+			ret.array[subidx] = newchild;
 			return ret;
 			}
 		}
-	if(shift == 0)
-		ptail.val = arr[arr.length - 1];
-	//contraction
-	if(arr.length == 1)
+	else if(subidx == 0)
 		return null;
-	Object[] ret = new Object[arr.length - 1];
-	System.arraycopy(arr, 0, ret, 0, ret.length);
-	return ret;
+	else
+		{
+		Node ret = new Node(root.edit, node.array.clone());
+		ret.array[subidx] = null;
+		return ret;
+		}
 }
 
+static final class MutableVector extends AFn implements IMutableVector, Counted{
+	int cnt;
+	int shift;
+	Node root;
+	Object[] tail;
+
+	MutableVector(int cnt, int shift, Node root, Object[] tail){
+		this.cnt = cnt;
+		this.shift = shift;
+		this.root = root;
+		this.tail = tail;
+	}
+
+	MutableVector(PersistentVector v){
+		this(v.cnt, v.shift, editableRoot(v.root), editableTail(v.tail));
+	}
+
+	public int count(){
+		ensureEditable();
+		return cnt;
+	}
+	
+	Node ensureEditable(Node node){
+		if(node.edit == root.edit)
+			return node;
+		return new Node(root.edit, node.array.clone());
+	}
+
+	void ensureEditable(){
+		Thread owner = root.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");
+
+//		root = editableRoot(root);
+//		tail = editableTail(tail);
+	}
+
+	static Node editableRoot(Node node){
+		return new Node(new AtomicReference<Thread>(Thread.currentThread()), node.array.clone());
+	}
+
+	public PersistentVector immutable(){
+		ensureEditable();
+//		Thread owner = root.edit.get();
+//		if(owner != null && owner != Thread.currentThread())
+//			{
+//			throw new IllegalAccessError("Mutation release by non-owner thread");
+//			}
+		root.edit.set(null);
+		Object[] trimmedTail = new Object[cnt-tailoff()];
+		System.arraycopy(tail,0,trimmedTail,0,trimmedTail.length);
+		return new PersistentVector(cnt, shift, root, trimmedTail);
+	}
+
+	static Object[] editableTail(Object[] tl){
+		Object[] ret = new Object[32];
+		System.arraycopy(tl,0,ret,0,tl.length);
+		return ret;
+	}
+
+	public MutableVector conj(Object val){
+		ensureEditable();
+		int i = cnt;
+		//room in tail?
+		if(i - tailoff() < 32)
+			{
+			tail[i & 0x01f] = val;
+			++cnt;
+			return this;
+			}
+		//full tail, push into tree
+		Node newroot;
+		Node tailnode = new Node(root.edit, tail);
+		tail = new Object[32];
+		tail[0] = val;
+		int newshift = shift;
+		//overflow root?
+		if((cnt >>> 5) > (1 << shift))
+			{
+			newroot = new Node(root.edit);
+			newroot.array[0] = root;
+			newroot.array[1] = newPath(root.edit,shift, tailnode);
+			newshift += 5;
+			}
+		else
+			newroot = pushTail(shift, root, tailnode);
+		root = newroot;
+		shift = newshift;
+		++cnt;
+		return this;
+	}
+
+	private Node pushTail(int level, Node parent, Node tailnode){
+		//if parent is leaf, insert node,
+		// else does it map to an existing child? -> nodeToInsert = pushNode one more level
+		// else alloc new path
+		//return  nodeToInsert placed in parent
+		parent = ensureEditable(parent);
+		int subidx = ((cnt - 1) >>> level) & 0x01f;
+		Node ret = parent;
+		Node nodeToInsert;
+		if(level == 5)
+			{
+			nodeToInsert = tailnode;
+			}
+		else
+			{
+			Node child = (Node) parent.array[subidx];
+			nodeToInsert = (child != null) ?
+			               pushTail(level - 5, child, tailnode)
+			                               : newPath(root.edit, level - 5, tailnode);
+			}
+		ret.array[subidx] = nodeToInsert;
+		return ret;
+	}
+
+	final private int tailoff(){
+		if(cnt < 32)
+			return 0;
+		return ((cnt-1) >>> 5) << 5;
+	}
+
+	private Object[] arrayFor(int i){
+		if(i >= 0 && i < cnt)
+			{
+			if(i >= tailoff())
+				return tail;
+			Node node = root;
+			for(int level = shift; level > 0; level -= 5)
+				node = (Node) node.array[(i >>> level) & 0x01f];
+			return node.array;
+			}
+		throw new IndexOutOfBoundsException();
+	}
+
+	public Object valAt(Object key){
+		//note - relies on ensureEditable in 2-arg valAt
+		return valAt(key, null);
+	}
+
+	public Object valAt(Object key, Object notFound){
+		ensureEditable();
+		if(Util.isInteger(key))
+			{
+			int i = ((Number) key).intValue();
+			if(i >= 0 && i < cnt)
+				return nth(i);
+			}
+		return notFound;
+	}
+
+	public Object invoke(Object arg1) throws Exception{
+		//note - relies on ensureEditable in nth
+		if(Util.isInteger(arg1))
+			return nth(((Number) arg1).intValue());
+		throw new IllegalArgumentException("Key must be integer");
+	}
+
+	public Object nth(int i){
+		ensureEditable();
+		Object[] node = arrayFor(i);
+		return node[i & 0x01f];
+	}
+
+	public MutableVector assocN(int i, Object val){
+		ensureEditable();
+		if(i >= 0 && i < cnt)
+			{
+			if(i >= tailoff())
+				{
+				tail[i & 0x01f] = val;
+				return this;
+				}
+
+			root = doAssoc(shift, root, i, val);
+			return this;
+			}
+		if(i == cnt)
+			return conj(val);
+		throw new IndexOutOfBoundsException();
+	}
+
+	public MutableVector assoc(Object key, Object val){
+		//note - relies on ensureEditable in assocN
+		if(Util.isInteger(key))
+			{
+			int i = ((Number) key).intValue();
+			return assocN(i, val);
+			}
+		throw new IllegalArgumentException("Key must be integer");
+	}
+
+	private Node doAssoc(int level, Node node, int i, Object val){
+		node = ensureEditable(node);
+		Node ret = node;
+		if(level == 0)
+			{
+			ret.array[i & 0x01f] = val;
+			}
+		else
+			{
+			int subidx = (i >>> level) & 0x01f;
+			ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
+			}
+		return ret;
+	}
+
+	public MutableVector pop(){
+		ensureEditable();
+		if(cnt == 0)
+			throw new IllegalStateException("Can't pop empty vector");
+		if(cnt == 1)
+			{
+			cnt = 0;
+			return this;
+			}
+		int i = cnt - 1;
+		//pop in tail?
+		if((i & 0x01f) > 0)
+			{
+			--cnt;
+			return this;
+			}
+
+		Object[] newtail = arrayFor(cnt - 2);
+
+		Node newroot = popTail(shift, root);
+		int newshift = shift;
+		if(newroot == null)
+			{
+			newroot = EMPTY_NODE;
+			}
+		if(shift > 5 && newroot.array[1] == null)
+			{
+			newroot = (Node) newroot.array[0];
+			newshift -= 5;
+			}
+		root = newroot;
+		shift = newshift;
+		--cnt;
+		tail = newtail;
+		return this;
+	}
+
+	private Node popTail(int level, Node node){
+		node = ensureEditable(node);
+		int subidx = ((cnt - 2) >>> level) & 0x01f;
+		if(level > 5)
+			{
+			Node newchild = popTail(level - 5, (Node) node.array[subidx]);
+			if(newchild == null && subidx == 0)
+				return null;
+			else
+				{
+				Node ret = node;
+				ret.array[subidx] = newchild;
+				return ret;
+				}
+			}
+		else if(subidx == 0)
+			return null;
+		else
+			{
+			Node ret = node;
+			ret.array[subidx] = null;
+			return ret;
+			}
+	}
+}
 /*
 static public void main(String[] args){
 	if(args.length != 3)
@@ -333,23 +651,27 @@ static public void main(String[] args){
 	int size = Integer.parseInt(args[0]);
 	int writes = Integer.parseInt(args[1]);
 	int reads = Integer.parseInt(args[2]);
-	Vector v = new Vector(size);
-	v.setSize(size);
+//	Vector v = new Vector(size);
+	ArrayList v = new ArrayList(size);
+//	v.setSize(size);
 	//PersistentArray p = new PersistentArray(size);
 	PersistentVector p = PersistentVector.EMPTY;
+//	MutableVector mp = p.mutable();
 
 	for(int i = 0; i < size; i++)
 		{
-		v.set(i, i);
+		v.add(i);
+//		v.set(i, i);
 		//p