    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
    026    import java.io.Serializable;
    027    import java.util.AbstractList;
    028    import java.util.Arrays;
    029    import java.util.BitSet;
    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 boolean} primitives, that are not
    038     * already found in either {@link Boolean} or {@link Arrays}.
    039     *
    040     * @author Kevin Bourrillion
    041     * @since 1.0
    042     */
    043    @GwtCompatible
    044    public final class Booleans {
    045      private Booleans() {}
    046
    047      /**
    048       * Returns a hash code for {@code value}; equal to the result of invoking
    049       * {@code ((Boolean) value).hashCode()}.
    050       *
    051       * @param value a primitive {@code boolean} value
    052       * @return a hash code for the value
    053       */
    054      public static int hashCode(boolean value) {
    055        return value ? 1231 : 1237;
    056      }
    057
    058      /**
    059       * Compares the two specified {@code boolean} values in the standard way
    060       * ({@code false} is considered less than {@code true}). The sign of the
    061       * value returned is the same as that of {@code ((Boolean) a).compareTo(b)}.
    062       *
    063       * @param a the first {@code boolean} to compare
    064       * @param b the second {@code boolean} to compare
    065       * @return a positive number if only {@code a} is {@code true}, a negative
    066       *     number if only {@code b} is true, or zero if {@code a == b}
    067       */
    068      public static int compare(boolean a, boolean b) {
    069        return (a == b) ? 0 : (a ? 1 : -1);
    070      }
    071
    072      /**
    073       * Returns {@code true} if {@code target} is present as an element anywhere in
    074       * {@code array}.
    075       *
    076       * <p><b>Note:</b> consider representing the array as a {@link
    077       * BitSet} instead, replacing {@code Booleans.contains(array, true)}
    078       * with {@code !bitSet.isEmpty()} and {@code Booleans.contains(array, false)}
    079       * with {@code bitSet.nextClearBit(0) == sizeOfBitSet}.
    080       *
    081       * @param array an array of {@code boolean} values, possibly empty
    082       * @param target a primitive {@code boolean} value
    083       * @return {@code true} if {@code array[i] == target} for some value of {@code
    084       *     i}
    085       */
    086      public static boolean contains(boolean[] array, boolean target) {
    087        for (boolean value : array) {
    088          if (value == target) {
    089            return true;
    090          }
    091        }
    092        return false;
    093      }
    094
    095      /**
    096       * Returns the index of the first appearance of the value {@code target} in
    097       * {@code array}.
    098       *
    099       * <p><b>Note:</b> consider representing the array as a {@link BitSet}
    100       * instead, and using {@link BitSet#nextSetBit(int)} or {@link
    101       * BitSet#nextClearBit(int)}.
    102       *
    103       * @param array an array of {@code boolean} values, possibly empty
    104       * @param target a primitive {@code boolean} value
    105       * @return the least index {@code i} for which {@code array[i] == target}, or
    106       *     {@code -1} if no such index exists.
    107       */
    108      public static int indexOf(boolean[] array, boolean target) {
    109        return indexOf(array, target, 0, array.length);
    110      }
    111
    112      // TODO(kevinb): consider making this public
    113      private static int indexOf(
    114          boolean[] array, boolean target, int start, int end) {
    115        for (int i = start; i < end; i++) {
    116          if (array[i] == target) {
    117            return i;
    118          }
    119        }
    120        return -1;
    121      }
    122
    123      /**
    124       * Returns the start position of the first occurrence of the specified {@code
    125       * target} within {@code array}, or {@code -1} if there is no such occurrence.
    126       *
    127       * <p>More formally, returns the lowest index {@code i} such that {@code
    128       * java.util.Arrays.copyOfRange(array, i, i + target.length)} contains exactly
    129       * the same elements as {@code target}.
    130       *
    131       * @param array the array to search for the sequence {@code target}
    132       * @param target the array to search for as a sub-sequence of {@code array}
    133       */
    134      public static int indexOf(boolean[] array, boolean[] target) {
    135        checkNotNull(array, "array");
    136        checkNotNull(target, "target");
    137        if (target.length == 0) {
    138          return 0;
    139        }
    140
    141        outer:
    142        for (int i = 0; i < array.length - target.length + 1; i++) {
    143          for (int j = 0; j < target.length; j++) {
    144            if (array[i + j] != target[j]) {
    145              continue outer;
    146            }
    147          }
    148          return i;
    149        }
    150        return -1;
    151      }
    152
    153      /**
    154       * Returns the index of the last appearance of the value {@code target} in
    155       * {@code array}.
    156       *
    157       * @param array an array of {@code boolean} values, possibly empty
    158       * @param target a primitive {@code boolean} value
    159       * @return the greatest index {@code i} for which {@code array[i] == target},
    160       *     or {@code -1} if no such index exists.
    161       */
    162      public static int lastIndexOf(boolean[] array, boolean target) {
    163        return lastIndexOf(array, target, 0, array.length);
    164      }
    165
    166      // TODO(kevinb): consider making this public
    167      private static int lastIndexOf(
    168          boolean[] array, boolean target, int start, int end) {
    169        for (int i = end - 1; i >= start; i--) {
    170          if (array[i] == target) {
    171            return i;
    172          }
    173        }
    174        return -1;
    175      }
    176
    177      /**
    178       * Returns the values from each provided array combined into a single array.
    179       * For example, {@code concat(new boolean[] {a, b}, new boolean[] {}, new
    180       * boolean[] {c}} returns the array {@code {a, b, c}}.
    181       *
    182       * @param arrays zero or more {@code boolean} arrays
    183       * @return a single array containing all the values from the source arrays, in
    184       *     order
    185       */
    186      public static boolean[] concat(boolean[]... arrays) {
    187        int length = 0;
    188        for (boolean[] array : arrays) {
    189          length += array.length;
    190        }
    191        boolean[] result = new boolean[length];
    192        int pos = 0;
    193        for (boolean[] array : arrays) {
    194          System.arraycopy(array, 0, result, pos, array.length);
    195          pos += array.length;
    196        }
    197        return result;
    198      }
    199
    200      /**
    201       * Returns an array containing the same values as {@code array}, but
    202       * guaranteed to be of a specified minimum length. If {@code array} already
    203       * has a length of at least {@code minLength}, it is returned directly.
    204       * Otherwise, a new array of size {@code minLength + padding} is returned,
    205       * containing the values of {@code array}, and zeroes in the remaining places.
    206       *
    207       * @param array the source array
    208       * @param minLength the minimum length the returned array must guarantee
    209       * @param padding an extra amount to "grow" the array by if growth is
    210       *     necessary
    211       * @throws IllegalArgumentException if {@code minLength} or {@code padding} is
    212       *     negative
    213       * @return an array containing the values of {@code array}, with guaranteed
    214       *     minimum length {@code minLength}
    215       */
    216      public static boolean[] ensureCapacity(
    217          boolean[] array, int minLength, int padding) {
    218        checkArgument(minLength >= 0, "Invalid minLength: %s", minLength);
    219        checkArgument(padding >= 0, "Invalid padding: %s", padding);
    220        return (array.length < minLength)
    221            ? copyOf(array, minLength + padding)
    222            : array;
    223      }
    224
    225      // Arrays.copyOf() requires Java 6
    226      private static boolean[] copyOf(boolean[] original, int length) {
    227        boolean[] copy = new boolean[length];
    228        System.arraycopy(original, 0, copy, 0, Math.min(original.length, length));
    229        return copy;
    230      }
    231
    232      /**
    233       * Returns a string containing the supplied {@code boolean} values separated
    234       * by {@code separator}. For example, {@code join("-", false, true, false)}
    235       * returns the string {@code "false-true-false"}.
    236       *
    237       * @param separator the text that should appear between consecutive values in
    238       *     the resulting string (but not at the start or end)
    239       * @param array an array of {@code boolean} values, possibly empty
    240       */
    241      public static String join(String separator, boolean... array) {
    242        checkNotNull(separator);
    243        if (array.length == 0) {
    244          return "";
    245        }
    246
    247        // For pre-sizing a builder, just get the right order of magnitude
    248        StringBuilder builder = new StringBuilder(array.length * 7);
    249        builder.append(array[0]);
    250        for (int i = 1; i < array.length; i++) {
    251          builder.append(separator).append(array[i]);
    252        }
    253        return builder.toString();
    254      }
    255
    256      /**
    257       * Returns a comparator that compares two {@code boolean} arrays
    258       * lexicographically. That is, it compares, using {@link
    259       * #compare(boolean, boolean)}), the first pair of values that follow any
    260       * common prefix, or when one array is a prefix of the other, treats the
    261       * shorter array as the lesser. For example,
    262       * {@code [] < [false] < [false, true] < [true]}.
    263       *
    264       * <p>The returned comparator is inconsistent with {@link
    265       * Object#equals(Object)} (since arrays support only identity equality), but
    266       * it is consistent with {@link Arrays#equals(boolean[], boolean[])}.
    267       *
    268       * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">
    269       *     Lexicographical order article at Wikipedia</a>
    270       * @since 2.0
    271       */
    272      public static Comparator<boolean[]> lexicographicalComparator() {
    273        return LexicographicalComparator.INSTANCE;
    274      }
    275
    276      private enum LexicographicalComparator implements Comparator<boolean[]> {
    277        INSTANCE;
    278
    279        @Override
    280        public int compare(boolean[] left, boolean[] right) {
    281          int minLength = Math.min(left.length, right.length);
    282          for (int i = 0; i < minLength; i++) {
    283            int result = Booleans.compare(left[i], right[i]);
    284            if (result != 0) {
    285              return result;
    286            }
    287          }
    288          return left.length - right.length;
    289        }
    290      }
    291
    292      /**
    293       * Copies a collection of {@code Boolean} instances into a new array of
    294       * primitive {@code boolean} values.
    295       *
    296       * <p>Elements are copied from the argument collection as if by {@code
    297       * collection.toArray()}.  Calling this method is as thread-safe as calling
    298       * that method.
    299       *
    300       * <p><b>Note:</b> consider representing the collection as a {@link
    301       * BitSet} instead.
    302       *
    303       * @param collection a collection of {@code Boolean} objects
    304       * @return an array containing the same values as {@code collection}, in the
    305       *     same order, converted to primitives
    306       * @throws NullPointerException if {@code collection} or any of its elements
    307       *     is null
    308       */
    309      public static boolean[] toArray(Collection<Boolean> collection) {
    310        if (collection instanceof BooleanArrayAsList) {
    311          return ((BooleanArrayAsList) collection).toBooleanArray();
    312        }
    313
    314        Object[] boxedArray = collection.toArray();
    315        int len = boxedArray.length;
    316        boolean[] array = new boolean[len];
    317        for (int i = 0; i < len; i++) {
    318          // checkNotNull for GWT (do not optimize)
    319          array[i] = (Boolean) checkNotNull(boxedArray[i]);
    320        }
    321        return array;
    322      }
    323
    324      /**
    325       * Returns a fixed-size list backed by the specified array, similar to {@link
    326       * Arrays#asList(Object[])}. The list supports {@link List#set(int, Object)},
    327       * but any attempt to set a value to {@code null} will result in a {@link
    328       * NullPointerException}.
    329       *
    330       * <p>The returned list maintains the values, but not the identities, of
    331       * {@code Boolean} objects written to or read from it.  For example, whether
    332       * {@code list.get(0) == list.get(0)} is true for the returned list is
    333       * unspecified.
    334       *
    335       * @param backingArray the array to back the list
    336       * @return a list view of the array
    337       */
    338      public static List<Boolean> asList(boolean... backingArray) {
    339        if (backingArray.length == 0) {
    340          return Collections.emptyList();
    341        }
    342        return new BooleanArrayAsList(backingArray);
    343      }
    344
    345      @GwtCompatible
    346      private static class BooleanArrayAsList extends AbstractList<Boolean>
    347          implements RandomAccess, Serializable {
    348        final boolean[] array;
    349        final int start;
    350        final int end;
    351
    352        BooleanArrayAsList(boolean[] array) {
    353          this(array, 0, array.length);
    354        }
    355
    356        BooleanArrayAsList(boolean[] array, int start, int end) {
    357          this.array = array;
    358          this.start = start;
    359          this.end = end;
    360        }
    361
    362        @Override public int size() {
    363          return end - start;
    364        }
    365
    366        @Override public boolean isEmpty() {
    367          return false;
    368        }
    369
    370        @Override public Boolean get(int index) {
    371          checkElementIndex(index, size());
    372          return array[start + index];
    373        }
    374
    375        @Override public boolean contains(Object target) {
    376          // Overridden to prevent a ton of boxing
    377          return (target instanceof Boolean)
    378              && Booleans.indexOf(array, (Boolean) target, start, end) != -1;
    379        }
    380
    381        @Override public int indexOf(Object target) {
    382          // Overridden to prevent a ton of boxing
    383          if (target instanceof Boolean) {
    384            int i = Booleans.indexOf(array, (Boolean) target, start, end);
    385            if (i >= 0) {
    386              return i - start;
    387            }
    388          }
    389          return -1;
    390        }
    391
    392        @Override public int lastIndexOf(Object target) {
    393          // Overridden to prevent a ton of boxing
    394          if (target instanceof Boolean) {
    395            int i = Booleans.lastIndexOf(array, (Boolean) target, start, end);
    396            if (i >= 0) {
    397              return i - start;
    398            }
    399          }
    400          return -1;
    401        }
    402
    403        @Override public Boolean set(int index, Boolean element) {
    404          checkElementIndex(index, size());
    405          boolean oldValue = array[start + index];
    406          array[start + index] = checkNotNull(element);  // checkNotNull for GWT (do not optimize)
    407          return oldValue;
    408        }
    409
    410        @Override public List<Boolean> subList(int fromIndex, int toIndex) {
    411          int size = size();
    412          checkPositionIndexes(fromIndex, toIndex, size);
    413          if (fromIndex == toIndex) {
    414            return Collections.emptyList();
    415          }
    416          return new BooleanArrayAsList(array, start + fromIndex, start + toIndex);
    417        }
    418
    419        @Override public boolean equals(Object object) {
    420          if (object == this) {
    421            return true;
    422          }
    423          if (object instanceof BooleanArrayAsList) {
    424            BooleanArrayAsList that = (BooleanArrayAsList) object;
    425            int size = size();
    426            if (that.size() != size) {
    427              return false;
    428            }
    429            for (int i = 0; i < size; i++) {
    430              if (array[start + i] != that.array[that.start + i]) {
    431                return false;
    432              }
    433            }
    434            return true;
    435          }
    436          return super.equals(object);
    437        }
    438
    439        @Override public int hashCode() {
    440          int result = 1;
    441          for (int i = start; i < end; i++) {
    442            result = 31 * result + Booleans.hashCode(array[i]);
    443          }
    444          return result;
    445        }
    446
    447        @Override public String toString() {
    448          StringBuilder builder = new StringBuilder(size() * 7);
    449          builder.append(array[start] ? "[true" : "[false");
    450          for (int i = start + 1; i < end; i++) {
    451            builder.append(array[i] ? ", true" : ", false");
    452          }
    453          return builder.append(']').toString();
    454        }
    455
    456        boolean[] toBooleanArray() {
    457          // Arrays.copyOfRange() requires Java 6
    458          int size = size();
    459          boolean[] result = new boolean[size];
    460          System.arraycopy(array, start, result, 0, size);
    461          return result;
    462        }
    463
    464        private static final long serialVersionUID = 0;
    465      }
    466    }