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 javax.annotation.CheckForNull; 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 091@ElementTypesAreNonnullByDefault 092public final class ImmutableLongArray implements Serializable { 093 private static final ImmutableLongArray EMPTY = new ImmutableLongArray(new long[0]); 094 095 /** Returns the empty array. */ 096 public static ImmutableLongArray of() { 097 return EMPTY; 098 } 099 100 /** Returns an immutable array containing a single value. */ 101 public static ImmutableLongArray of(long e0) { 102 return new ImmutableLongArray(new long[] {e0}); 103 } 104 105 /** Returns an immutable array containing the given values, in order. */ 106 public static ImmutableLongArray of(long e0, long e1) { 107 return new ImmutableLongArray(new long[] {e0, e1}); 108 } 109 110 /** Returns an immutable array containing the given values, in order. */ 111 public static ImmutableLongArray of(long e0, long e1, long e2) { 112 return new ImmutableLongArray(new long[] {e0, e1, e2}); 113 } 114 115 /** Returns an immutable array containing the given values, in order. */ 116 public static ImmutableLongArray of(long e0, long e1, long e2, long e3) { 117 return new ImmutableLongArray(new long[] {e0, e1, e2, e3}); 118 } 119 120 /** Returns an immutable array containing the given values, in order. */ 121 public static ImmutableLongArray of(long e0, long e1, long e2, long e3, long e4) { 122 return new ImmutableLongArray(new long[] {e0, e1, e2, e3, e4}); 123 } 124 125 /** Returns an immutable array containing the given values, in order. */ 126 public static ImmutableLongArray of(long e0, long e1, long e2, long e3, long e4, long e5) { 127 return new ImmutableLongArray(new long[] {e0, e1, e2, e3, e4, e5}); 128 } 129 130 // TODO(kevinb): go up to 11? 131 132 /** 133 * Returns an immutable array containing the given values, in order. 134 * 135 * <p>The array {@code rest} must not be longer than {@code Integer.MAX_VALUE - 1}. 136 */ 137 // Use (first, rest) so that `of(someLongArray)` won't compile (they should use copyOf), which is 138 // okay since we have to copy the just-created array anyway. 139 public static ImmutableLongArray of(long first, long... rest) { 140 checkArgument( 141 rest.length <= Integer.MAX_VALUE - 1, "the total number of elements must fit in an int"); 142 long[] array = new long[rest.length + 1]; 143 array[0] = first; 144 System.arraycopy(rest, 0, array, 1, rest.length); 145 return new ImmutableLongArray(array); 146 } 147 148 /** Returns an immutable array containing the given values, in order. */ 149 public static ImmutableLongArray copyOf(long[] values) { 150 return values.length == 0 151 ? EMPTY 152 : new ImmutableLongArray(Arrays.copyOf(values, values.length)); 153 } 154 155 /** Returns an immutable array containing the given values, in order. */ 156 public static ImmutableLongArray copyOf(Collection<Long> values) { 157 return values.isEmpty() ? EMPTY : new ImmutableLongArray(Longs.toArray(values)); 158 } 159 160 /** 161 * Returns an immutable array containing the given values, in order. 162 * 163 * <p><b>Performance note:</b> this method delegates to {@link #copyOf(Collection)} if {@code 164 * values} is a {@link Collection}. Otherwise it creates a {@link #builder} and uses {@link 165 * Builder#addAll(Iterable)}, with all the performance implications associated with that. 166 */ 167 public static ImmutableLongArray copyOf(Iterable<Long> values) { 168 if (values instanceof Collection) { 169 return copyOf((Collection<Long>) values); 170 } 171 return builder().addAll(values).build(); 172 } 173 174 /** Returns an immutable array containing all the values from {@code stream}, in order. */ 175 public static ImmutableLongArray copyOf(LongStream stream) { 176 // Note this uses very different growth behavior from copyOf(Iterable) and the builder. 177 long[] array = stream.toArray(); 178 return (array.length == 0) ? EMPTY : new ImmutableLongArray(array); 179 } 180 181 /** 182 * Returns a new, empty builder for {@link ImmutableLongArray} instances, sized to hold up to 183 * {@code initialCapacity} values without resizing. The returned builder is not thread-safe. 184 * 185 * <p><b>Performance note:</b> When feasible, {@code initialCapacity} should be the exact number 186 * of values that will be added, if that knowledge is readily available. It is better to guess a 187 * value slightly too high than slightly too low. If the value is not exact, the {@link 188 * ImmutableLongArray} that is built will very likely occupy more memory than strictly necessary; 189 * to trim memory usage, build using {@code builder.build().trimmed()}. 190 */ 191 public static Builder builder(int initialCapacity) { 192 checkArgument(initialCapacity >= 0, "Invalid initialCapacity: %s", initialCapacity); 193 return new Builder(initialCapacity); 194 } 195 196 /** 197 * Returns a new, empty builder for {@link ImmutableLongArray} instances, with a default initial 198 * capacity. The returned builder is not thread-safe. 199 * 200 * <p><b>Performance note:</b> The {@link ImmutableLongArray} that is built will very likely 201 * occupy more memory than necessary; to trim memory usage, build using {@code 202 * builder.build().trimmed()}. 203 */ 204 public static Builder builder() { 205 return new Builder(10); 206 } 207 208 /** 209 * A builder for {@link ImmutableLongArray} instances; obtained using {@link 210 * ImmutableLongArray#builder}. 211 */ 212 @CanIgnoreReturnValue 213 public static final class Builder { 214 private long[] array; 215 private int count = 0; // <= array.length 216 217 Builder(int initialCapacity) { 218 array = new long[initialCapacity]; 219 } 220 221 /** 222 * Appends {@code value} to the end of the values the built {@link ImmutableLongArray} will 223 * contain. 224 */ 225 public Builder add(long value) { 226 ensureRoomFor(1); 227 array[count] = value; 228 count += 1; 229 return this; 230 } 231 232 /** 233 * Appends {@code values}, in order, to the end of the values the built {@link 234 * ImmutableLongArray} will contain. 235 */ 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 public Builder addAll(Iterable<Long> values) { 248 if (values instanceof Collection) { 249 return addAll((Collection<Long>) values); 250 } 251 for (Long value : values) { 252 add(value); 253 } 254 return this; 255 } 256 257 /** 258 * Appends {@code values}, in order, to the end of the values the built {@link 259 * ImmutableLongArray} will contain. 260 */ 261 public Builder addAll(Collection<Long> values) { 262 ensureRoomFor(values.size()); 263 for (Long value : values) { 264 array[count++] = value; 265 } 266 return this; 267 } 268 269 /** 270 * Appends all values from {@code stream}, in order, to the end of the values the built {@link 271 * ImmutableLongArray} will contain. 272 */ 273 public Builder addAll(LongStream stream) { 274 Spliterator.OfLong spliterator = stream.spliterator(); 275 long size = spliterator.getExactSizeIfKnown(); 276 if (size > 0) { // known *and* nonempty 277 ensureRoomFor(Ints.saturatedCast(size)); 278 } 279 spliterator.forEachRemaining((LongConsumer) this::add); 280 return this; 281 } 282 283 /** 284 * Appends {@code values}, in order, to the end of the values the built {@link 285 * ImmutableLongArray} will contain. 286 */ 287 public Builder addAll(ImmutableLongArray values) { 288 ensureRoomFor(values.length()); 289 System.arraycopy(values.array, values.start, array, count, values.length()); 290 count += values.length(); 291 return this; 292 } 293 294 private void ensureRoomFor(int numberToAdd) { 295 int newCount = count + numberToAdd; // TODO(kevinb): check overflow now? 296 if (newCount > array.length) { 297 array = Arrays.copyOf(array, expandedCapacity(array.length, newCount)); 298 } 299 } 300 301 // Unfortunately this is pasted from ImmutableCollection.Builder. 302 private static int expandedCapacity(int oldCapacity, int minCapacity) { 303 if (minCapacity < 0) { 304 throw new AssertionError("cannot store more than MAX_VALUE elements"); 305 } 306 // careful of overflow! 307 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; 308 if (newCapacity < minCapacity) { 309 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 310 } 311 if (newCapacity < 0) { 312 newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity 313 } 314 return newCapacity; 315 } 316 317 /** 318 * Returns a new immutable array. The builder can continue to be used after this call, to append 319 * more values and build again. 320 * 321 * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so 322 * no data is copied as part of this step, but this may occupy more memory than strictly 323 * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}. 324 */ 325 @CheckReturnValue 326 public ImmutableLongArray build() { 327 return count == 0 ? EMPTY : new ImmutableLongArray(array, 0, count); 328 } 329 } 330 331 // Instance stuff here 332 333 // The array is never mutated after storing in this field and the construction strategies ensure 334 // it doesn't escape this class 335 @SuppressWarnings("Immutable") 336 private final long[] array; 337 338 /* 339 * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most 340 * instances. Note that the instances that would get smaller are the right set to care about 341 * optimizing, because the rest have the option of calling `trimmed`. 342 */ 343 344 private final transient int start; // it happens that we only serialize instances where this is 0 345 private final int end; // exclusive 346 347 private ImmutableLongArray(long[] array) { 348 this(array, 0, array.length); 349 } 350 351 private ImmutableLongArray(long[] array, int start, int end) { 352 this.array = array; 353 this.start = start; 354 this.end = end; 355 } 356 357 /** Returns the number of values in this array. */ 358 public int length() { 359 return end - start; 360 } 361 362 /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */ 363 public boolean isEmpty() { 364 return end == start; 365 } 366 367 /** 368 * Returns the {@code long} value present at the given index. 369 * 370 * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to 371 * {@link #length} 372 */ 373 public long get(int index) { 374 Preconditions.checkElementIndex(index, length()); 375 return array[start + index]; 376 } 377 378 /** 379 * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no 380 * such index exists. Equivalent to {@code asList().indexOf(target)}. 381 */ 382 public int indexOf(long target) { 383 for (int i = start; i < end; i++) { 384 if (array[i] == target) { 385 return i - start; 386 } 387 } 388 return -1; 389 } 390 391 /** 392 * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no 393 * such index exists. Equivalent to {@code asList().lastIndexOf(target)}. 394 */ 395 public int lastIndexOf(long target) { 396 for (int i = end - 1; i >= start; i--) { 397 if (array[i] == target) { 398 return i - start; 399 } 400 } 401 return -1; 402 } 403 404 /** 405 * Returns {@code true} if {@code target} is present at any index in this array. Equivalent to 406 * {@code asList().contains(target)}. 407 */ 408 public boolean contains(long target) { 409 return indexOf(target) >= 0; 410 } 411 412 /** Invokes {@code consumer} for each value contained in this array, in order. */ 413 public void forEach(LongConsumer consumer) { 414 checkNotNull(consumer); 415 for (int i = start; i < end; i++) { 416 consumer.accept(array[i]); 417 } 418 } 419 420 /** Returns a stream over the values in this array, in order. */ 421 public LongStream stream() { 422 return Arrays.stream(array, start, end); 423 } 424 425 /** Returns a new, mutable copy of this array's values, as a primitive {@code long[]}. */ 426 public long[] toArray() { 427 return Arrays.copyOfRange(array, start, end); 428 } 429 430 /** 431 * Returns a new immutable array containing the values in the specified range. 432 * 433 * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one 434 * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start, 435 * end).trimmed()}. 436 */ 437 public ImmutableLongArray subArray(int startIndex, int endIndex) { 438 Preconditions.checkPositionIndexes(startIndex, endIndex, length()); 439 return startIndex == endIndex 440 ? EMPTY 441 : new ImmutableLongArray(array, start + startIndex, start + endIndex); 442 } 443 444 private Spliterator.OfLong spliterator() { 445 return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED); 446 } 447 448 /** 449 * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code 450 * long} values are boxed into {@link Long} instances on demand, which can be very expensive. The 451 * returned list should be used once and discarded. For any usages beyond that, pass the returned 452 * list to {@link com.google.common.collect.ImmutableList#copyOf(Collection) ImmutableList.copyOf} 453 * and use that list instead. 454 */ 455 public List<Long> asList() { 456 /* 457 * Typically we cache this kind of thing, but much repeated use of this view is a performance 458 * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if 459 * they never use this method. 460 */ 461 return new AsList(this); 462 } 463 464 static class AsList extends AbstractList<Long> implements RandomAccess, Serializable { 465 private final ImmutableLongArray parent; 466 467 private AsList(ImmutableLongArray parent) { 468 this.parent = parent; 469 } 470 471 // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations 472 473 @Override 474 public int size() { 475 return parent.length(); 476 } 477 478 @Override 479 public Long get(int index) { 480 return parent.get(index); 481 } 482 483 @Override 484 public boolean contains(@CheckForNull Object target) { 485 return indexOf(target) >= 0; 486 } 487 488 @Override 489 public int indexOf(@CheckForNull Object target) { 490 return target instanceof Long ? parent.indexOf((Long) target) : -1; 491 } 492 493 @Override 494 public int lastIndexOf(@CheckForNull Object target) { 495 return target instanceof Long ? parent.lastIndexOf((Long) target) : -1; 496 } 497 498 @Override 499 public List<Long> subList(int fromIndex, int toIndex) { 500 return parent.subArray(fromIndex, toIndex).asList(); 501 } 502 503 // The default List spliterator is not efficiently splittable 504 @Override 505 public Spliterator<Long> spliterator() { 506 return parent.spliterator(); 507 } 508 509 @Override 510 public boolean equals(@CheckForNull Object object) { 511 if (object instanceof AsList) { 512 AsList that = (AsList) object; 513 return this.parent.equals(that.parent); 514 } 515 // We could delegate to super now but it would still box too much 516 if (!(object instanceof List)) { 517 return false; 518 } 519 List<?> that = (List<?>) object; 520 if (this.size() != that.size()) { 521 return false; 522 } 523 int i = parent.start; 524 // Since `that` is very likely RandomAccess we could avoid allocating this iterator... 525 for (Object element : that) { 526 if (!(element instanceof Long) || parent.array[i++] != (Long) element) { 527 return false; 528 } 529 } 530 return true; 531 } 532 533 // Because we happen to use the same formula. If that changes, just don't override this. 534 @Override 535 public int hashCode() { 536 return parent.hashCode(); 537 } 538 539 @Override 540 public String toString() { 541 return parent.toString(); 542 } 543 } 544 545 /** 546 * Returns {@code true} if {@code object} is an {@code ImmutableLongArray} containing the same 547 * values as this one, in the same order. 548 */ 549 @Override 550 public boolean equals(@CheckForNull Object object) { 551 if (object == this) { 552 return true; 553 } 554 if (!(object instanceof ImmutableLongArray)) { 555 return false; 556 } 557 ImmutableLongArray that = (ImmutableLongArray) object; 558 if (this.length() != that.length()) { 559 return false; 560 } 561 for (int i = 0; i < length(); i++) { 562 if (this.get(i) != that.get(i)) { 563 return false; 564 } 565 } 566 return true; 567 } 568 569 /** Returns an unspecified hash code for the contents of this immutable array. */ 570 @Override 571 public int hashCode() { 572 int hash = 1; 573 for (int i = start; i < end; i++) { 574 hash *= 31; 575 hash += Longs.hashCode(array[i]); 576 } 577 return hash; 578 } 579 580 /** 581 * Returns a string representation of this array in the same form as {@link 582 * Arrays#toString(long[])}, for example {@code "[1, 2, 3]"}. 583 */ 584 @Override 585 public String toString() { 586 if (isEmpty()) { 587 return "[]"; 588 } 589 StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine 590 builder.append('[').append(array[start]); 591 592 for (int i = start + 1; i < end; i++) { 593 builder.append(", ").append(array[i]); 594 } 595 builder.append(']'); 596 return builder.toString(); 597 } 598 599 /** 600 * Returns an immutable array containing the same values as {@code this} array. This is logically 601 * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance 602 * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range 603 * of values, resulting in an equivalent array with a smaller memory footprint. 604 */ 605 public ImmutableLongArray trimmed() { 606 return isPartialView() ? new ImmutableLongArray(toArray()) : this; 607 } 608 609 private boolean isPartialView() { 610 return start > 0 || end < array.length; 611 } 612 613 Object writeReplace() { 614 return trimmed(); 615 } 616 617 Object readResolve() { 618 return isEmpty() ? EMPTY : this; 619 } 620}