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