View Javadoc
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.Nullable;
25  
26  /**
27   * This class provides a skeletal implementation of the {@link SortedMultiset} interface.
28   *
29   * <p>The {@link #count} and {@link #size} implementations all iterate across the set returned by
30   * {@link Multiset#entrySet()}, as do many methods acting on the set returned by
31   * {@link #elementSet()}. Override those methods for better performance.
32   *
33   * @author Louis Wasserman
34   */
35  @GwtCompatible(emulated = true)
36  abstract class AbstractSortedMultiset<E> extends AbstractMultiset<E> implements SortedMultiset<E> {
37    @GwtTransient final Comparator<? super E> comparator;
38  
39    // needed for serialization
40    @SuppressWarnings("unchecked")
41    AbstractSortedMultiset() {
42      this((Comparator) Ordering.natural());
43    }
44  
45    AbstractSortedMultiset(Comparator<? super E> comparator) {
46      this.comparator = checkNotNull(comparator);
47    }
48  
49    @Override
50    public NavigableSet<E> elementSet() {
51      return (NavigableSet<E>) super.elementSet();
52    }
53  
54    @Override
55    NavigableSet<E> createElementSet() {
56      return new SortedMultisets.NavigableElementSet<E>(this);
57    }
58  
59    @Override
60    public Comparator<? super E> comparator() {
61      return comparator;
62    }
63  
64    @Override
65    public Entry<E> firstEntry() {
66      Iterator<Entry<E>> entryIterator = entryIterator();
67      return entryIterator.hasNext() ? entryIterator.next() : null;
68    }
69  
70    @Override
71    public Entry<E> lastEntry() {
72      Iterator<Entry<E>> entryIterator = descendingEntryIterator();
73      return entryIterator.hasNext() ? entryIterator.next() : null;
74    }
75  
76    @Override
77    public Entry<E> pollFirstEntry() {
78      Iterator<Entry<E>> entryIterator = entryIterator();
79      if (entryIterator.hasNext()) {
80        Entry<E> result = entryIterator.next();
81        result = Multisets.immutableEntry(result.getElement(), result.getCount());
82        entryIterator.remove();
83        return result;
84      }
85      return null;
86    }
87  
88    @Override
89    public Entry<E> pollLastEntry() {
90      Iterator<Entry<E>> entryIterator = descendingEntryIterator();
91      if (entryIterator.hasNext()) {
92        Entry<E> result = entryIterator.next();
93        result = Multisets.immutableEntry(result.getElement(), result.getCount());
94        entryIterator.remove();
95        return result;
96      }
97      return null;
98    }
99  
100   @Override
101   public SortedMultiset<E> subMultiset(
102       @Nullable E fromElement,
103       BoundType fromBoundType,
104       @Nullable E toElement,
105       BoundType toBoundType) {
106     // These are checked elsewhere, but NullPointerTester wants them checked eagerly.
107     checkNotNull(fromBoundType);
108     checkNotNull(toBoundType);
109     return tailMultiset(fromElement, fromBoundType).headMultiset(toElement, toBoundType);
110   }
111 
112   abstract Iterator<Entry<E>> descendingEntryIterator();
113 
114   Iterator<E> descendingIterator() {
115     return Multisets.iteratorImpl(descendingMultiset());
116   }
117 
118   private transient SortedMultiset<E> descendingMultiset;
119 
120   @Override
121   public SortedMultiset<E> descendingMultiset() {
122     SortedMultiset<E> result = descendingMultiset;
123     return (result == null) ? descendingMultiset = createDescendingMultiset() : result;
124   }
125 
126   SortedMultiset<E> createDescendingMultiset() {
127     @WeakOuter
128     class DescendingMultisetImpl extends DescendingMultiset<E> {
129       @Override
130       SortedMultiset<E> forwardMultiset() {
131         return AbstractSortedMultiset.this;
132       }
133 
134       @Override
135       Iterator<Entry<E>> entryIterator() {
136         return descendingEntryIterator();
137       }
138 
139       @Override
140       public Iterator<E> iterator() {
141         return descendingIterator();
142       }
143     }
144     return new DescendingMultisetImpl();
145   }
146 }