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