1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not 5 * use this file except in compliance with the License. You may obtain a copy of 6 * the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13 * License for the specific language governing permissions and limitations under 14 * the License. 15 */ 16 17package com.google.common.collect; 18 19import com.google.common.annotations.GwtCompatible; 20import com.google.common.collect.Multiset.Entry; 21 22import java.util.Comparator; 23import java.util.Iterator; 24import java.util.NoSuchElementException; 25import java.util.Set; 26import java.util.SortedSet; 27 28/** 29 * Provides static utility methods for creating and working with 30 * {@link SortedMultiset} instances. 31 * 32 * @author Louis Wasserman 33 */ 34@GwtCompatible 35final class SortedMultisets { 36 private SortedMultisets() { 37 } 38 39 /** 40 * A skeleton implementation for {@link SortedMultiset#elementSet}. 41 */ 42 static abstract class ElementSet<E> extends Multisets.ElementSet<E> implements 43 SortedSet<E> { 44 @Override abstract SortedMultiset<E> multiset(); 45 46 @Override public Comparator<? super E> comparator() { 47 return multiset().comparator(); 48 } 49 50 @Override public SortedSet<E> subSet(E fromElement, E toElement) { 51 return multiset().subMultiset(fromElement, BoundType.CLOSED, toElement, 52 BoundType.OPEN).elementSet(); 53 } 54 55 @Override public SortedSet<E> headSet(E toElement) { 56 return multiset().headMultiset(toElement, BoundType.OPEN).elementSet(); 57 } 58 59 @Override public SortedSet<E> tailSet(E fromElement) { 60 return multiset().tailMultiset(fromElement, BoundType.CLOSED) 61 .elementSet(); 62 } 63 64 @Override public E first() { 65 return getElementOrThrow(multiset().firstEntry()); 66 } 67 68 @Override public E last() { 69 return getElementOrThrow(multiset().lastEntry()); 70 } 71 } 72 73 private static <E> E getElementOrThrow(Entry<E> entry) { 74 if (entry == null) { 75 throw new NoSuchElementException(); 76 } 77 return entry.getElement(); 78 } 79 80 /** 81 * A skeleton implementation of a descending multiset. Only needs 82 * {@code forwardMultiset()} and {@code entryIterator()}. 83 */ 84 static abstract class DescendingMultiset<E> extends ForwardingMultiset<E> 85 implements SortedMultiset<E> { 86 abstract SortedMultiset<E> forwardMultiset(); 87 88 private transient Comparator<? super E> comparator; 89 90 @Override public Comparator<? super E> comparator() { 91 Comparator<? super E> result = comparator; 92 if (result == null) { 93 return comparator = 94 Ordering.from(forwardMultiset().comparator()).<E>reverse(); 95 } 96 return result; 97 } 98 99 private transient SortedSet<E> elementSet; 100 101 @Override public SortedSet<E> elementSet() { 102 SortedSet<E> result = elementSet; 103 if (result == null) { 104 return elementSet = new SortedMultisets.ElementSet<E>() { 105 @Override SortedMultiset<E> multiset() { 106 return DescendingMultiset.this; 107 } 108 }; 109 } 110 return result; 111 } 112 113 @Override public Entry<E> pollFirstEntry() { 114 return forwardMultiset().pollLastEntry(); 115 } 116 117 @Override public Entry<E> pollLastEntry() { 118 return forwardMultiset().pollFirstEntry(); 119 } 120 121 @Override public SortedMultiset<E> headMultiset(E toElement, 122 BoundType boundType) { 123 return forwardMultiset().tailMultiset(toElement, boundType) 124 .descendingMultiset(); 125 } 126 127 @Override public SortedMultiset<E> subMultiset(E fromElement, 128 BoundType fromBoundType, E toElement, BoundType toBoundType) { 129 return forwardMultiset().subMultiset(toElement, toBoundType, fromElement, 130 fromBoundType).descendingMultiset(); 131 } 132 133 @Override public SortedMultiset<E> tailMultiset(E fromElement, 134 BoundType boundType) { 135 return forwardMultiset().headMultiset(fromElement, boundType) 136 .descendingMultiset(); 137 } 138 139 @Override protected Multiset<E> delegate() { 140 return forwardMultiset(); 141 } 142 143 @Override public SortedMultiset<E> descendingMultiset() { 144 return forwardMultiset(); 145 } 146 147 @Override public Entry<E> firstEntry() { 148 return forwardMultiset().lastEntry(); 149 } 150 151 @Override public Entry<E> lastEntry() { 152 return forwardMultiset().firstEntry(); 153 } 154 155 abstract Iterator<Entry<E>> entryIterator(); 156 157 private transient Set<Entry<E>> entrySet; 158 159 @Override public Set<Entry<E>> entrySet() { 160 Set<Entry<E>> result = entrySet; 161 return (result == null) ? entrySet = createEntrySet() : result; 162 } 163 164 Set<Entry<E>> createEntrySet() { 165 return new Multisets.EntrySet<E>() { 166 @Override Multiset<E> multiset() { 167 return DescendingMultiset.this; 168 } 169 170 @Override public Iterator<Entry<E>> iterator() { 171 return entryIterator(); 172 } 173 174 @Override public int size() { 175 return forwardMultiset().entrySet().size(); 176 } 177 }; 178 } 179 180 @Override public Iterator<E> iterator() { 181 return Multisets.iteratorImpl(this); 182 } 183 184 @Override public Object[] toArray() { 185 return standardToArray(); 186 } 187 188 @Override public <T> T[] toArray(T[] array) { 189 return standardToArray(array); 190 } 191 192 @Override public String toString() { 193 return entrySet().toString(); 194 } 195 } 196} 197