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