alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Java example source code file (Collections2.java)

This example Java source code file (Collections2.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

abstractcollection, annotation, beta, collection, comparator, filteredcollection, function, immutablelist, iterator, list, object, orderedpermutationcollection, override, predicate, util

The Collections2.java Java example source code

/*
 * Copyright (C) 2008 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Predicates.and;
import static com.google.common.base.Predicates.in;
import static com.google.common.base.Predicates.not;
import static com.google.common.collect.CollectPreconditions.checkNonnegative;
import static com.google.common.math.LongMath.binomial;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.math.IntMath;
import com.google.common.primitives.Ints;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import javax.annotation.Nullable;

/**
 * Provides static methods for working with {@code Collection} instances.
 *
 * @author Chris Povirk
 * @author Mike Bostock
 * @author Jared Levy
 * @since 2.0
 */
@GwtCompatible
public final class Collections2 {
  private Collections2() {}

  /**
   * Returns the elements of {@code unfiltered} that satisfy a predicate. The
   * returned collection is a live view of {@code unfiltered}; changes to one
   * affect the other.
   *
   * <p>The resulting collection's iterator does not support {@code remove()},
   * but all other collection methods are supported. When given an element that
   * doesn't satisfy the predicate, the collection's {@code add()} and {@code
   * addAll()} methods throw an {@link IllegalArgumentException}. When methods
   * such as {@code removeAll()} and {@code clear()} are called on the filtered
   * collection, only elements that satisfy the filter will be removed from the
   * underlying collection.
   *
   * <p>The returned collection isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered collection's methods, such as {@code size()},
   * iterate across every element in the underlying collection and determine
   * which elements satisfy the filter. When a live view is <i>not needed,
   * it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
   * and use the copy.
   *
   * <p>Warning: {@code predicate} must be consistent with equals,
   * as documented at {@link Predicate#apply}. Do not provide a predicate such
   * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
   * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
   * functionality.)
   */
  // TODO(kevinb): how can we omit that Iterables link when building gwt
  // javadoc?
  public static <E> Collection filter(Collection unfiltered, Predicate predicate) {
    if (unfiltered instanceof FilteredCollection) {
      // Support clear(), removeAll(), and retainAll() when filtering a filtered
      // collection.
      return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
    }

    return new FilteredCollection<E>(checkNotNull(unfiltered), checkNotNull(predicate));
  }

  /**
   * Delegates to {@link Collection#contains}. Returns {@code false} if the
   * {@code contains} method throws a {@code ClassCastException} or
   * {@code NullPointerException}.
   */
  static boolean safeContains(Collection<?> collection, @Nullable Object object) {
    checkNotNull(collection);
    try {
      return collection.contains(object);
    } catch (ClassCastException e) {
      return false;
    } catch (NullPointerException e) {
      return false;
    }
  }

  /**
   * Delegates to {@link Collection#remove}. Returns {@code false} if the
   * {@code remove} method throws a {@code ClassCastException} or
   * {@code NullPointerException}.
   */
  static boolean safeRemove(Collection<?> collection, @Nullable Object object) {
    checkNotNull(collection);
    try {
      return collection.remove(object);
    } catch (ClassCastException e) {
      return false;
    } catch (NullPointerException e) {
      return false;
    }
  }

  static class FilteredCollection<E> extends AbstractCollection {
    final Collection<E> unfiltered;
    final Predicate<? super E> predicate;

    FilteredCollection(Collection<E> unfiltered, Predicate predicate) {
      this.unfiltered = unfiltered;
      this.predicate = predicate;
    }

    FilteredCollection<E> createCombined(Predicate newPredicate) {
      return new FilteredCollection<E>(unfiltered, Predicates.and(predicate, newPredicate));
      // .<E> above needed to compile in JDK 5
    }

    @Override
    public boolean add(E element) {
      checkArgument(predicate.apply(element));
      return unfiltered.add(element);
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
      for (E element : collection) {
        checkArgument(predicate.apply(element));
      }
      return unfiltered.addAll(collection);
    }

    @Override
    public void clear() {
      Iterables.removeIf(unfiltered, predicate);
    }

    @Override
    public boolean contains(@Nullable Object element) {
      if (safeContains(unfiltered, element)) {
        @SuppressWarnings("unchecked") // element is in unfiltered, so it must be an E
        E e = (E) element;
        return predicate.apply(e);
      }
      return false;
    }

    @Override
    public boolean containsAll(Collection<?> collection) {
      return containsAllImpl(this, collection);
    }

    @Override
    public boolean isEmpty() {
      return !Iterables.any(unfiltered, predicate);
    }

    @Override
    public Iterator<E> iterator() {
      return Iterators.filter(unfiltered.iterator(), predicate);
    }

    @Override
    public boolean remove(Object element) {
      return contains(element) && unfiltered.remove(element);
    }

    @Override
    public boolean removeAll(final Collection<?> collection) {
      return Iterables.removeIf(unfiltered, and(predicate, Predicates.<Object>in(collection)));
    }

    @Override
    public boolean retainAll(final Collection<?> collection) {
      return Iterables.removeIf(unfiltered, and(predicate, not(Predicates.<Object>in(collection))));
    }

    @Override
    public int size() {
      return Iterators.size(iterator());
    }

    @Override
    public Object[] toArray() {
      // creating an ArrayList so filtering happens once
      return Lists.newArrayList(iterator()).toArray();
    }

    @Override
    public <T> T[] toArray(T[] array) {
      return Lists.newArrayList(iterator()).toArray(array);
    }
  }

  /**
   * Returns a collection that applies {@code function} to each element of
   * {@code fromCollection}. The returned collection is a live view of {@code
   * fromCollection}; changes to one affect the other.
   *
   * <p>The returned collection's {@code add()} and {@code addAll()} methods
   * throw an {@link UnsupportedOperationException}. All other collection
   * methods are supported, as long as {@code fromCollection} supports them.
   *
   * <p>The returned collection isn't threadsafe or serializable, even if
   * {@code fromCollection} is.
   *
   * <p>When a live view is not needed, it may be faster to copy the
   * transformed collection and use the copy.
   *
   * <p>If the input {@code Collection} is known to be a {@code List}, consider
   * {@link Lists#transform}. If only an {@code Iterable} is available, use
   * {@link Iterables#transform}.
   */
  public static <F, T> Collection transform(
      Collection<F> fromCollection, Function function) {
    return new TransformedCollection<F, T>(fromCollection, function);
  }

  static class TransformedCollection<F, T> extends AbstractCollection {
    final Collection<F> fromCollection;
    final Function<? super F, ? extends T> function;

    TransformedCollection(Collection<F> fromCollection, Function function) {
      this.fromCollection = checkNotNull(fromCollection);
      this.function = checkNotNull(function);
    }

    @Override
    public void clear() {
      fromCollection.clear();
    }

    @Override
    public boolean isEmpty() {
      return fromCollection.isEmpty();
    }

    @Override
    public Iterator<T> iterator() {
      return Iterators.transform(fromCollection.iterator(), function);
    }

    @Override
    public int size() {
      return fromCollection.size();
    }
  }

  /**
   * Returns {@code true} if the collection {@code self} contains all of the
   * elements in the collection {@code c}.
   *
   * <p>This method iterates over the specified collection {@code c}, checking
   * each element returned by the iterator in turn to see if it is contained in
   * the specified collection {@code self}. If all elements are so contained,
   * {@code true} is returned, otherwise {@code false}.
   *
   * @param self a collection which might contain all elements in {@code c}
   * @param c a collection whose elements might be contained by {@code self}
   */
  static boolean containsAllImpl(Collection<?> self, Collection c) {
    return Iterables.all(c, Predicates.in(self));
  }

  /**
   * An implementation of {@link Collection#toString()}.
   */
  static String toStringImpl(final Collection<?> collection) {
    StringBuilder sb = newStringBuilderForCollection(collection.size()).append('[');
    STANDARD_JOINER.appendTo(
        sb,
        Iterables.transform(
            collection,
            new Function<Object, Object>() {
              @Override
              public Object apply(Object input) {
                return input == collection ? "(this Collection)" : input;
              }
            }));
    return sb.append(']').toString();
  }

  /**
   * Returns best-effort-sized StringBuilder based on the given collection size.
   */
  static StringBuilder newStringBuilderForCollection(int size) {
    checkNonnegative(size, "size");
    return new StringBuilder((int) Math.min(size * 8L, Ints.MAX_POWER_OF_TWO));
  }

  /**
   * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
   */
  static <T> Collection cast(Iterable iterable) {
    return (Collection<T>) iterable;
  }

  static final Joiner STANDARD_JOINER = Joiner.on(", ").useForNull("null");

  /**
   * Returns a {@link Collection} of all the permutations of the specified
   * {@link Iterable}.
   *
   * <p>Notes: This is an implementation of the algorithm for
   * Lexicographical Permutations Generation, described in Knuth's "The Art of
   * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The
   * iteration order follows the lexicographical order. This means that
   * the first permutation will be in ascending order, and the last will be in
   * descending order.
   *
   * <p>Duplicate elements are considered equal. For example, the list [1, 1]
   * will have only one permutation, instead of two. This is why the elements
   * have to implement {@link Comparable}.
   *
   * <p>An empty iterable has only one permutation, which is an empty list.
   *
   * <p>This method is equivalent to
   * {@code Collections2.orderedPermutations(list, Ordering.natural())}.
   *
   * @param elements the original iterable whose elements have to be permuted.
   * @return an immutable {@link Collection} containing all the different
   *     permutations of the original iterable.
   * @throws NullPointerException if the specified iterable is null or has any
   *     null elements.
   * @since 12.0
   */
  @Beta
  public static <E extends Comparable Collection> orderedPermutations(
      Iterable<E> elements) {
    return orderedPermutations(elements, Ordering.natural());
  }

  /**
   * Returns a {@link Collection} of all the permutations of the specified
   * {@link Iterable} using the specified {@link Comparator} for establishing
   * the lexicographical ordering.
   *
   * <p>Examples: 
   {@code
   *
   *   for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) {
   *     println(perm);
   *   }
   *   // -> ["a", "b", "c"]
   *   // -> ["a", "c", "b"]
   *   // -> ["b", "a", "c"]
   *   // -> ["b", "c", "a"]
   *   // -> ["c", "a", "b"]
   *   // -> ["c", "b", "a"]
   *
   *   for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) {
   *     println(perm);
   *   }
   *   // -> [1, 1, 2, 2]
   *   // -> [1, 2, 1, 2]
   *   // -> [1, 2, 2, 1]
   *   // -> [2, 1, 1, 2]
   *   // -> [2, 1, 2, 1]
   *   // -> [2, 2, 1, 1]}</pre>
   *
   * <p>Notes: This is an implementation of the algorithm for
   * Lexicographical Permutations Generation, described in Knuth's "The Art of
   * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The
   * iteration order follows the lexicographical order. This means that
   * the first permutation will be in ascending order, and the last will be in
   * descending order.
   *
   * <p>Elements that compare equal are considered equal and no new permutations
   * are created by swapping them.
   *
   * <p>An empty iterable has only one permutation, which is an empty list.
   *
   * @param elements the original iterable whose elements have to be permuted.
   * @param comparator a comparator for the iterable's elements.
   * @return an immutable {@link Collection} containing all the different
   *     permutations of the original iterable.
   * @throws NullPointerException If the specified iterable is null, has any
   *     null elements, or if the specified comparator is null.
   * @since 12.0
   */
  @Beta
  public static <E> Collection> orderedPermutations(
      Iterable<E> elements, Comparator comparator) {
    return new OrderedPermutationCollection<E>(elements, comparator);
  }

  private static final class OrderedPermutationCollection<E> extends AbstractCollection> {
    final ImmutableList<E> inputList;
    final Comparator<? super E> comparator;
    final int size;

    OrderedPermutationCollection(Iterable<E> input, Comparator comparator) {
      this.inputList = Ordering.from(comparator).immutableSortedCopy(input);
      this.comparator = comparator;
      this.size = calculateSize(inputList, comparator);
    }

    /**
     * The number of permutations with repeated elements is calculated as
     * follows:
     * <ul>
     * <li>For an empty list, it is 1 (base case).
     * <li>When r numbers are added to a list of n-r elements, the number of
     * permutations is increased by a factor of (n choose r).</li>
     * </ul>
     */
    private static <E> int calculateSize(
        List<E> sortedInputList, Comparator comparator) {
      long permutations = 1;
      int n = 1;
      int r = 1;
      while (n < sortedInputList.size()) {
        int comparison = comparator.compare(sortedInputList.get(n - 1), sortedInputList.get(n));
        if (comparison < 0) {
          // We move to the next non-repeated element.
          permutations *= binomial(n, r);
          r = 0;
          if (!isPositiveInt(permutations)) {
            return Integer.MAX_VALUE;
          }
        }
        n++;
        r++;
      }
      permutations *= binomial(n, r);
      if (!isPositiveInt(permutations)) {
        return Integer.MAX_VALUE;
      }
      return (int) permutations;
    }

    @Override
    public int size() {
      return size;
    }

    @Override
    public boolean isEmpty() {
      return false;
    }

    @Override
    public Iterator<List iterator() {
      return new OrderedPermutationIterator<E>(inputList, comparator);
    }

    @Override
    public boolean contains(@Nullable Object obj) {
      if (obj instanceof List) {
        List<?> list = (List) obj;
        return isPermutation(inputList, list);
      }
      return false;
    }

    @Override
    public String toString() {
      return "orderedPermutationCollection(" + inputList + ")";
    }
  }

  private static final class OrderedPermutationIterator<E> extends AbstractIterator> {

    List<E> nextPermutation;
    final Comparator<? super E> comparator;

    OrderedPermutationIterator(List<E> list, Comparator comparator) {
      this.nextPermutation = Lists.newArrayList(list);
      this.comparator = comparator;
    }

    @Override
    protected List<E> computeNext() {
      if (nextPermutation == null) {
        return endOfData();
      }
      ImmutableList<E> next = ImmutableList.copyOf(nextPermutation);
      calculateNextPermutation();
      return next;
    }

    void calculateNextPermutation() {
      int j = findNextJ();
      if (j == -1) {
        nextPermutation = null;
        return;
      }

      int l = findNextL(j);
      Collections.swap(nextPermutation, j, l);
      int n = nextPermutation.size();
      Collections.reverse(nextPermutation.subList(j + 1, n));
    }

    int findNextJ() {
      for (int k = nextPermutation.size() - 2; k >= 0; k--) {
        if (comparator.compare(nextPermutation.get(k), nextPermutation.get(k + 1)) < 0) {
          return k;
        }
      }
      return -1;
    }

    int findNextL(int j) {
      E ak = nextPermutation.get(j);
      for (int l = nextPermutation.size() - 1; l > j; l--) {
        if (comparator.compare(ak, nextPermutation.get(l)) < 0) {
          return l;
        }
      }
      throw new AssertionError("this statement should be unreachable");
    }
  }

  /**
   * Returns a {@link Collection} of all the permutations of the specified
   * {@link Collection}.
   *
   * <p>Notes: This is an implementation of the Plain Changes algorithm
   * for permutations generation, described in Knuth's "The Art of Computer
   * Programming", Volume 4, Chapter 7, Section 7.2.1.2.
   *
   * <p>If the input list contains equal elements, some of the generated
   * permutations will be equal.
   *
   * <p>An empty collection has only one permutation, which is an empty list.
   *
   * @param elements the original collection whose elements have to be permuted.
   * @return an immutable {@link Collection} containing all the different
   *     permutations of the original collection.
   * @throws NullPointerException if the specified collection is null or has any
   *     null elements.
   * @since 12.0
   */
  @Beta
  public static <E> Collection> permutations(Collection elements) {
    return new PermutationCollection<E>(ImmutableList.copyOf(elements));
  }

  private static final class PermutationCollection<E> extends AbstractCollection> {
    final ImmutableList<E> inputList;

    PermutationCollection(ImmutableList<E> input) {
      this.inputList = input;
    }

    @Override
    public int size() {
      return IntMath.factorial(inputList.size());
    }

    @Override
    public boolean isEmpty() {
      return false;
    }

    @Override
    public Iterator<List iterator() {
      return new PermutationIterator<E>(inputList);
    }

    @Override
    public boolean contains(@Nullable Object obj) {
      if (obj instanceof List) {
        List<?> list = (List) obj;
        return isPermutation(inputList, list);
      }
      return false;
    }

    @Override
    public String toString() {
      return "permutations(" + inputList + ")";
    }
  }

  private static class PermutationIterator<E> extends AbstractIterator> {
    final List<E> list;
    final int[] c;
    final int[] o;
    int j;

    PermutationIterator(List<E> list) {
      this.list = new ArrayList<E>(list);
      int n = list.size();
      c = new int[n];
      o = new int[n];
      Arrays.fill(c, 0);
      Arrays.fill(o, 1);
      j = Integer.MAX_VALUE;
    }

    @Override
    protected List<E> computeNext() {
      if (j <= 0) {
        return endOfData();
      }
      ImmutableList<E> next = ImmutableList.copyOf(list);
      calculateNextPermutation();
      return next;
    }

    void calculateNextPermutation() {
      j = list.size() - 1;
      int s = 0;

      // Handle the special case of an empty list. Skip the calculation of the
      // next permutation.
      if (j == -1) {
        return;
      }

      while (true) {
        int q = c[j] + o[j];
        if (q < 0) {
          switchDirection();
          continue;
        }
        if (q == j + 1) {
          if (j == 0) {
            break;
          }
          s++;
          switchDirection();
          continue;
        }

        Collections.swap(list, j - c[j] + s, j - q + s);
        c[j] = q;
        break;
      }
    }

    void switchDirection() {
      o[j] = -o[j];
      j--;
    }
  }

  /**
   * Returns {@code true} if the second list is a permutation of the first.
   */
  private static boolean isPermutation(List<?> first, List second) {
    if (first.size() != second.size()) {
      return false;
    }
    Multiset<?> firstMultiset = HashMultiset.create(first);
    Multiset<?> secondMultiset = HashMultiset.create(second);
    return firstMultiset.equals(secondMultiset);
  }

  private static boolean isPositiveInt(long n) {
    return n >= 0 && n <= Integer.MAX_VALUE;
  }
}

Other Java examples (source code examples)

Here is a short list of links related to this Java Collections2.java source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.