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