guava/src/com/google/common/collect/AbstractMapBasedMultiset.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2007 The Guava Authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.google.common.collect;

 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
 import static com.google.common.collect.CollectPreconditions.checkRemove;

 import com.google.common.annotations.GwtCompatible;
 import com.google.common.annotations.GwtIncompatible;
 import com.google.common.primitives.Ints;

 import java.io.InvalidObjectException;
 import java.io.ObjectStreamException;
 import java.io.Serializable;
 import java.util.ConcurrentModificationException;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;

 import javax.annotation.Nullable;

 /**
  * Basic implementation of {@code Multiset<E>} backed by an instance of {@code
  * Map<E, Count>}.
  *
  * <p>For serialization to work, the subclass must specify explicit {@code
  * readObject} and {@code writeObject} methods.
  *
  * @author Kevin Bourrillion
  */
 @GwtCompatible(emulated = true)
 abstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E>
     implements Serializable {

   private transient Map<E, Count> backingMap;

   /*
    * Cache the size for efficiency. Using a long lets us avoid the need for
    * overflow checking and ensures that size() will function correctly even if
    * the multiset had once been larger than Integer.MAX_VALUE.
    */
   private transient long size;

   /** Standard constructor. */
   protected AbstractMapBasedMultiset(Map<E, Count> backingMap) {
     this.backingMap = checkNotNull(backingMap);
     this.size = super.size();
   }

   /** Used during deserialization only. The backing map must be empty. */
   void setBackingMap(Map<E, Count> backingMap) {
     this.backingMap = backingMap;
   }

   // Required Implementations

   /**
    * {@inheritDoc}
    *
    * <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned
    * set always returns the current count of that element in the multiset, as
    * opposed to the count at the time the entry was retrieved.
    */
   @Override
   public Set<Multiset.Entry<E>> entrySet() {
     return super.entrySet();
   }

   @Override
   Iterator<Entry<E>> entryIterator() {
     final Iterator<Map.Entry<E, Count>> backingEntries =
         backingMap.entrySet().iterator();
     return new Iterator<Multiset.Entry<E>>() {
       Map.Entry<E, Count> toRemove;

       @Override
       public boolean hasNext() {
         return backingEntries.hasNext();
       }

       @Override
       public Multiset.Entry<E> next() {
         final Map.Entry<E, Count> mapEntry = backingEntries.next();
         toRemove = mapEntry;
         return new Multisets.AbstractEntry<E>() {
           @Override
           public E getElement() {
             return mapEntry.getKey();
           }
           @Override
           public int getCount() {
             Count count = mapEntry.getValue();
             if (count == null || count.get() == 0) {
               Count frequency = backingMap.get(getElement());
               if (frequency != null) {
                 return frequency.get();
               }
             }
             return (count == null) ? 0 : count.get();
           }
         };
       }

       @Override
       public void remove() {
         checkRemove(toRemove != null);
         size -= toRemove.getValue().getAndSet(0);
         backingEntries.remove();
         toRemove = null;
       }
     };
   }

   @Override
   public void clear() {
     for (Count frequency : backingMap.values()) {
       frequency.set(0);
     }
     backingMap.clear();
     size = 0L;
   }

   @Override
   int distinctElements() {
     return backingMap.size();
   }

   // Optimizations - Query Operations

   @Override public int size() {
     return Ints.saturatedCast(size);
   }

   @Override public Iterator<E> iterator() {
     return new MapBasedMultisetIterator();
   }

   /*
    * Not subclassing AbstractMultiset$MultisetIterator because next() needs to
    * retrieve the Map.Entry<E, Count> entry, which can then be used for
    * a more efficient remove() call.
    */
   private class MapBasedMultisetIterator implements Iterator<E> {
     final Iterator<Map.Entry<E, Count>> entryIterator;
     Map.Entry<E, Count> currentEntry;
     int occurrencesLeft;
     boolean canRemove;

     MapBasedMultisetIterator() {
       this.entryIterator = backingMap.entrySet().iterator();
     }

     @Override
     public boolean hasNext() {
       return occurrencesLeft > 0 || entryIterator.hasNext();
     }

     @Override
     public E next() {
       if (occurrencesLeft == 0) {
         currentEntry = entryIterator.next();
         occurrencesLeft = currentEntry.getValue().get();
       }
       occurrencesLeft--;
       canRemove = true;
       return currentEntry.getKey();
     }

     @Override
     public void remove() {
       checkRemove(canRemove);
       int frequency = currentEntry.getValue().get();
       if (frequency <= 0) {
         throw new ConcurrentModificationException();
       }
       if (currentEntry.getValue().addAndGet(-1) == 0) {
         entryIterator.remove();
       }
       size--;
       canRemove = false;
     }
   }

   @Override public int count(@Nullable Object element) {
     Count frequency = Maps.safeGet(backingMap, element);
     return (frequency == null) ? 0 : frequency.get();
   }

   // Optional Operations - Modification Operations

   /**
    * {@inheritDoc}
    *
    * @throws IllegalArgumentException if the call would result in more than
    *     {@link Integer#MAX_VALUE} occurrences of {@code element} in this
    *     multiset.
    */
   @Override public int add(@Nullable E element, int occurrences) {
     if (occurrences == 0) {
       return count(element);
     }
     checkArgument(
         occurrences > 0, "occurrences cannot be negative: %s", occurrences);
     Count frequency = backingMap.get(element);
     int oldCount;
     if (frequency == null) {
       oldCount = 0;
       backingMap.put(element, new Count(occurrences));
     } else {
       oldCount = frequency.get();
       long newCount = (long) oldCount + (long) occurrences;
       checkArgument(newCount <= Integer.MAX_VALUE,
           "too many occurrences: %s", newCount);
       frequency.getAndAdd(occurrences);
     }
     size += occurrences;
     return oldCount;
   }

   @Override public int remove(@Nullable Object element, int occurrences) {
     if (occurrences == 0) {
       return count(element);
     }
     checkArgument(
         occurrences > 0, "occurrences cannot be negative: %s", occurrences);
     Count frequency = backingMap.get(element);
     if (frequency == null) {
       return 0;
     }

     int oldCount = frequency.get();

     int numberRemoved;
     if (oldCount > occurrences) {
       numberRemoved = occurrences;
     } else {
       numberRemoved = oldCount;
       backingMap.remove(element);
     }

     frequency.addAndGet(-numberRemoved);
     size -= numberRemoved;
     return oldCount;
   }

   // Roughly a 33% performance improvement over AbstractMultiset.setCount().
   @Override public int setCount(@Nullable E element, int count) {
     checkNonnegative(count, "count");

     Count existingCounter;
     int oldCount;
     if (count == 0) {
       existingCounter = backingMap.remove(element);
       oldCount = getAndSet(existingCounter, count);
     } else {
       existingCounter = backingMap.get(element);
       oldCount = getAndSet(existingCounter, count);

       if (existingCounter == null) {
         backingMap.put(element, new Count(count));
       }
     }

     size += (count - oldCount);
     return oldCount;
   }

   private static int getAndSet(Count i, int count) {
     if (i == null) {
       return 0;
     }

     return i.getAndSet(count);
   }

   // Don't allow default serialization.
   @GwtIncompatible("java.io.ObjectStreamException")
   @SuppressWarnings("unused") // actually used during deserialization
   private void readObjectNoData() throws ObjectStreamException {
     throw new InvalidObjectException("Stream data required");
   }

   @GwtIncompatible("not needed in emulated source.")
   private static final long serialVersionUID = -2250766705698539974L;
 }
	/*
	* Copyright (C) 2007 The Guava Authors
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.google.common.collect;

	import static com.google.common.base.Preconditions.checkArgument;
	import static com.google.common.base.Preconditions.checkNotNull;
	import static com.google.common.collect.CollectPreconditions.checkNonnegative;
	import static com.google.common.collect.CollectPreconditions.checkRemove;

	import com.google.common.annotations.GwtCompatible;
	import com.google.common.annotations.GwtIncompatible;
	import com.google.common.primitives.Ints;

	import java.io.InvalidObjectException;
	import java.io.ObjectStreamException;
	import java.io.Serializable;
	import java.util.ConcurrentModificationException;
	import java.util.Iterator;
	import java.util.Map;
	import java.util.Set;

	import javax.annotation.Nullable;

	/**
	* Basic implementation of {@code Multiset<E>} backed by an instance of {@code
	* Map<E, Count>}.
	*
	* <p>For serialization to work, the subclass must specify explicit {@code
	* readObject} and {@code writeObject} methods.
	*
	* @author Kevin Bourrillion
	*/
	@GwtCompatible(emulated = true)
	abstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E>
	implements Serializable {

	private transient Map<E, Count> backingMap;

	/*
	* Cache the size for efficiency. Using a long lets us avoid the need for
	* overflow checking and ensures that size() will function correctly even if
	* the multiset had once been larger than Integer.MAX_VALUE.
	*/
	private transient long size;

	/** Standard constructor. */
	protected AbstractMapBasedMultiset(Map<E, Count> backingMap) {
	this.backingMap = checkNotNull(backingMap);
	this.size = super.size();
	}

	/** Used during deserialization only. The backing map must be empty. */
	void setBackingMap(Map<E, Count> backingMap) {
	this.backingMap = backingMap;
	}

	// Required Implementations

	/**
	* {@inheritDoc}
	*
	* <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned
	* set always returns the current count of that element in the multiset, as
	* opposed to the count at the time the entry was retrieved.
	*/
	@Override
	public Set<Multiset.Entry<E>> entrySet() {
	return super.entrySet();
	}

	@Override
	Iterator<Entry<E>> entryIterator() {
	final Iterator<Map.Entry<E, Count>> backingEntries =
	backingMap.entrySet().iterator();
	return new Iterator<Multiset.Entry<E>>() {
	Map.Entry<E, Count> toRemove;

	@Override
	public boolean hasNext() {
	return backingEntries.hasNext();
	}

	@Override
	public Multiset.Entry<E> next() {
	final Map.Entry<E, Count> mapEntry = backingEntries.next();
	toRemove = mapEntry;
	return new Multisets.AbstractEntry<E>() {
	@Override
	public E getElement() {
	return mapEntry.getKey();
	}
	@Override
	public int getCount() {
	Count count = mapEntry.getValue();
	if (count == null \|\| count.get() == 0) {
	Count frequency = backingMap.get(getElement());
	if (frequency != null) {
	return frequency.get();
	}
	}
	return (count == null) ? 0 : count.get();
	}
	};
	}

	@Override
	public void remove() {
	checkRemove(toRemove != null);
	size -= toRemove.getValue().getAndSet(0);
	backingEntries.remove();
	toRemove = null;
	}
	};
	}

	@Override
	public void clear() {
	for (Count frequency : backingMap.values()) {
	frequency.set(0);
	}
	backingMap.clear();
	size = 0L;
	}

	@Override
	int distinctElements() {
	return backingMap.size();
	}

	// Optimizations - Query Operations

	@Override public int size() {
	return Ints.saturatedCast(size);
	}

	@Override public Iterator<E> iterator() {
	return new MapBasedMultisetIterator();
	}

	/*
	* Not subclassing AbstractMultiset$MultisetIterator because next() needs to
	* retrieve the Map.Entry<E, Count> entry, which can then be used for
	* a more efficient remove() call.
	*/
	private class MapBasedMultisetIterator implements Iterator<E> {
	final Iterator<Map.Entry<E, Count>> entryIterator;
	Map.Entry<E, Count> currentEntry;
	int occurrencesLeft;
	boolean canRemove;

	MapBasedMultisetIterator() {
	this.entryIterator = backingMap.entrySet().iterator();
	}

	@Override
	public boolean hasNext() {
	return occurrencesLeft > 0 \|\| entryIterator.hasNext();
	}

	@Override
	public E next() {
	if (occurrencesLeft == 0) {
	currentEntry = entryIterator.next();
	occurrencesLeft = currentEntry.getValue().get();
	}
	occurrencesLeft--;
	canRemove = true;
	return currentEntry.getKey();
	}

	@Override
	public void remove() {
	checkRemove(canRemove);
	int frequency = currentEntry.getValue().get();
	if (frequency <= 0) {
	throw new ConcurrentModificationException();
	}
	if (currentEntry.getValue().addAndGet(-1) == 0) {
	entryIterator.remove();
	}
	size--;
	canRemove = false;
	}
	}

	@Override public int count(@Nullable Object element) {
	Count frequency = Maps.safeGet(backingMap, element);
	return (frequency == null) ? 0 : frequency.get();
	}

	// Optional Operations - Modification Operations

	/**
	* {@inheritDoc}
	*
	* @throws IllegalArgumentException if the call would result in more than
	* {@link Integer#MAX_VALUE} occurrences of {@code element} in this
	* multiset.
	*/
	@Override public int add(@Nullable E element, int occurrences) {
	if (occurrences == 0) {
	return count(element);
	}
	checkArgument(
	occurrences > 0, "occurrences cannot be negative: %s", occurrences);
	Count frequency = backingMap.get(element);
	int oldCount;
	if (frequency == null) {
	oldCount = 0;
	backingMap.put(element, new Count(occurrences));
	} else {
	oldCount = frequency.get();
	long newCount = (long) oldCount + (long) occurrences;
	checkArgument(newCount <= Integer.MAX_VALUE,
	"too many occurrences: %s", newCount);
	frequency.getAndAdd(occurrences);
	}
	size += occurrences;
	return oldCount;
	}

	@Override public int remove(@Nullable Object element, int occurrences) {
	if (occurrences == 0) {
	return count(element);
	}
	checkArgument(
	occurrences > 0, "occurrences cannot be negative: %s", occurrences);
	Count frequency = backingMap.get(element);
	if (frequency == null) {
	return 0;
	}

	int oldCount = frequency.get();

	int numberRemoved;
	if (oldCount > occurrences) {
	numberRemoved = occurrences;
	} else {
	numberRemoved = oldCount;
	backingMap.remove(element);
	}

	frequency.addAndGet(-numberRemoved);
	size -= numberRemoved;
	return oldCount;
	}

	// Roughly a 33% performance improvement over AbstractMultiset.setCount().
	@Override public int setCount(@Nullable E element, int count) {
	checkNonnegative(count, "count");

	Count existingCounter;
	int oldCount;
	if (count == 0) {
	existingCounter = backingMap.remove(element);
	oldCount = getAndSet(existingCounter, count);
	} else {
	existingCounter = backingMap.get(element);
	oldCount = getAndSet(existingCounter, count);

	if (existingCounter == null) {
	backingMap.put(element, new Count(count));
	}
	}

	size += (count - oldCount);
	return oldCount;
	}

	private static int getAndSet(Count i, int count) {
	if (i == null) {
	return 0;
	}

	return i.getAndSet(count);
	}

	// Don't allow default serialization.
	@GwtIncompatible("java.io.ObjectStreamException")
	@SuppressWarnings("unused") // actually used during deserialization
	private void readObjectNoData() throws ObjectStreamException {
	throw new InvalidObjectException("Stream data required");
	}

	@GwtIncompatible("not needed in emulated source.")
	private static final long serialVersionUID = -2250766705698539974L;
	}