    001    /*
    002     * Copyright (C) 2008 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.primitives;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkElementIndex;
    021    import static com.google.common.base.Preconditions.checkNotNull;
    022    import static com.google.common.base.Preconditions.checkPositionIndexes;
    023
    024    import com.google.common.annotations.GwtCompatible;
    025    import com.google.common.annotations.GwtIncompatible;
    026
    027    import java.io.Serializable;
    028    import java.util.AbstractList;
    029    import java.util.Arrays;
    030    import java.util.Collection;
    031    import java.util.Collections;
    032    import java.util.Comparator;
    033    import java.util.List;
    034    import java.util.RandomAccess;
    035
    036    /**
    037     * Static utility methods pertaining to {@code int} primitives, that are not
    038     * already found in either {@link Integer} or {@link Arrays}.
    039     *
    040     * @author Kevin Bourrillion
    041     * @since 1.0
    042     */
    043    @GwtCompatible(emulated = true)
    044    public final class Ints {
    045      private Ints() {}
    046
    047      /**
    048       * The number of bytes required to represent a primitive {@code int}
    049       * value.
    050       */
    051      public static final int BYTES = Integer.SIZE / Byte.SIZE;
    052
    053      /**
    054       * The largest power of two that can be represented as an {@code int}.
    055       *
    056       * @since 10.0
    057       */
    058      public static final int MAX_POWER_OF_TWO = 1 << (Integer.SIZE - 2);
    059
    060      /**
    061       * Returns a hash code for {@code value}; equal to the result of invoking
    062       * {@code ((Integer) value).hashCode()}.
    063       *
    064       * @param value a primitive {@code int} value
    065       * @return a hash code for the value
    066       */
    067      public static int hashCode(int value) {
    068        return value;
    069      }
    070
    071      /**
    072       * Returns the {@code int} value that is equal to {@code value}, if possible.
    073       *
    074       * @param value any value in the range of the {@code int} type
    075       * @return the {@code int} value that equals {@code value}
    076       * @throws IllegalArgumentException if {@code value} is greater than {@link
    077       *     Integer#MAX_VALUE} or less than {@link Integer#MIN_VALUE}
    078       */
    079      public static int checkedCast(long value) {
    080        int result = (int) value;
    081        checkArgument(result == value, "Out of range: %s", value);
    082        return result;
    083      }
    084
    085      /**
    086       * Returns the {@code int} nearest in value to {@code value}.
    087       *
    088       * @param value any {@code long} value
    089       * @return the same value cast to {@code int} if it is in the range of the
    090       *     {@code int} type, {@link Integer#MAX_VALUE} if it is too large,
    091       *     or {@link Integer#MIN_VALUE} if it is too small
    092       */
    093      public static int saturatedCast(long value) {
    094        if (value > Integer.MAX_VALUE) {
    095          return Integer.MAX_VALUE;
    096        }
    097        if (value < Integer.MIN_VALUE) {
    098          return Integer.MIN_VALUE;
    099        }
    100        return (int) value;
    101      }
    102
    103      /**
    104       * Compares the two specified {@code int} values. The sign of the value
    105       * returned is the same as that of {@code ((Integer) a).compareTo(b)}.
    106       *
    107       * @param a the first {@code int} to compare
    108       * @param b the second {@code int} to compare
    109       * @return a negative value if {@code a} is less than {@code b}; a positive
    110       *     value if {@code a} is greater than {@code b}; or zero if they are equal
    111       */
    112      public static int compare(int a, int b) {
    113        return (a < b) ? -1 : ((a > b) ? 1 : 0);
    114      }
    115
    116      /**
    117       * Returns {@code true} if {@code target} is present as an element anywhere in
    118       * {@code array}.
    119       *
    120       * @param array an array of {@code int} values, possibly empty
    121       * @param target a primitive {@code int} value
    122       * @return {@code true} if {@code array[i] == target} for some value of {@code
    123       *     i}
    124       */
    125      public static boolean contains(int[] array, int target) {
    126        for (int value : array) {
    127          if (value == target) {
    128            return true;
    129          }
    130        }
    131        return false;
    132      }
    133
    134      /**
    135       * Returns the index of the first appearance of the value {@code target} in
    136       * {@code array}.
    137       *
    138       * @param array an array of {@code int} values, possibly empty
    139       * @param target a primitive {@code int} value
    140       * @return the least index {@code i} for which {@code array[i] == target}, or
    141       *     {@code -1} if no such index exists.
    142       */
    143      public static int indexOf(int[] array, int target) {
    144        return indexOf(array, target, 0, array.length);
    145      }
    146
    147      // TODO(kevinb): consider making this public
    148      private static int indexOf(
    149          int[] array, int target, int start, int end) {
    150        for (int i = start; i < end; i++) {
    151          if (array[i] == target) {
    152            return i;
    153          }
    154        }
    155        return -1;
    156      }
    157
    158      /**
    159       * Returns the start position of the first occurrence of the specified {@code
    160       * target} within {@code array}, or {@code -1} if there is no such occurrence.
    161       *
    162       * <p>More formally, returns the lowest index {@code i} such that {@code
    163       * java.util.Arrays.copyOfRange(array, i, i + target.length)} contains exactly
    164       * the same elements as {@code target}.
    165       *
    166       * @param array the array to search for the sequence {@code target}
    167       * @param target the array to search for as a sub-sequence of {@code array}
    168       */
    169      public static int indexOf(int[] array, int[] target) {
    170        checkNotNull(array, "array");
    171        checkNotNull(target, "target");
    172        if (target.length == 0) {
    173          return 0;
    174        }
    175
    176        outer:
    177        for (int i = 0; i < array.length - target.length + 1; i++) {
    178          for (int j = 0; j < target.length; j++) {
    179            if (array[i + j] != target[j]) {
    180              continue outer;
    181            }
    182          }
    183          return i;
    184        }
    185        return -1;
    186      }
    187
    188      /**
    189       * Returns the index of the last appearance of the value {@code target} in
    190       * {@code array}.
    191       *
    192       * @param array an array of {@code int} values, possibly empty
    193       * @param target a primitive {@code int} value
    194       * @return the greatest index {@code i} for which {@code array[i] == target},
    195       *     or {@code -1} if no such index exists.
    196       */
    197      public static int lastIndexOf(int[] array, int target) {
    198        return lastIndexOf(array, target, 0, array.length);
    199      }
    200
    201      // TODO(kevinb): consider making this public
    202      private static int lastIndexOf(
    203          int[] array, int target, int start, int end) {
    204        for (int i = end - 1; i >= start; i--) {
    205          if (array[i] == target) {
    206            return i;
    207          }
    208        }
    209        return -1;
    210      }
    211
    212      /**
    213       * Returns the least value present in {@code array}.
    214       *
    215       * @param array a <i>nonempty</i> array of {@code int} values
    216       * @return the value present in {@code array} that is less than or equal to
    217       *     every other value in the array
    218       * @throws IllegalArgumentException if {@code array} is empty
    219       */
    220      public static int min(int... array) {
    221        checkArgument(array.length > 0);
    222        int min = array[0];
    223        for (int i = 1; i < array.length; i++) {
    224          if (array[i] < min) {
    225            min = array[i];
    226          }
    227        }
    228        return min;
    229      }
    230
    231      /**
    232       * Returns the greatest value present in {@code array}.
    233       *
    234       * @param array a <i>nonempty</i> array of {@code int} values
    235       * @return the value present in {@code array} that is greater than or equal to
    236       *     every other value in the array
    237       * @throws IllegalArgumentException if {@code array} is empty
    238       */
    239      public static int max(int... array) {
    240        checkArgument(array.length > 0);
    241        int max = array[0];
    242        for (int i = 1; i < array.length; i++) {
    243          if (array[i] > max) {
    244            max = array[i];
    245          }
    246        }
    247        return max;
    248      }
    249
    250      /**
    251       * Returns the values from each provided array combined into a single array.
    252       * For example, {@code concat(new int[] {a, b}, new int[] {}, new
    253       * int[] {c}} returns the array {@code {a, b, c}}.
    254       *
    255       * @param arrays zero or more {@code int} arrays
    256       * @return a single array containing all the values from the source arrays, in
    257       *     order
    258       */
    259      public static int[] concat(int[]... arrays) {
    260        int length = 0;
    261        for (int[] array : arrays) {
    262          length += array.length;
    263        }
    264        int[] result = new int[length];
    265        int pos = 0;
    266        for (int[] array : arrays) {
    267          System.arraycopy(array, 0, result, pos, array.length);
    268          pos += array.length;
    269        }
    270        return result;
    271      }
    272
    273      /**
    274       * Returns a big-endian representation of {@code value} in a 4-element byte
    275       * array; equivalent to {@code ByteBuffer.allocate(4).putInt(value).array()}.
    276       * For example, the input value {@code 0x12131415} would yield the byte array
    277       * {@code {0x12, 0x13, 0x14, 0x15}}.
    278       *
    279       * <p>If you need to convert and concatenate several values (possibly even of
    280       * different types), use a shared {@link java.nio.ByteBuffer} instance, or use
    281       * {@link com.google.common.io.ByteStreams#newDataOutput()} to get a growable
    282       * buffer.
    283       */
    284      @GwtIncompatible("doesn't work")
    285      public static byte[] toByteArray(int value) {
    286        return new byte[] {
    287            (byte) (value >> 24),
    288            (byte) (value >> 16),
    289            (byte) (value >> 8),
    290            (byte) value};
    291      }
    292
    293      /**
    294       * Returns the {@code int} value whose big-endian representation is stored in
    295       * the first 4 bytes of {@code bytes}; equivalent to {@code
    296       * ByteBuffer.wrap(bytes).getInt()}. For example, the input byte array {@code
    297       * {0x12, 0x13, 0x14, 0x15, 0x33}} would yield the {@code int} value {@code
    298       * 0x12131415}.
    299       *
    300       * <p>Arguably, it's preferable to use {@link java.nio.ByteBuffer}; that
    301       * library exposes much more flexibility at little cost in readability.
    302       *
    303       * @throws IllegalArgumentException if {@code bytes} has fewer than 4 elements
    304       */
    305      @GwtIncompatible("doesn't work")
    306      public static int fromByteArray(byte[] bytes) {
    307        checkArgument(bytes.length >= BYTES,
    308            "array too small: %s < %s", bytes.length, BYTES);
    309        return fromBytes(bytes[0], bytes[1], bytes[2], bytes[3]);
    310      }
    311
    312      /**
    313       * Returns the {@code int} value whose byte representation is the given 4
    314       * bytes, in big-endian order; equivalent to {@code Ints.fromByteArray(new
    315       * byte[] {b1, b2, b3, b4})}.
    316       *
    317       * @since 7.0
    318       */
    319      @GwtIncompatible("doesn't work")
    320      public static int fromBytes(byte b1, byte b2, byte b3, byte b4) {
    321        return b1 << 24 | (b2 & 0xFF) << 16 | (b3 & 0xFF) << 8 | (b4 & 0xFF);
    322      }
    323
    324      /**
    325       * Returns an array containing the same values as {@code array}, but
    326       * guaranteed to be of a specified minimum length. If {@code array} already
    327       * has a length of at least {@code minLength}, it is returned directly.
    328       * Otherwise, a new array of size {@code minLength + padding} is returned,
    329       * containing the values of {@code array}, and zeroes in the remaining places.
    330       *
    331       * @param array the source array
    332       * @param minLength the minimum length the returned array must guarantee
    333       * @param padding an extra amount to "grow" the array by if growth is
    334       *     necessary
    335       * @throws IllegalArgumentException if {@code minLength} or {@code padding} is
    336       *     negative
    337       * @return an array containing the values of {@code array}, with guaranteed
    338       *     minimum length {@code minLength}
    339       */
    340      public static int[] ensureCapacity(
    341          int[] array, int minLength, int padding) {
    342        checkArgument(minLength >= 0, "Invalid minLength: %s", minLength);
    343        checkArgument(padding >= 0, "Invalid padding: %s", padding);
    344        return (array.length < minLength)
    345            ? copyOf(array, minLength + padding)
    346            : array;
    347      }
    348
    349      // Arrays.copyOf() requires Java 6
    350      private static int[] copyOf(int[] original, int length) {
    351        int[] copy = new int[length];
    352        System.arraycopy(original, 0, copy, 0, Math.min(original.length, length));
    353        return copy;
    354      }
    355
    356      /**
    357       * Returns a string containing the supplied {@code int} values separated
    358       * by {@code separator}. For example, {@code join("-", 1, 2, 3)} returns
    359       * the string {@code "1-2-3"}.
    360       *
    361       * @param separator the text that should appear between consecutive values in
    362       *     the resulting string (but not at the start or end)
    363       * @param array an array of {@code int} values, possibly empty
    364       */
    365      public static String join(String separator, int... array) {
    366        checkNotNull(separator);
    367        if (array.length == 0) {
    368          return "";
    369        }
    370
    371        // For pre-sizing a builder, just get the right order of magnitude
    372        StringBuilder builder = new StringBuilder(array.length * 5);
    373        builder.append(array[0]);
    374        for (int i = 1; i < array.length; i++) {
    375          builder.append(separator).append(array[i]);
    376        }
    377        return builder.toString();
    378      }
    379
    380      /**
    381       * Returns a comparator that compares two {@code int} arrays
    382       * lexicographically. That is, it compares, using {@link
    383       * #compare(int, int)}), the first pair of values that follow any
    384       * common prefix, or when one array is a prefix of the other, treats the
    385       * shorter array as the lesser. For example, {@code [] < [1] < [1, 2] < [2]}.
    386       *
    387       * <p>The returned comparator is inconsistent with {@link
    388       * Object#equals(Object)} (since arrays support only identity equality), but
    389       * it is consistent with {@link Arrays#equals(int[], int[])}.
    390       *
    391       * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">
    392       *     Lexicographical order article at Wikipedia</a>
    393       * @since 2.0
    394       */
    395      public static Comparator<int[]> lexicographicalComparator() {
    396        return LexicographicalComparator.INSTANCE;
    397      }
    398
    399      private enum LexicographicalComparator implements Comparator<int[]> {
    400        INSTANCE;
    401
    402        @Override
    403        public int compare(int[] left, int[] right) {
    404          int minLength = Math.min(left.length, right.length);
    405          for (int i = 0; i < minLength; i++) {
    406            int result = Ints.compare(left[i], right[i]);
    407            if (result != 0) {
    408              return result;
    409            }
    410          }
    411          return left.length - right.length;
    412        }
    413      }
    414
    415      /**
    416       * Copies a collection of {@code Integer} instances into a new array of
    417       * primitive {@code int} values.
    418       *
    419       * <p>Elements are copied from the argument collection as if by {@code
    420       * collection.toArray()}.  Calling this method is as thread-safe as calling
    421       * that method.
    422       *
    423       * @param collection a collection of {@code Integer} objects
    424       * @return an array containing the same values as {@code collection}, in the
    425       *     same order, converted to primitives
    426       * @throws NullPointerException if {@code collection} or any of its elements
    427       *     is null
    428       */
    429      public static int[] toArray(Collection<Integer> collection) {
    430        if (collection instanceof IntArrayAsList) {
    431          return ((IntArrayAsList) collection).toIntArray();
    432        }
    433
    434        Object[] boxedArray = collection.toArray();
    435        int len = boxedArray.length;
    436        int[] array = new int[len];
    437        for (int i = 0; i < len; i++) {
    438          // checkNotNull for GWT (do not optimize)
    439          array[i] = (Integer) checkNotNull(boxedArray[i]);
    440        }
    441        return array;
    442      }
    443
    444      /**
    445       * Returns a fixed-size list backed by the specified array, similar to {@link
    446       * Arrays#asList(Object[])}. The list supports {@link List#set(int, Object)},
    447       * but any attempt to set a value to {@code null} will result in a {@link
    448       * NullPointerException}.
    449       *
    450       * <p>The returned list maintains the values, but not the identities, of
    451       * {@code Integer} objects written to or read from it.  For example, whether
    452       * {@code list.get(0) == list.get(0)} is true for the returned list is
    453       * unspecified.
    454       *
    455       * @param backingArray the array to back the list
    456       * @return a list view of the array
    457       */
    458      public static List<Integer> asList(int... backingArray) {
    459        if (backingArray.length == 0) {
    460          return Collections.emptyList();
    461        }
    462        return new IntArrayAsList(backingArray);
    463      }
    464
    465      @GwtCompatible
    466      private static class IntArrayAsList extends AbstractList<Integer>
    467          implements RandomAccess, Serializable {
    468        final int[] array;
    469        final int start;
    470        final int end;
    471
    472        IntArrayAsList(int[] array) {
    473          this(array, 0, array.length);
    474        }
    475
    476        IntArrayAsList(int[] array, int start, int end) {
    477          this.array = array;
    478          this.start = start;
    479          this.end = end;
    480        }
    481
    482        @Override public int size() {
    483          return end - start;
    484        }
    485
    486        @Override public boolean isEmpty() {
    487          return false;
    488        }
    489
    490        @Override public Integer get(int index) {
    491          checkElementIndex(index, size());
    492          return array[start + index];
    493        }
    494
    495        @Override public boolean contains(Object target) {
    496          // Overridden to prevent a ton of boxing
    497          return (target instanceof Integer)
    498              && Ints.indexOf(array, (Integer) target, start, end) != -1;
    499        }
    500
    501        @Override public int indexOf(Object target) {
    502          // Overridden to prevent a ton of boxing
    503          if (target instanceof Integer) {
    504            int i = Ints.indexOf(array, (Integer) target, start, end);
    505            if (i >= 0) {
    506              return i - start;
    507            }
    508          }
    509          return -1;
    510        }
    511
    512        @Override public int lastIndexOf(Object target) {
    513          // Overridden to prevent a ton of boxing
    514          if (target instanceof Integer) {
    515            int i = Ints.lastIndexOf(array, (Integer) target, start, end);
    516            if (i >= 0) {
    517              return i - start;
    518            }
    519          }
    520          return -1;
    521        }
    522
    523        @Override public Integer set(int index, Integer element) {
    524          checkElementIndex(index, size());
    525          int oldValue = array[start + index];
    526          array[start + index] = checkNotNull(element);  // checkNotNull for GWT (do not optimize)
    527          return oldValue;
    528        }
    529
    530        @Override public List<Integer> subList(int fromIndex, int toIndex) {
    531          int size = size();
    532          checkPositionIndexes(fromIndex, toIndex, size);
    533          if (fromIndex == toIndex) {
    534            return Collections.emptyList();
    535          }
    536          return new IntArrayAsList(array, start + fromIndex, start + toIndex);
    537        }
    538
    539        @Override public boolean equals(Object object) {
    540          if (object == this) {
    541            return true;
    542          }
    543          if (object instanceof IntArrayAsList) {
    544            IntArrayAsList that = (IntArrayAsList) object;
    545            int size = size();
    546            if (that.size() != size) {
    547              return false;
    548            }
    549            for (int i = 0; i < size; i++) {
    550              if (array[start + i] != that.array[that.start + i]) {
    551                return false;
    552              }
    553            }
    554            return true;
    555          }
    556          return super.equals(object);
    557        }
    558
    559        @Override public int hashCode() {
    560          int result = 1;
    561          for (int i = start; i < end; i++) {
    562            result = 31 * result + Ints.hashCode(array[i]);
    563          }
    564          return result;
    565        }
    566
    567        @Override public String toString() {
    568          StringBuilder builder = new StringBuilder(size() * 5);
    569          builder.append('[').append(array[start]);
    570          for (int i = start + 1; i < end; i++) {
    571            builder.append(", ").append(array[i]);
    572          }
    573          return builder.append(']').toString();
    574        }
    575
    576        int[] toIntArray() {
    577          // Arrays.copyOfRange() requires Java 6
    578          int size = size();
    579          int[] result = new int[size];
    580          System.arraycopy(array, start, result, 0, size);
    581          return result;
    582        }
    583
    584        private static final long serialVersionUID = 0;
    585      }
    586    }