SortedMultisets.java revision 1d580d0f6ee4f21eb309ba7b509d2c6d671c4044 
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