001/* 002 * Copyright (C) 2017 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.primitives; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019 020import com.google.common.annotations.Beta; 021import com.google.common.annotations.GwtCompatible; 022import com.google.common.base.Preconditions; 023import com.google.errorprone.annotations.CanIgnoreReturnValue; 024import com.google.errorprone.annotations.CheckReturnValue; 025import com.google.errorprone.annotations.Immutable; 026import java.io.Serializable; 027import java.util.AbstractList; 028import java.util.Arrays; 029import java.util.Collection; 030import java.util.List; 031import java.util.RandomAccess; 032import java.util.Spliterator; 033import java.util.Spliterators; 034import java.util.function.LongConsumer; 035import java.util.stream.LongStream; 036import org.checkerframework.checker.nullness.qual.Nullable; 037 038/** 039 * An immutable array of {@code long} values, with an API resembling {@link List}. 040 * 041 * <p>Advantages compared to {@code long[]}: 042 * 043 * <ul> 044 * <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, third 045 * edition, Item 17). 046 * <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link 047 * #toString} behavior you expect. 048 * <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to 049 * hunt through classes like {@link Arrays} and {@link Longs} for them. 050 * <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to 051 * add overloads that accept start and end indexes. 052 * <li>Can be streamed without "breaking the chain": {@code foo.getBarLongs().stream()...}. 053 * <li>Access to all collection-based utilities via {@link #asList} (though at the cost of 054 * allocating garbage). 055 * </ul> 056 * 057 * <p>Disadvantages compared to {@code long[]}: 058 * 059 * <ul> 060 * <li>Memory footprint has a fixed overhead (about 24 bytes per instance). 061 * <li><i>Some</i> construction use cases force the data to be copied (though several construction 062 * APIs are offered that don't). 063 * <li>Can't be passed directly to methods that expect {@code long[]} (though the most common 064 * utilities do have replacements here). 065 * <li>Dependency on {@code com.google.common} / Guava. 066 * </ul> 067 * 068 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code 069 * <Long>}: 070 * 071 * <ul> 072 * <li>Improved memory compactness and locality. 073 * <li>Can be queried without allocating garbage. 074 * <li>Access to {@code LongStream} features (like {@link LongStream#sum}) using {@code stream()} 075 * instead of the awkward {@code stream().mapToLong(v -> v)}. 076 * </ul> 077 * 078 * <p>Disadvantages compared to {@code ImmutableList<Long>}: 079 * 080 * <ul> 081 * <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or 082 * {@code List} (though the most common utilities do have replacements here, and there is a 083 * lazy {@link #asList} view). 084 * </ul> 085 * 086 * @since 22.0 087 */ 088@Beta 089@GwtCompatible 090@Immutable 091public final class ImmutableLongArray implements Serializable { 092 private static final ImmutableLongArray EMPTY = new ImmutableLongArray(new long[0]); 093 094 /** Returns the empty array. */ 095 public static ImmutableLongArray of() { 096 return EMPTY; 097 } 098 099 /** Returns an immutable array containing a single value. */ 100 public static ImmutableLongArray of(long e0) { 101 return new ImmutableLongArray(new long[] {e0}); 102 } 103 104 /** Returns an immutable array containing the given values, in order. */ 105 public static ImmutableLongArray of(long e0, long e1) { 106 return new ImmutableLongArray(new long[] {e0, e1}); 107 } 108 109 /** Returns an immutable array containing the given values, in order. */ 110 public static ImmutableLongArray of(long e0, long e1, long e2) { 111 return new ImmutableLongArray(new long[] {e0, e1, e2}); 112 } 113 114 /** Returns an immutable array containing the given values, in order. */ 115 public static ImmutableLongArray of(long e0, long e1, long e2, long e3) { 116 return new ImmutableLongArray(new long[] {e0, e1, e2, e3}); 117 } 118 119 /** Returns an immutable array containing the given values, in order. */ 120 public static ImmutableLongArray of(long e0, long e1, long e2, long e3, long e4) { 121 return new ImmutableLongArray(new long[] {e0, e1, e2, e3, e4}); 122 } 123 124 /** Returns an immutable array containing the given values, in order. */ 125 public static ImmutableLongArray of(long e0, long e1, long e2, long e3, long e4, long e5) { 126 return new ImmutableLongArray(new long[] {e0, e1, e2, e3, e4, e5}); 127 } 128 129 // TODO(kevinb): go up to 11? 130 131 /** 132 * Returns an immutable array containing the given values, in order. 133 * 134 * <p>The array {@code rest} must not be longer than {@code Integer.MAX_VALUE - 1}. 135 */ 136 // Use (first, rest) so that `of(someLongArray)` won't compile (they should use copyOf), which is 137 // okay since we have to copy the just-created array anyway. 138 public static ImmutableLongArray of(long first, long... rest) { 139 checkArgument( 140 rest.length <= Integer.MAX_VALUE - 1, "the total number of elements must fit in an int"); 141 long[] array = new long[rest.length + 1]; 142 array[0] = first; 143 System.arraycopy(rest, 0, array, 1, rest.length); 144 return new ImmutableLongArray(array); 145 } 146 147 /** Returns an immutable array containing the given values, in order. */ 148 public static ImmutableLongArray copyOf(long[] values) { 149 return values.length == 0 150 ? EMPTY 151 : new ImmutableLongArray(Arrays.copyOf(values, values.length)); 152 } 153 154 /** Returns an immutable array containing the given values, in order. */ 155 public static ImmutableLongArray copyOf(Collection<Long> values) { 156 return values.isEmpty() ? EMPTY : new ImmutableLongArray(Longs.toArray(values)); 157 } 158 159 /** 160 * Returns an immutable array containing the given values, in order. 161 * 162 * <p><b>Performance note:</b> this method delegates to {@link #copyOf(Collection)} if {@code 163 * values} is a {@link Collection}. Otherwise it creates a {@link #builder} and uses {@link 164 * Builder#addAll(Iterable)}, with all the performance implications associated with that. 165 */ 166 public static ImmutableLongArray copyOf(Iterable<Long> values) { 167 if (values instanceof Collection) { 168 return copyOf((Collection<Long>) values); 169 } 170 return builder().addAll(values).build(); 171 } 172 173 /** Returns an immutable array containing all the values from {@code stream}, in order. */ 174 public static ImmutableLongArray copyOf(LongStream stream) { 175 // Note this uses very different growth behavior from copyOf(Iterable) and the builder. 176 long[] array = stream.toArray(); 177 return (array.length == 0) ? EMPTY : new ImmutableLongArray(array); 178 } 179 180 /** 181 * Returns a new, empty builder for {@link ImmutableLongArray} instances, sized to hold up to 182 * {@code initialCapacity} values without resizing. The returned builder is not thread-safe. 183 * 184 * <p><b>Performance note:</b> When feasible, {@code initialCapacity} should be the exact number 185 * of values that will be added, if that knowledge is readily available. It is better to guess a 186 * value slightly too high than slightly too low. If the value is not exact, the {@link 187 * ImmutableLongArray} that is built will very likely occupy more memory than strictly necessary; 188 * to trim memory usage, build using {@code builder.build().trimmed()}. 189 */ 190 public static Builder builder(int initialCapacity) { 191 checkArgument(initialCapacity >= 0, "Invalid initialCapacity: %s", initialCapacity); 192 return new Builder(initialCapacity); 193 } 194 195 /** 196 * Returns a new, empty builder for {@link ImmutableLongArray} instances, with a default initial 197 * capacity. The returned builder is not thread-safe. 198 * 199 * <p><b>Performance note:</b> The {@link ImmutableLongArray} that is built will very likely 200 * occupy more memory than necessary; to trim memory usage, build using {@code 201 * builder.build().trimmed()}. 202 */ 203 public static Builder builder() { 204 return new Builder(10); 205 } 206 207 /** 208 * A builder for {@link ImmutableLongArray} instances; obtained using {@link 209 * ImmutableLongArray#builder}. 210 */ 211 @CanIgnoreReturnValue 212 public static final class Builder { 213 private long[] array; 214 private int count = 0; // <= array.length 215 216 Builder(int initialCapacity) { 217 array = new long[initialCapacity]; 218 } 219 220 /** 221 * Appends {@code value} to the end of the values the built {@link ImmutableLongArray} will 222 * contain. 223 */ 224 public Builder add(long value) { 225 ensureRoomFor(1); 226 array[count] = value; 227 count += 1; 228 return this; 229 } 230 231 /** 232 * Appends {@code values}, in order, to the end of the values the built {@link 233 * ImmutableLongArray} will contain. 234 */ 235 public Builder addAll(long[] values) { 236 ensureRoomFor(values.length); 237 System.arraycopy(values, 0, array, count, values.length); 238 count += values.length; 239 return this; 240 } 241 242 /** 243 * Appends {@code values}, in order, to the end of the values the built {@link 244 * ImmutableLongArray} will contain. 245 */ 246 public Builder addAll(Iterable<Long> values) { 247 if (values instanceof Collection) { 248 return addAll((Collection<Long>) values); 249 } 250 for (Long value : values) { 251 add(value); 252 } 253 return this; 254 } 255 256 /** 257 * Appends {@code values}, in order, to the end of the values the built {@link 258 * ImmutableLongArray} will contain. 259 */ 260 public Builder addAll(Collection<Long> values) { 261 ensureRoomFor(values.size()); 262 for (Long value : values) { 263 array[count++] = value; 264 } 265 return this; 266 } 267 268 /** 269 * Appends all values from {@code stream}, in order, to the end of the values the built {@link 270 * ImmutableLongArray} will contain. 271 */ 272 public Builder addAll(LongStream stream) { 273 Spliterator.OfLong spliterator = stream.spliterator(); 274 long size = spliterator.getExactSizeIfKnown(); 275 if (size > 0) { // known *and* nonempty 276 ensureRoomFor(Ints.saturatedCast(size)); 277 } 278 spliterator.forEachRemaining((LongConsumer) this::add); 279 return this; 280 } 281 282 /** 283 * Appends {@code values}, in order, to the end of the values the built {@link 284 * ImmutableLongArray} will contain. 285 */ 286 public Builder addAll(ImmutableLongArray values) { 287 ensureRoomFor(values.length()); 288 System.arraycopy(values.array, values.start, array, count, values.length()); 289 count += values.length(); 290 return this; 291 } 292 293 private void ensureRoomFor(int numberToAdd) { 294 int newCount = count + numberToAdd; // TODO(kevinb): check overflow now? 295 if (newCount > array.length) { 296 long[] newArray = new long[expandedCapacity(array.length, newCount)]; 297 System.arraycopy(array, 0, newArray, 0, count); 298 this.array = newArray; 299 } 300 } 301 302 // Unfortunately this is pasted from ImmutableCollection.Builder. 303 private static int expandedCapacity(int oldCapacity, int minCapacity) { 304 if (minCapacity < 0) { 305 throw new AssertionError("cannot store more than MAX_VALUE elements"); 306 } 307 // careful of overflow! 308 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; 309 if (newCapacity < minCapacity) { 310 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 311 } 312 if (newCapacity < 0) { 313 newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity 314 } 315 return newCapacity; 316 } 317 318 /** 319 * Returns a new immutable array. The builder can continue to be used after this call, to append 320 * more values and build again. 321 * 322 * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so 323 * no data is copied as part of this step, but this may occupy more memory than strictly 324 * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}. 325 */ 326 @CheckReturnValue 327 public ImmutableLongArray build() { 328 return count == 0 ? EMPTY : new ImmutableLongArray(array, 0, count); 329 } 330 } 331 332 // Instance stuff here 333 334 // The array is never mutated after storing in this field and the construction strategies ensure 335 // it doesn't escape this class 336 @SuppressWarnings("Immutable") 337 private final long[] array; 338 339 /* 340 * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most 341 * instances. Note that the instances that would get smaller are the right set to care about 342 * optimizing, because the rest have the option of calling `trimmed`. 343 */ 344 345 private final transient int start; // it happens that we only serialize instances where this is 0 346 private final int end; // exclusive 347 348 private ImmutableLongArray(long[] array) { 349 this(array, 0, array.length); 350 } 351 352 private ImmutableLongArray(long[] array, int start, int end) { 353 this.array = array; 354 this.start = start; 355 this.end = end; 356 } 357 358 /** Returns the number of values in this array. */ 359 public int length() { 360 return end - start; 361 } 362 363 /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */ 364 public boolean isEmpty() { 365 return end == start; 366 } 367 368 /** 369 * Returns the {@code long} value present at the given index. 370 * 371 * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to 372 * {@link #length} 373 */ 374 public long get(int index) { 375 Preconditions.checkElementIndex(index, length()); 376 return array[start + index]; 377 } 378 379 /** 380 * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no 381 * such index exists. Equivalent to {@code asList().indexOf(target)}. 382 */ 383 public int indexOf(long target) { 384 for (int i = start; i < end; i++) { 385 if (array[i] == target) { 386 return i - start; 387 } 388 } 389 return -1; 390 } 391 392 /** 393 * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no 394 * such index exists. Equivalent to {@code asList().lastIndexOf(target)}. 395 */ 396 public int lastIndexOf(long target) { 397 for (int i = end - 1; i >= start; i--) { 398 if (array[i] == target) { 399 return i - start; 400 } 401 } 402 return -1; 403 } 404 405 /** 406 * Returns {@code true} if {@code target} is present at any index in this array. Equivalent to 407 * {@code asList().contains(target)}. 408 */ 409 public boolean contains(long target) { 410 return indexOf(target) >= 0; 411 } 412 413 /** Invokes {@code consumer} for each value contained in this array, in order. */ 414 public void forEach(LongConsumer consumer) { 415 checkNotNull(consumer); 416 for (int i = start; i < end; i++) { 417 consumer.accept(array[i]); 418 } 419 } 420 421 /** Returns a stream over the values in this array, in order. */ 422 public LongStream stream() { 423 return Arrays.stream(array, start, end); 424 } 425 426 /** Returns a new, mutable copy of this array's values, as a primitive {@code long[]}. */ 427 public long[] toArray() { 428 return Arrays.copyOfRange(array, start, end); 429 } 430 431 /** 432 * Returns a new immutable array containing the values in the specified range. 433 * 434 * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one 435 * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start, 436 * end).trimmed()}. 437 */ 438 public ImmutableLongArray subArray(int startIndex, int endIndex) { 439 Preconditions.checkPositionIndexes(startIndex, endIndex, length()); 440 return startIndex == endIndex 441 ? EMPTY 442 : new ImmutableLongArray(array, start + startIndex, start + endIndex); 443 } 444 445 private Spliterator.OfLong spliterator() { 446 return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED); 447 } 448 449 /** 450 * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code 451 * long} values are boxed into {@link Long} instances on demand, which can be very expensive. The 452 * returned list should be used once and discarded. For any usages beyond that, pass the returned 453 * list to {@link com.google.common.collect.ImmutableList#copyOf(Collection) ImmutableList.copyOf} 454 * and use that list instead. 455 */ 456 public List<Long> asList() { 457 /* 458 * Typically we cache this kind of thing, but much repeated use of this view is a performance 459 * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if 460 * they never use this method. 461 */ 462 return new AsList(this); 463 } 464 465 static class AsList extends AbstractList<Long> implements RandomAccess, Serializable { 466 private final ImmutableLongArray parent; 467 468 private AsList(ImmutableLongArray parent) { 469 this.parent = parent; 470 } 471 472 // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations 473 474 @Override 475 public int size() { 476 return parent.length(); 477 } 478 479 @Override 480 public Long get(int index) { 481 return parent.get(index); 482 } 483 484 @Override 485 public boolean contains(Object target) { 486 return indexOf(target) >= 0; 487 } 488 489 @Override 490 public int indexOf(Object target) { 491 return target instanceof Long ? parent.indexOf((Long) target) : -1; 492 } 493 494 @Override 495 public int lastIndexOf(Object target) { 496 return target instanceof Long ? parent.lastIndexOf((Long) target) : -1; 497 } 498 499 @Override 500 public List<Long> subList(int fromIndex, int toIndex) { 501 return parent.subArray(fromIndex, toIndex).asList(); 502 } 503 504 // The default List spliterator is not efficiently splittable 505 @Override 506 public Spliterator<Long> spliterator() { 507 return parent.spliterator(); 508 } 509 510 @Override 511 public boolean equals(@Nullable Object object) { 512 if (object instanceof AsList) { 513 AsList that = (AsList) object; 514 return this.parent.equals(that.parent); 515 } 516 // We could delegate to super now but it would still box too much 517 if (!(object instanceof List)) { 518 return false; 519 } 520 List<?> that = (List<?>) object; 521 if (this.size() != that.size()) { 522 return false; 523 } 524 int i = parent.start; 525 // Since `that` is very likely RandomAccess we could avoid allocating this iterator... 526 for (Object element : that) { 527 if (!(element instanceof Long) || parent.array[i++] != (Long) element) { 528 return false; 529 } 530 } 531 return true; 532 } 533 534 // Because we happen to use the same formula. If that changes, just don't override this. 535 @Override 536 public int hashCode() { 537 return parent.hashCode(); 538 } 539 540 @Override 541 public String toString() { 542 return parent.toString(); 543 } 544 } 545 546 /** 547 * Returns {@code true} if {@code object} is an {@code ImmutableLongArray} containing the same 548 * values as this one, in the same order. 549 */ 550 @Override 551 public boolean equals(@Nullable Object object) { 552 if (object == this) { 553 return true; 554 } 555 if (!(object instanceof ImmutableLongArray)) { 556 return false; 557 } 558 ImmutableLongArray that = (ImmutableLongArray) object; 559 if (this.length() != that.length()) { 560 return false; 561 } 562 for (int i = 0; i < length(); i++) { 563 if (this.get(i) != that.get(i)) { 564 return false; 565 } 566 } 567 return true; 568 } 569 570 /** Returns an unspecified hash code for the contents of this immutable array. */ 571 @Override 572 public int hashCode() { 573 int hash = 1; 574 for (int i = start; i < end; i++) { 575 hash *= 31; 576 hash += Longs.hashCode(array[i]); 577 } 578 return hash; 579 } 580 581 /** 582 * Returns a string representation of this array in the same form as {@link 583 * Arrays#toString(long[])}, for example {@code "[1, 2, 3]"}. 584 */ 585 @Override 586 public String toString() { 587 if (isEmpty()) { 588 return "[]"; 589 } 590 StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine 591 builder.append('[').append(array[start]); 592 593 for (int i = start + 1; i < end; i++) { 594 builder.append(", ").append(array[i]); 595 } 596 builder.append(']'); 597 return builder.toString(); 598 } 599 600 /** 601 * Returns an immutable array containing the same values as {@code this} array. This is logically 602 * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance 603 * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range 604 * of values, resulting in an equivalent array with a smaller memory footprint. 605 */ 606 public ImmutableLongArray trimmed() { 607 return isPartialView() ? new ImmutableLongArray(toArray()) : this; 608 } 609 610 private boolean isPartialView() { 611 return start > 0 || end < array.length; 612 } 613 614 Object writeReplace() { 615 return trimmed(); 616 } 617 618 Object readResolve() { 619 return isEmpty() ? EMPTY : this; 620 } 621}