1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkNotNull; 18 19import com.google.common.annotations.GwtCompatible; 20import com.google.common.base.Function; 21import com.google.common.collect.Multiset.Entry; 22 23import java.util.Arrays; 24import java.util.Collection; 25import java.util.Collections; 26import java.util.Comparator; 27import java.util.Iterator; 28import java.util.List; 29import java.util.Set; 30import java.util.SortedSet; 31 32/** 33 * Utilities for dealing with sorted collections of all types. 34 * 35 * @author Louis Wasserman 36 */ 37@GwtCompatible 38final class SortedIterables { 39 private SortedIterables() {} 40 41 /** 42 * Returns {@code true} if {@code elements} is a sorted collection using an ordering equivalent 43 * to {@code comparator}. 44 */ 45 public static boolean hasSameComparator(Comparator<?> comparator, Iterable<?> elements) { 46 checkNotNull(comparator); 47 checkNotNull(elements); 48 Comparator<?> comparator2; 49 if (elements instanceof SortedSet) { 50 SortedSet<?> sortedSet = (SortedSet<?>) elements; 51 comparator2 = sortedSet.comparator(); 52 if (comparator2 == null) { 53 comparator2 = (Comparator) Ordering.natural(); 54 } 55 } else if (elements instanceof SortedIterable) { 56 comparator2 = ((SortedIterable<?>) elements).comparator(); 57 } else { 58 comparator2 = null; 59 } 60 return comparator.equals(comparator2); 61 } 62 63 /** 64 * Returns a sorted collection of the unique elements according to the specified comparator. Does 65 * not check for null. 66 */ 67 @SuppressWarnings("unchecked") 68 public static <E> Collection<E> sortedUnique( 69 Comparator<? super E> comparator, Iterator<E> elements) { 70 SortedSet<E> sortedSet = Sets.newTreeSet(comparator); 71 Iterators.addAll(sortedSet, elements); 72 return sortedSet; 73 } 74 75 /** 76 * Returns a sorted collection of the unique elements according to the specified comparator. Does 77 * not check for null. 78 */ 79 @SuppressWarnings("unchecked") 80 public static <E> Collection<E> sortedUnique( 81 Comparator<? super E> comparator, Iterable<E> elements) { 82 if (elements instanceof Multiset) { 83 elements = ((Multiset<E>) elements).elementSet(); 84 } 85 if (elements instanceof Set) { 86 if (hasSameComparator(comparator, elements)) { 87 return (Set<E>) elements; 88 } 89 List<E> list = Lists.newArrayList(elements); 90 Collections.sort(list, comparator); 91 return list; 92 } 93 E[] array = (E[]) Iterables.toArray(elements); 94 if (!hasSameComparator(comparator, elements)) { 95 Arrays.sort(array, comparator); 96 } 97 return uniquifySortedArray(comparator, array); 98 } 99 100 private static <E> Collection<E> uniquifySortedArray( 101 Comparator<? super E> comparator, E[] array) { 102 if (array.length == 0) { 103 return Collections.emptySet(); 104 } 105 int length = 1; 106 for (int i = 1; i < array.length; i++) { 107 int cmp = comparator.compare(array[i], array[length - 1]); 108 if (cmp != 0) { 109 array[length++] = array[i]; 110 } 111 } 112 if (length < array.length) { 113 array = ObjectArrays.arraysCopyOf(array, length); 114 } 115 return Arrays.asList(array); 116 } 117 118 /** 119 * Returns a collection of multiset entries representing the counts of the distinct elements, in 120 * sorted order. Does not check for null. 121 */ 122 public static <E> Collection<Multiset.Entry<E>> sortedCounts( 123 Comparator<? super E> comparator, Iterator<E> elements) { 124 TreeMultiset<E> multiset = TreeMultiset.create(comparator); 125 Iterators.addAll(multiset, elements); 126 return multiset.entrySet(); 127 } 128 129 /** 130 * Returns a collection of multiset entries representing the counts of the distinct elements, in 131 * sorted order. Does not check for null. 132 */ 133 public static <E> Collection<Multiset.Entry<E>> sortedCounts( 134 Comparator<? super E> comparator, Iterable<E> elements) { 135 if (elements instanceof Multiset) { 136 Multiset<E> multiset = (Multiset<E>) elements; 137 if (hasSameComparator(comparator, elements)) { 138 return multiset.entrySet(); 139 } 140 List<Multiset.Entry<E>> entries = Lists.newArrayList(multiset.entrySet()); 141 Collections.sort( 142 entries, Ordering.from(comparator).onResultOf(new Function<Multiset.Entry<E>, E>() { 143 @Override 144 public E apply(Entry<E> entry) { 145 return entry.getElement(); 146 } 147 })); 148 return entries; 149 } else if (elements instanceof Set) { // known distinct 150 Collection<E> sortedElements; 151 if (hasSameComparator(comparator, elements)) { 152 sortedElements = (Collection<E>) elements; 153 } else { 154 List<E> list = Lists.newArrayList(elements); 155 Collections.sort(list, comparator); 156 sortedElements = list; 157 } 158 return singletonEntries(sortedElements); 159 } else if (hasSameComparator(comparator, elements)) { 160 E current = null; 161 int currentCount = 0; 162 List<Multiset.Entry<E>> sortedEntries = Lists.newArrayList(); 163 for (E e : elements) { 164 if (currentCount > 0) { 165 if (comparator.compare(current, e) == 0) { 166 currentCount++; 167 } else { 168 sortedEntries.add(Multisets.immutableEntry(current, currentCount)); 169 current = e; 170 currentCount = 1; 171 } 172 } else { 173 current = e; 174 currentCount = 1; 175 } 176 } 177 if (currentCount > 0) { 178 sortedEntries.add(Multisets.immutableEntry(current, currentCount)); 179 } 180 return sortedEntries; 181 } 182 TreeMultiset<E> multiset = TreeMultiset.create(comparator); 183 Iterables.addAll(multiset, elements); 184 return multiset.entrySet(); 185 } 186 187 static <E> Collection<Multiset.Entry<E>> singletonEntries(Collection<E> set) { 188 return Collections2.transform(set, new Function<E, Multiset.Entry<E>>() { 189 @Override 190 public Entry<E> apply(E elem) { 191 return Multisets.immutableEntry(elem, 1); 192 } 193 }); 194 } 195} 196