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