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