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