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.Immutable; 025import java.io.Serializable; 026import java.util.AbstractList; 027import java.util.Arrays; 028import java.util.Collection; 029import java.util.List; 030import java.util.RandomAccess; 031import java.util.Spliterator; 032import java.util.Spliterators; 033import java.util.function.LongConsumer; 034import java.util.stream.LongStream; 035import javax.annotation.CheckForNull; 036 037/** 038 * An immutable array of {@code long} values, with an API resembling {@link List}. 039 * 040 * <p>Advantages compared to {@code long[]}: 041 * 042 * <ul> 043 * <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, third 044 * edition, Item 17). 045 * <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link 046 * #toString} behavior you expect. 047 * <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to 048 * hunt through classes like {@link Arrays} and {@link Longs} for them. 049 * <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to 050 * add overloads that accept start and end indexes. 051 * <li>Can be streamed without "breaking the chain": {@code foo.getBarLongs().stream()...}. 052 * <li>Access to all collection-based utilities via {@link #asList} (though at the cost of 053 * allocating garbage). 054 * </ul> 055 * 056 * <p>Disadvantages compared to {@code long[]}: 057 * 058 * <ul> 059 * <li>Memory footprint has a fixed overhead (about 24 bytes per instance). 060 * <li><i>Some</i> construction use cases force the data to be copied (though several construction 061 * APIs are offered that don't). 062 * <li>Can't be passed directly to methods that expect {@code long[]} (though the most common 063 * utilities do have replacements here). 064 * <li>Dependency on {@code com.google.common} / Guava. 065 * </ul> 066 * 067 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code 068 * <Long>}: 069 * 070 * <ul> 071 * <li>Improved memory compactness and locality. 072 * <li>Can be queried without allocating garbage. 073 * <li>Access to {@code LongStream} features (like {@link LongStream#sum}) using {@code stream()} 074 * instead of the awkward {@code stream().mapToLong(v -> v)}. 075 * </ul> 076 * 077 * <p>Disadvantages compared to {@code ImmutableList<Long>}: 078 * 079 * <ul> 080 * <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or 081 * {@code List} (though the most common utilities do have replacements here, and there is a 082 * lazy {@link #asList} view). 083 * </ul> 084 * 085 * @since 22.0 086 */ 087@Beta 088@GwtCompatible 089@Immutable 090@ElementTypesAreNonnullByDefault 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 public static final class Builder { 212 private long[] array; 213 private int count = 0; // <= array.length 214 215 Builder(int initialCapacity) { 216 array = new long[initialCapacity]; 217 } 218 219 /** 220 * Appends {@code value} to the end of the values the built {@link ImmutableLongArray} will 221 * contain. 222 */ 223 @CanIgnoreReturnValue 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 @CanIgnoreReturnValue 236 public Builder addAll(long[] values) { 237 ensureRoomFor(values.length); 238 System.arraycopy(values, 0, array, count, values.length); 239 count += values.length; 240 return this; 241 } 242 243 /** 244 * Appends {@code values}, in order, to the end of the values the built {@link 245 * ImmutableLongArray} will contain. 246 */ 247 @CanIgnoreReturnValue 248 public Builder addAll(Iterable<Long> values) { 249 if (values instanceof Collection) { 250 return addAll((Collection<Long>) values); 251 } 252 for (Long value : values) { 253 add(value); 254 } 255 return this; 256 } 257 258 /** 259 * Appends {@code values}, in order, to the end of the values the built {@link 260 * ImmutableLongArray} will contain. 261 */ 262 @CanIgnoreReturnValue 263 public Builder addAll(Collection<Long> values) { 264 ensureRoomFor(values.size()); 265 for (Long value : values) { 266 array[count++] = value; 267 } 268 return this; 269 } 270 271 /** 272 * Appends all values from {@code stream}, in order, to the end of the values the built {@link 273 * ImmutableLongArray} will contain. 274 */ 275 @CanIgnoreReturnValue 276 public Builder addAll(LongStream stream) { 277 Spliterator.OfLong spliterator = stream.spliterator(); 278 long size = spliterator.getExactSizeIfKnown(); 279 if (size > 0) { // known *and* nonempty 280 ensureRoomFor(Ints.saturatedCast(size)); 281 } 282 spliterator.forEachRemaining((LongConsumer) this::add); 283 return this; 284 } 285 286 /** 287 * Appends {@code values}, in order, to the end of the values the built {@link 288 * ImmutableLongArray} will contain. 289 */ 290 @CanIgnoreReturnValue 291 public Builder addAll(ImmutableLongArray values) { 292 ensureRoomFor(values.length()); 293 System.arraycopy(values.array, values.start, array, count, values.length()); 294 count += values.length(); 295 return this; 296 } 297 298 private void ensureRoomFor(int numberToAdd) { 299 int newCount = count + numberToAdd; // TODO(kevinb): check overflow now? 300 if (newCount > array.length) { 301 array = Arrays.copyOf(array, expandedCapacity(array.length, newCount)); 302 } 303 } 304 305 // Unfortunately this is pasted from ImmutableCollection.Builder. 306 private static int expandedCapacity(int oldCapacity, int minCapacity) { 307 if (minCapacity < 0) { 308 throw new AssertionError("cannot store more than MAX_VALUE elements"); 309 } 310 // careful of overflow! 311 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; 312 if (newCapacity < minCapacity) { 313 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 314 } 315 if (newCapacity < 0) { 316 newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity 317 } 318 return newCapacity; 319 } 320 321 /** 322 * Returns a new immutable array. The builder can continue to be used after this call, to append 323 * more values and build again. 324 * 325 * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so 326 * no data is copied as part of this step, but this may occupy more memory than strictly 327 * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}. 328 */ 329 public ImmutableLongArray build() { 330 return count == 0 ? EMPTY : new ImmutableLongArray(array, 0, count); 331 } 332 } 333 334 // Instance stuff here 335 336 // The array is never mutated after storing in this field and the construction strategies ensure 337 // it doesn't escape this class 338 @SuppressWarnings("Immutable") 339 private final long[] array; 340 341 /* 342 * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most 343 * instances. Note that the instances that would get smaller are the right set to care about 344 * optimizing, because the rest have the option of calling `trimmed`. 345 */ 346 347 private final transient int start; // it happens that we only serialize instances where this is 0 348 private final int end; // exclusive 349 350 private ImmutableLongArray(long[] array) { 351 this(array, 0, array.length); 352 } 353 354 private ImmutableLongArray(long[] array, int start, int end) { 355 this.array = array; 356 this.start = start; 357 this.end = end; 358 } 359 360 /** Returns the number of values in this array. */ 361 public int length() { 362 return end - start; 363 } 364 365 /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */ 366 public boolean isEmpty() { 367 return end == start; 368 } 369 370 /** 371 * Returns the {@code long} value present at the given index. 372 * 373 * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to 374 * {@link #length} 375 */ 376 public long get(int index) { 377 Preconditions.checkElementIndex(index, length()); 378 return array[start + index]; 379 } 380 381 /** 382 * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no 383 * such index exists. Equivalent to {@code asList().indexOf(target)}. 384 */ 385 public int indexOf(long target) { 386 for (int i = start; i < end; i++) { 387 if (array[i] == target) { 388 return i - start; 389 } 390 } 391 return -1; 392 } 393 394 /** 395 * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no 396 * such index exists. Equivalent to {@code asList().lastIndexOf(target)}. 397 */ 398 public int lastIndexOf(long target) { 399 for (int i = end - 1; i >= start; i--) { 400 if (array[i] == target) { 401 return i - start; 402 } 403 } 404 return -1; 405 } 406 407 /** 408 * Returns {@code true} if {@code target} is present at any index in this array. Equivalent to 409 * {@code asList().contains(target)}. 410 */ 411 public boolean contains(long target) { 412 return indexOf(target) >= 0; 413 } 414 415 /** Invokes {@code consumer} for each value contained in this array, in order. */ 416 public void forEach(LongConsumer consumer) { 417 checkNotNull(consumer); 418 for (int i = start; i < end; i++) { 419 consumer.accept(array[i]); 420 } 421 } 422 423 /** Returns a stream over the values in this array, in order. */ 424 public LongStream stream() { 425 return Arrays.stream(array, start, end); 426 } 427 428 /** Returns a new, mutable copy of this array's values, as a primitive {@code long[]}. */ 429 public long[] toArray() { 430 return Arrays.copyOfRange(array, start, end); 431 } 432 433 /** 434 * Returns a new immutable array containing the values in the specified range. 435 * 436 * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one 437 * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start, 438 * end).trimmed()}. 439 */ 440 public ImmutableLongArray subArray(int startIndex, int endIndex) { 441 Preconditions.checkPositionIndexes(startIndex, endIndex, length()); 442 return startIndex == endIndex 443 ? EMPTY 444 : new ImmutableLongArray(array, start + startIndex, start + endIndex); 445 } 446 447 private Spliterator.OfLong spliterator() { 448 return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED); 449 } 450 451 /** 452 * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code 453 * long} values are boxed into {@link Long} instances on demand, which can be very expensive. The 454 * returned list should be used once and discarded. For any usages beyond that, pass the returned 455 * list to {@link com.google.common.collect.ImmutableList#copyOf(Collection) ImmutableList.copyOf} 456 * and use that list instead. 457 */ 458 public List<Long> asList() { 459 /* 460 * Typically we cache this kind of thing, but much repeated use of this view is a performance 461 * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if 462 * they never use this method. 463 */ 464 return new AsList(this); 465 } 466 467 static class AsList extends AbstractList<Long> implements RandomAccess, Serializable { 468 private final ImmutableLongArray parent; 469 470 private AsList(ImmutableLongArray parent) { 471 this.parent = parent; 472 } 473 474 // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations 475 476 @Override 477 public int size() { 478 return parent.length(); 479 } 480 481 @Override 482 public Long get(int index) { 483 return parent.get(index); 484 } 485 486 @Override 487 public boolean contains(@CheckForNull Object target) { 488 return indexOf(target) >= 0; 489 } 490 491 @Override 492 public int indexOf(@CheckForNull Object target) { 493 return target instanceof Long ? parent.indexOf((Long) target) : -1; 494 } 495 496 @Override 497 public int lastIndexOf(@CheckForNull Object target) { 498 return target instanceof Long ? parent.lastIndexOf((Long) target) : -1; 499 } 500 501 @Override 502 public List<Long> subList(int fromIndex, int toIndex) { 503 return parent.subArray(fromIndex, toIndex).asList(); 504 } 505 506 // The default List spliterator is not efficiently splittable 507 @Override 508 public Spliterator<Long> spliterator() { 509 return parent.spliterator(); 510 } 511 512 @Override 513 public boolean equals(@CheckForNull Object object) { 514 if (object instanceof AsList) { 515 AsList that = (AsList) object; 516 return this.parent.equals(that.parent); 517 } 518 // We could delegate to super now but it would still box too much 519 if (!(object instanceof List)) { 520 return false; 521 } 522 List<?> that = (List<?>) object; 523 if (this.size() != that.size()) { 524 return false; 525 } 526 int i = parent.start; 527 // Since `that` is very likely RandomAccess we could avoid allocating this iterator... 528 for (Object element : that) { 529 if (!(element instanceof Long) || parent.array[i++] != (Long) element) { 530 return false; 531 } 532 } 533 return true; 534 } 535 536 // Because we happen to use the same formula. If that changes, just don't override this. 537 @Override 538 public int hashCode() { 539 return parent.hashCode(); 540 } 541 542 @Override 543 public String toString() { 544 return parent.toString(); 545 } 546 } 547 548 /** 549 * Returns {@code true} if {@code object} is an {@code ImmutableLongArray} containing the same 550 * values as this one, in the same order. 551 */ 552 @Override 553 public boolean equals(@CheckForNull Object object) { 554 if (object == this) { 555 return true; 556 } 557 if (!(object instanceof ImmutableLongArray)) { 558 return false; 559 } 560 ImmutableLongArray that = (ImmutableLongArray) object; 561 if (this.length() != that.length()) { 562 return false; 563 } 564 for (int i = 0; i < length(); i++) { 565 if (this.get(i) != that.get(i)) { 566 return false; 567 } 568 } 569 return true; 570 } 571 572 /** Returns an unspecified hash code for the contents of this immutable array. */ 573 @Override 574 public int hashCode() { 575 int hash = 1; 576 for (int i = start; i < end; i++) { 577 hash *= 31; 578 hash += Longs.hashCode(array[i]); 579 } 580 return hash; 581 } 582 583 /** 584 * Returns a string representation of this array in the same form as {@link 585 * Arrays#toString(long[])}, for example {@code "[1, 2, 3]"}. 586 */ 587 @Override 588 public String toString() { 589 if (isEmpty()) { 590 return "[]"; 591 } 592 StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine 593 builder.append('[').append(array[start]); 594 595 for (int i = start + 1; i < end; i++) { 596 builder.append(", ").append(array[i]); 597 } 598 builder.append(']'); 599 return builder.toString(); 600 } 601 602 /** 603 * Returns an immutable array containing the same values as {@code this} array. This is logically 604 * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance 605 * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range 606 * of values, resulting in an equivalent array with a smaller memory footprint. 607 */ 608 public ImmutableLongArray trimmed() { 609 return isPartialView() ? new ImmutableLongArray(toArray()) : this; 610 } 611 612 private boolean isPartialView() { 613 return start > 0 || end < array.length; 614 } 615 616 Object writeReplace() { 617 return trimmed(); 618 } 619 620 Object readResolve() { 621 return isEmpty() ? EMPTY : this; 622 } 623}