1 /* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.base.Preconditions.checkArgument; 20 import static com.google.common.base.Preconditions.checkNotNull; 21 import static com.google.common.collect.CollectPreconditions.checkNonnegative; 22 23 import com.google.common.annotations.GwtCompatible; 24 import com.google.common.annotations.GwtIncompatible; 25 import com.google.common.annotations.J2ktIncompatible; 26 import com.google.common.primitives.Ints; 27 import com.google.errorprone.annotations.CanIgnoreReturnValue; 28 import java.io.IOException; 29 import java.io.ObjectInputStream; 30 import java.io.ObjectOutputStream; 31 import java.io.Serializable; 32 import java.util.ConcurrentModificationException; 33 import java.util.Iterator; 34 import java.util.NoSuchElementException; 35 import javax.annotation.CheckForNull; 36 import org.checkerframework.checker.nullness.qual.Nullable; 37 38 /** 39 * Basic implementation of {@code Multiset<E>} backed by an instance of {@code 40 * ObjectCountHashMap<E>}. 41 * 42 * <p>For serialization to work, the subclass must specify explicit {@code readObject} and {@code 43 * writeObject} methods. 44 * 45 * @author Kevin Bourrillion 46 */ 47 @GwtCompatible(emulated = true) 48 @ElementTypesAreNonnullByDefault 49 abstract class AbstractMapBasedMultiset<E extends @Nullable Object> extends AbstractMultiset<E> 50 implements Serializable { 51 52 transient ObjectCountHashMap<E> backingMap; 53 transient long size; 54 AbstractMapBasedMultiset(int distinctElements)55 AbstractMapBasedMultiset(int distinctElements) { 56 backingMap = newBackingMap(distinctElements); 57 } 58 newBackingMap(int distinctElements)59 abstract ObjectCountHashMap<E> newBackingMap(int distinctElements); 60 61 @Override count(@heckForNull Object element)62 public final int count(@CheckForNull Object element) { 63 return backingMap.get(element); 64 } 65 66 // Optional Operations - Modification Operations 67 68 /** 69 * {@inheritDoc} 70 * 71 * @throws IllegalArgumentException if the call would result in more than {@link 72 * Integer#MAX_VALUE} occurrences of {@code element} in this multiset. 73 */ 74 @CanIgnoreReturnValue 75 @Override add(@arametricNullness E element, int occurrences)76 public final int add(@ParametricNullness E element, int occurrences) { 77 if (occurrences == 0) { 78 return count(element); 79 } 80 checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences); 81 int entryIndex = backingMap.indexOf(element); 82 if (entryIndex == -1) { 83 backingMap.put(element, occurrences); 84 size += occurrences; 85 return 0; 86 } 87 int oldCount = backingMap.getValue(entryIndex); 88 long newCount = (long) oldCount + (long) occurrences; 89 checkArgument(newCount <= Integer.MAX_VALUE, "too many occurrences: %s", newCount); 90 backingMap.setValue(entryIndex, (int) newCount); 91 size += occurrences; 92 return oldCount; 93 } 94 95 @CanIgnoreReturnValue 96 @Override remove(@heckForNull Object element, int occurrences)97 public final int remove(@CheckForNull Object element, int occurrences) { 98 if (occurrences == 0) { 99 return count(element); 100 } 101 checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences); 102 int entryIndex = backingMap.indexOf(element); 103 if (entryIndex == -1) { 104 return 0; 105 } 106 int oldCount = backingMap.getValue(entryIndex); 107 int numberRemoved; 108 if (oldCount > occurrences) { 109 numberRemoved = occurrences; 110 backingMap.setValue(entryIndex, oldCount - occurrences); 111 } else { 112 numberRemoved = oldCount; 113 backingMap.removeEntry(entryIndex); 114 } 115 size -= numberRemoved; 116 return oldCount; 117 } 118 119 @CanIgnoreReturnValue 120 @Override setCount(@arametricNullness E element, int count)121 public final int setCount(@ParametricNullness E element, int count) { 122 checkNonnegative(count, "count"); 123 int oldCount = (count == 0) ? backingMap.remove(element) : backingMap.put(element, count); 124 size += (count - oldCount); 125 return oldCount; 126 } 127 128 @Override setCount(@arametricNullness E element, int oldCount, int newCount)129 public final boolean setCount(@ParametricNullness E element, int oldCount, int newCount) { 130 checkNonnegative(oldCount, "oldCount"); 131 checkNonnegative(newCount, "newCount"); 132 int entryIndex = backingMap.indexOf(element); 133 if (entryIndex == -1) { 134 if (oldCount != 0) { 135 return false; 136 } 137 if (newCount > 0) { 138 backingMap.put(element, newCount); 139 size += newCount; 140 } 141 return true; 142 } 143 int actualOldCount = backingMap.getValue(entryIndex); 144 if (actualOldCount != oldCount) { 145 return false; 146 } 147 if (newCount == 0) { 148 backingMap.removeEntry(entryIndex); 149 size -= oldCount; 150 } else { 151 backingMap.setValue(entryIndex, newCount); 152 size += newCount - oldCount; 153 } 154 return true; 155 } 156 157 @Override clear()158 public final void clear() { 159 backingMap.clear(); 160 size = 0; 161 } 162 163 /** 164 * Skeleton of per-entry iterators. We could push this down and win a few bytes, but it's complex 165 * enough it's not especially worth it. 166 */ 167 abstract class Itr<T extends @Nullable Object> implements Iterator<T> { 168 int entryIndex = backingMap.firstIndex(); 169 int toRemove = -1; 170 int expectedModCount = backingMap.modCount; 171 172 @ParametricNullness result(int entryIndex)173 abstract T result(int entryIndex); 174 checkForConcurrentModification()175 private void checkForConcurrentModification() { 176 if (backingMap.modCount != expectedModCount) { 177 throw new ConcurrentModificationException(); 178 } 179 } 180 181 @Override hasNext()182 public boolean hasNext() { 183 checkForConcurrentModification(); 184 return entryIndex >= 0; 185 } 186 187 @Override 188 @ParametricNullness next()189 public T next() { 190 if (!hasNext()) { 191 throw new NoSuchElementException(); 192 } 193 T result = result(entryIndex); 194 toRemove = entryIndex; 195 entryIndex = backingMap.nextIndex(entryIndex); 196 return result; 197 } 198 199 @Override remove()200 public void remove() { 201 checkForConcurrentModification(); 202 CollectPreconditions.checkRemove(toRemove != -1); 203 size -= backingMap.removeEntry(toRemove); 204 entryIndex = backingMap.nextIndexAfterRemove(entryIndex, toRemove); 205 toRemove = -1; 206 expectedModCount = backingMap.modCount; 207 } 208 } 209 210 @Override elementIterator()211 final Iterator<E> elementIterator() { 212 return new Itr<E>() { 213 @Override 214 @ParametricNullness 215 E result(int entryIndex) { 216 return backingMap.getKey(entryIndex); 217 } 218 }; 219 } 220 221 @Override 222 final Iterator<Entry<E>> entryIterator() { 223 return new Itr<Entry<E>>() { 224 @Override 225 Entry<E> result(int entryIndex) { 226 return backingMap.getEntry(entryIndex); 227 } 228 }; 229 } 230 231 /** Allocation-free implementation of {@code target.addAll(this)}. */ 232 void addTo(Multiset<? super E> target) { 233 checkNotNull(target); 234 for (int i = backingMap.firstIndex(); i >= 0; i = backingMap.nextIndex(i)) { 235 target.add(backingMap.getKey(i), backingMap.getValue(i)); 236 } 237 } 238 239 @Override 240 final int distinctElements() { 241 return backingMap.size(); 242 } 243 244 @Override 245 public final Iterator<E> iterator() { 246 return Multisets.iteratorImpl(this); 247 } 248 249 @Override 250 public final int size() { 251 return Ints.saturatedCast(size); 252 } 253 254 /** 255 * @serialData the number of distinct elements, the first element, its count, the second element, 256 * its count, and so on 257 */ 258 @GwtIncompatible // java.io.ObjectOutputStream 259 @J2ktIncompatible 260 private void writeObject(ObjectOutputStream stream) throws IOException { 261 stream.defaultWriteObject(); 262 Serialization.writeMultiset(this, stream); 263 } 264 265 @GwtIncompatible // java.io.ObjectInputStream 266 @J2ktIncompatible 267 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 268 stream.defaultReadObject(); 269 int distinctElements = Serialization.readCount(stream); 270 backingMap = newBackingMap(ObjectCountHashMap.DEFAULT_SIZE); 271 Serialization.populateMultiset(this, stream, distinctElements); 272 } 273 274 @GwtIncompatible // Not needed in emulated source. 275 @J2ktIncompatible 276 private static final long serialVersionUID = 0; 277 } 278