/*
* Copyright (C) 2011 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.checkNotNull;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import com.google.common.collect.Multiset.Entry;
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 java.util.Set;
import java.util.SortedSet;
/**
* Utilities for dealing with sorted collections of all types.
*
* @author Louis Wasserman
*/
@GwtCompatible
final class SortedIterables {
private SortedIterables() {}
/**
* Returns {@code true} if {@code elements} is a sorted collection using an ordering equivalent
* to {@code comparator}.
*/
public static boolean hasSameComparator(Comparator<?> comparator, Iterable<?> elements) {
checkNotNull(comparator);
checkNotNull(elements);
Comparator<?> comparator2;
if (elements instanceof SortedSet) {
SortedSet<?> sortedSet = (SortedSet<?>) elements;
comparator2 = sortedSet.comparator();
if (comparator2 == null) {
comparator2 = (Comparator) Ordering.natural();
}
} else if (elements instanceof SortedIterable) {
comparator2 = ((SortedIterable<?>) elements).comparator();
} else {
comparator2 = null;
}
return comparator.equals(comparator2);
}
/**
* Returns a sorted collection of the unique elements according to the specified comparator. Does
* not check for null.
*/
@SuppressWarnings("unchecked")
public static <E> Collection<E> sortedUnique(
Comparator<? super E> comparator, Iterator<E> elements) {
SortedSet<E> sortedSet = Sets.newTreeSet(comparator);
Iterators.addAll(sortedSet, elements);
return sortedSet;
}
/**
* Returns a sorted collection of the unique elements according to the specified comparator. Does
* not check for null.
*/
@SuppressWarnings("unchecked")
public static <E> Collection<E> sortedUnique(
Comparator<? super E> comparator, Iterable<E> elements) {
if (elements instanceof Multiset) {
elements = ((Multiset<E>) elements).elementSet();
}
if (elements instanceof Set) {
if (hasSameComparator(comparator, elements)) {
return (Set<E>) elements;
}
List<E> list = Lists.newArrayList(elements);
Collections.sort(list, comparator);
return list;
}
E[] array = (E[]) Iterables.toArray(elements);
if (!hasSameComparator(comparator, elements)) {
Arrays.sort(array, comparator);
}
return uniquifySortedArray(comparator, array);
}
private static <E> Collection<E> uniquifySortedArray(
Comparator<? super E> comparator, E[] array) {
if (array.length == 0) {
return Collections.emptySet();
}
int length = 1;
for (int i = 1; i < array.length; i++) {
int cmp = comparator.compare(array[i], array[length - 1]);
if (cmp != 0) {
array[length++] = array[i];
}
}
if (length < array.length) {
array = ObjectArrays.arraysCopyOf(array, length);
}
return Arrays.asList(array);
}
/**
* Returns a collection of multiset entries representing the counts of the distinct elements, in
* sorted order. Does not check for null.
*/
public static <E> Collection<Multiset.Entry<E>> sortedCounts(
Comparator<? super E> comparator, Iterator<E> elements) {
TreeMultiset<E> multiset = TreeMultiset.create(comparator);
Iterators.addAll(multiset, elements);
return multiset.entrySet();
}
/**
* Returns a collection of multiset entries representing the counts of the distinct elements, in
* sorted order. Does not check for null.
*/
public static <E> Collection<Multiset.Entry<E>> sortedCounts(
Comparator<? super E> comparator, Iterable<E> elements) {
if (elements instanceof Multiset) {
Multiset<E> multiset = (Multiset<E>) elements;
if (hasSameComparator(comparator, elements)) {
return multiset.entrySet();
}
List<Multiset.Entry<E>> entries = Lists.newArrayList(multiset.entrySet());
Collections.sort(
entries, Ordering.from(comparator).onResultOf(new Function<Multiset.Entry<E>, E>() {
@Override
public E apply(Entry<E> entry) {
return entry.getElement();
}
}));
return entries;
} else if (elements instanceof Set) { // known distinct
Collection<E> sortedElements;
if (hasSameComparator(comparator, elements)) {
sortedElements = (Collection<E>) elements;
} else {
List<E> list = Lists.newArrayList(elements);
Collections.sort(list, comparator);
sortedElements = list;
}
return singletonEntries(sortedElements);
} else if (hasSameComparator(comparator, elements)) {
E current = null;
int currentCount = 0;
List<Multiset.Entry<E>> sortedEntries = Lists.newArrayList();
for (E e : elements) {
if (currentCount > 0) {
if (comparator.compare(current, e) == 0) {
currentCount++;
} else {
sortedEntries.add(Multisets.immutableEntry(current, currentCount));
current = e;
currentCount = 1;
}
} else {
current = e;
currentCount = 1;
}
}
if (currentCount > 0) {
sortedEntries.add(Multisets.immutableEntry(current, currentCount));
}
return sortedEntries;
}
TreeMultiset<E> multiset = TreeMultiset.create(comparator);
Iterables.addAll(multiset, elements);
return multiset.entrySet();
}
static <E> Collection<Multiset.Entry<E>> singletonEntries(Collection<E> set) {
return Collections2.transform(set, new Function<E, Multiset.Entry<E>>() {
@Override
public Entry<E> apply(E elem) {
return Multisets.immutableEntry(elem, 1);
}
});
}
}
|