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