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.DoubleConsumer; 035import java.util.stream.DoubleStream; 036import org.checkerframework.checker.nullness.qual.Nullable; 037 038/** 039 * An immutable array of {@code double} values, with an API resembling {@link List}. 040 * 041 * <p>Advantages compared to {@code double[]}: 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 Doubles} 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.getBarDoubles().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 double[]}: 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 double[]} (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 * <Double>}: 070 * 071 * <ul> 072 * <li>Improved memory compactness and locality. 073 * <li>Can be queried without allocating garbage. 074 * <li>Access to {@code DoubleStream} features (like {@link DoubleStream#sum}) using {@code 075 * stream()} instead of the awkward {@code stream().mapToDouble(v -> v)}. 076 * </ul> 077 * 078 * <p>Disadvantages compared to {@code ImmutableList<Double>}: 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 ImmutableDoubleArray implements Serializable { 092 private static final ImmutableDoubleArray EMPTY = new ImmutableDoubleArray(new double[0]); 093 094 /** Returns the empty array. */ 095 public static ImmutableDoubleArray of() { 096 return EMPTY; 097 } 098 099 /** Returns an immutable array containing a single value. */ 100 public static ImmutableDoubleArray of(double e0) { 101 return new ImmutableDoubleArray(new double[] {e0}); 102 } 103 104 /** Returns an immutable array containing the given values, in order. */ 105 public static ImmutableDoubleArray of(double e0, double e1) { 106 return new ImmutableDoubleArray(new double[] {e0, e1}); 107 } 108 109 /** Returns an immutable array containing the given values, in order. */ 110 public static ImmutableDoubleArray of(double e0, double e1, double e2) { 111 return new ImmutableDoubleArray(new double[] {e0, e1, e2}); 112 } 113 114 /** Returns an immutable array containing the given values, in order. */ 115 public static ImmutableDoubleArray of(double e0, double e1, double e2, double e3) { 116 return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3}); 117 } 118 119 /** Returns an immutable array containing the given values, in order. */ 120 public static ImmutableDoubleArray of(double e0, double e1, double e2, double e3, double e4) { 121 return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3, e4}); 122 } 123 124 /** Returns an immutable array containing the given values, in order. */ 125 public static ImmutableDoubleArray of( 126 double e0, double e1, double e2, double e3, double e4, double e5) { 127 return new ImmutableDoubleArray(new double[] {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(someDoubleArray)` won't compile (they should use copyOf), which 138 // is okay since we have to copy the just-created array anyway. 139 public static ImmutableDoubleArray of(double first, double... rest) { 140 checkArgument( 141 rest.length <= Integer.MAX_VALUE - 1, "the total number of elements must fit in an int"); 142 double[] array = new double[rest.length + 1]; 143 array[0] = first; 144 System.arraycopy(rest, 0, array, 1, rest.length); 145 return new ImmutableDoubleArray(array); 146 } 147 148 /** Returns an immutable array containing the given values, in order. */ 149 public static ImmutableDoubleArray copyOf(double[] values) { 150 return values.length == 0 151 ? EMPTY 152 : new ImmutableDoubleArray(Arrays.copyOf(values, values.length)); 153 } 154 155 /** Returns an immutable array containing the given values, in order. */ 156 public static ImmutableDoubleArray copyOf(Collection<Double> values) { 157 return values.isEmpty() ? EMPTY : new ImmutableDoubleArray(Doubles.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 ImmutableDoubleArray copyOf(Iterable<Double> values) { 168 if (values instanceof Collection) { 169 return copyOf((Collection<Double>) 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 ImmutableDoubleArray copyOf(DoubleStream stream) { 176 // Note this uses very different growth behavior from copyOf(Iterable) and the builder. 177 double[] array = stream.toArray(); 178 return (array.length == 0) ? EMPTY : new ImmutableDoubleArray(array); 179 } 180 181 /** 182 * Returns a new, empty builder for {@link ImmutableDoubleArray} 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 * ImmutableDoubleArray} that is built will very likely occupy more memory than strictly 189 * necessary; 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 ImmutableDoubleArray} instances, with a default initial 198 * capacity. The returned builder is not thread-safe. 199 * 200 * <p><b>Performance note:</b> The {@link ImmutableDoubleArray} 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 ImmutableDoubleArray} instances; obtained using {@link 210 * ImmutableDoubleArray#builder}. 211 */ 212 @CanIgnoreReturnValue 213 public static final class Builder { 214 private double[] array; 215 private int count = 0; // <= array.length 216 217 Builder(int initialCapacity) { 218 array = new double[initialCapacity]; 219 } 220 221 /** 222 * Appends {@code value} to the end of the values the built {@link ImmutableDoubleArray} will 223 * contain. 224 */ 225 public Builder add(double 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 * ImmutableDoubleArray} will contain. 235 */ 236 public Builder addAll(double[] 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 * ImmutableDoubleArray} will contain. 246 */ 247 public Builder addAll(Iterable<Double> values) { 248 if (values instanceof Collection) { 249 return addAll((Collection<Double>) values); 250 } 251 for (Double 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 * ImmutableDoubleArray} will contain. 260 */ 261 public Builder addAll(Collection<Double> values) { 262 ensureRoomFor(values.size()); 263 for (Double 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 * ImmutableDoubleArray} will contain. 272 */ 273 public Builder addAll(DoubleStream stream) { 274 Spliterator.OfDouble spliterator = stream.spliterator(); 275 long size = spliterator.getExactSizeIfKnown(); 276 if (size > 0) { // known *and* nonempty 277 ensureRoomFor(Ints.saturatedCast(size)); 278 } 279 spliterator.forEachRemaining((DoubleConsumer) this::add); 280 return this; 281 } 282 283 /** 284 * Appends {@code values}, in order, to the end of the values the built {@link 285 * ImmutableDoubleArray} will contain. 286 */ 287 public Builder addAll(ImmutableDoubleArray 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 double[] newArray = new double[expandedCapacity(array.length, newCount)]; 298 System.arraycopy(array, 0, newArray, 0, count); 299 this.array = newArray; 300 } 301 } 302 303 // Unfortunately this is pasted from ImmutableCollection.Builder. 304 private static int expandedCapacity(int oldCapacity, int minCapacity) { 305 if (minCapacity < 0) { 306 throw new AssertionError("cannot store more than MAX_VALUE elements"); 307 } 308 // careful of overflow! 309 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; 310 if (newCapacity < minCapacity) { 311 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 312 } 313 if (newCapacity < 0) { 314 newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity 315 } 316 return newCapacity; 317 } 318 319 /** 320 * Returns a new immutable array. The builder can continue to be used after this call, to append 321 * more values and build again. 322 * 323 * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so 324 * no data is copied as part of this step, but this may occupy more memory than strictly 325 * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}. 326 */ 327 @CheckReturnValue 328 public ImmutableDoubleArray build() { 329 return count == 0 ? EMPTY : new ImmutableDoubleArray(array, 0, count); 330 } 331 } 332 333 // Instance stuff here 334 335 // The array is never mutated after storing in this field and the construction strategies ensure 336 // it doesn't escape this class 337 @SuppressWarnings("Immutable") 338 private final double[] array; 339 340 /* 341 * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most 342 * instances. Note that the instances that would get smaller are the right set to care about 343 * optimizing, because the rest have the option of calling `trimmed`. 344 */ 345 346 private final transient int start; // it happens that we only serialize instances where this is 0 347 private final int end; // exclusive 348 349 private ImmutableDoubleArray(double[] array) { 350 this(array, 0, array.length); 351 } 352 353 private ImmutableDoubleArray(double[] array, int start, int end) { 354 this.array = array; 355 this.start = start; 356 this.end = end; 357 } 358 359 /** Returns the number of values in this array. */ 360 public int length() { 361 return end - start; 362 } 363 364 /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */ 365 public boolean isEmpty() { 366 return end == start; 367 } 368 369 /** 370 * Returns the {@code double} value present at the given index. 371 * 372 * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to 373 * {@link #length} 374 */ 375 public double get(int index) { 376 Preconditions.checkElementIndex(index, length()); 377 return array[start + index]; 378 } 379 380 /** 381 * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no 382 * such index exists. Values are compared as if by {@link Double#equals}. Equivalent to {@code 383 * asList().indexOf(target)}. 384 */ 385 public int indexOf(double target) { 386 for (int i = start; i < end; i++) { 387 if (areEqual(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. Values are compared as if by {@link Double#equals}. Equivalent to {@code 397 * asList().lastIndexOf(target)}. 398 */ 399 public int lastIndexOf(double target) { 400 for (int i = end - 1; i >= start; i--) { 401 if (areEqual(array[i], target)) { 402 return i - start; 403 } 404 } 405 return -1; 406 } 407 408 /** 409 * Returns {@code true} if {@code target} is present at any index in this array. Values are 410 * compared as if by {@link Double#equals}. Equivalent to {@code asList().contains(target)}. 411 */ 412 public boolean contains(double target) { 413 return indexOf(target) >= 0; 414 } 415 416 /** Invokes {@code consumer} for each value contained in this array, in order. */ 417 public void forEach(DoubleConsumer consumer) { 418 checkNotNull(consumer); 419 for (int i = start; i < end; i++) { 420 consumer.accept(array[i]); 421 } 422 } 423 424 /** Returns a stream over the values in this array, in order. */ 425 public DoubleStream stream() { 426 return Arrays.stream(array, start, end); 427 } 428 429 /** Returns a new, mutable copy of this array's values, as a primitive {@code double[]}. */ 430 public double[] toArray() { 431 return Arrays.copyOfRange(array, start, end); 432 } 433 434 /** 435 * Returns a new immutable array containing the values in the specified range. 436 * 437 * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one 438 * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start, 439 * end).trimmed()}. 440 */ 441 public ImmutableDoubleArray subArray(int startIndex, int endIndex) { 442 Preconditions.checkPositionIndexes(startIndex, endIndex, length()); 443 return startIndex == endIndex 444 ? EMPTY 445 : new ImmutableDoubleArray(array, start + startIndex, start + endIndex); 446 } 447 448 private Spliterator.OfDouble spliterator() { 449 return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED); 450 } 451 452 /** 453 * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code 454 * double} values are boxed into {@link Double} instances on demand, which can be very expensive. 455 * The returned list should be used once and discarded. For any usages beyond that, pass the 456 * returned list to {@link com.google.common.collect.ImmutableList#copyOf(Collection) 457 * ImmutableList.copyOf} and use that list instead. 458 */ 459 public List<Double> asList() { 460 /* 461 * Typically we cache this kind of thing, but much repeated use of this view is a performance 462 * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if 463 * they never use this method. 464 */ 465 return new AsList(this); 466 } 467 468 static class AsList extends AbstractList<Double> implements RandomAccess, Serializable { 469 private final ImmutableDoubleArray parent; 470 471 private AsList(ImmutableDoubleArray parent) { 472 this.parent = parent; 473 } 474 475 // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations 476 477 @Override 478 public int size() { 479 return parent.length(); 480 } 481 482 @Override 483 public Double get(int index) { 484 return parent.get(index); 485 } 486 487 @Override 488 public boolean contains(Object target) { 489 return indexOf(target) >= 0; 490 } 491 492 @Override 493 public int indexOf(Object target) { 494 return target instanceof Double ? parent.indexOf((Double) target) : -1; 495 } 496 497 @Override 498 public int lastIndexOf(Object target) { 499 return target instanceof Double ? parent.lastIndexOf((Double) target) : -1; 500 } 501 502 @Override 503 public List<Double> subList(int fromIndex, int toIndex) { 504 return parent.subArray(fromIndex, toIndex).asList(); 505 } 506 507 // The default List spliterator is not efficiently splittable 508 @Override 509 public Spliterator<Double> spliterator() { 510 return parent.spliterator(); 511 } 512 513 @Override 514 public boolean equals(@Nullable Object object) { 515 if (object instanceof AsList) { 516 AsList that = (AsList) object; 517 return this.parent.equals(that.parent); 518 } 519 // We could delegate to super now but it would still box too much 520 if (!(object instanceof List)) { 521 return false; 522 } 523 List<?> that = (List<?>) object; 524 if (this.size() != that.size()) { 525 return false; 526 } 527 int i = parent.start; 528 // Since `that` is very likely RandomAccess we could avoid allocating this iterator... 529 for (Object element : that) { 530 if (!(element instanceof Double) || !areEqual(parent.array[i++], (Double) element)) { 531 return false; 532 } 533 } 534 return true; 535 } 536 537 // Because we happen to use the same formula. If that changes, just don't override this. 538 @Override 539 public int hashCode() { 540 return parent.hashCode(); 541 } 542 543 @Override 544 public String toString() { 545 return parent.toString(); 546 } 547 } 548 549 /** 550 * Returns {@code true} if {@code object} is an {@code ImmutableDoubleArray} containing the same 551 * values as this one, in the same order. Values are compared as if by {@link Double#equals}. 552 */ 553 @Override 554 public boolean equals(@Nullable Object object) { 555 if (object == this) { 556 return true; 557 } 558 if (!(object instanceof ImmutableDoubleArray)) { 559 return false; 560 } 561 ImmutableDoubleArray that = (ImmutableDoubleArray) object; 562 if (this.length() != that.length()) { 563 return false; 564 } 565 for (int i = 0; i < length(); i++) { 566 if (!areEqual(this.get(i), that.get(i))) { 567 return false; 568 } 569 } 570 return true; 571 } 572 573 // Match the behavior of Double.equals() 574 private static boolean areEqual(double a, double b) { 575 return Double.doubleToLongBits(a) == Double.doubleToLongBits(b); 576 } 577 578 /** Returns an unspecified hash code for the contents of this immutable array. */ 579 @Override 580 public int hashCode() { 581 int hash = 1; 582 for (int i = start; i < end; i++) { 583 hash *= 31; 584 hash += Doubles.hashCode(array[i]); 585 } 586 return hash; 587 } 588 589 /** 590 * Returns a string representation of this array in the same form as {@link 591 * Arrays#toString(double[])}, for example {@code "[1, 2, 3]"}. 592 */ 593 @Override 594 public String toString() { 595 if (isEmpty()) { 596 return "[]"; 597 } 598 StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine 599 builder.append('[').append(array[start]); 600 601 for (int i = start + 1; i < end; i++) { 602 builder.append(", ").append(array[i]); 603 } 604 builder.append(']'); 605 return builder.toString(); 606 } 607 608 /** 609 * Returns an immutable array containing the same values as {@code this} array. This is logically 610 * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance 611 * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range 612 * of values, resulting in an equivalent array with a smaller memory footprint. 613 */ 614 public ImmutableDoubleArray trimmed() { 615 return isPartialView() ? new ImmutableDoubleArray(toArray()) : this; 616 } 617 618 private boolean isPartialView() { 619 return start > 0 || end < array.length; 620 } 621 622 Object writeReplace() { 623 return trimmed(); 624 } 625 626 Object readResolve() { 627 return isEmpty() ? EMPTY : this; 628 } 629}