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}