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