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 License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * 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;
20
21import java.util.Comparator;
22import java.util.Iterator;
23import java.util.SortedSet;
24
25/**
26 * This class provides a skeletal implementation of the {@link SortedMultiset} interface.
27 *
28 * <p>The {@link #count} and {@link #size} implementations all iterate across the set returned by
29 * {@link Multiset#entrySet()}, as do many methods acting on the set returned by
30 * {@link #elementSet()}. Override those methods for better performance.
31 *
32 * @author Louis Wasserman
33 */
34@GwtCompatible
35abstract class AbstractSortedMultiset<E> extends AbstractMultiset<E> implements SortedMultiset<E> {
36  final Comparator<? super E> comparator;
37
38  // needed for serialization
39  @SuppressWarnings("unchecked")
40  AbstractSortedMultiset() {
41    this((Comparator) Ordering.natural());
42  }
43
44  AbstractSortedMultiset(Comparator<? super E> comparator) {
45    this.comparator = checkNotNull(comparator);
46  }
47
48  @Override
49  public SortedSet<E> elementSet() {
50    return (SortedSet<E>) super.elementSet();
51  }
52
53  @Override
54  SortedSet<E> createElementSet() {
55    return new SortedMultisets.ElementSet<E>() {
56      @Override
57      SortedMultiset<E> multiset() {
58        return AbstractSortedMultiset.this;
59      }
60    };
61  }
62
63  @Override
64  public Comparator<? super E> comparator() {
65    return comparator;
66  }
67
68  @Override
69  public Entry<E> firstEntry() {
70    Iterator<Entry<E>> entryIterator = entryIterator();
71    return entryIterator.hasNext() ? entryIterator.next() : null;
72  }
73
74  @Override
75  public Entry<E> lastEntry() {
76    Iterator<Entry<E>> entryIterator = descendingEntryIterator();
77    return entryIterator.hasNext() ? entryIterator.next() : null;
78  }
79
80  @Override
81  public Entry<E> pollFirstEntry() {
82    Iterator<Entry<E>> entryIterator = entryIterator();
83    if (entryIterator.hasNext()) {
84      Entry<E> result = entryIterator.next();
85      result = Multisets.immutableEntry(result.getElement(), result.getCount());
86      entryIterator.remove();
87      return result;
88    }
89    return null;
90  }
91
92  @Override
93  public Entry<E> pollLastEntry() {
94    Iterator<Entry<E>> entryIterator = descendingEntryIterator();
95    if (entryIterator.hasNext()) {
96      Entry<E> result = entryIterator.next();
97      result = Multisets.immutableEntry(result.getElement(), result.getCount());
98      entryIterator.remove();
99      return result;
100    }
101    return null;
102  }
103
104  @Override
105  public SortedMultiset<E> subMultiset(E fromElement, BoundType fromBoundType, E toElement,
106      BoundType toBoundType) {
107    return tailMultiset(fromElement, fromBoundType).headMultiset(toElement, toBoundType);
108  }
109
110  abstract Iterator<Entry<E>> descendingEntryIterator();
111
112  Iterator<E> descendingIterator() {
113    return Multisets.iteratorImpl(descendingMultiset());
114  }
115
116  private transient SortedMultiset<E> descendingMultiset;
117
118  @Override
119  public SortedMultiset<E> descendingMultiset() {
120    SortedMultiset<E> result = descendingMultiset;
121    return (result == null) ? descendingMultiset = createDescendingMultiset() : result;
122  }
123
124  SortedMultiset<E> createDescendingMultiset() {
125    return new SortedMultisets.DescendingMultiset<E>() {
126      @Override
127      SortedMultiset<E> forwardMultiset() {
128        return AbstractSortedMultiset.this;
129      }
130
131      @Override
132      Iterator<Entry<E>> entryIterator() {
133        return descendingEntryIterator();
134      }
135
136      @Override
137      public Iterator<E> iterator() {
138        return descendingIterator();
139      }
140    };
141  }
142}
143