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