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
25import javax.annotation.Nullable;
26
27/**
28 * This class provides a skeletal implementation of the {@link SortedMultiset} interface.
29 *
30 * <p>The {@link #count} and {@link #size} implementations all iterate across the set returned by
31 * {@link Multiset#entrySet()}, as do many methods acting on the set returned by
32 * {@link #elementSet()}. Override those methods for better performance.
33 *
34 * @author Louis Wasserman
35 */
36@GwtCompatible(emulated = true)
37abstract class AbstractSortedMultiset<E> extends AbstractMultiset<E> implements SortedMultiset<E> {
38  @GwtTransient final Comparator<? super E> comparator;
39
40  // needed for serialization
41  @SuppressWarnings("unchecked")
42  AbstractSortedMultiset() {
43    this((Comparator) Ordering.natural());
44  }
45
46  AbstractSortedMultiset(Comparator<? super E> comparator) {
47    this.comparator = checkNotNull(comparator);
48  }
49
50  @Override
51  public SortedSet<E> elementSet() {
52    return (SortedSet<E>) super.elementSet();
53  }
54
55  @Override
56  SortedSet<E> createElementSet() {
57    return new SortedMultisets.ElementSet<E>(this);
58  }
59
60  @Override
61  public Comparator<? super E> comparator() {
62    return comparator;
63  }
64
65  @Override
66  public Entry<E> firstEntry() {
67    Iterator<Entry<E>> entryIterator = entryIterator();
68    return entryIterator.hasNext() ? entryIterator.next() : null;
69  }
70
71  @Override
72  public Entry<E> lastEntry() {
73    Iterator<Entry<E>> entryIterator = descendingEntryIterator();
74    return entryIterator.hasNext() ? entryIterator.next() : null;
75  }
76
77  @Override
78  public Entry<E> pollFirstEntry() {
79    Iterator<Entry<E>> entryIterator = entryIterator();
80    if (entryIterator.hasNext()) {
81      Entry<E> result = entryIterator.next();
82      result = Multisets.immutableEntry(result.getElement(), result.getCount());
83      entryIterator.remove();
84      return result;
85    }
86    return null;
87  }
88
89  @Override
90  public Entry<E> pollLastEntry() {
91    Iterator<Entry<E>> entryIterator = descendingEntryIterator();
92    if (entryIterator.hasNext()) {
93      Entry<E> result = entryIterator.next();
94      result = Multisets.immutableEntry(result.getElement(), result.getCount());
95      entryIterator.remove();
96      return result;
97    }
98    return null;
99  }
100
101  @Override
102  public SortedMultiset<E> subMultiset(@Nullable E fromElement, BoundType fromBoundType,
103      @Nullable E toElement, BoundType toBoundType) {
104    // These are checked elsewhere, but NullPointerTester wants them checked eagerly.
105    checkNotNull(fromBoundType);
106    checkNotNull(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 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