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