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
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkNotNull;
18
19 import com.google.common.annotations.GwtCompatible;
20 import com.google.j2objc.annotations.WeakOuter;
21 import java.util.Comparator;
22 import java.util.Iterator;
23 import java.util.NavigableSet;
24 import javax.annotation.CheckForNull;
25 import org.checkerframework.checker.nullness.qual.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 {@link
32 * #elementSet()}. Override those methods for better performance.
33 *
34 * @author Louis Wasserman
35 */
36 @GwtCompatible(emulated = true)
37 @ElementTypesAreNonnullByDefault
38 abstract class AbstractSortedMultiset<E extends @Nullable Object> extends AbstractMultiset<E>
39 implements SortedMultiset<E> {
40 @GwtTransient final Comparator<? super E> comparator;
41
42 // needed for serialization
43 @SuppressWarnings("unchecked")
44 AbstractSortedMultiset() {
45 this((Comparator) Ordering.natural());
46 }
47
48 AbstractSortedMultiset(Comparator<? super E> comparator) {
49 this.comparator = checkNotNull(comparator);
50 }
51
52 @Override
53 public NavigableSet<E> elementSet() {
54 return (NavigableSet<E>) super.elementSet();
55 }
56
57 @Override
58 NavigableSet<E> createElementSet() {
59 return new SortedMultisets.NavigableElementSet<E>(this);
60 }
61
62 @Override
63 public Comparator<? super E> comparator() {
64 return comparator;
65 }
66
67 @Override
68 @CheckForNull
69 public Entry<E> firstEntry() {
70 Iterator<Entry<E>> entryIterator = entryIterator();
71 return entryIterator.hasNext() ? entryIterator.next() : null;
72 }
73
74 @Override
75 @CheckForNull
76 public Entry<E> lastEntry() {
77 Iterator<Entry<E>> entryIterator = descendingEntryIterator();
78 return entryIterator.hasNext() ? entryIterator.next() : null;
79 }
80
81 @Override
82 @CheckForNull
83 public Entry<E> pollFirstEntry() {
84 Iterator<Entry<E>> entryIterator = entryIterator();
85 if (entryIterator.hasNext()) {
86 Entry<E> result = entryIterator.next();
87 result = Multisets.immutableEntry(result.getElement(), result.getCount());
88 entryIterator.remove();
89 return result;
90 }
91 return null;
92 }
93
94 @Override
95 @CheckForNull
96 public Entry<E> pollLastEntry() {
97 Iterator<Entry<E>> entryIterator = descendingEntryIterator();
98 if (entryIterator.hasNext()) {
99 Entry<E> result = entryIterator.next();
100 result = Multisets.immutableEntry(result.getElement(), result.getCount());
101 entryIterator.remove();
102 return result;
103 }
104 return null;
105 }
106
107 @Override
108 public SortedMultiset<E> subMultiset(
109 @ParametricNullness E fromElement,
110 BoundType fromBoundType,
111 @ParametricNullness E toElement,
112 BoundType toBoundType) {
113 // These are checked elsewhere, but NullPointerTester wants them checked eagerly.
114 checkNotNull(fromBoundType);
115 checkNotNull(toBoundType);
116 return tailMultiset(fromElement, fromBoundType).headMultiset(toElement, toBoundType);
117 }
118
119 abstract Iterator<Entry<E>> descendingEntryIterator();
120
121 Iterator<E> descendingIterator() {
122 return Multisets.iteratorImpl(descendingMultiset());
123 }
124
125 @CheckForNull private transient SortedMultiset<E> descendingMultiset;
126
127 @Override
128 public SortedMultiset<E> descendingMultiset() {
129 SortedMultiset<E> result = descendingMultiset;
130 return (result == null) ? descendingMultiset = createDescendingMultiset() : result;
131 }
132
133 SortedMultiset<E> createDescendingMultiset() {
134 @WeakOuter
135 class DescendingMultisetImpl extends DescendingMultiset<E> {
136 @Override
137 SortedMultiset<E> forwardMultiset() {
138 return AbstractSortedMultiset.this;
139 }
140
141 @Override
142 Iterator<Entry<E>> entryIterator() {
143 return descendingEntryIterator();
144 }
145
146 @Override
147 public Iterator<E> iterator() {
148 return descendingIterator();
149 }
150 }
151 return new DescendingMultisetImpl();
152 }
153 }