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