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

 /*
  * Copyright (C) 2007 Google Inc.
  *
  * 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 com.google.common.annotations.VisibleForTesting;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.collect.Multisets.checkNonnegative;
 import com.google.common.collect.Serialization.FieldSetter;

 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.util.AbstractSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ConcurrentMap;

 import javax.annotation.Nullable;

 /**
  * A multiset that supports concurrent modifications and that provides atomic
  * versions of most {@code Multiset} operations (exceptions where noted). Null
  * elements are not supported.
  *
  * @author Cliff L. Biffle
  * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
  */
 public final class ConcurrentHashMultiset<E> extends AbstractMultiset<E>
     implements Serializable {
   /*
    * The ConcurrentHashMultiset's atomic operations are implemented in terms of
    * ConcurrentMap's atomic operations. Many of them, such as add(E, int), are
    * read-modify-write sequences, and so are implemented as loops that wrap
    * ConcurrentMap's compare-and-set operations (like putIfAbsent).
    */

   /** The number of occurrences of each element. */
   private final transient ConcurrentMap<E, Integer> countMap;

   // This constant allows the deserialization code to set a final field. This
   // holder class makes sure it is not initialized unless an instance is
   // deserialized.
   private static class FieldSettersHolder {
     @SuppressWarnings("unchecked")
     // eclipse doesn't like the raw type here, but it's harmless
     static final FieldSetter<ConcurrentHashMultiset> COUNT_MAP_FIELD_SETTER
         = Serialization.getFieldSetter(
             ConcurrentHashMultiset.class, "countMap");
   }

   /**
    * Creates a new, empty {@code ConcurrentHashMultiset} using the default
    * initial capacity, load factor, and concurrency settings.
    */
   public static <E> ConcurrentHashMultiset<E> create() {
     return new ConcurrentHashMultiset<E>(new ConcurrentHashMap<E, Integer>());
   }

   /**
    * Creates a new {@code ConcurrentHashMultiset} containing the specified
    * elements, using the default initial capacity, load factor, and concurrency
    * settings.
    *
    * @param elements the elements that the multiset should contain
    */
   public static <E> ConcurrentHashMultiset<E> create(
       Iterable<? extends E> elements) {
     ConcurrentHashMultiset<E> multiset = ConcurrentHashMultiset.create();
     Iterables.addAll(multiset, elements);
     return multiset;
   }

   /**
    * Creates an instance using {@code countMap} to store elements and their
    * counts.
    *
    * <p>This instance will assume ownership of {@code countMap}, and other code
    * should not maintain references to the map or modify it in any way.
    *
    * @param countMap backing map for storing the elements in the multiset and
    *     their counts. It must be empty.
    * @throws IllegalArgumentException if {@code countMap} is not empty
    */
   @VisibleForTesting ConcurrentHashMultiset(
       ConcurrentMap<E, Integer> countMap) {
     checkArgument(countMap.isEmpty());
     this.countMap = countMap;
   }

   // Query Operations

   /**
    * Returns the number of occurrences of {@code element} in this multiset.
    *
    * @param element the element to look for
    * @return the nonnegative number of occurrences of the element
    */
   @Override public int count(@Nullable Object element) {
     try {
       return unbox(countMap.get(element));
     } catch (NullPointerException e) {
       return 0;
     } catch (ClassCastException e) {
       return 0;
     }
   }

   /**
    * {@inheritDoc}
    *
    * <p>If the data in the multiset is modified by any other threads during this
    * method, it is undefined which (if any) of these modifications will be
    * reflected in the result.
    */
   @Override public int size() {
     long sum = 0L;
     for (Integer value : countMap.values()) {
       sum += value;
     }
     return (int) Math.min(sum, Integer.MAX_VALUE);
   }

   /*
    * Note: the superclass toArray() methods assume that size() gives a correct
    * answer, which ours does not.
    */

   @Override public Object[] toArray() {
     return snapshot().toArray();
   }

   @Override public <T> T[] toArray(T[] array) {
     return snapshot().toArray(array);
   }

   /*
    * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
    * either of these would recurse back to us again!
    */
   private List<E> snapshot() {
     List<E> list = Lists.newArrayListWithExpectedSize(size());
     for (Multiset.Entry<E> entry : entrySet()) {
       E element = entry.getElement();
       for (int i = entry.getCount(); i > 0; i--) {
         list.add(element);
       }
     }
     return list;
   }

   // Modification Operations

   /**
    * Adds a number of occurrences of the specified element to this multiset.
    *
    * @param element the element to add
    * @param occurrences the number of occurrences to add
    * @return the previous count of the element before the operation; possibly
    *     zero
    * @throws IllegalArgumentException if {@code occurrences} is negative, or if
    *     the resulting amount would exceed {@link Integer#MAX_VALUE}
    */
   @Override public int add(E element, int occurrences) {
     if (occurrences == 0) {
       return count(element);
     }
     checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);

     while (true) {
       int current = count(element);
       if (current == 0) {
         if (countMap.putIfAbsent(element, occurrences) == null) {
           return 0;
         }
       } else {
         checkArgument(occurrences <= Integer.MAX_VALUE - current,
             "Overflow adding %s occurrences to a count of %s",
             occurrences, current);
         int next = current + occurrences;
         if (countMap.replace(element, current, next)) {
           return current;
         }
       }
       // If we're still here, there was a race, so just try again.
     }
   }

   /**
    * Removes a number of occurrences of the specified element from this
    * multiset. If the multiset contains fewer than this number of occurrences to
    * begin with, all occurrences will be removed.
    *
    * @param element the element whose occurrences should be removed
    * @param occurrences the number of occurrences of the element to remove
    * @return the count of the element before the operation; possibly zero
    * @throws IllegalArgumentException if {@code occurrences} is negative
    */
   @Override public int remove(@Nullable Object element, int occurrences) {
     if (occurrences == 0) {
       return count(element);
     }
     checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);

     while (true) {
       int current = count(element);
       if (current == 0) {
         return 0;
       }
       if (occurrences >= current) {
         if (countMap.remove(element, current)) {
           return current;
         }
       } else {
         // We know it's an "E" because it already exists in the map.
         @SuppressWarnings("unchecked")
         E casted = (E) element;

         if (countMap.replace(casted, current, current - occurrences)) {
           return current;
         }
       }
       // If we're still here, there was a race, so just try again.
     }
   }

   /**
    * Removes <b>all</b> occurrences of the specified element from this multiset.
    * This method complements {@link Multiset#remove(Object)}, which removes only
    * one occurrence at a time.
    *
    * @param element the element whose occurrences should all be removed
    * @return the number of occurrences successfully removed, possibly zero
    */
   private int removeAllOccurrences(@Nullable Object element) {
     try {
       return unbox(countMap.remove(element));
     } catch (NullPointerException e) {
       return 0;
     } catch (ClassCastException e) {
       return 0;
     }
   }

   /**
    * Removes exactly the specified number of occurrences of {@code element}, or
    * makes no change if this is not possible.
    *
    * <p>This method, in contrast to {@link #remove(Object, int)}, has no effect
    * when the element count is smaller than {@code occurrences}.
    *
    * @param element the element to remove
    * @param occurrences the number of occurrences of {@code element} to remove
    * @return {@code true} if the removal was possible (including if {@code
    *     occurrences} is zero)
    */
   public boolean removeExactly(@Nullable Object element, int occurrences) {
     if (occurrences == 0) {
       return true;
     }
     checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);

     while (true) {
       int current = count(element);
       if (occurrences > current) {
         return false;
       }
       if (occurrences == current) {
         if (countMap.remove(element, occurrences)) {
           return true;
         }
       } else {
         @SuppressWarnings("unchecked") // it's in the map, must be an "E"
         E casted = (E) element;
         if (countMap.replace(casted, current, current - occurrences)) {
           return true;
         }
       }
       // If we're still here, there was a race, so just try again.
     }
   }

   /**
    * Adds or removes occurrences of {@code element} such that the {@link #count}
    * of the element becomes {@code count}.
    *
    * @return the count of {@code element} in the multiset before this call
    * @throws IllegalArgumentException if {@code count} is negative
    */
   @Override public int setCount(E element, int count) {
     checkNonnegative(count, "count");
     return (count == 0)
         ? removeAllOccurrences(element)
         : unbox(countMap.put(element, count));
   }

   /**
    * Sets the number of occurrences of {@code element} to {@code newCount}, but
    * only if the count is currently {@code oldCount}. If {@code element} does
    * not appear in the multiset exactly {@code oldCount} times, no changes will
    * be made.
    *
    * @return {@code true} if the change was successful. This usually indicates
    *     that the multiset has been modified, but not always: in the case that
    *     {@code oldCount == newCount}, the method will return {@code true} if
    *     the condition was met.
    * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is
    *     negative
    */
   @Override public boolean setCount(E element, int oldCount, int newCount) {
     checkNonnegative(oldCount, "oldCount");
     checkNonnegative(newCount, "newCount");
     if (newCount == 0) {
       if (oldCount == 0) {
         // No change to make, but must return true if the element is not present
         return !countMap.containsKey(element);
       } else {
         return countMap.remove(element, oldCount);
       }
     }
     if (oldCount == 0) {
       return countMap.putIfAbsent(element, newCount) == null;
     }
     return countMap.replace(element, oldCount, newCount);
   }

   // Views

   @Override Set<E> createElementSet() {
     final Set<E> delegate = countMap.keySet();
     return new ForwardingSet<E>() {
       @Override protected Set<E> delegate() {
         return delegate;
       }
       @Override public boolean remove(Object object) {
         try {
           return delegate.remove(object);
         } catch (NullPointerException e) {
           return false;
         } catch (ClassCastException e) {
           return false;
         }
       }
     };
   }

   private transient EntrySet entrySet;

   @Override public Set<Multiset.Entry<E>> entrySet() {
     EntrySet result = entrySet;
     if (result == null) {
       entrySet = result = new EntrySet();
     }
     return result;
   }

   private class EntrySet extends AbstractSet<Multiset.Entry<E>> {
     @Override public int size() {
       return countMap.size();
     }

     @Override public boolean isEmpty() {
       return countMap.isEmpty();
     }

     @Override public boolean contains(Object object) {
       if (object instanceof Multiset.Entry) {
         Multiset.Entry<?> entry = (Multiset.Entry<?>) object;
         Object element = entry.getElement();
         int entryCount = entry.getCount();
         return entryCount > 0 && count(element) == entryCount;
       }
       return false;
     }

     @Override public Iterator<Multiset.Entry<E>> iterator() {
       final Iterator<Map.Entry<E, Integer>> backingIterator
           = countMap.entrySet().iterator();
       return new Iterator<Multiset.Entry<E>>() {
         public boolean hasNext() {
           return backingIterator.hasNext();
         }

         public Multiset.Entry<E> next() {
           Map.Entry<E, Integer> backingEntry = backingIterator.next();
           return Multisets.immutableEntry(
               backingEntry.getKey(), backingEntry.getValue());
         }

         public void remove() {
           backingIterator.remove();
         }
       };
     }

     /*
      * Note: the superclass toArray() methods assume that size() gives a correct
      * answer, which ours does not.
      */

     @Override public Object[] toArray() {
       return snapshot().toArray();
     }

     @Override public <T> T[] toArray(T[] array) {
       return snapshot().toArray(array);
     }

     /*
      * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
      * either of these would recurse back to us again!
      */
     private List<Multiset.Entry<E>> snapshot() {
       List<Multiset.Entry<E>> list = Lists.newArrayListWithExpectedSize(size());
       for (Multiset.Entry<E> entry : this) {
         list.add(entry);
       }
       return list;
     }

     @Override public boolean remove(Object object) {
       if (object instanceof Multiset.Entry) {
         Multiset.Entry<?> entry = (Multiset.Entry<?>) object;
         Object element = entry.getElement();
         int entryCount = entry.getCount();
         return countMap.remove(element, entryCount);
       }
       return false;
     }

     @Override public void clear() {
       countMap.clear();
     }

     /**
      * The hash code is the same as countMap's, though the objects aren't equal.
      */
     @Override public int hashCode() {
       return countMap.hashCode();
     }
   }

   /**
    * We use a special form of unboxing that treats null as zero.
    */
   private static int unbox(Integer i) {
     return (i == null) ? 0 : i;
   }

   /**
    * @serialData the number of distinct elements, the first element, its count,
    *     the second element, its count, and so on
    */
   private void writeObject(ObjectOutputStream stream) throws IOException {
     stream.defaultWriteObject();
     // creating HashMultiset to handle concurrent changes
     Serialization.writeMultiset(HashMultiset.create(this), stream);
   }

   private void readObject(ObjectInputStream stream)
       throws IOException, ClassNotFoundException {
     stream.defaultReadObject();
     FieldSettersHolder.COUNT_MAP_FIELD_SETTER.set(
         this, new ConcurrentHashMap<Object, Object>());
     Serialization.populateMultiset(this, stream);
   }

   private static final long serialVersionUID = 0L;
 }
	/*
	* Copyright (C) 2007 Google Inc.
	*
	* 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 com.google.common.annotations.VisibleForTesting;
	import static com.google.common.base.Preconditions.checkArgument;
	import static com.google.common.collect.Multisets.checkNonnegative;
	import com.google.common.collect.Serialization.FieldSetter;

	import java.io.IOException;
	import java.io.ObjectInputStream;
	import java.io.ObjectOutputStream;
	import java.io.Serializable;
	import java.util.AbstractSet;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import java.util.concurrent.ConcurrentHashMap;
	import java.util.concurrent.ConcurrentMap;

	import javax.annotation.Nullable;

	/**
	* A multiset that supports concurrent modifications and that provides atomic
	* versions of most {@code Multiset} operations (exceptions where noted). Null
	* elements are not supported.
	*
	* @author Cliff L. Biffle
	* @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
	*/
	public final class ConcurrentHashMultiset<E> extends AbstractMultiset<E>
	implements Serializable {
	/*
	* The ConcurrentHashMultiset's atomic operations are implemented in terms of
	* ConcurrentMap's atomic operations. Many of them, such as add(E, int), are
	* read-modify-write sequences, and so are implemented as loops that wrap
	* ConcurrentMap's compare-and-set operations (like putIfAbsent).
	*/

	/** The number of occurrences of each element. */
	private final transient ConcurrentMap<E, Integer> countMap;

	// This constant allows the deserialization code to set a final field. This
	// holder class makes sure it is not initialized unless an instance is
	// deserialized.
	private static class FieldSettersHolder {
	@SuppressWarnings("unchecked")
	// eclipse doesn't like the raw type here, but it's harmless
	static final FieldSetter<ConcurrentHashMultiset> COUNT_MAP_FIELD_SETTER
	= Serialization.getFieldSetter(
	ConcurrentHashMultiset.class, "countMap");
	}

	/**
	* Creates a new, empty {@code ConcurrentHashMultiset} using the default
	* initial capacity, load factor, and concurrency settings.
	*/
	public static <E> ConcurrentHashMultiset<E> create() {
	return new ConcurrentHashMultiset<E>(new ConcurrentHashMap<E, Integer>());
	}

	/**
	* Creates a new {@code ConcurrentHashMultiset} containing the specified
	* elements, using the default initial capacity, load factor, and concurrency
	* settings.
	*
	* @param elements the elements that the multiset should contain
	*/
	public static <E> ConcurrentHashMultiset<E> create(
	Iterable<? extends E> elements) {
	ConcurrentHashMultiset<E> multiset = ConcurrentHashMultiset.create();
	Iterables.addAll(multiset, elements);
	return multiset;
	}

	/**
	* Creates an instance using {@code countMap} to store elements and their
	* counts.
	*
	* <p>This instance will assume ownership of {@code countMap}, and other code
	* should not maintain references to the map or modify it in any way.
	*
	* @param countMap backing map for storing the elements in the multiset and
	* their counts. It must be empty.
	* @throws IllegalArgumentException if {@code countMap} is not empty
	*/
	@VisibleForTesting ConcurrentHashMultiset(
	ConcurrentMap<E, Integer> countMap) {
	checkArgument(countMap.isEmpty());
	this.countMap = countMap;
	}

	// Query Operations

	/**
	* Returns the number of occurrences of {@code element} in this multiset.
	*
	* @param element the element to look for
	* @return the nonnegative number of occurrences of the element
	*/
	@Override public int count(@Nullable Object element) {
	try {
	return unbox(countMap.get(element));
	} catch (NullPointerException e) {
	return 0;
	} catch (ClassCastException e) {
	return 0;
	}
	}

	/**
	* {@inheritDoc}
	*
	* <p>If the data in the multiset is modified by any other threads during this
	* method, it is undefined which (if any) of these modifications will be
	* reflected in the result.
	*/
	@Override public int size() {
	long sum = 0L;
	for (Integer value : countMap.values()) {
	sum += value;
	}
	return (int) Math.min(sum, Integer.MAX_VALUE);
	}

	/*
	* Note: the superclass toArray() methods assume that size() gives a correct
	* answer, which ours does not.
	*/

	@Override public Object[] toArray() {
	return snapshot().toArray();
	}

	@Override public <T> T[] toArray(T[] array) {
	return snapshot().toArray(array);
	}

	/*
	* We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
	* either of these would recurse back to us again!
	*/
	private List<E> snapshot() {
	List<E> list = Lists.newArrayListWithExpectedSize(size());
	for (Multiset.Entry<E> entry : entrySet()) {
	E element = entry.getElement();
	for (int i = entry.getCount(); i > 0; i--) {
	list.add(element);
	}
	}
	return list;
	}

	// Modification Operations

	/**
	* Adds a number of occurrences of the specified element to this multiset.
	*
	* @param element the element to add
	* @param occurrences the number of occurrences to add
	* @return the previous count of the element before the operation; possibly
	* zero
	* @throws IllegalArgumentException if {@code occurrences} is negative, or if
	* the resulting amount would exceed {@link Integer#MAX_VALUE}
	*/
	@Override public int add(E element, int occurrences) {
	if (occurrences == 0) {
	return count(element);
	}
	checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);

	while (true) {
	int current = count(element);
	if (current == 0) {
	if (countMap.putIfAbsent(element, occurrences) == null) {
	return 0;
	}
	} else {
	checkArgument(occurrences <= Integer.MAX_VALUE - current,
	"Overflow adding %s occurrences to a count of %s",
	occurrences, current);
	int next = current + occurrences;
	if (countMap.replace(element, current, next)) {
	return current;
	}
	}
	// If we're still here, there was a race, so just try again.
	}
	}

	/**
	* Removes a number of occurrences of the specified element from this
	* multiset. If the multiset contains fewer than this number of occurrences to
	* begin with, all occurrences will be removed.
	*
	* @param element the element whose occurrences should be removed
	* @param occurrences the number of occurrences of the element to remove
	* @return the count of the element before the operation; possibly zero
	* @throws IllegalArgumentException if {@code occurrences} is negative
	*/
	@Override public int remove(@Nullable Object element, int occurrences) {
	if (occurrences == 0) {
	return count(element);
	}
	checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);

	while (true) {
	int current = count(element);
	if (current == 0) {
	return 0;
	}
	if (occurrences >= current) {
	if (countMap.remove(element, current)) {
	return current;
	}
	} else {
	// We know it's an "E" because it already exists in the map.
	@SuppressWarnings("unchecked")
	E casted = (E) element;

	if (countMap.replace(casted, current, current - occurrences)) {
	return current;
	}
	}
	// If we're still here, there was a race, so just try again.
	}
	}

	/**
	* Removes <b>all</b> occurrences of the specified element from this multiset.
	* This method complements {@link Multiset#remove(Object)}, which removes only
	* one occurrence at a time.
	*
	* @param element the element whose occurrences should all be removed
	* @return the number of occurrences successfully removed, possibly zero
	*/
	private int removeAllOccurrences(@Nullable Object element) {
	try {
	return unbox(countMap.remove(element));
	} catch (NullPointerException e) {
	return 0;
	} catch (ClassCastException e) {
	return 0;
	}
	}

	/**
	* Removes exactly the specified number of occurrences of {@code element}, or
	* makes no change if this is not possible.
	*
	* <p>This method, in contrast to {@link #remove(Object, int)}, has no effect
	* when the element count is smaller than {@code occurrences}.
	*
	* @param element the element to remove
	* @param occurrences the number of occurrences of {@code element} to remove
	* @return {@code true} if the removal was possible (including if {@code
	* occurrences} is zero)
	*/
	public boolean removeExactly(@Nullable Object element, int occurrences) {
	if (occurrences == 0) {
	return true;
	}
	checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);

	while (true) {
	int current = count(element);
	if (occurrences > current) {
	return false;
	}
	if (occurrences == current) {
	if (countMap.remove(element, occurrences)) {
	return true;
	}
	} else {
	@SuppressWarnings("unchecked") // it's in the map, must be an "E"
	E casted = (E) element;
	if (countMap.replace(casted, current, current - occurrences)) {
	return true;
	}
	}
	// If we're still here, there was a race, so just try again.
	}
	}

	/**
	* Adds or removes occurrences of {@code element} such that the {@link #count}
	* of the element becomes {@code count}.
	*
	* @return the count of {@code element} in the multiset before this call
	* @throws IllegalArgumentException if {@code count} is negative
	*/
	@Override public int setCount(E element, int count) {
	checkNonnegative(count, "count");
	return (count == 0)
	? removeAllOccurrences(element)
	: unbox(countMap.put(element, count));
	}

	/**
	* Sets the number of occurrences of {@code element} to {@code newCount}, but
	* only if the count is currently {@code oldCount}. If {@code element} does
	* not appear in the multiset exactly {@code oldCount} times, no changes will
	* be made.
	*
	* @return {@code true} if the change was successful. This usually indicates
	* that the multiset has been modified, but not always: in the case that
	* {@code oldCount == newCount}, the method will return {@code true} if
	* the condition was met.
	* @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is
	* negative
	*/
	@Override public boolean setCount(E element, int oldCount, int newCount) {
	checkNonnegative(oldCount, "oldCount");
	checkNonnegative(newCount, "newCount");
	if (newCount == 0) {
	if (oldCount == 0) {
	// No change to make, but must return true if the element is not present
	return !countMap.containsKey(element);
	} else {
	return countMap.remove(element, oldCount);
	}
	}
	if (oldCount == 0) {
	return countMap.putIfAbsent(element, newCount) == null;
	}
	return countMap.replace(element, oldCount, newCount);
	}

	// Views

	@Override Set<E> createElementSet() {
	final Set<E> delegate = countMap.keySet();
	return new ForwardingSet<E>() {
	@Override protected Set<E> delegate() {
	return delegate;
	}
	@Override public boolean remove(Object object) {
	try {
	return delegate.remove(object);
	} catch (NullPointerException e) {
	return false;
	} catch (ClassCastException e) {
	return false;
	}
	}
	};
	}

	private transient EntrySet entrySet;

	@Override public Set<Multiset.Entry<E>> entrySet() {
	EntrySet result = entrySet;
	if (result == null) {
	entrySet = result = new EntrySet();
	}
	return result;
	}

	private class EntrySet extends AbstractSet<Multiset.Entry<E>> {
	@Override public int size() {
	return countMap.size();
	}

	@Override public boolean isEmpty() {
	return countMap.isEmpty();
	}

	@Override public boolean contains(Object object) {
	if (object instanceof Multiset.Entry) {
	Multiset.Entry<?> entry = (Multiset.Entry<?>) object;
	Object element = entry.getElement();
	int entryCount = entry.getCount();
	return entryCount > 0 && count(element) == entryCount;
	}
	return false;
	}

	@Override public Iterator<Multiset.Entry<E>> iterator() {
	final Iterator<Map.Entry<E, Integer>> backingIterator
	= countMap.entrySet().iterator();
	return new Iterator<Multiset.Entry<E>>() {
	public boolean hasNext() {
	return backingIterator.hasNext();
	}

	public Multiset.Entry<E> next() {
	Map.Entry<E, Integer> backingEntry = backingIterator.next();
	return Multisets.immutableEntry(
	backingEntry.getKey(), backingEntry.getValue());
	}

	public void remove() {
	backingIterator.remove();
	}
	};
	}

	/*
	* Note: the superclass toArray() methods assume that size() gives a correct
	* answer, which ours does not.
	*/

	@Override public Object[] toArray() {
	return snapshot().toArray();
	}

	@Override public <T> T[] toArray(T[] array) {
	return snapshot().toArray(array);
	}

	/*
	* We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
	* either of these would recurse back to us again!
	*/
	private List<Multiset.Entry<E>> snapshot() {
	List<Multiset.Entry<E>> list = Lists.newArrayListWithExpectedSize(size());
	for (Multiset.Entry<E> entry : this) {
	list.add(entry);
	}
	return list;
	}

	@Override public boolean remove(Object object) {
	if (object instanceof Multiset.Entry) {
	Multiset.Entry<?> entry = (Multiset.Entry<?>) object;
	Object element = entry.getElement();
	int entryCount = entry.getCount();
	return countMap.remove(element, entryCount);
	}
	return false;
	}

	@Override public void clear() {
	countMap.clear();
	}

	/**
	* The hash code is the same as countMap's, though the objects aren't equal.
	*/
	@Override public int hashCode() {
	return countMap.hashCode();
	}
	}

	/**
	* We use a special form of unboxing that treats null as zero.
	*/
	private static int unbox(Integer i) {
	return (i == null) ? 0 : i;
	}

	/**
	* @serialData the number of distinct elements, the first element, its count,
	* the second element, its count, and so on
	*/
	private void writeObject(ObjectOutputStream stream) throws IOException {
	stream.defaultWriteObject();
	// creating HashMultiset to handle concurrent changes
	Serialization.writeMultiset(HashMultiset.create(this), stream);
	}

	private void readObject(ObjectInputStream stream)
	throws IOException, ClassNotFoundException {
	stream.defaultReadObject();
	FieldSettersHolder.COUNT_MAP_FIELD_SETTER.set(
	this, new ConcurrentHashMap<Object, Object>());
	Serialization.populateMultiset(this, stream);
	}

	private static final long serialVersionUID = 0L;
	}