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 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkNotNull; 18import static com.google.common.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX; 19import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER; 20import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER; 21import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT; 22 23import com.google.common.primitives.Ints; 24 25import java.util.Comparator; 26import java.util.List; 27 28import javax.annotation.Nullable; 29 30/** 31 * An immutable sorted multiset with one or more distinct elements. 32 * 33 * @author Louis Wasserman 34 */ 35final class RegularImmutableSortedMultiset<E> extends ImmutableSortedMultiset<E> { 36 private static final class CumulativeCountEntry<E> extends Multisets.AbstractEntry<E> { 37 final E element; 38 final int count; 39 final long cumulativeCount; 40 41 CumulativeCountEntry(E element, int count, @Nullable CumulativeCountEntry<E> previous) { 42 this.element = element; 43 this.count = count; 44 this.cumulativeCount = count + ((previous == null) ? 0 : previous.cumulativeCount); 45 } 46 47 @Override 48 public E getElement() { 49 return element; 50 } 51 52 @Override 53 public int getCount() { 54 return count; 55 } 56 } 57 58 static <E> RegularImmutableSortedMultiset<E> createFromSorted(Comparator<? super E> comparator, 59 List<? extends Multiset.Entry<E>> entries) { 60 List<CumulativeCountEntry<E>> newEntries = Lists.newArrayListWithCapacity(entries.size()); 61 CumulativeCountEntry<E> previous = null; 62 for (Multiset.Entry<E> entry : entries) { 63 newEntries.add( 64 previous = new CumulativeCountEntry<E>(entry.getElement(), entry.getCount(), previous)); 65 } 66 return new RegularImmutableSortedMultiset<E>(comparator, ImmutableList.copyOf(newEntries)); 67 } 68 69 final transient ImmutableList<CumulativeCountEntry<E>> entries; 70 71 RegularImmutableSortedMultiset( 72 Comparator<? super E> comparator, ImmutableList<CumulativeCountEntry<E>> entries) { 73 super(comparator); 74 this.entries = entries; 75 assert !entries.isEmpty(); 76 } 77 78 ImmutableList<E> elementList() { 79 return new TransformedImmutableList<CumulativeCountEntry<E>, E>(entries) { 80 @Override 81 E transform(CumulativeCountEntry<E> entry) { 82 return entry.getElement(); 83 } 84 }; 85 } 86 87 @Override 88 ImmutableSortedSet<E> createElementSet() { 89 return new RegularImmutableSortedSet<E>(elementList(), comparator()); 90 } 91 92 @Override 93 ImmutableSortedSet<E> createDescendingElementSet() { 94 return new RegularImmutableSortedSet<E>(elementList().reverse(), reverseComparator()); 95 } 96 97 @SuppressWarnings("unchecked") 98 @Override 99 UnmodifiableIterator<Multiset.Entry<E>> entryIterator() { 100 return (UnmodifiableIterator) entries.iterator(); 101 } 102 103 @SuppressWarnings("unchecked") 104 @Override 105 UnmodifiableIterator<Multiset.Entry<E>> descendingEntryIterator() { 106 return (UnmodifiableIterator) entries.reverse().iterator(); 107 } 108 109 @Override 110 public CumulativeCountEntry<E> firstEntry() { 111 return entries.get(0); 112 } 113 114 @Override 115 public CumulativeCountEntry<E> lastEntry() { 116 return entries.get(entries.size() - 1); 117 } 118 119 @Override 120 public int size() { 121 CumulativeCountEntry<E> firstEntry = firstEntry(); 122 CumulativeCountEntry<E> lastEntry = lastEntry(); 123 return Ints.saturatedCast( 124 lastEntry.cumulativeCount - firstEntry.cumulativeCount + firstEntry.count); 125 } 126 127 @Override 128 int distinctElements() { 129 return entries.size(); 130 } 131 132 @Override 133 boolean isPartialView() { 134 return entries.isPartialView(); 135 } 136 137 @SuppressWarnings("unchecked") 138 @Override 139 public int count(@Nullable Object element) { 140 if (element == null) { 141 return 0; 142 } 143 try { 144 int index = SortedLists.binarySearch( 145 elementList(), (E) element, comparator(), ANY_PRESENT, INVERTED_INSERTION_INDEX); 146 return (index >= 0) ? entries.get(index).getCount() : 0; 147 } catch (ClassCastException e) { 148 return 0; 149 } 150 } 151 152 @Override 153 public ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType) { 154 int index; 155 switch (boundType) { 156 case OPEN: 157 index = SortedLists.binarySearch( 158 elementList(), checkNotNull(upperBound), comparator(), ANY_PRESENT, NEXT_HIGHER); 159 break; 160 case CLOSED: 161 index = SortedLists.binarySearch( 162 elementList(), checkNotNull(upperBound), comparator(), ANY_PRESENT, NEXT_LOWER) + 1; 163 break; 164 default: 165 throw new AssertionError(); 166 } 167 return createSubMultiset(0, index); 168 } 169 170 @Override 171 public ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) { 172 int index; 173 switch (boundType) { 174 case OPEN: 175 index = SortedLists.binarySearch( 176 elementList(), checkNotNull(lowerBound), comparator(), ANY_PRESENT, NEXT_LOWER) + 1; 177 break; 178 case CLOSED: 179 index = SortedLists.binarySearch( 180 elementList(), checkNotNull(lowerBound), comparator(), ANY_PRESENT, NEXT_HIGHER); 181 break; 182 default: 183 throw new AssertionError(); 184 } 185 return createSubMultiset(index, distinctElements()); 186 } 187 188 private ImmutableSortedMultiset<E> createSubMultiset(int newFromIndex, int newToIndex) { 189 if (newFromIndex == 0 && newToIndex == entries.size()) { 190 return this; 191 } else if (newFromIndex >= newToIndex) { 192 return emptyMultiset(comparator()); 193 } else { 194 return new RegularImmutableSortedMultiset<E>( 195 comparator(), entries.subList(newFromIndex, newToIndex)); 196 } 197 } 198} 199