Mercurial > lasercutter

annotate src/clojure/lang/PersistentVector.java @ 10:ef7dbbd6452c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added clojure source goodness
author Robert McIntyre <rlm@mit.edu>
date Sat, 21 Aug 2010 06:25:44 -0400
parents
children
rev   line source
rlm@10 1 /**
rlm@10 2 * Copyright (c) Rich Hickey. All rights reserved.
rlm@10 3 * The use and distribution terms for this software are covered by the
rlm@10 4 * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
rlm@10 5 * which can be found in the file epl-v10.html at the root of this distribution.
rlm@10 6 * By using this software in any fashion, you are agreeing to be bound by
rlm@10 7 * the terms of this license.
rlm@10 8 * You must not remove this notice, or any other, from this software.
rlm@10 9 **/
rlm@10 10
rlm@10 11 /* rich Jul 5, 2007 */
rlm@10 12
rlm@10 13 package clojure.lang;
rlm@10 14
rlm@10 15 import java.io.Serializable;
rlm@10 16 import java.util.List;
rlm@10 17 import java.util.concurrent.atomic.AtomicReference;
rlm@10 18
rlm@10 19 public class PersistentVector extends APersistentVector implements IObj, IEditableCollection{
rlm@10 20
rlm@10 21 static class Node implements Serializable {
rlm@10 22 transient final AtomicReference<Thread> edit;
rlm@10 23 final Object[] array;
rlm@10 24
rlm@10 25 Node(AtomicReference<Thread> edit, Object[] array){
rlm@10 26 this.edit = edit;
rlm@10 27 this.array = array;
rlm@10 28 }
rlm@10 29
rlm@10 30 Node(AtomicReference<Thread> edit){
rlm@10 31 this.edit = edit;
rlm@10 32 this.array = new Object[32];
rlm@10 33 }
rlm@10 34 }
rlm@10 35
rlm@10 36 final static AtomicReference<Thread> NOEDIT = new AtomicReference<Thread>(null);
rlm@10 37 final static Node EMPTY_NODE = new Node(NOEDIT, new Object[32]);
rlm@10 38
rlm@10 39 final int cnt;
rlm@10 40 final int shift;
rlm@10 41 final Node root;
rlm@10 42 final Object[] tail;
rlm@10 43 final IPersistentMap _meta;
rlm@10 44
rlm@10 45
rlm@10 46 public final static PersistentVector EMPTY = new PersistentVector(0, 5, EMPTY_NODE, new Object[]{});
rlm@10 47
rlm@10 48 static public PersistentVector create(ISeq items){
rlm@10 49 TransientVector ret = EMPTY.asTransient();
rlm@10 50 for(; items != null; items = items.next())
rlm@10 51 ret = ret.conj(items.first());
rlm@10 52 return ret.persistent();
rlm@10 53 }
rlm@10 54
rlm@10 55 static public PersistentVector create(List items){
rlm@10 56 TransientVector ret = EMPTY.asTransient();
rlm@10 57 for(Object item : items)
rlm@10 58 ret = ret.conj(item);
rlm@10 59 return ret.persistent();
rlm@10 60 }
rlm@10 61
rlm@10 62 static public PersistentVector create(Object... items){
rlm@10 63 TransientVector ret = EMPTY.asTransient();
rlm@10 64 for(Object item : items)
rlm@10 65 ret = ret.conj(item);
rlm@10 66 return ret.persistent();
rlm@10 67 }
rlm@10 68
rlm@10 69 PersistentVector(int cnt, int shift, Node root, Object[] tail){
rlm@10 70 this._meta = null;
rlm@10 71 this.cnt = cnt;
rlm@10 72 this.shift = shift;
rlm@10 73 this.root = root;
rlm@10 74 this.tail = tail;
rlm@10 75 }
rlm@10 76
rlm@10 77
rlm@10 78 PersistentVector(IPersistentMap meta, int cnt, int shift, Node root, Object[] tail){
rlm@10 79 this._meta = meta;
rlm@10 80 this.cnt = cnt;
rlm@10 81 this.shift = shift;
rlm@10 82 this.root = root;
rlm@10 83 this.tail = tail;
rlm@10 84 }
rlm@10 85
rlm@10 86 public TransientVector asTransient(){
rlm@10 87 return new TransientVector(this);
rlm@10 88 }
rlm@10 89
rlm@10 90 final int tailoff(){
rlm@10 91 if(cnt < 32)
rlm@10 92 return 0;
rlm@10 93 return ((cnt - 1) >>> 5) << 5;
rlm@10 94 }
rlm@10 95
rlm@10 96 public Object[] arrayFor(int i){
rlm@10 97 if(i >= 0 && i < cnt)
rlm@10 98 {
rlm@10 99 if(i >= tailoff())
rlm@10 100 return tail;
rlm@10 101 Node node = root;
rlm@10 102 for(int level = shift; level > 0; level -= 5)
rlm@10 103 node = (Node) node.array[(i >>> level) & 0x01f];
rlm@10 104 return node.array;
rlm@10 105 }
rlm@10 106 throw new IndexOutOfBoundsException();
rlm@10 107 }
rlm@10 108
rlm@10 109 public Object nth(int i){
rlm@10 110 Object[] node = arrayFor(i);
rlm@10 111 return node[i & 0x01f];
rlm@10 112 }
rlm@10 113
rlm@10 114 public Object nth(int i, Object notFound){
rlm@10 115 if(i >= 0 && i < cnt)
rlm@10 116 return nth(i);
rlm@10 117 return notFound;
rlm@10 118 }
rlm@10 119
rlm@10 120 public PersistentVector assocN(int i, Object val){
rlm@10 121 if(i >= 0 && i < cnt)
rlm@10 122 {
rlm@10 123 if(i >= tailoff())
rlm@10 124 {
rlm@10 125 Object[] newTail = new Object[tail.length];
rlm@10 126 System.arraycopy(tail, 0, newTail, 0, tail.length);
rlm@10 127 newTail[i & 0x01f] = val;
rlm@10 128
rlm@10 129 return new PersistentVector(meta(), cnt, shift, root, newTail);
rlm@10 130 }
rlm@10 131
rlm@10 132 return new PersistentVector(meta(), cnt, shift, doAssoc(shift, root, i, val), tail);
rlm@10 133 }
rlm@10 134 if(i == cnt)
rlm@10 135 return cons(val);
rlm@10 136 throw new IndexOutOfBoundsException();
rlm@10 137 }
rlm@10 138
rlm@10 139 private static Node doAssoc(int level, Node node, int i, Object val){
rlm@10 140 Node ret = new Node(node.edit,node.array.clone());
rlm@10 141 if(level == 0)
rlm@10 142 {
rlm@10 143 ret.array[i & 0x01f] = val;
rlm@10 144 }
rlm@10 145 else
rlm@10 146 {
rlm@10 147 int subidx = (i >>> level) & 0x01f;
rlm@10 148 ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
rlm@10 149 }
rlm@10 150 return ret;
rlm@10 151 }
rlm@10 152
rlm@10 153 public int count(){
rlm@10 154 return cnt;
rlm@10 155 }
rlm@10 156
rlm@10 157 public PersistentVector withMeta(IPersistentMap meta){
rlm@10 158 return new PersistentVector(meta, cnt, shift, root, tail);
rlm@10 159 }
rlm@10 160
rlm@10 161 public IPersistentMap meta(){
rlm@10 162 return _meta;
rlm@10 163 }
rlm@10 164
rlm@10 165
rlm@10 166 public PersistentVector cons(Object val){
rlm@10 167 int i = cnt;
rlm@10 168 //room in tail?
rlm@10 169 // if(tail.length < 32)
rlm@10 170 if(cnt - tailoff() < 32)
rlm@10 171 {
rlm@10 172 Object[] newTail = new Object[tail.length + 1];
rlm@10 173 System.arraycopy(tail, 0, newTail, 0, tail.length);
rlm@10 174 newTail[tail.length] = val;
rlm@10 175 return new PersistentVector(meta(), cnt + 1, shift, root, newTail);
rlm@10 176 }
rlm@10 177 //full tail, push into tree
rlm@10 178 Node newroot;
rlm@10 179 Node tailnode = new Node(root.edit,tail);
rlm@10 180 int newshift = shift;
rlm@10 181 //overflow root?
rlm@10 182 if((cnt >>> 5) > (1 << shift))
rlm@10 183 {
rlm@10 184 newroot = new Node(root.edit);
rlm@10 185 newroot.array[0] = root;
rlm@10 186 newroot.array[1] = newPath(root.edit,shift, tailnode);
rlm@10 187 newshift += 5;
rlm@10 188 }
rlm@10 189 else
rlm@10 190 newroot = pushTail(shift, root, tailnode);
rlm@10 191 return new PersistentVector(meta(), cnt + 1, newshift, newroot, new Object[]{val});
rlm@10 192 }
rlm@10 193
rlm@10 194 private Node pushTail(int level, Node parent, Node tailnode){
rlm@10 195 //if parent is leaf, insert node,
rlm@10 196 // else does it map to an existing child? -> nodeToInsert = pushNode one more level
rlm@10 197 // else alloc new path
rlm@10 198 //return nodeToInsert placed in copy of parent
rlm@10 199 int subidx = ((cnt - 1) >>> level) & 0x01f;
rlm@10 200 Node ret = new Node(parent.edit, parent.array.clone());
rlm@10 201 Node nodeToInsert;
rlm@10 202 if(level == 5)
rlm@10 203 {
rlm@10 204 nodeToInsert = tailnode;
rlm@10 205 }
rlm@10 206 else
rlm@10 207 {
rlm@10 208 Node child = (Node) parent.array[subidx];
rlm@10 209 nodeToInsert = (child != null)?
rlm@10 210 pushTail(level-5,child, tailnode)
rlm@10 211 :newPath(root.edit,level-5, tailnode);
rlm@10 212 }
rlm@10 213 ret.array[subidx] = nodeToInsert;
rlm@10 214 return ret;
rlm@10 215 }
rlm@10 216
rlm@10 217 private static Node newPath(AtomicReference<Thread> edit,int level, Node node){
rlm@10 218 if(level == 0)
rlm@10 219 return node;
rlm@10 220 Node ret = new Node(edit);
rlm@10 221 ret.array[0] = newPath(edit, level - 5, node);
rlm@10 222 return ret;
rlm@10 223 }
rlm@10 224
rlm@10 225 public IChunkedSeq chunkedSeq(){
rlm@10 226 if(count() == 0)
rlm@10 227 return null;
rlm@10 228 return new ChunkedSeq(this,0,0);
rlm@10 229 }
rlm@10 230
rlm@10 231 public ISeq seq(){
rlm@10 232 return chunkedSeq();
rlm@10 233 }
rlm@10 234
rlm@10 235 static public final class ChunkedSeq extends ASeq implements IChunkedSeq{
rlm@10 236
rlm@10 237 public final PersistentVector vec;
rlm@10 238 final Object[] node;
rlm@10 239 final int i;
rlm@10 240 public final int offset;
rlm@10 241
rlm@10 242 public ChunkedSeq(PersistentVector vec, int i, int offset){
rlm@10 243 this.vec = vec;
rlm@10 244 this.i = i;
rlm@10 245 this.offset = offset;
rlm@10 246 this.node = vec.arrayFor(i);
rlm@10 247 }
rlm@10 248
rlm@10 249 ChunkedSeq(IPersistentMap meta, PersistentVector vec, Object[] node, int i, int offset){
rlm@10 250 super(meta);
rlm@10 251 this.vec = vec;
rlm@10 252 this.node = node;
rlm@10 253 this.i = i;
rlm@10 254 this.offset = offset;
rlm@10 255 }
rlm@10 256
rlm@10 257 ChunkedSeq(PersistentVector vec, Object[] node, int i, int offset){
rlm@10 258 this.vec = vec;
rlm@10 259 this.node = node;
rlm@10 260 this.i = i;
rlm@10 261 this.offset = offset;
rlm@10 262 }
rlm@10 263
rlm@10 264 public IChunk chunkedFirst() throws Exception{
rlm@10 265 return new ArrayChunk(node, offset);
rlm@10 266 }
rlm@10 267
rlm@10 268 public ISeq chunkedNext(){
rlm@10 269 if(i + node.length < vec.cnt)
rlm@10 270 return new ChunkedSeq(vec,i+ node.length,0);
rlm@10 271 return null;
rlm@10 272 }
rlm@10 273
rlm@10 274 public ISeq chunkedMore(){
rlm@10 275 ISeq s = chunkedNext();
rlm@10 276 if(s == null)
rlm@10 277 return PersistentList.EMPTY;
rlm@10 278 return s;
rlm@10 279 }
rlm@10 280
rlm@10 281 public Obj withMeta(IPersistentMap meta){
rlm@10 282 if(meta == this._meta)
rlm@10 283 return this;
rlm@10 284 return new ChunkedSeq(meta, vec, node, i, offset);
rlm@10 285 }
rlm@10 286
rlm@10 287 public Object first(){
rlm@10 288 return node[offset];
rlm@10 289 }
rlm@10 290
rlm@10 291 public ISeq next(){
rlm@10 292 if(offset + 1 < node.length)
rlm@10 293 return new ChunkedSeq(vec, node, i, offset + 1);
rlm@10 294 return chunkedNext();
rlm@10 295 }
rlm@10 296 }
rlm@10 297
rlm@10 298 public IPersistentCollection empty(){
rlm@10 299 return EMPTY.withMeta(meta());
rlm@10 300 }
rlm@10 301
rlm@10 302 //private Node pushTail(int level, Node node, Object[] tailNode, Box expansion){
rlm@10 303 // Object newchild;
rlm@10 304 // if(level == 0)
rlm@10 305 // {
rlm@10 306 // newchild = tailNode;
rlm@10 307 // }
rlm@10 308 // else
rlm@10 309 // {
rlm@10 310 // newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
rlm@10 311 // if(expansion.val == null)
rlm@10 312 // {
rlm@10 313 // Object[] ret = arr.clone();
rlm@10 314 // ret[arr.length - 1] = newchild;
rlm@10 315 // return ret;
rlm@10 316 // }
rlm@10 317 // else
rlm@10 318 // newchild = expansion.val;
rlm@10 319 // }
rlm@10 320 // //expansion
rlm@10 321 // if(arr.length == 32)
rlm@10 322 // {
rlm@10 323 // expansion.val = new Object[]{newchild};
rlm@10 324 // return arr;
rlm@10 325 // }
rlm@10 326 // Object[] ret = new Object[arr.length + 1];
rlm@10 327 // System.arraycopy(arr, 0, ret, 0, arr.length);
rlm@10 328 // ret[arr.length] = newchild;
rlm@10 329 // expansion.val = null;
rlm@10 330 // return ret;
rlm@10 331 //}
rlm@10 332
rlm@10 333 public PersistentVector pop(){
rlm@10 334 if(cnt == 0)
rlm@10 335 throw new IllegalStateException("Can't pop empty vector");
rlm@10 336 if(cnt == 1)
rlm@10 337 return EMPTY.withMeta(meta());
rlm@10 338 //if(tail.length > 1)
rlm@10 339 if(cnt-tailoff() > 1)
rlm@10 340 {
rlm@10 341 Object[] newTail = new Object[tail.length - 1];
rlm@10 342 System.arraycopy(tail, 0, newTail, 0, newTail.length);
rlm@10 343 return new PersistentVector(meta(), cnt - 1, shift, root, newTail);
rlm@10 344 }
rlm@10 345 Object[] newtail = arrayFor(cnt - 2);
rlm@10 346
rlm@10 347 Node newroot = popTail(shift, root);
rlm@10 348 int newshift = shift;
rlm@10 349 if(newroot == null)
rlm@10 350 {
rlm@10 351 newroot = EMPTY_NODE;
rlm@10 352 }
rlm@10 353 if(shift > 5 && newroot.array[1] == null)
rlm@10 354 {
rlm@10 355 newroot = (Node) newroot.array[0];
rlm@10 356 newshift -= 5;
rlm@10 357 }
rlm@10 358 return new PersistentVector(meta(), cnt - 1, newshift, newroot, newtail);
rlm@10 359 }
rlm@10 360
rlm@10 361 private Node popTail(int level, Node node){
rlm@10 362 int subidx = ((cnt-2) >>> level) & 0x01f;
rlm@10 363 if(level > 5)
rlm@10 364 {
rlm@10 365 Node newchild = popTail(level - 5, (Node) node.array[subidx]);
rlm@10 366 if(newchild == null && subidx == 0)
rlm@10 367 return null;
rlm@10 368 else
rlm@10 369 {
rlm@10 370 Node ret = new Node(root.edit, node.array.clone());
rlm@10 371 ret.array[subidx] = newchild;
rlm@10 372 return ret;
rlm@10 373 }
rlm@10 374 }
rlm@10 375 else if(subidx == 0)
rlm@10 376 return null;
rlm@10 377 else
rlm@10 378 {
rlm@10 379 Node ret = new Node(root.edit, node.array.clone());
rlm@10 380 ret.array[subidx] = null;
rlm@10 381 return ret;
rlm@10 382 }
rlm@10 383 }
rlm@10 384
rlm@10 385 static final class TransientVector extends AFn implements ITransientVector, Counted{
rlm@10 386 int cnt;
rlm@10 387 int shift;
rlm@10 388 Node root;
rlm@10 389 Object[] tail;
rlm@10 390
rlm@10 391 TransientVector(int cnt, int shift, Node root, Object[] tail){
rlm@10 392 this.cnt = cnt;
rlm@10 393 this.shift = shift;
rlm@10 394 this.root = root;
rlm@10 395 this.tail = tail;
rlm@10 396 }
rlm@10 397
rlm@10 398 TransientVector(PersistentVector v){
rlm@10 399 this(v.cnt, v.shift, editableRoot(v.root), editableTail(v.tail));
rlm@10 400 }
rlm@10 401
rlm@10 402 public int count(){
rlm@10 403 ensureEditable();
rlm@10 404 return cnt;
rlm@10 405 }
rlm@10 406
rlm@10 407 Node ensureEditable(Node node){
rlm@10 408 if(node.edit == root.edit)
rlm@10 409 return node;
rlm@10 410 return new Node(root.edit, node.array.clone());
rlm@10 411 }
rlm@10 412
rlm@10 413 void ensureEditable(){
rlm@10 414 Thread owner = root.edit.get();
rlm@10 415 if(owner == Thread.currentThread())
rlm@10 416 return;
rlm@10 417 if(owner != null)
rlm@10 418 throw new IllegalAccessError("Transient used by non-owner thread");
rlm@10 419 throw new IllegalAccessError("Transient used after persistent! call");
rlm@10 420
rlm@10 421 // root = editableRoot(root);
rlm@10 422 // tail = editableTail(tail);
rlm@10 423 }
rlm@10 424
rlm@10 425 static Node editableRoot(Node node){
rlm@10 426 return new Node(new AtomicReference<Thread>(Thread.currentThread()), node.array.clone());
rlm@10 427 }
rlm@10 428
rlm@10 429 public PersistentVector persistent(){
rlm@10 430 ensureEditable();
rlm@10 431 // Thread owner = root.edit.get();
rlm@10 432 // if(owner != null && owner != Thread.currentThread())
rlm@10 433 // {
rlm@10 434 // throw new IllegalAccessError("Mutation release by non-owner thread");
rlm@10 435 // }
rlm@10 436 root.edit.set(null);
rlm@10 437 Object[] trimmedTail = new Object[cnt-tailoff()];
rlm@10 438 System.arraycopy(tail,0,trimmedTail,0,trimmedTail.length);
rlm@10 439 return new PersistentVector(cnt, shift, root, trimmedTail);
rlm@10 440 }
rlm@10 441
rlm@10 442 static Object[] editableTail(Object[] tl){
rlm@10 443 Object[] ret = new Object[32];
rlm@10 444 System.arraycopy(tl,0,ret,0,tl.length);
rlm@10 445 return ret;
rlm@10 446 }
rlm@10 447
rlm@10 448 public TransientVector conj(Object val){
rlm@10 449 ensureEditable();
rlm@10 450 int i = cnt;
rlm@10 451 //room in tail?
rlm@10 452 if(i - tailoff() < 32)
rlm@10 453 {
rlm@10 454 tail[i & 0x01f] = val;
rlm@10 455 ++cnt;
rlm@10 456 return this;
rlm@10 457 }
rlm@10 458 //full tail, push into tree
rlm@10 459 Node newroot;
rlm@10 460 Node tailnode = new Node(root.edit, tail);
rlm@10 461 tail = new Object[32];
rlm@10 462 tail[0] = val;
rlm@10 463 int newshift = shift;
rlm@10 464 //overflow root?
rlm@10 465 if((cnt >>> 5) > (1 << shift))
rlm@10 466 {
rlm@10 467 newroot = new Node(root.edit);
rlm@10 468 newroot.array[0] = root;
rlm@10 469 newroot.array[1] = newPath(root.edit,shift, tailnode);
rlm@10 470 newshift += 5;
rlm@10 471 }
rlm@10 472 else
rlm@10 473 newroot = pushTail(shift, root, tailnode);
rlm@10 474 root = newroot;
rlm@10 475 shift = newshift;
rlm@10 476 ++cnt;
rlm@10 477 return this;
rlm@10 478 }
rlm@10 479
rlm@10 480 private Node pushTail(int level, Node parent, Node tailnode){
rlm@10 481 //if parent is leaf, insert node,
rlm@10 482 // else does it map to an existing child? -> nodeToInsert = pushNode one more level
rlm@10 483 // else alloc new path
rlm@10 484 //return nodeToInsert placed in parent
rlm@10 485 parent = ensureEditable(parent);
rlm@10 486 int subidx = ((cnt - 1) >>> level) & 0x01f;
rlm@10 487 Node ret = parent;
rlm@10 488 Node nodeToInsert;
rlm@10 489 if(level == 5)
rlm@10 490 {
rlm@10 491 nodeToInsert = tailnode;
rlm@10 492 }
rlm@10 493 else
rlm@10 494 {
rlm@10 495 Node child = (Node) parent.array[subidx];
rlm@10 496 nodeToInsert = (child != null) ?
rlm@10 497 pushTail(level - 5, child, tailnode)
rlm@10 498 : newPath(root.edit, level - 5, tailnode);
rlm@10 499 }
rlm@10 500 ret.array[subidx] = nodeToInsert;
rlm@10 501 return ret;
rlm@10 502 }
rlm@10 503
rlm@10 504 final private int tailoff(){
rlm@10 505 if(cnt < 32)
rlm@10 506 return 0;
rlm@10 507 return ((cnt-1) >>> 5) << 5;
rlm@10 508 }
rlm@10 509
rlm@10 510 private Object[] arrayFor(int i){
rlm@10 511 if(i >= 0 && i < cnt)
rlm@10 512 {
rlm@10 513 if(i >= tailoff())
rlm@10 514 return tail;
rlm@10 515 Node node = root;
rlm@10 516 for(int level = shift; level > 0; level -= 5)
rlm@10 517 node = (Node) node.array[(i >>> level) & 0x01f];
rlm@10 518 return node.array;
rlm@10 519 }
rlm@10 520 throw new IndexOutOfBoundsException();
rlm@10 521 }
rlm@10 522
rlm@10 523 public Object valAt(Object key){
rlm@10 524 //note - relies on ensureEditable in 2-arg valAt
rlm@10 525 return valAt(key, null);
rlm@10 526 }
rlm@10 527
rlm@10 528 public Object valAt(Object key, Object notFound){
rlm@10 529 ensureEditable();
rlm@10 530 if(Util.isInteger(key))
rlm@10 531 {
rlm@10 532 int i = ((Number) key).intValue();
rlm@10 533 if(i >= 0 && i < cnt)
rlm@10 534 return nth(i);
rlm@10 535 }
rlm@10 536 return notFound;
rlm@10 537 }
rlm@10 538
rlm@10 539 public Object invoke(Object arg1) throws Exception{
rlm@10 540 //note - relies on ensureEditable in nth
rlm@10 541 if(Util.isInteger(arg1))
rlm@10 542 return nth(((Number) arg1).intValue());
rlm@10 543 throw new IllegalArgumentException("Key must be integer");
rlm@10 544 }
rlm@10 545
rlm@10 546 public Object nth(int i){
rlm@10 547 ensureEditable();
rlm@10 548 Object[] node = arrayFor(i);
rlm@10 549 return node[i & 0x01f];
rlm@10 550 }
rlm@10 551
rlm@10 552 public Object nth(int i, Object notFound){
rlm@10 553 if(i >= 0 && i < count())
rlm@10 554 return nth(i);
rlm@10 555 return notFound;
rlm@10 556 }
rlm@10 557
rlm@10 558 public TransientVector assocN(int i, Object val){
rlm@10 559 ensureEditable();
rlm@10 560 if(i >= 0 && i < cnt)
rlm@10 561 {
rlm@10 562 if(i >= tailoff())
rlm@10 563 {
rlm@10 564 tail[i & 0x01f] = val;
rlm@10 565 return this;
rlm@10 566 }
rlm@10 567
rlm@10 568 root = doAssoc(shift, root, i, val);
rlm@10 569 return this;
rlm@10 570 }
rlm@10 571 if(i == cnt)
rlm@10 572 return conj(val);
rlm@10 573 throw new IndexOutOfBoundsException();
rlm@10 574 }
rlm@10 575
rlm@10 576 public TransientVector assoc(Object key, Object val){
rlm@10 577 //note - relies on ensureEditable in assocN
rlm@10 578 if(Util.isInteger(key))
rlm@10 579 {
rlm@10 580 int i = ((Number) key).intValue();
rlm@10 581 return assocN(i, val);
rlm@10 582 }
rlm@10 583 throw new IllegalArgumentException("Key must be integer");
rlm@10 584 }
rlm@10 585
rlm@10 586 private Node doAssoc(int level, Node node, int i, Object val){
rlm@10 587 node = ensureEditable(node);
rlm@10 588 Node ret = node;
rlm@10 589 if(level == 0)
rlm@10 590 {
rlm@10 591 ret.array[i & 0x01f] = val;
rlm@10 592 }
rlm@10 593 else
rlm@10 594 {
rlm@10 595 int subidx = (i >>> level) & 0x01f;
rlm@10 596 ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
rlm@10 597 }
rlm@10 598 return ret;
rlm@10 599 }
rlm@10 600
rlm@10 601 public TransientVector pop(){
rlm@10 602 ensureEditable();
rlm@10 603 if(cnt == 0)
rlm@10 604 throw new IllegalStateException("Can't pop empty vector");
rlm@10 605 if(cnt == 1)
rlm@10 606 {
rlm@10 607 cnt = 0;
rlm@10 608 return this;
rlm@10 609 }
rlm@10 610 int i = cnt - 1;
rlm@10 611 //pop in tail?
rlm@10 612 if((i & 0x01f) > 0)
rlm@10 613 {
rlm@10 614 --cnt;
rlm@10 615 return this;
rlm@10 616 }
rlm@10 617
rlm@10 618 Object[] newtail = arrayFor(cnt - 2);
rlm@10 619
rlm@10 620 Node newroot = popTail(shift, root);
rlm@10 621 int newshift = shift;
rlm@10 622 if(newroot == null)
rlm@10 623 {
rlm@10 624 newroot = new Node(root.edit);
rlm@10 625 }
rlm@10 626 if(shift > 5 && newroot.array[1] == null)
rlm@10 627 {
rlm@10 628 newroot = ensureEditable((Node) newroot.array[0]);
rlm@10 629 newshift -= 5;
rlm@10 630 }
rlm@10 631 root = newroot;
rlm@10 632 shift = newshift;
rlm@10 633 --cnt;
rlm@10 634 tail = newtail;
rlm@10 635 return this;
rlm@10 636 }
rlm@10 637
rlm@10 638 private Node popTail(int level, Node node){
rlm@10 639 node = ensureEditable(node);
rlm@10 640 int subidx = ((cnt - 2) >>> level) & 0x01f;
rlm@10 641 if(level > 5)
rlm@10 642 {
rlm@10 643 Node newchild = popTail(level - 5, (Node) node.array[subidx]);
rlm@10 644 if(newchild == null && subidx == 0)
rlm@10 645 return null;
rlm@10 646 else
rlm@10 647 {
rlm@10 648 Node ret = node;
rlm@10 649 ret.array[subidx] = newchild;
rlm@10 650 return ret;
rlm@10 651 }
rlm@10 652 }
rlm@10 653 else if(subidx == 0)
rlm@10 654 return null;
rlm@10 655 else
rlm@10 656 {
rlm@10 657 Node ret = node;
rlm@10 658 ret.array[subidx] = null;
rlm@10 659 return ret;
rlm@10 660 }
rlm@10 661 }
rlm@10 662 }
rlm@10 663 /*
rlm@10 664 static public void main(String[] args){
rlm@10 665 if(args.length != 3)
rlm@10 666 {
rlm@10 667 System.err.println("Usage: PersistentVector size writes reads");
rlm@10 668 return;
rlm@10 669 }
rlm@10 670 int size = Integer.parseInt(args[0]);
rlm@10 671 int writes = Integer.parseInt(args[1]);
rlm@10 672 int reads = Integer.parseInt(args[2]);
rlm@10 673 // Vector v = new Vector(size);
rlm@10 674 ArrayList v = new ArrayList(size);
rlm@10 675 // v.setSize(size);
rlm@10 676 //PersistentArray p = new PersistentArray(size);
rlm@10 677 PersistentVector p = PersistentVector.EMPTY;
rlm@10 678 // MutableVector mp = p.mutable();
rlm@10 679
rlm@10 680 for(int i = 0; i < size; i++)
rlm@10 681 {
rlm@10 682 v.add(i);
rlm@10 683 // v.set(i, i);
rlm@10 684 //p = p.set(i, 0);
rlm@10 685 p = p.cons(i);
rlm@10 686 // mp = mp.conj(i);
rlm@10 687 }
rlm@10 688
rlm@10 689 Random rand;
rlm@10 690
rlm@10 691 rand = new Random(42);
rlm@10 692 long tv = 0;
rlm@10 693 System.out.println("ArrayList");
rlm@10 694 long startTime = System.nanoTime();
rlm@10 695 for(int i = 0; i < writes; i++)
rlm@10 696 {
rlm@10 697 v.set(rand.nextInt(size), i);
rlm@10 698 }
rlm@10 699 for(int i = 0; i < reads; i++)
rlm@10 700 {
rlm@10 701 tv += (Integer) v.get(rand.nextInt(size));
rlm@10 702 }
rlm@10 703 long estimatedTime = System.nanoTime() - startTime;
rlm@10 704 System.out.println("time: " + estimatedTime / 1000000);
rlm@10 705 System.out.println("PersistentVector");
rlm@10 706 rand = new Random(42);
rlm@10 707 startTime = System.nanoTime();
rlm@10 708 long tp = 0;
rlm@10 709
rlm@10 710 // PersistentVector oldp = p;
rlm@10 711 //Random rand2 = new Random(42);
rlm@10 712
rlm@10 713 MutableVector mp = p.mutable();
rlm@10 714 for(int i = 0; i < writes; i++)
rlm@10 715 {
rlm@10 716 // p = p.assocN(rand.nextInt(size), i);
rlm@10 717 mp = mp.assocN(rand.nextInt(size), i);
rlm@10 718 // mp = mp.assoc(rand.nextInt(size), i);
rlm@10 719 //dummy set to force perverse branching
rlm@10 720 //oldp = oldp.assocN(rand2.nextInt(size), i);
rlm@10 721 }
rlm@10 722 for(int i = 0; i < reads; i++)
rlm@10 723 {
rlm@10 724 // tp += (Integer) p.nth(rand.nextInt(size));
rlm@10 725 tp += (Integer) mp.nth(rand.nextInt(size));
rlm@10 726 }
rlm@10 727 // p = mp.immutable();
rlm@10 728 //mp.cons(42);
rlm@10 729 estimatedTime = System.nanoTime() - startTime;
rlm@10 730 System.out.println("time: " + estimatedTime / 1000000);
rlm@10 731 for(int i = 0; i < size / 2; i++)
rlm@10 732 {
rlm@10 733 mp = mp.pop();
rlm@10 734 // p = p.pop();
rlm@10 735 v.remove(v.size() - 1);
rlm@10 736 }
rlm@10 737 p = (PersistentVector) mp.immutable();
rlm@10 738 //mp.pop(); //should fail
rlm@10 739 for(int i = 0; i < size / 2; i++)
rlm@10 740 {
rlm@10 741 tp += (Integer) p.nth(i);
rlm@10 742 tv += (Integer) v.get(i);
rlm@10 743 }
rlm@10 744 System.out.println("Done: " + tv + ", " + tp);
rlm@10 745
rlm@10 746 }
rlm@10 747 // */
rlm@10 748 }