SpinedBuffer.java revision d0a2645e29a9b84d7e5ec822eb9904e93bd6c013
1/* 2 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25package java.util.stream; 26 27import java.util.ArrayList; 28import java.util.Arrays; 29import java.util.Iterator; 30import java.util.List; 31import java.util.Objects; 32import java.util.PrimitiveIterator; 33import java.util.Spliterator; 34import java.util.Spliterators; 35import java.util.function.Consumer; 36import java.util.function.DoubleConsumer; 37import java.util.function.IntConsumer; 38import java.util.function.IntFunction; 39import java.util.function.LongConsumer; 40 41/** 42 * An ordered collection of elements. Elements can be added, but not removed. 43 * Goes through a building phase, during which elements can be added, and a 44 * traversal phase, during which elements can be traversed in order but no 45 * further modifications are possible. 46 * 47 * <p> One or more arrays are used to store elements. The use of a multiple 48 * arrays has better performance characteristics than a single array used by 49 * {@link ArrayList}, as when the capacity of the list needs to be increased 50 * no copying of elements is required. This is usually beneficial in the case 51 * where the results will be traversed a small number of times. 52 * 53 * @param <E> the type of elements in this list 54 * @since 1.8 55 */ 56class SpinedBuffer<E> 57 extends AbstractSpinedBuffer 58 implements Consumer<E>, Iterable<E> { 59 60 /* 61 * We optimistically hope that all the data will fit into the first chunk, 62 * so we try to avoid inflating the spine[] and priorElementCount[] arrays 63 * prematurely. So methods must be prepared to deal with these arrays being 64 * null. If spine is non-null, then spineIndex points to the current chunk 65 * within the spine, otherwise it is zero. The spine and priorElementCount 66 * arrays are always the same size, and for any i <= spineIndex, 67 * priorElementCount[i] is the sum of the sizes of all the prior chunks. 68 * 69 * The curChunk pointer is always valid. The elementIndex is the index of 70 * the next element to be written in curChunk; this may be past the end of 71 * curChunk so we have to check before writing. When we inflate the spine 72 * array, curChunk becomes the first element in it. When we clear the 73 * buffer, we discard all chunks except the first one, which we clear, 74 * restoring it to the initial single-chunk state. 75 */ 76 77 /** 78 * Chunk that we're currently writing into; may or may not be aliased with 79 * the first element of the spine. 80 */ 81 protected E[] curChunk; 82 83 /** 84 * All chunks, or null if there is only one chunk. 85 */ 86 protected E[][] spine; 87 88 /** 89 * Constructs an empty list with the specified initial capacity. 90 * 91 * @param initialCapacity the initial capacity of the list 92 * @throws IllegalArgumentException if the specified initial capacity 93 * is negative 94 */ 95 @SuppressWarnings("unchecked") 96 SpinedBuffer(int initialCapacity) { 97 super(initialCapacity); 98 curChunk = (E[]) new Object[1 << initialChunkPower]; 99 } 100 101 /** 102 * Constructs an empty list with an initial capacity of sixteen. 103 */ 104 @SuppressWarnings("unchecked") 105 SpinedBuffer() { 106 super(); 107 curChunk = (E[]) new Object[1 << initialChunkPower]; 108 } 109 110 /** 111 * Returns the current capacity of the buffer 112 */ 113 protected long capacity() { 114 return (spineIndex == 0) 115 ? curChunk.length 116 : priorElementCount[spineIndex] + spine[spineIndex].length; 117 } 118 119 @SuppressWarnings("unchecked") 120 private void inflateSpine() { 121 if (spine == null) { 122 spine = (E[][]) new Object[MIN_SPINE_SIZE][]; 123 priorElementCount = new long[MIN_SPINE_SIZE]; 124 spine[0] = curChunk; 125 } 126 } 127 128 /** 129 * Ensure that the buffer has at least capacity to hold the target size 130 */ 131 @SuppressWarnings("unchecked") 132 protected final void ensureCapacity(long targetSize) { 133 long capacity = capacity(); 134 if (targetSize > capacity) { 135 inflateSpine(); 136 for (int i=spineIndex+1; targetSize > capacity; i++) { 137 if (i >= spine.length) { 138 int newSpineSize = spine.length * 2; 139 spine = Arrays.copyOf(spine, newSpineSize); 140 priorElementCount = Arrays.copyOf(priorElementCount, newSpineSize); 141 } 142 int nextChunkSize = chunkSize(i); 143 spine[i] = (E[]) new Object[nextChunkSize]; 144 priorElementCount[i] = priorElementCount[i-1] + spine[i-1].length; 145 capacity += nextChunkSize; 146 } 147 } 148 } 149 150 /** 151 * Force the buffer to increase its capacity. 152 */ 153 protected void increaseCapacity() { 154 ensureCapacity(capacity() + 1); 155 } 156 157 /** 158 * Retrieve the element at the specified index. 159 */ 160 public E get(long index) { 161 // @@@ can further optimize by caching last seen spineIndex, 162 // which is going to be right most of the time 163 164 // Casts to int are safe since the spine array index is the index minus 165 // the prior element count from the current spine 166 if (spineIndex == 0) { 167 if (index < elementIndex) 168 return curChunk[((int) index)]; 169 else 170 throw new IndexOutOfBoundsException(Long.toString(index)); 171 } 172 173 if (index >= count()) 174 throw new IndexOutOfBoundsException(Long.toString(index)); 175 176 for (int j=0; j <= spineIndex; j++) 177 if (index < priorElementCount[j] + spine[j].length) 178 return spine[j][((int) (index - priorElementCount[j]))]; 179 180 throw new IndexOutOfBoundsException(Long.toString(index)); 181 } 182 183 /** 184 * Copy the elements, starting at the specified offset, into the specified 185 * array. 186 */ 187 public void copyInto(E[] array, int offset) { 188 long finalOffset = offset + count(); 189 if (finalOffset > array.length || finalOffset < offset) { 190 throw new IndexOutOfBoundsException("does not fit"); 191 } 192 193 if (spineIndex == 0) 194 System.arraycopy(curChunk, 0, array, offset, elementIndex); 195 else { 196 // full chunks 197 for (int i=0; i < spineIndex; i++) { 198 System.arraycopy(spine[i], 0, array, offset, spine[i].length); 199 offset += spine[i].length; 200 } 201 if (elementIndex > 0) 202 System.arraycopy(curChunk, 0, array, offset, elementIndex); 203 } 204 } 205 206 /** 207 * Create a new array using the specified array factory, and copy the 208 * elements into it. 209 */ 210 public E[] asArray(IntFunction<E[]> arrayFactory) { 211 long size = count(); 212 if (size >= Nodes.MAX_ARRAY_SIZE) 213 throw new IllegalArgumentException(Nodes.BAD_SIZE); 214 E[] result = arrayFactory.apply((int) size); 215 copyInto(result, 0); 216 return result; 217 } 218 219 @Override 220 public void clear() { 221 if (spine != null) { 222 curChunk = spine[0]; 223 for (int i=0; i<curChunk.length; i++) 224 curChunk[i] = null; 225 spine = null; 226 priorElementCount = null; 227 } 228 else { 229 for (int i=0; i<elementIndex; i++) 230 curChunk[i] = null; 231 } 232 elementIndex = 0; 233 spineIndex = 0; 234 } 235 236 @Override 237 public Iterator<E> iterator() { 238 return Spliterators.iterator(spliterator()); 239 } 240 241 @Override 242 public void forEach(Consumer<? super E> consumer) { 243 // completed chunks, if any 244 for (int j = 0; j < spineIndex; j++) 245 for (E t : spine[j]) 246 consumer.accept(t); 247 248 // current chunk 249 for (int i=0; i<elementIndex; i++) 250 consumer.accept(curChunk[i]); 251 } 252 253 @Override 254 public void accept(E e) { 255 if (elementIndex == curChunk.length) { 256 inflateSpine(); 257 if (spineIndex+1 >= spine.length || spine[spineIndex+1] == null) 258 increaseCapacity(); 259 elementIndex = 0; 260 ++spineIndex; 261 curChunk = spine[spineIndex]; 262 } 263 curChunk[elementIndex++] = e; 264 } 265 266 @Override 267 public String toString() { 268 List<E> list = new ArrayList<>(); 269 forEach(list::add); 270 return "SpinedBuffer:" + list.toString(); 271 } 272 273 private static final int SPLITERATOR_CHARACTERISTICS 274 = Spliterator.SIZED | Spliterator.ORDERED | Spliterator.SUBSIZED; 275 276 /** 277 * Return a {@link Spliterator} describing the contents of the buffer. 278 */ 279 public Spliterator<E> spliterator() { 280 class Splitr implements Spliterator<E> { 281 // The current spine index 282 int splSpineIndex; 283 284 // Last spine index 285 final int lastSpineIndex; 286 287 // The current element index into the current spine 288 int splElementIndex; 289 290 // Last spine's last element index + 1 291 final int lastSpineElementFence; 292 293 // When splSpineIndex >= lastSpineIndex and 294 // splElementIndex >= lastSpineElementFence then 295 // this spliterator is fully traversed 296 // tryAdvance can set splSpineIndex > spineIndex if the last spine is full 297 298 // The current spine array 299 E[] splChunk; 300 301 Splitr(int firstSpineIndex, int lastSpineIndex, 302 int firstSpineElementIndex, int lastSpineElementFence) { 303 this.splSpineIndex = firstSpineIndex; 304 this.lastSpineIndex = lastSpineIndex; 305 this.splElementIndex = firstSpineElementIndex; 306 this.lastSpineElementFence = lastSpineElementFence; 307 assert spine != null || firstSpineIndex == 0 && lastSpineIndex == 0; 308 splChunk = (spine == null) ? curChunk : spine[firstSpineIndex]; 309 } 310 311 @Override 312 public long estimateSize() { 313 return (splSpineIndex == lastSpineIndex) 314 ? (long) lastSpineElementFence - splElementIndex 315 : // # of elements prior to end - 316 priorElementCount[lastSpineIndex] + lastSpineElementFence - 317 // # of elements prior to current 318 priorElementCount[splSpineIndex] - splElementIndex; 319 } 320 321 @Override 322 public int characteristics() { 323 return SPLITERATOR_CHARACTERISTICS; 324 } 325 326 @Override 327 public boolean tryAdvance(Consumer<? super E> consumer) { 328 Objects.requireNonNull(consumer); 329 330 if (splSpineIndex < lastSpineIndex 331 || (splSpineIndex == lastSpineIndex && splElementIndex < lastSpineElementFence)) { 332 consumer.accept(splChunk[splElementIndex++]); 333 334 if (splElementIndex == splChunk.length) { 335 splElementIndex = 0; 336 ++splSpineIndex; 337 if (spine != null && splSpineIndex <= lastSpineIndex) 338 splChunk = spine[splSpineIndex]; 339 } 340 return true; 341 } 342 return false; 343 } 344 345 @Override 346 public void forEachRemaining(Consumer<? super E> consumer) { 347 Objects.requireNonNull(consumer); 348 349 if (splSpineIndex < lastSpineIndex 350 || (splSpineIndex == lastSpineIndex && splElementIndex < lastSpineElementFence)) { 351 int i = splElementIndex; 352 // completed chunks, if any 353 for (int sp = splSpineIndex; sp < lastSpineIndex; sp++) { 354 E[] chunk = spine[sp]; 355 for (; i < chunk.length; i++) { 356 consumer.accept(chunk[i]); 357 } 358 i = 0; 359 } 360 // last (or current uncompleted) chunk 361 E[] chunk = (splSpineIndex == lastSpineIndex) ? splChunk : spine[lastSpineIndex]; 362 int hElementIndex = lastSpineElementFence; 363 for (; i < hElementIndex; i++) { 364 consumer.accept(chunk[i]); 365 } 366 // mark consumed 367 splSpineIndex = lastSpineIndex; 368 splElementIndex = lastSpineElementFence; 369 } 370 } 371 372 @Override 373 public Spliterator<E> trySplit() { 374 if (splSpineIndex < lastSpineIndex) { 375 // split just before last chunk (if it is full this means 50:50 split) 376 Spliterator<E> ret = new Splitr(splSpineIndex, lastSpineIndex - 1, 377 splElementIndex, spine[lastSpineIndex-1].length); 378 // position to start of last chunk 379 splSpineIndex = lastSpineIndex; 380 splElementIndex = 0; 381 splChunk = spine[splSpineIndex]; 382 return ret; 383 } 384 else if (splSpineIndex == lastSpineIndex) { 385 int t = (lastSpineElementFence - splElementIndex) / 2; 386 if (t == 0) 387 return null; 388 else { 389 Spliterator<E> ret = Arrays.spliterator(splChunk, splElementIndex, splElementIndex + t); 390 splElementIndex += t; 391 return ret; 392 } 393 } 394 else { 395 return null; 396 } 397 } 398 } 399 return new Splitr(0, spineIndex, 0, elementIndex); 400 } 401 402 /** 403 * An ordered collection of primitive values. Elements can be added, but 404 * not removed. Goes through a building phase, during which elements can be 405 * added, and a traversal phase, during which elements can be traversed in 406 * order but no further modifications are possible. 407 * 408 * <p> One or more arrays are used to store elements. The use of a multiple 409 * arrays has better performance characteristics than a single array used by 410 * {@link ArrayList}, as when the capacity of the list needs to be increased 411 * no copying of elements is required. This is usually beneficial in the case 412 * where the results will be traversed a small number of times. 413 * 414 * @param <E> the wrapper type for this primitive type 415 * @paramthe array type for this primitive type 416 * @param the Consumer type for this primitive type 417 */ 418 abstract static class OfPrimitive<E, T_ARR, T_CONS> 419 extends AbstractSpinedBuffer implements Iterable<E> { 420 421 /* 422 * We optimistically hope that all the data will fit into the first chunk, 423 * so we try to avoid inflating the spine[] and priorElementCount[] arrays 424 * prematurely. So methods must be prepared to deal with these arrays being 425 * null. If spine is non-null, then spineIndex points to the current chunk 426 * within the spine, otherwise it is zero. The spine and priorElementCount 427 * arrays are always the same size, and for any i <= spineIndex, 428 * priorElementCount[i] is the sum of the sizes of all the prior chunks. 429 * 430 * The curChunk pointer is always valid. The elementIndex is the index of 431 * the next element to be written in curChunk; this may be past the end of 432 * curChunk so we have to check before writing. When we inflate the spine 433 * array, curChunk becomes the first element in it. When we clear the 434 * buffer, we discard all chunks except the first one, which we clear, 435 * restoring it to the initial single-chunk state. 436 */ 437 438 // The chunk we're currently writing into 439 T_ARR curChunk; 440 441 // All chunks, or null if there is only one chunk 442 T_ARR[] spine; 443 444 /** 445 * Constructs an empty list with the specified initial capacity. 446 * 447 * @param initialCapacity the initial capacity of the list 448 * @throws IllegalArgumentException if the specified initial capacity 449 * is negative 450 */ 451 OfPrimitive(int initialCapacity) { 452 super(initialCapacity); 453 curChunk = newArray(1 << initialChunkPower); 454 } 455 456 /** 457 * Constructs an empty list with an initial capacity of sixteen. 458 */ 459 OfPrimitive() { 460 super(); 461 curChunk = newArray(1 << initialChunkPower); 462 } 463 464 @Override 465 public abstract Iterator<E> iterator(); 466 467 @Override 468 public abstract void forEach(Consumer<? super E> consumer); 469 470 /** Create a new array-of-array of the proper type and size */ 471 protected abstract T_ARR[] newArrayArray(int size); 472 473 /** Create a new array of the proper type and size */ 474 public abstract T_ARR newArray(int size); 475 476 /** Get the length of an array */ 477 protected abstract int arrayLength(T_ARR array); 478 479 /** Iterate an array with the provided consumer */ 480 protected abstract void arrayForEach(T_ARR array, int from, int to, 481 T_CONS consumer); 482 483 protected long capacity() { 484 return (spineIndex == 0) 485 ? arrayLength(curChunk) 486 : priorElementCount[spineIndex] + arrayLength(spine[spineIndex]); 487 } 488 489 private void inflateSpine() { 490 if (spine == null) { 491 spine = newArrayArray(MIN_SPINE_SIZE); 492 priorElementCount = new long[MIN_SPINE_SIZE]; 493 spine[0] = curChunk; 494 } 495 } 496 497 protected final void ensureCapacity(long targetSize) { 498 long capacity = capacity(); 499 if (targetSize > capacity) { 500 inflateSpine(); 501 for (int i=spineIndex+1; targetSize > capacity; i++) { 502 if (i >= spine.length) { 503 int newSpineSize = spine.length * 2; 504 spine = Arrays.copyOf(spine, newSpineSize); 505 priorElementCount = Arrays.copyOf(priorElementCount, newSpineSize); 506 } 507 int nextChunkSize = chunkSize(i); 508 spine[i] = newArray(nextChunkSize); 509 priorElementCount[i] = priorElementCount[i-1] + arrayLength(spine[i - 1]); 510 capacity += nextChunkSize; 511 } 512 } 513 } 514 515 protected void increaseCapacity() { 516 ensureCapacity(capacity() + 1); 517 } 518 519 protected int chunkFor(long index) { 520 if (spineIndex == 0) { 521 if (index < elementIndex) 522 return 0; 523 else 524 throw new IndexOutOfBoundsException(Long.toString(index)); 525 } 526 527 if (index >= count()) 528 throw new IndexOutOfBoundsException(Long.toString(index)); 529 530 for (int j=0; j <= spineIndex; j++) 531 if (index < priorElementCount[j] + arrayLength(spine[j])) 532 return j; 533 534 throw new IndexOutOfBoundsException(Long.toString(index)); 535 } 536 537 public void copyInto(T_ARR array, int offset) { 538 long finalOffset = offset + count(); 539 if (finalOffset > arrayLength(array) || finalOffset < offset) { 540 throw new IndexOutOfBoundsException("does not fit"); 541 } 542 543 if (spineIndex == 0) 544 System.arraycopy(curChunk, 0, array, offset, elementIndex); 545 else { 546 // full chunks 547 for (int i=0; i < spineIndex; i++) { 548 System.arraycopy(spine[i], 0, array, offset, arrayLength(spine[i])); 549 offset += arrayLength(spine[i]); 550 } 551 if (elementIndex > 0) 552 System.arraycopy(curChunk, 0, array, offset, elementIndex); 553 } 554 } 555 556 public T_ARR asPrimitiveArray() { 557 long size = count(); 558 if (size >= Nodes.MAX_ARRAY_SIZE) 559 throw new IllegalArgumentException(Nodes.BAD_SIZE); 560 T_ARR result = newArray((int) size); 561 copyInto(result, 0); 562 return result; 563 } 564 565 protected void preAccept() { 566 if (elementIndex == arrayLength(curChunk)) { 567 inflateSpine(); 568 if (spineIndex+1 >= spine.length || spine[spineIndex+1] == null) 569 increaseCapacity(); 570 elementIndex = 0; 571 ++spineIndex; 572 curChunk = spine[spineIndex]; 573 } 574 } 575 576 public void clear() { 577 if (spine != null) { 578 curChunk = spine[0]; 579 spine = null; 580 priorElementCount = null; 581 } 582 elementIndex = 0; 583 spineIndex = 0; 584 } 585 586 @SuppressWarnings("overloads") 587 public void forEach(T_CONS consumer) { 588 // completed chunks, if any 589 for (int j = 0; j < spineIndex; j++) 590 arrayForEach(spine[j], 0, arrayLength(spine[j]), consumer); 591 592 // current chunk 593 arrayForEach(curChunk, 0, elementIndex, consumer); 594 } 595 596 abstract class BaseSpliterator<T_SPLITR extends Spliterator.OfPrimitive<E, T_CONS, T_SPLITR>> 597 implements Spliterator.OfPrimitive<E, T_CONS, T_SPLITR> { 598 // The current spine index 599 int splSpineIndex; 600 601 // Last spine index 602 final int lastSpineIndex; 603 604 // The current element index into the current spine 605 int splElementIndex; 606 607 // Last spine's last element index + 1 608 final int lastSpineElementFence; 609 610 // When splSpineIndex >= lastSpineIndex and 611 // splElementIndex >= lastSpineElementFence then 612 // this spliterator is fully traversed 613 // tryAdvance can set splSpineIndex > spineIndex if the last spine is full 614 615 // The current spine array 616 T_ARR splChunk; 617 618 BaseSpliterator(int firstSpineIndex, int lastSpineIndex, 619 int firstSpineElementIndex, int lastSpineElementFence) { 620 this.splSpineIndex = firstSpineIndex; 621 this.lastSpineIndex = lastSpineIndex; 622 this.splElementIndex = firstSpineElementIndex; 623 this.lastSpineElementFence = lastSpineElementFence; 624 assert spine != null || firstSpineIndex == 0 && lastSpineIndex == 0; 625 splChunk = (spine == null) ? curChunk : spine[firstSpineIndex]; 626 } 627 628 abstract T_SPLITR newSpliterator(int firstSpineIndex, int lastSpineIndex, 629 int firstSpineElementIndex, int lastSpineElementFence); 630 631 abstract void arrayForOne(T_ARR array, int index, T_CONS consumer); 632 633 abstract T_SPLITR arraySpliterator(T_ARR array, int offset, int len); 634 635 @Override 636 public long estimateSize() { 637 return (splSpineIndex == lastSpineIndex) 638 ? (long) lastSpineElementFence - splElementIndex 639 : // # of elements prior to end - 640 priorElementCount[lastSpineIndex] + lastSpineElementFence - 641 // # of elements prior to current 642 priorElementCount[splSpineIndex] - splElementIndex; 643 } 644 645 @Override 646 public int characteristics() { 647 return SPLITERATOR_CHARACTERISTICS; 648 } 649 650 @Override 651 public boolean tryAdvance(T_CONS consumer) { 652 Objects.requireNonNull(consumer); 653 654 if (splSpineIndex < lastSpineIndex 655 || (splSpineIndex == lastSpineIndex && splElementIndex < lastSpineElementFence)) { 656 arrayForOne(splChunk, splElementIndex++, consumer); 657 658 if (splElementIndex == arrayLength(splChunk)) { 659 splElementIndex = 0; 660 ++splSpineIndex; 661 if (spine != null && splSpineIndex <= lastSpineIndex) 662 splChunk = spine[splSpineIndex]; 663 } 664 return true; 665 } 666 return false; 667 } 668 669 @Override 670 public void forEachRemaining(T_CONS consumer) { 671 Objects.requireNonNull(consumer); 672 673 if (splSpineIndex < lastSpineIndex 674 || (splSpineIndex == lastSpineIndex && splElementIndex < lastSpineElementFence)) { 675 int i = splElementIndex; 676 // completed chunks, if any 677 for (int sp = splSpineIndex; sp < lastSpineIndex; sp++) { 678 T_ARR chunk = spine[sp]; 679 arrayForEach(chunk, i, arrayLength(chunk), consumer); 680 i = 0; 681 } 682 // last (or current uncompleted) chunk 683 T_ARR chunk = (splSpineIndex == lastSpineIndex) ? splChunk : spine[lastSpineIndex]; 684 arrayForEach(chunk, i, lastSpineElementFence, consumer); 685 // mark consumed 686 splSpineIndex = lastSpineIndex; 687 splElementIndex = lastSpineElementFence; 688 } 689 } 690 691 @Override 692 public T_SPLITR trySplit() { 693 if (splSpineIndex < lastSpineIndex) { 694 // split just before last chunk (if it is full this means 50:50 split) 695 T_SPLITR ret = newSpliterator(splSpineIndex, lastSpineIndex - 1, 696 splElementIndex, arrayLength(spine[lastSpineIndex - 1])); 697 // position us to start of last chunk 698 splSpineIndex = lastSpineIndex; 699 splElementIndex = 0; 700 splChunk = spine[splSpineIndex]; 701 return ret; 702 } 703 else if (splSpineIndex == lastSpineIndex) { 704 int t = (lastSpineElementFence - splElementIndex) / 2; 705 if (t == 0) 706 return null; 707 else { 708 T_SPLITR ret = arraySpliterator(splChunk, splElementIndex, t); 709 splElementIndex += t; 710 return ret; 711 } 712 } 713 else { 714 return null; 715 } 716 } 717 } 718 } 719 720 /** 721 * An ordered collection of {@code int} values. 722 */ 723 static class OfInt extends SpinedBuffer.OfPrimitive<Integer, int[], IntConsumer> 724 implements IntConsumer { 725 OfInt() { } 726 727 OfInt(int initialCapacity) { 728 super(initialCapacity); 729 } 730 731 @Override 732 public void forEach(Consumer<? super Integer> consumer) { 733 if (consumer instanceof IntConsumer) { 734 forEach((IntConsumer) consumer); 735 } 736 else { 737 if (Tripwire.ENABLED) 738 Tripwire.trip(getClass(), "{0} calling SpinedBuffer.OfInt.forEach(Consumer)"); 739 spliterator().forEachRemaining(consumer); 740 } 741 } 742 743 @Override 744 protected int[][] newArrayArray(int size) { 745 return new int[size][]; 746 } 747 748 @Override 749 public int[] newArray(int size) { 750 return new int[size]; 751 } 752 753 @Override 754 protected int arrayLength(int[] array) { 755 return array.length; 756 } 757 758 @Override 759 protected void arrayForEach(int[] array, 760 int from, int to, 761 IntConsumer consumer) { 762 for (int i = from; i < to; i++) 763 consumer.accept(array[i]); 764 } 765 766 @Override 767 public void accept(int i) { 768 preAccept(); 769 curChunk[elementIndex++] = i; 770 } 771 772 public int get(long index) { 773 // Casts to int are safe since the spine array index is the index minus 774 // the prior element count from the current spine 775 int ch = chunkFor(index); 776 if (spineIndex == 0 && ch == 0) 777 return curChunk[(int) index]; 778 else 779 return spine[ch][(int) (index - priorElementCount[ch])]; 780 } 781 782 @Override 783 public PrimitiveIterator.OfInt iterator() { 784 return Spliterators.iterator(spliterator()); 785 } 786 787 public Spliterator.OfInt spliterator() { 788 class Splitr extends BaseSpliterator<Spliterator.OfInt> 789 implements Spliterator.OfInt { 790 Splitr(int firstSpineIndex, int lastSpineIndex, 791 int firstSpineElementIndex, int lastSpineElementFence) { 792 super(firstSpineIndex, lastSpineIndex, 793 firstSpineElementIndex, lastSpineElementFence); 794 } 795 796 @Override 797 Splitr newSpliterator(int firstSpineIndex, int lastSpineIndex, 798 int firstSpineElementIndex, int lastSpineElementFence) { 799 return new Splitr(firstSpineIndex, lastSpineIndex, 800 firstSpineElementIndex, lastSpineElementFence); 801 } 802 803 @Override 804 void arrayForOne(int[] array, int index, IntConsumer consumer) { 805 consumer.accept(array[index]); 806 } 807 808 @Override 809 Spliterator.OfInt arraySpliterator(int[] array, int offset, int len) { 810 return Arrays.spliterator(array, offset, offset+len); 811 } 812 } 813 return new Splitr(0, spineIndex, 0, elementIndex); 814 } 815 816 @Override 817 public String toString() { 818 int[] array = asPrimitiveArray(); 819 if (array.length < 200) { 820 return String.format("%s[length=%d, chunks=%d]%s", 821 getClass().getSimpleName(), array.length, 822 spineIndex, Arrays.toString(array)); 823 } 824 else { 825 int[] array2 = Arrays.copyOf(array, 200); 826 return String.format("%s[length=%d, chunks=%d]%s...", 827 getClass().getSimpleName(), array.length, 828 spineIndex, Arrays.toString(array2)); 829 } 830 } 831 } 832 833 /** 834 * An ordered collection of {@code long} values. 835 */ 836 static class OfLong extends SpinedBuffer.OfPrimitive<Long, long[], LongConsumer> 837 implements LongConsumer { 838 OfLong() { } 839 840 OfLong(int initialCapacity) { 841 super(initialCapacity); 842 } 843 844 @Override 845 public void forEach(Consumer<? super Long> consumer) { 846 if (consumer instanceof LongConsumer) { 847 forEach((LongConsumer) consumer); 848 } 849 else { 850 if (Tripwire.ENABLED) 851 Tripwire.trip(getClass(), "{0} calling SpinedBuffer.OfLong.forEach(Consumer)"); 852 spliterator().forEachRemaining(consumer); 853 } 854 } 855 856 @Override 857 protected long[][] newArrayArray(int size) { 858 return new long[size][]; 859 } 860 861 @Override 862 public long[] newArray(int size) { 863 return new long[size]; 864 } 865 866 @Override 867 protected int arrayLength(long[] array) { 868 return array.length; 869 } 870 871 @Override 872 protected void arrayForEach(long[] array, 873 int from, int to, 874 LongConsumer consumer) { 875 for (int i = from; i < to; i++) 876 consumer.accept(array[i]); 877 } 878 879 @Override 880 public void accept(long i) { 881 preAccept(); 882 curChunk[elementIndex++] = i; 883 } 884 885 public long get(long index) { 886 // Casts to int are safe since the spine array index is the index minus 887 // the prior element count from the current spine 888 int ch = chunkFor(index); 889 if (spineIndex == 0 && ch == 0) 890 return curChunk[(int) index]; 891 else 892 return spine[ch][(int) (index - priorElementCount[ch])]; 893 } 894 895 @Override 896 public PrimitiveIterator.OfLong iterator() { 897 return Spliterators.iterator(spliterator()); 898 } 899 900 901 public Spliterator.OfLong spliterator() { 902 class Splitr extends BaseSpliterator<Spliterator.OfLong> 903 implements Spliterator.OfLong { 904 Splitr(int firstSpineIndex, int lastSpineIndex, 905 int firstSpineElementIndex, int lastSpineElementFence) { 906 super(firstSpineIndex, lastSpineIndex, 907 firstSpineElementIndex, lastSpineElementFence); 908 } 909 910 @Override 911 Splitr newSpliterator(int firstSpineIndex, int lastSpineIndex, 912 int firstSpineElementIndex, int lastSpineElementFence) { 913 return new Splitr(firstSpineIndex, lastSpineIndex, 914 firstSpineElementIndex, lastSpineElementFence); 915 } 916 917 @Override 918 void arrayForOne(long[] array, int index, LongConsumer consumer) { 919 consumer.accept(array[index]); 920 } 921 922 @Override 923 Spliterator.OfLong arraySpliterator(long[] array, int offset, int len) { 924 return Arrays.spliterator(array, offset, offset+len); 925 } 926 } 927 return new Splitr(0, spineIndex, 0, elementIndex); 928 } 929 930 @Override 931 public String toString() { 932 long[] array = asPrimitiveArray(); 933 if (array.length < 200) { 934 return String.format("%s[length=%d, chunks=%d]%s", 935 getClass().getSimpleName(), array.length, 936 spineIndex, Arrays.toString(array)); 937 } 938 else { 939 long[] array2 = Arrays.copyOf(array, 200); 940 return String.format("%s[length=%d, chunks=%d]%s...", 941 getClass().getSimpleName(), array.length, 942 spineIndex, Arrays.toString(array2)); 943 } 944 } 945 } 946 947 /** 948 * An ordered collection of {@code double} values. 949 */ 950 static class OfDouble 951 extends SpinedBuffer.OfPrimitive<Double, double[], DoubleConsumer> 952 implements DoubleConsumer { 953 OfDouble() { } 954 955 OfDouble(int initialCapacity) { 956 super(initialCapacity); 957 } 958 959 @Override 960 public void forEach(Consumer<? super Double> consumer) { 961 if (consumer instanceof DoubleConsumer) { 962 forEach((DoubleConsumer) consumer); 963 } 964 else { 965 if (Tripwire.ENABLED) 966 Tripwire.trip(getClass(), "{0} calling SpinedBuffer.OfDouble.forEach(Consumer)"); 967 spliterator().forEachRemaining(consumer); 968 } 969 } 970 971 @Override 972 protected double[][] newArrayArray(int size) { 973 return new double[size][]; 974 } 975 976 @Override 977 public double[] newArray(int size) { 978 return new double[size]; 979 } 980 981 @Override 982 protected int arrayLength(double[] array) { 983 return array.length; 984 } 985 986 @Override 987 protected void arrayForEach(double[] array, 988 int from, int to, 989 DoubleConsumer consumer) { 990 for (int i = from; i < to; i++) 991 consumer.accept(array[i]); 992 } 993 994 @Override 995 public void accept(double i) { 996 preAccept(); 997 curChunk[elementIndex++] = i; 998 } 999 1000 public double get(long index) { 1001 // Casts to int are safe since the spine array index is the index minus 1002 // the prior element count from the current spine 1003 int ch = chunkFor(index); 1004 if (spineIndex == 0 && ch == 0) 1005 return curChunk[(int) index]; 1006 else 1007 return spine[ch][(int) (index - priorElementCount[ch])]; 1008 } 1009 1010 @Override 1011 public PrimitiveIterator.OfDouble iterator() { 1012 return Spliterators.iterator(spliterator()); 1013 } 1014 1015 public Spliterator.OfDouble spliterator() { 1016 class Splitr extends BaseSpliterator<Spliterator.OfDouble> 1017 implements Spliterator.OfDouble { 1018 Splitr(int firstSpineIndex, int lastSpineIndex, 1019 int firstSpineElementIndex, int lastSpineElementFence) { 1020 super(firstSpineIndex, lastSpineIndex, 1021 firstSpineElementIndex, lastSpineElementFence); 1022 } 1023 1024 @Override 1025 Splitr newSpliterator(int firstSpineIndex, int lastSpineIndex, 1026 int firstSpineElementIndex, int lastSpineElementFence) { 1027 return new Splitr(firstSpineIndex, lastSpineIndex, 1028 firstSpineElementIndex, lastSpineElementFence); 1029 } 1030 1031 @Override 1032 void arrayForOne(double[] array, int index, DoubleConsumer consumer) { 1033 consumer.accept(array[index]); 1034 } 1035 1036 @Override 1037 Spliterator.OfDouble arraySpliterator(double[] array, int offset, int len) { 1038 return Arrays.spliterator(array, offset, offset+len); 1039 } 1040 } 1041 return new Splitr(0, spineIndex, 0, elementIndex); 1042 } 1043 1044 @Override 1045 public String toString() { 1046 double[] array = asPrimitiveArray(); 1047 if (array.length < 200) { 1048 return String.format("%s[length=%d, chunks=%d]%s", 1049 getClass().getSimpleName(), array.length, 1050 spineIndex, Arrays.toString(array)); 1051 } 1052 else { 1053 double[] array2 = Arrays.copyOf(array, 200); 1054 return String.format("%s[length=%d, chunks=%d]%s...", 1055 getClass().getSimpleName(), array.length, 1056 spineIndex, Arrays.toString(array2)); 1057 } 1058 } 1059 } 1060} 1061 1062