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