1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.primitives;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.base.Preconditions.checkElementIndex;
21import static com.google.common.base.Preconditions.checkNotNull;
22import static com.google.common.base.Preconditions.checkPositionIndexes;
23
24import com.google.common.annotations.Beta;
25import com.google.common.annotations.GwtCompatible;
26
27import java.io.Serializable;
28import java.util.AbstractList;
29import java.util.Arrays;
30import java.util.BitSet;
31import java.util.Collection;
32import java.util.Collections;
33import java.util.Comparator;
34import java.util.List;
35import java.util.RandomAccess;
36
37/**
38 * Static utility methods pertaining to {@code boolean} primitives, that are not
39 * already found in either {@link Boolean} or {@link Arrays}.
40 *
41 * <p>See the Guava User Guide article on <a href=
42 * "http://code.google.com/p/guava-libraries/wiki/PrimitivesExplained">
43 * primitive utilities</a>.
44 *
45 * @author Kevin Bourrillion
46 * @since 1.0
47 */
48@GwtCompatible
49public final class Booleans {
50  private Booleans() {}
51
52  /**
53   * Returns a hash code for {@code value}; equal to the result of invoking
54   * {@code ((Boolean) value).hashCode()}.
55   *
56   * @param value a primitive {@code boolean} value
57   * @return a hash code for the value
58   */
59  public static int hashCode(boolean value) {
60    return value ? 1231 : 1237;
61  }
62
63  /**
64   * Compares the two specified {@code boolean} values in the standard way
65   * ({@code false} is considered less than {@code true}). The sign of the
66   * value returned is the same as that of {@code ((Boolean) a).compareTo(b)}.
67   *
68   * <p><b>Note for Java 7 and later:</b> this method should be treated as
69   * deprecated; use the equivalent {@link Boolean#compare} method instead.
70   *
71   * @param a the first {@code boolean} to compare
72   * @param b the second {@code boolean} to compare
73   * @return a positive number if only {@code a} is {@code true}, a negative
74   *     number if only {@code b} is true, or zero if {@code a == b}
75   */
76  public static int compare(boolean a, boolean b) {
77    return (a == b) ? 0 : (a ? 1 : -1);
78  }
79
80  /**
81   * Returns {@code true} if {@code target} is present as an element anywhere in
82   * {@code array}.
83   *
84   * <p><b>Note:</b> consider representing the array as a {@link
85   * BitSet} instead, replacing {@code Booleans.contains(array, true)}
86   * with {@code !bitSet.isEmpty()} and {@code Booleans.contains(array, false)}
87   * with {@code bitSet.nextClearBit(0) == sizeOfBitSet}.
88   *
89   * @param array an array of {@code boolean} values, possibly empty
90   * @param target a primitive {@code boolean} value
91   * @return {@code true} if {@code array[i] == target} for some value of {@code
92   *     i}
93   */
94  public static boolean contains(boolean[] array, boolean target) {
95    for (boolean value : array) {
96      if (value == target) {
97        return true;
98      }
99    }
100    return false;
101  }
102
103  /**
104   * Returns the index of the first appearance of the value {@code target} in
105   * {@code array}.
106   *
107   * <p><b>Note:</b> consider representing the array as a {@link BitSet}
108   * instead, and using {@link BitSet#nextSetBit(int)} or {@link
109   * BitSet#nextClearBit(int)}.
110   *
111   * @param array an array of {@code boolean} values, possibly empty
112   * @param target a primitive {@code boolean} value
113   * @return the least index {@code i} for which {@code array[i] == target}, or
114   *     {@code -1} if no such index exists.
115   */
116  public static int indexOf(boolean[] array, boolean target) {
117    return indexOf(array, target, 0, array.length);
118  }
119
120  // TODO(kevinb): consider making this public
121  private static int indexOf(
122      boolean[] array, boolean target, int start, int end) {
123    for (int i = start; i < end; i++) {
124      if (array[i] == target) {
125        return i;
126      }
127    }
128    return -1;
129  }
130
131  /**
132   * Returns the start position of the first occurrence of the specified {@code
133   * target} within {@code array}, or {@code -1} if there is no such occurrence.
134   *
135   * <p>More formally, returns the lowest index {@code i} such that {@code
136   * java.util.Arrays.copyOfRange(array, i, i + target.length)} contains exactly
137   * the same elements as {@code target}.
138   *
139   * @param array the array to search for the sequence {@code target}
140   * @param target the array to search for as a sub-sequence of {@code array}
141   */
142  public static int indexOf(boolean[] array, boolean[] target) {
143    checkNotNull(array, "array");
144    checkNotNull(target, "target");
145    if (target.length == 0) {
146      return 0;
147    }
148
149    outer:
150    for (int i = 0; i < array.length - target.length + 1; i++) {
151      for (int j = 0; j < target.length; j++) {
152        if (array[i + j] != target[j]) {
153          continue outer;
154        }
155      }
156      return i;
157    }
158    return -1;
159  }
160
161  /**
162   * Returns the index of the last appearance of the value {@code target} in
163   * {@code array}.
164   *
165   * @param array an array of {@code boolean} values, possibly empty
166   * @param target a primitive {@code boolean} value
167   * @return the greatest index {@code i} for which {@code array[i] == target},
168   *     or {@code -1} if no such index exists.
169   */
170  public static int lastIndexOf(boolean[] array, boolean target) {
171    return lastIndexOf(array, target, 0, array.length);
172  }
173
174  // TODO(kevinb): consider making this public
175  private static int lastIndexOf(
176      boolean[] array, boolean target, int start, int end) {
177    for (int i = end - 1; i >= start; i--) {
178      if (array[i] == target) {
179        return i;
180      }
181    }
182    return -1;
183  }
184
185  /**
186   * Returns the values from each provided array combined into a single array.
187   * For example, {@code concat(new boolean[] {a, b}, new boolean[] {}, new
188   * boolean[] {c}} returns the array {@code {a, b, c}}.
189   *
190   * @param arrays zero or more {@code boolean} arrays
191   * @return a single array containing all the values from the source arrays, in
192   *     order
193   */
194  public static boolean[] concat(boolean[]... arrays) {
195    int length = 0;
196    for (boolean[] array : arrays) {
197      length += array.length;
198    }
199    boolean[] result = new boolean[length];
200    int pos = 0;
201    for (boolean[] array : arrays) {
202      System.arraycopy(array, 0, result, pos, array.length);
203      pos += array.length;
204    }
205    return result;
206  }
207
208  /**
209   * Returns an array containing the same values as {@code array}, but
210   * guaranteed to be of a specified minimum length. If {@code array} already
211   * has a length of at least {@code minLength}, it is returned directly.
212   * Otherwise, a new array of size {@code minLength + padding} is returned,
213   * containing the values of {@code array}, and zeroes in the remaining places.
214   *
215   * @param array the source array
216   * @param minLength the minimum length the returned array must guarantee
217   * @param padding an extra amount to "grow" the array by if growth is
218   *     necessary
219   * @throws IllegalArgumentException if {@code minLength} or {@code padding} is
220   *     negative
221   * @return an array containing the values of {@code array}, with guaranteed
222   *     minimum length {@code minLength}
223   */
224  public static boolean[] ensureCapacity(
225      boolean[] array, int minLength, int padding) {
226    checkArgument(minLength >= 0, "Invalid minLength: %s", minLength);
227    checkArgument(padding >= 0, "Invalid padding: %s", padding);
228    return (array.length < minLength)
229        ? copyOf(array, minLength + padding)
230        : array;
231  }
232
233  // Arrays.copyOf() requires Java 6
234  private static boolean[] copyOf(boolean[] original, int length) {
235    boolean[] copy = new boolean[length];
236    System.arraycopy(original, 0, copy, 0, Math.min(original.length, length));
237    return copy;
238  }
239
240  /**
241   * Returns a string containing the supplied {@code boolean} values separated
242   * by {@code separator}. For example, {@code join("-", false, true, false)}
243   * returns the string {@code "false-true-false"}.
244   *
245   * @param separator the text that should appear between consecutive values in
246   *     the resulting string (but not at the start or end)
247   * @param array an array of {@code boolean} values, possibly empty
248   */
249  public static String join(String separator, boolean... array) {
250    checkNotNull(separator);
251    if (array.length == 0) {
252      return "";
253    }
254
255    // For pre-sizing a builder, just get the right order of magnitude
256    StringBuilder builder = new StringBuilder(array.length * 7);
257    builder.append(array[0]);
258    for (int i = 1; i < array.length; i++) {
259      builder.append(separator).append(array[i]);
260    }
261    return builder.toString();
262  }
263
264  /**
265   * Returns a comparator that compares two {@code boolean} arrays
266   * lexicographically. That is, it compares, using {@link
267   * #compare(boolean, boolean)}), the first pair of values that follow any
268   * common prefix, or when one array is a prefix of the other, treats the
269   * shorter array as the lesser. For example,
270   * {@code [] < [false] < [false, true] < [true]}.
271   *
272   * <p>The returned comparator is inconsistent with {@link
273   * Object#equals(Object)} (since arrays support only identity equality), but
274   * it is consistent with {@link Arrays#equals(boolean[], boolean[])}.
275   *
276   * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">
277   *     Lexicographical order article at Wikipedia</a>
278   * @since 2.0
279   */
280  public static Comparator<boolean[]> lexicographicalComparator() {
281    return LexicographicalComparator.INSTANCE;
282  }
283
284  private enum LexicographicalComparator implements Comparator<boolean[]> {
285    INSTANCE;
286
287    @Override
288    public int compare(boolean[] left, boolean[] right) {
289      int minLength = Math.min(left.length, right.length);
290      for (int i = 0; i < minLength; i++) {
291        int result = Booleans.compare(left[i], right[i]);
292        if (result != 0) {
293          return result;
294        }
295      }
296      return left.length - right.length;
297    }
298  }
299
300  /**
301   * Copies a collection of {@code Boolean} instances into a new array of
302   * primitive {@code boolean} values.
303   *
304   * <p>Elements are copied from the argument collection as if by {@code
305   * collection.toArray()}.  Calling this method is as thread-safe as calling
306   * that method.
307   *
308   * <p><b>Note:</b> consider representing the collection as a {@link
309   * BitSet} instead.
310   *
311   * @param collection a collection of {@code Boolean} objects
312   * @return an array containing the same values as {@code collection}, in the
313   *     same order, converted to primitives
314   * @throws NullPointerException if {@code collection} or any of its elements
315   *     is null
316   */
317  public static boolean[] toArray(Collection<Boolean> collection) {
318    if (collection instanceof BooleanArrayAsList) {
319      return ((BooleanArrayAsList) collection).toBooleanArray();
320    }
321
322    Object[] boxedArray = collection.toArray();
323    int len = boxedArray.length;
324    boolean[] array = new boolean[len];
325    for (int i = 0; i < len; i++) {
326      // checkNotNull for GWT (do not optimize)
327      array[i] = (Boolean) checkNotNull(boxedArray[i]);
328    }
329    return array;
330  }
331
332  /**
333   * Returns a fixed-size list backed by the specified array, similar to {@link
334   * Arrays#asList(Object[])}. The list supports {@link List#set(int, Object)},
335   * but any attempt to set a value to {@code null} will result in a {@link
336   * NullPointerException}.
337   *
338   * <p>The returned list maintains the values, but not the identities, of
339   * {@code Boolean} objects written to or read from it.  For example, whether
340   * {@code list.get(0) == list.get(0)} is true for the returned list is
341   * unspecified.
342   *
343   * @param backingArray the array to back the list
344   * @return a list view of the array
345   */
346  public static List<Boolean> asList(boolean... backingArray) {
347    if (backingArray.length == 0) {
348      return Collections.emptyList();
349    }
350    return new BooleanArrayAsList(backingArray);
351  }
352
353  @GwtCompatible
354  private static class BooleanArrayAsList extends AbstractList<Boolean>
355      implements RandomAccess, Serializable {
356    final boolean[] array;
357    final int start;
358    final int end;
359
360    BooleanArrayAsList(boolean[] array) {
361      this(array, 0, array.length);
362    }
363
364    BooleanArrayAsList(boolean[] array, int start, int end) {
365      this.array = array;
366      this.start = start;
367      this.end = end;
368    }
369
370    @Override public int size() {
371      return end - start;
372    }
373
374    @Override public boolean isEmpty() {
375      return false;
376    }
377
378    @Override public Boolean get(int index) {
379      checkElementIndex(index, size());
380      return array[start + index];
381    }
382
383    @Override public boolean contains(Object target) {
384      // Overridden to prevent a ton of boxing
385      return (target instanceof Boolean)
386          && Booleans.indexOf(array, (Boolean) target, start, end) != -1;
387    }
388
389    @Override public int indexOf(Object target) {
390      // Overridden to prevent a ton of boxing
391      if (target instanceof Boolean) {
392        int i = Booleans.indexOf(array, (Boolean) target, start, end);
393        if (i >= 0) {
394          return i - start;
395        }
396      }
397      return -1;
398    }
399
400    @Override public int lastIndexOf(Object target) {
401      // Overridden to prevent a ton of boxing
402      if (target instanceof Boolean) {
403        int i = Booleans.lastIndexOf(array, (Boolean) target, start, end);
404        if (i >= 0) {
405          return i - start;
406        }
407      }
408      return -1;
409    }
410
411    @Override public Boolean set(int index, Boolean element) {
412      checkElementIndex(index, size());
413      boolean oldValue = array[start + index];
414      // checkNotNull for GWT (do not optimize)
415      array[start + index] = checkNotNull(element);
416      return oldValue;
417    }
418
419    @Override public List<Boolean> subList(int fromIndex, int toIndex) {
420      int size = size();
421      checkPositionIndexes(fromIndex, toIndex, size);
422      if (fromIndex == toIndex) {
423        return Collections.emptyList();
424      }
425      return new BooleanArrayAsList(array, start + fromIndex, start + toIndex);
426    }
427
428    @Override public boolean equals(Object object) {
429      if (object == this) {
430        return true;
431      }
432      if (object instanceof BooleanArrayAsList) {
433        BooleanArrayAsList that = (BooleanArrayAsList) object;
434        int size = size();
435        if (that.size() != size) {
436          return false;
437        }
438        for (int i = 0; i < size; i++) {
439          if (array[start + i] != that.array[that.start + i]) {
440            return false;
441          }
442        }
443        return true;
444      }
445      return super.equals(object);
446    }
447
448    @Override public int hashCode() {
449      int result = 1;
450      for (int i = start; i < end; i++) {
451        result = 31 * result + Booleans.hashCode(array[i]);
452      }
453      return result;
454    }
455
456    @Override public String toString() {
457      StringBuilder builder = new StringBuilder(size() * 7);
458      builder.append(array[start] ? "[true" : "[false");
459      for (int i = start + 1; i < end; i++) {
460        builder.append(array[i] ? ", true" : ", false");
461      }
462      return builder.append(']').toString();
463    }
464
465    boolean[] toBooleanArray() {
466      // Arrays.copyOfRange() is not available under GWT
467      int size = size();
468      boolean[] result = new boolean[size];
469      System.arraycopy(array, start, result, 0, size);
470      return result;
471    }
472
473    private static final long serialVersionUID = 0;
474  }
475
476  /**
477   * Returns the number of {@code values} that are {@code true}.
478   *
479   * @since 16.0
480   */
481  @Beta
482  public static int countTrue(boolean... values) {
483    int count = 0;
484    for (boolean value : values) {
485      if (value) {
486        count++;
487      }
488    }
489    return count;
490  }
491}
492