1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/lang/PersistentVector.java	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,748 @@
     1.4 +/**
     1.5 + *   Copyright (c) Rich Hickey. All rights reserved.
     1.6 + *   The use and distribution terms for this software are covered by the
     1.7 + *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
     1.8 + *   which can be found in the file epl-v10.html at the root of this distribution.
     1.9 + *   By using this software in any fashion, you are agreeing to be bound by
    1.10 + * 	 the terms of this license.
    1.11 + *   You must not remove this notice, or any other, from this software.
    1.12 + **/
    1.13 +
    1.14 +/* rich Jul 5, 2007 */
    1.15 +
    1.16 +package clojure.lang;
    1.17 +
    1.18 +import java.io.Serializable;
    1.19 +import java.util.List;
    1.20 +import java.util.concurrent.atomic.AtomicReference;
    1.21 +
    1.22 +public class PersistentVector extends APersistentVector implements IObj, IEditableCollection{
    1.23 +
    1.24 +static class Node implements Serializable {
    1.25 +	transient final AtomicReference<Thread> edit;
    1.26 +	final Object[] array;
    1.27 +
    1.28 +	Node(AtomicReference<Thread> edit, Object[] array){
    1.29 +		this.edit = edit;
    1.30 +		this.array = array;
    1.31 +	}
    1.32 +
    1.33 +	Node(AtomicReference<Thread> edit){
    1.34 +		this.edit = edit;
    1.35 +		this.array = new Object[32];
    1.36 +	}
    1.37 +}
    1.38 +
    1.39 +final static AtomicReference<Thread> NOEDIT = new AtomicReference<Thread>(null);
    1.40 +final static Node EMPTY_NODE = new Node(NOEDIT, new Object[32]);
    1.41 +
    1.42 +final int cnt;
    1.43 +final int shift;
    1.44 +final Node root;
    1.45 +final Object[] tail;
    1.46 +final IPersistentMap _meta;
    1.47 +
    1.48 +
    1.49 +public final static PersistentVector EMPTY = new PersistentVector(0, 5, EMPTY_NODE, new Object[]{});
    1.50 +
    1.51 +static public PersistentVector create(ISeq items){
    1.52 +	TransientVector ret = EMPTY.asTransient();
    1.53 +	for(; items != null; items = items.next())
    1.54 +		ret = ret.conj(items.first());
    1.55 +	return ret.persistent();
    1.56 +}
    1.57 +
    1.58 +static public PersistentVector create(List items){
    1.59 +	TransientVector ret = EMPTY.asTransient();
    1.60 +	for(Object item : items)
    1.61 +		ret = ret.conj(item);
    1.62 +	return ret.persistent();
    1.63 +}
    1.64 +
    1.65 +static public PersistentVector create(Object... items){
    1.66 +	TransientVector ret = EMPTY.asTransient();
    1.67 +	for(Object item : items)
    1.68 +		ret = ret.conj(item);
    1.69 +	return ret.persistent();
    1.70 +}
    1.71 +
    1.72 +PersistentVector(int cnt, int shift, Node root, Object[] tail){
    1.73 +	this._meta = null;
    1.74 +	this.cnt = cnt;
    1.75 +	this.shift = shift;
    1.76 +	this.root = root;
    1.77 +	this.tail = tail;
    1.78 +}
    1.79 +
    1.80 +
    1.81 +PersistentVector(IPersistentMap meta, int cnt, int shift, Node root, Object[] tail){
    1.82 +	this._meta = meta;
    1.83 +	this.cnt = cnt;
    1.84 +	this.shift = shift;
    1.85 +	this.root = root;
    1.86 +	this.tail = tail;
    1.87 +}
    1.88 +
    1.89 +public TransientVector asTransient(){
    1.90 +	return new TransientVector(this);
    1.91 +}
    1.92 +
    1.93 +final int tailoff(){
    1.94 +	if(cnt < 32)
    1.95 +		return 0;
    1.96 +	return ((cnt - 1) >>> 5) << 5;
    1.97 +}
    1.98 +
    1.99 +public Object[] arrayFor(int i){
   1.100 +	if(i >= 0 && i < cnt)
   1.101 +		{
   1.102 +		if(i >= tailoff())
   1.103 +			return tail;
   1.104 +		Node node = root;
   1.105 +		for(int level = shift; level > 0; level -= 5)
   1.106 +			node = (Node) node.array[(i >>> level) & 0x01f];
   1.107 +		return node.array;
   1.108 +		}
   1.109 +	throw new IndexOutOfBoundsException();
   1.110 +}
   1.111 +
   1.112 +public Object nth(int i){
   1.113 +	Object[] node = arrayFor(i);
   1.114 +	return node[i & 0x01f];
   1.115 +}
   1.116 +
   1.117 +public Object nth(int i, Object notFound){
   1.118 +	if(i >= 0 && i < cnt)
   1.119 +		return nth(i);
   1.120 +	return notFound;
   1.121 +}
   1.122 +
   1.123 +public PersistentVector assocN(int i, Object val){
   1.124 +	if(i >= 0 && i < cnt)
   1.125 +		{
   1.126 +		if(i >= tailoff())
   1.127 +			{
   1.128 +			Object[] newTail = new Object[tail.length];
   1.129 +			System.arraycopy(tail, 0, newTail, 0, tail.length);
   1.130 +			newTail[i & 0x01f] = val;
   1.131 +
   1.132 +			return new PersistentVector(meta(), cnt, shift, root, newTail);
   1.133 +			}
   1.134 +
   1.135 +		return new PersistentVector(meta(), cnt, shift, doAssoc(shift, root, i, val), tail);
   1.136 +		}
   1.137 +	if(i == cnt)
   1.138 +		return cons(val);
   1.139 +	throw new IndexOutOfBoundsException();
   1.140 +}
   1.141 +
   1.142 +private static Node doAssoc(int level, Node node, int i, Object val){
   1.143 +	Node ret = new Node(node.edit,node.array.clone());
   1.144 +	if(level == 0)
   1.145 +		{
   1.146 +		ret.array[i & 0x01f] = val;
   1.147 +		}
   1.148 +	else
   1.149 +		{
   1.150 +		int subidx = (i >>> level) & 0x01f;
   1.151 +		ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
   1.152 +		}
   1.153 +	return ret;
   1.154 +}
   1.155 +
   1.156 +public int count(){
   1.157 +	return cnt;
   1.158 +}
   1.159 +
   1.160 +public PersistentVector withMeta(IPersistentMap meta){
   1.161 +	return new PersistentVector(meta, cnt, shift, root, tail);
   1.162 +}
   1.163 +
   1.164 +public IPersistentMap meta(){
   1.165 +	return _meta;
   1.166 +}
   1.167 +
   1.168 +
   1.169 +public PersistentVector cons(Object val){
   1.170 +	int i = cnt;
   1.171 +	//room in tail?
   1.172 +//	if(tail.length < 32)
   1.173 +	if(cnt - tailoff() < 32)
   1.174 +		{
   1.175 +		Object[] newTail = new Object[tail.length + 1];
   1.176 +		System.arraycopy(tail, 0, newTail, 0, tail.length);
   1.177 +		newTail[tail.length] = val;
   1.178 +		return new PersistentVector(meta(), cnt + 1, shift, root, newTail);
   1.179 +		}
   1.180 +	//full tail, push into tree
   1.181 +	Node newroot;
   1.182 +	Node tailnode = new Node(root.edit,tail);
   1.183 +	int newshift = shift;
   1.184 +	//overflow root?
   1.185 +	if((cnt >>> 5) > (1 << shift))
   1.186 +		{
   1.187 +		newroot = new Node(root.edit);
   1.188 +		newroot.array[0] = root;
   1.189 +		newroot.array[1] = newPath(root.edit,shift, tailnode);
   1.190 +		newshift += 5;
   1.191 +		}
   1.192 +	else
   1.193 +		newroot = pushTail(shift, root, tailnode);
   1.194 +	return new PersistentVector(meta(), cnt + 1, newshift, newroot, new Object[]{val});
   1.195 +}
   1.196 +
   1.197 +private Node pushTail(int level, Node parent, Node tailnode){
   1.198 +	//if parent is leaf, insert node,
   1.199 +	// else does it map to an existing child? -> nodeToInsert = pushNode one more level
   1.200 +	// else alloc new path
   1.201 +	//return  nodeToInsert placed in copy of parent
   1.202 +	int subidx = ((cnt - 1) >>> level) & 0x01f;
   1.203 +	Node ret = new Node(parent.edit, parent.array.clone());
   1.204 +	Node nodeToInsert;
   1.205 +	if(level == 5)
   1.206 +		{
   1.207 +		nodeToInsert = tailnode;
   1.208 +		}
   1.209 +	else
   1.210 +		{
   1.211 +		Node child = (Node) parent.array[subidx];
   1.212 +		nodeToInsert = (child != null)?
   1.213 +		                pushTail(level-5,child, tailnode)
   1.214 +		                :newPath(root.edit,level-5, tailnode);
   1.215 +		}
   1.216 +	ret.array[subidx] = nodeToInsert;
   1.217 +	return ret;
   1.218 +}
   1.219 +
   1.220 +private static Node newPath(AtomicReference<Thread> edit,int level, Node node){
   1.221 +	if(level == 0)
   1.222 +		return node;
   1.223 +	Node ret = new Node(edit);
   1.224 +	ret.array[0] = newPath(edit, level - 5, node);
   1.225 +	return ret;
   1.226 +}
   1.227 +
   1.228 +public IChunkedSeq chunkedSeq(){
   1.229 +	if(count() == 0)
   1.230 +		return null;
   1.231 +	return new ChunkedSeq(this,0,0);
   1.232 +}
   1.233 +
   1.234 +public ISeq seq(){
   1.235 +	return chunkedSeq();
   1.236 +}
   1.237 +
   1.238 +static public final class ChunkedSeq extends ASeq implements IChunkedSeq{
   1.239 +
   1.240 +	public final PersistentVector vec;
   1.241 +	final Object[] node;
   1.242 +	final int i;
   1.243 +	public final int offset;
   1.244 +
   1.245 +	public ChunkedSeq(PersistentVector vec, int i, int offset){
   1.246 +		this.vec = vec;
   1.247 +		this.i = i;
   1.248 +		this.offset = offset;
   1.249 +		this.node = vec.arrayFor(i);
   1.250 +	}
   1.251 +
   1.252 +	ChunkedSeq(IPersistentMap meta, PersistentVector vec, Object[] node, int i, int offset){
   1.253 +		super(meta);
   1.254 +		this.vec = vec;
   1.255 +		this.node = node;
   1.256 +		this.i = i;
   1.257 +		this.offset = offset;
   1.258 +	}
   1.259 +
   1.260 +	ChunkedSeq(PersistentVector vec, Object[] node, int i, int offset){
   1.261 +		this.vec = vec;
   1.262 +		this.node = node;
   1.263 +		this.i = i;
   1.264 +		this.offset = offset;
   1.265 +	}
   1.266 +
   1.267 +	public IChunk chunkedFirst() throws Exception{
   1.268 +		return new ArrayChunk(node, offset);
   1.269 +		}
   1.270 +
   1.271 +	public ISeq chunkedNext(){
   1.272 +		if(i + node.length < vec.cnt)
   1.273 +			return new ChunkedSeq(vec,i+ node.length,0);
   1.274 +		return null;
   1.275 +		}
   1.276 +
   1.277 +	public ISeq chunkedMore(){
   1.278 +		ISeq s = chunkedNext();
   1.279 +		if(s == null)
   1.280 +			return PersistentList.EMPTY;
   1.281 +		return s;
   1.282 +	}
   1.283 +
   1.284 +	public Obj withMeta(IPersistentMap meta){
   1.285 +		if(meta == this._meta)
   1.286 +			return this;
   1.287 +		return new ChunkedSeq(meta, vec, node, i, offset);
   1.288 +	}
   1.289 +
   1.290 +	public Object first(){
   1.291 +		return node[offset];
   1.292 +	}
   1.293 +
   1.294 +	public ISeq next(){
   1.295 +		if(offset + 1 < node.length)
   1.296 +			return new ChunkedSeq(vec, node, i, offset + 1);
   1.297 +		return chunkedNext();
   1.298 +	}
   1.299 +}
   1.300 +
   1.301 +public IPersistentCollection empty(){
   1.302 +	return EMPTY.withMeta(meta());
   1.303 +}
   1.304 +
   1.305 +//private Node pushTail(int level, Node node, Object[] tailNode, Box expansion){
   1.306 +//	Object newchild;
   1.307 +//	if(level == 0)
   1.308 +//		{
   1.309 +//		newchild = tailNode;
   1.310 +//		}
   1.311 +//	else
   1.312 +//		{
   1.313 +//		newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
   1.314 +//		if(expansion.val == null)
   1.315 +//			{
   1.316 +//			Object[] ret = arr.clone();
   1.317 +//			ret[arr.length - 1] = newchild;
   1.318 +//			return ret;
   1.319 +//			}
   1.320 +//		else
   1.321 +//			newchild = expansion.val;
   1.322 +//		}
   1.323 +//	//expansion
   1.324 +//	if(arr.length == 32)
   1.325 +//		{
   1.326 +//		expansion.val = new Object[]{newchild};
   1.327 +//		return arr;
   1.328 +//		}
   1.329 +//	Object[] ret = new Object[arr.length + 1];
   1.330 +//	System.arraycopy(arr, 0, ret, 0, arr.length);
   1.331 +//	ret[arr.length] = newchild;
   1.332 +//	expansion.val = null;
   1.333 +//	return ret;
   1.334 +//}
   1.335 +
   1.336 +public PersistentVector pop(){
   1.337 +	if(cnt == 0)
   1.338 +		throw new IllegalStateException("Can't pop empty vector");
   1.339 +	if(cnt == 1)
   1.340 +		return EMPTY.withMeta(meta());
   1.341 +	//if(tail.length > 1)
   1.342 +	if(cnt-tailoff() > 1)
   1.343 +		{
   1.344 +		Object[] newTail = new Object[tail.length - 1];
   1.345 +		System.arraycopy(tail, 0, newTail, 0, newTail.length);
   1.346 +		return new PersistentVector(meta(), cnt - 1, shift, root, newTail);
   1.347 +		}
   1.348 +	Object[] newtail = arrayFor(cnt - 2);
   1.349 +
   1.350 +	Node newroot = popTail(shift, root);
   1.351 +	int newshift = shift;
   1.352 +	if(newroot == null)
   1.353 +		{
   1.354 +		newroot = EMPTY_NODE;
   1.355 +		}
   1.356 +	if(shift > 5 && newroot.array[1] == null)
   1.357 +		{
   1.358 +		newroot = (Node) newroot.array[0];
   1.359 +		newshift -= 5;
   1.360 +		}
   1.361 +	return new PersistentVector(meta(), cnt - 1, newshift, newroot, newtail);
   1.362 +}
   1.363 +
   1.364 +private Node popTail(int level, Node node){
   1.365 +	int subidx = ((cnt-2) >>> level) & 0x01f;
   1.366 +	if(level > 5)
   1.367 +		{
   1.368 +		Node newchild = popTail(level - 5, (Node) node.array[subidx]);
   1.369 +		if(newchild == null && subidx == 0)
   1.370 +			return null;
   1.371 +		else
   1.372 +			{
   1.373 +			Node ret = new Node(root.edit, node.array.clone());
   1.374 +			ret.array[subidx] = newchild;
   1.375 +			return ret;
   1.376 +			}
   1.377 +		}
   1.378 +	else if(subidx == 0)
   1.379 +		return null;
   1.380 +	else
   1.381 +		{
   1.382 +		Node ret = new Node(root.edit, node.array.clone());
   1.383 +		ret.array[subidx] = null;
   1.384 +		return ret;
   1.385 +		}
   1.386 +}
   1.387 +
   1.388 +static final class TransientVector extends AFn implements ITransientVector, Counted{
   1.389 +	int cnt;
   1.390 +	int shift;
   1.391 +	Node root;
   1.392 +	Object[] tail;
   1.393 +
   1.394 +	TransientVector(int cnt, int shift, Node root, Object[] tail){
   1.395 +		this.cnt = cnt;
   1.396 +		this.shift = shift;
   1.397 +		this.root = root;
   1.398 +		this.tail = tail;
   1.399 +	}
   1.400 +
   1.401 +	TransientVector(PersistentVector v){
   1.402 +		this(v.cnt, v.shift, editableRoot(v.root), editableTail(v.tail));
   1.403 +	}
   1.404 +
   1.405 +	public int count(){
   1.406 +		ensureEditable();
   1.407 +		return cnt;
   1.408 +	}
   1.409 +	
   1.410 +	Node ensureEditable(Node node){
   1.411 +		if(node.edit == root.edit)
   1.412 +			return node;
   1.413 +		return new Node(root.edit, node.array.clone());
   1.414 +	}
   1.415 +
   1.416 +	void ensureEditable(){
   1.417 +		Thread owner = root.edit.get();
   1.418 +		if(owner == Thread.currentThread())
   1.419 +			return;
   1.420 +		if(owner != null)
   1.421 +			throw new IllegalAccessError("Transient used by non-owner thread");
   1.422 +		throw new IllegalAccessError("Transient used after persistent! call");
   1.423 +
   1.424 +//		root = editableRoot(root);
   1.425 +//		tail = editableTail(tail);
   1.426 +	}
   1.427 +
   1.428 +	static Node editableRoot(Node node){
   1.429 +		return new Node(new AtomicReference<Thread>(Thread.currentThread()), node.array.clone());
   1.430 +	}
   1.431 +
   1.432 +	public PersistentVector persistent(){
   1.433 +		ensureEditable();
   1.434 +//		Thread owner = root.edit.get();
   1.435 +//		if(owner != null && owner != Thread.currentThread())
   1.436 +//			{
   1.437 +//			throw new IllegalAccessError("Mutation release by non-owner thread");
   1.438 +//			}
   1.439 +		root.edit.set(null);
   1.440 +		Object[] trimmedTail = new Object[cnt-tailoff()];
   1.441 +		System.arraycopy(tail,0,trimmedTail,0,trimmedTail.length);
   1.442 +		return new PersistentVector(cnt, shift, root, trimmedTail);
   1.443 +	}
   1.444 +
   1.445 +	static Object[] editableTail(Object[] tl){
   1.446 +		Object[] ret = new Object[32];
   1.447 +		System.arraycopy(tl,0,ret,0,tl.length);
   1.448 +		return ret;
   1.449 +	}
   1.450 +
   1.451 +	public TransientVector conj(Object val){
   1.452 +		ensureEditable();
   1.453 +		int i = cnt;
   1.454 +		//room in tail?
   1.455 +		if(i - tailoff() < 32)
   1.456 +			{
   1.457 +			tail[i & 0x01f] = val;
   1.458 +			++cnt;
   1.459 +			return this;
   1.460 +			}
   1.461 +		//full tail, push into tree
   1.462 +		Node newroot;
   1.463 +		Node tailnode = new Node(root.edit, tail);
   1.464 +		tail = new Object[32];
   1.465 +		tail[0] = val;
   1.466 +		int newshift = shift;
   1.467 +		//overflow root?
   1.468 +		if((cnt >>> 5) > (1 << shift))
   1.469 +			{
   1.470 +			newroot = new Node(root.edit);
   1.471 +			newroot.array[0] = root;
   1.472 +			newroot.array[1] = newPath(root.edit,shift, tailnode);
   1.473 +			newshift += 5;
   1.474 +			}
   1.475 +		else
   1.476 +			newroot = pushTail(shift, root, tailnode);
   1.477 +		root = newroot;
   1.478 +		shift = newshift;
   1.479 +		++cnt;
   1.480 +		return this;
   1.481 +	}
   1.482 +
   1.483 +	private Node pushTail(int level, Node parent, Node tailnode){
   1.484 +		//if parent is leaf, insert node,
   1.485 +		// else does it map to an existing child? -> nodeToInsert = pushNode one more level
   1.486 +		// else alloc new path
   1.487 +		//return  nodeToInsert placed in parent
   1.488 +		parent = ensureEditable(parent);
   1.489 +		int subidx = ((cnt - 1) >>> level) & 0x01f;
   1.490 +		Node ret = parent;
   1.491 +		Node nodeToInsert;
   1.492 +		if(level == 5)
   1.493 +			{
   1.494 +			nodeToInsert = tailnode;
   1.495 +			}
   1.496 +		else
   1.497 +			{
   1.498 +			Node child = (Node) parent.array[subidx];
   1.499 +			nodeToInsert = (child != null) ?
   1.500 +			               pushTail(level - 5, child, tailnode)
   1.501 +			                               : newPath(root.edit, level - 5, tailnode);
   1.502 +			}
   1.503 +		ret.array[subidx] = nodeToInsert;
   1.504 +		return ret;
   1.505 +	}
   1.506 +
   1.507 +	final private int tailoff(){
   1.508 +		if(cnt < 32)
   1.509 +			return 0;
   1.510 +		return ((cnt-1) >>> 5) << 5;
   1.511 +	}
   1.512 +
   1.513 +	private Object[] arrayFor(int i){
   1.514 +		if(i >= 0 && i < cnt)
   1.515 +			{
   1.516 +			if(i >= tailoff())
   1.517 +				return tail;
   1.518 +			Node node = root;
   1.519 +			for(int level = shift; level > 0; level -= 5)
   1.520 +				node = (Node) node.array[(i >>> level) & 0x01f];
   1.521 +			return node.array;
   1.522 +			}
   1.523 +		throw new IndexOutOfBoundsException();
   1.524 +	}
   1.525 +
   1.526 +	public Object valAt(Object key){
   1.527 +		//note - relies on ensureEditable in 2-arg valAt
   1.528 +		return valAt(key, null);
   1.529 +	}
   1.530 +
   1.531 +	public Object valAt(Object key, Object notFound){
   1.532 +		ensureEditable();
   1.533 +		if(Util.isInteger(key))
   1.534 +			{
   1.535 +			int i = ((Number) key).intValue();
   1.536 +			if(i >= 0 && i < cnt)
   1.537 +				return nth(i);
   1.538 +			}
   1.539 +		return notFound;
   1.540 +	}
   1.541 +
   1.542 +	public Object invoke(Object arg1) throws Exception{
   1.543 +		//note - relies on ensureEditable in nth
   1.544 +		if(Util.isInteger(arg1))
   1.545 +			return nth(((Number) arg1).intValue());
   1.546 +		throw new IllegalArgumentException("Key must be integer");
   1.547 +	}
   1.548 +
   1.549 +	public Object nth(int i){
   1.550 +		ensureEditable();
   1.551 +		Object[] node = arrayFor(i);
   1.552 +		return node[i & 0x01f];
   1.553 +	}
   1.554 +
   1.555 +	public Object nth(int i, Object notFound){
   1.556 +		if(i >= 0 && i < count())
   1.557 +			return nth(i);
   1.558 +		return notFound;
   1.559 +	}
   1.560 +
   1.561 +	public TransientVector assocN(int i, Object val){
   1.562 +		ensureEditable();
   1.563 +		if(i >= 0 && i < cnt)
   1.564 +			{
   1.565 +			if(i >= tailoff())
   1.566 +				{
   1.567 +				tail[i & 0x01f] = val;
   1.568 +				return this;
   1.569 +				}
   1.570 +
   1.571 +			root = doAssoc(shift, root, i, val);
   1.572 +			return this;
   1.573 +			}
   1.574 +		if(i == cnt)
   1.575 +			return conj(val);
   1.576 +		throw new IndexOutOfBoundsException();
   1.577 +	}
   1.578 +
   1.579 +	public TransientVector assoc(Object key, Object val){
   1.580 +		//note - relies on ensureEditable in assocN
   1.581 +		if(Util.isInteger(key))
   1.582 +			{
   1.583 +			int i = ((Number) key).intValue();
   1.584 +			return assocN(i, val);
   1.585 +			}
   1.586 +		throw new IllegalArgumentException("Key must be integer");
   1.587 +	}
   1.588 +
   1.589 +	private Node doAssoc(int level, Node node, int i, Object val){
   1.590 +		node = ensureEditable(node);
   1.591 +		Node ret = node;
   1.592 +		if(level == 0)
   1.593 +			{
   1.594 +			ret.array[i & 0x01f] = val;
   1.595 +			}
   1.596 +		else
   1.597 +			{
   1.598 +			int subidx = (i >>> level) & 0x01f;
   1.599 +			ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
   1.600 +			}
   1.601 +		return ret;
   1.602 +	}
   1.603 +
   1.604 +	public TransientVector pop(){
   1.605 +		ensureEditable();
   1.606 +		if(cnt == 0)
   1.607 +			throw new IllegalStateException("Can't pop empty vector");
   1.608 +		if(cnt == 1)
   1.609 +			{
   1.610 +			cnt = 0;
   1.611 +			return this;
   1.612 +			}
   1.613 +		int i = cnt - 1;
   1.614 +		//pop in tail?
   1.615 +		if((i & 0x01f) > 0)
   1.616 +			{
   1.617 +			--cnt;
   1.618 +			return this;
   1.619 +			}
   1.620 +
   1.621 +		Object[] newtail = arrayFor(cnt - 2);
   1.622 +
   1.623 +		Node newroot = popTail(shift, root);
   1.624 +		int newshift = shift;
   1.625 +		if(newroot == null)
   1.626 +			{
   1.627 +			newroot = new Node(root.edit);
   1.628 +			}
   1.629 +		if(shift > 5 && newroot.array[1] == null)
   1.630 +			{
   1.631 +			newroot = ensureEditable((Node) newroot.array[0]);
   1.632 +			newshift -= 5;
   1.633 +			}
   1.634 +		root = newroot;
   1.635 +		shift = newshift;
   1.636 +		--cnt;
   1.637 +		tail = newtail;
   1.638 +		return this;
   1.639 +	}
   1.640 +
   1.641 +	private Node popTail(int level, Node node){
   1.642 +		node = ensureEditable(node);
   1.643 +		int subidx = ((cnt - 2) >>> level) & 0x01f;
   1.644 +		if(level > 5)
   1.645 +			{
   1.646 +			Node newchild = popTail(level - 5, (Node) node.array[subidx]);
   1.647 +			if(newchild == null && subidx == 0)
   1.648 +				return null;
   1.649 +			else
   1.650 +				{
   1.651 +				Node ret = node;
   1.652 +				ret.array[subidx] = newchild;
   1.653 +				return ret;
   1.654 +				}
   1.655 +			}
   1.656 +		else if(subidx == 0)
   1.657 +			return null;
   1.658 +		else
   1.659 +			{
   1.660 +			Node ret = node;
   1.661 +			ret.array[subidx] = null;
   1.662 +			return ret;
   1.663 +			}
   1.664 +	}
   1.665 +}
   1.666 +/*
   1.667 +static public void main(String[] args){
   1.668 +	if(args.length != 3)
   1.669 +		{
   1.670 +		System.err.println("Usage: PersistentVector size writes reads");
   1.671 +		return;
   1.672 +		}
   1.673 +	int size = Integer.parseInt(args[0]);
   1.674 +	int writes = Integer.parseInt(args[1]);
   1.675 +	int reads = Integer.parseInt(args[2]);
   1.676 +//	Vector v = new Vector(size);
   1.677 +	ArrayList v = new ArrayList(size);
   1.678 +//	v.setSize(size);
   1.679 +	//PersistentArray p = new PersistentArray(size);
   1.680 +	PersistentVector p = PersistentVector.EMPTY;
   1.681 +//	MutableVector mp = p.mutable();
   1.682 +
   1.683 +	for(int i = 0; i < size; i++)
   1.684 +		{
   1.685 +		v.add(i);
   1.686 +//		v.set(i, i);
   1.687 +		//p = p.set(i, 0);
   1.688 +		p = p.cons(i);
   1.689 +//		mp = mp.conj(i);
   1.690 +		}
   1.691 +
   1.692 +	Random rand;
   1.693 +
   1.694 +	rand = new Random(42);
   1.695 +	long tv = 0;
   1.696 +	System.out.println("ArrayList");
   1.697 +	long startTime = System.nanoTime();
   1.698 +	for(int i = 0; i < writes; i++)
   1.699 +		{
   1.700 +		v.set(rand.nextInt(size), i);
   1.701 +		}
   1.702 +	for(int i = 0; i < reads; i++)
   1.703 +		{
   1.704 +		tv += (Integer) v.get(rand.nextInt(size));
   1.705 +		}
   1.706 +	long estimatedTime = System.nanoTime() - startTime;
   1.707 +	System.out.println("time: " + estimatedTime / 1000000);
   1.708 +	System.out.println("PersistentVector");
   1.709 +	rand = new Random(42);
   1.710 +	startTime = System.nanoTime();
   1.711 +	long tp = 0;
   1.712 +
   1.713 +//	PersistentVector oldp = p;
   1.714 +	//Random rand2 = new Random(42);
   1.715 +
   1.716 +	MutableVector mp = p.mutable();
   1.717 +	for(int i = 0; i < writes; i++)
   1.718 +		{
   1.719 +//		p = p.assocN(rand.nextInt(size), i);
   1.720 +		mp = mp.assocN(rand.nextInt(size), i);
   1.721 +//		mp = mp.assoc(rand.nextInt(size), i);
   1.722 +		//dummy set to force perverse branching
   1.723 +		//oldp =	oldp.assocN(rand2.nextInt(size), i);
   1.724 +		}
   1.725 +	for(int i = 0; i < reads; i++)
   1.726 +		{
   1.727 +//		tp += (Integer) p.nth(rand.nextInt(size));
   1.728 +		tp += (Integer) mp.nth(rand.nextInt(size));
   1.729 +		}
   1.730 +//	p = mp.immutable();
   1.731 +	//mp.cons(42);
   1.732 +	estimatedTime = System.nanoTime() - startTime;
   1.733 +	System.out.println("time: " + estimatedTime / 1000000);
   1.734 +	for(int i = 0; i < size / 2; i++)
   1.735 +		{
   1.736 +		mp = mp.pop();
   1.737 +//		p = p.pop();
   1.738 +		v.remove(v.size() - 1);
   1.739 +		}
   1.740 +	p = (PersistentVector) mp.immutable();
   1.741 +	//mp.pop();  //should fail
   1.742 +	for(int i = 0; i < size / 2; i++)
   1.743 +		{
   1.744 +		tp += (Integer) p.nth(i);
   1.745 +		tv += (Integer) v.get(i);
   1.746 +		}
   1.747 +	System.out.println("Done: " + tv + ", " + tp);
   1.748 +
   1.749 +}
   1.750 +//  */
   1.751 +}