You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2015/06/11 22:30:40 UTC

svn commit: r1684969 - in /commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4: ./ multiset/

Author: tn
Date: Thu Jun 11 20:30:39 2015
New Revision: 1684969

URL: http://svn.apache.org/r1684969
Log:
[COLLECTIONS-567] Add interface / skeleton code and first implementation of a MultiSet.

Added:
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java   (with props)

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java?rev=1684969&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java Thu Jun 11 20:30:39 2015
@@ -0,0 +1,270 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.commons.collections4;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * Defines a collection that counts the number of times an object appears in
+ * the collection.
+ * <p>
+ * Suppose you have a MultiSet that contains <code>{a, a, b, c}</code>.
+ * Calling {@link #getCount(Object)} on <code>a</code> would return 2, while
+ * calling {@link #uniqueSet()} would return <code>{a, b, c}</code>.
+ *
+ * @param <E> the type held in the multiset
+ * @since 4.1
+ * @version $Id$
+ */
+public interface MultiSet<E> extends Collection<E> {
+
+    /**
+     * Returns the number of occurrences of the given object currently
+     * in the MultiSet. If the object does not exist in the multiset,
+     * return 0.
+     *
+     * @param object  the object to search for
+     * @return the number of occurrences of the object, zero if not found
+     */
+    int getCount(Object object);
+
+    /**
+     * Sets the number of occurrences of the specified object in the MultiSet
+     * to the given count.
+     * <p>
+     * If the provided count is zero, the object will be removed from the
+     * {@link #uniqueSet()}.
+     * 
+     * @param object  the object to update
+     * @param count  the number of occurrences of the object
+     * @return the number of occurrences of the object before this operation, zero
+     *   if the object was not contained in the multiset
+     * @throws IllegalArgumentException if count is negative
+     */
+    int setCount(E object, int count);
+
+    /**
+     * Adds one copy of the specified object to the MultiSet.
+     * <p>
+     * If the object is already in the {@link #uniqueSet()} then increment its
+     * count as reported by {@link #getCount(Object)}. Otherwise add it to the
+     * {@link #uniqueSet()} and report its count as 1.
+     *
+     * @param object  the object to add
+     * @return <code>true</code> always, as the size of the MultiSet is increased
+     *   in any case
+     */
+    @Override
+    boolean add(E object);
+
+    /**
+     * Adds a number of occurrences of the specified object to the MultiSet.
+     * <p>
+     * If the object is already in the {@link #uniqueSet()} then increment its
+     * count as reported by {@link #getCount(Object)}. Otherwise add it to the
+     * {@link #uniqueSet()} and report its count as <code>occurrences</code>.
+     *
+     * @param object  the object to add
+     * @param occurrences  the number of occurrences to add, may be zero,
+     *   in which case no change is made to the multiset
+     * @return the number of occurrences of the object in the multiset before
+     *   this operation; possibly zero
+     * @throws IllegalArgumentException if occurrences is negative
+     */
+    int add(E object, int occurrences);
+
+    /**
+     * Removes one occurrence of the given object from the MultiSet.
+     * <p>
+     * If the number of occurrences after this operations is reduced
+     * to zero, the object will be removed from the {@link #uniqueSet()}.
+     *
+     * @param object  the object to remove
+     * @return <code>true</code> if this call changed the collection
+     */
+    @Override
+    boolean remove(Object object);
+
+    /**
+     * Removes a number of occurrences of the specified object from the MultiSet.
+     * <p>
+     * If the number of occurrences to remove is greater than the actual number of
+     * occurrences in the multiset, the object will be removed from the multiset.
+     *
+     * @param object  the object to remove
+     * @param occurrences  the number of occurrences to remove, may be zero,
+     *   in which case no change is made to the multiset
+     * @return the number of occurrences of the object in the multiset
+     *   before the operation; possibly zero
+     * @throws IllegalArgumentException if occurrences is negative
+     */
+    int remove(Object object, int occurrences);
+
+    /**
+     * Returns a {@link Set} of unique elements in the MultiSet.
+     * <p>
+     * Uniqueness constraints are the same as those in {@link java.util.Set}.
+     * <p>
+     * The returned set is backed by this multiset, so any change to either
+     * is immediately reflected in the other.
+     *
+     * @return the Set of unique MultiSet elements
+     */
+    Set<E> uniqueSet();
+
+    /**
+     * Returns a {@link Set} of all entries contained in the MultiSet.
+     * <p>
+     * The returned set is backed by this multiset, so any change to either
+     * is immediately reflected in the other.
+     *
+     * @return the Set of MultiSet entries
+     */
+    Set<Entry<E>> entrySet();
+
+    /**
+     * Returns an {@link Iterator} over the entire set of members,
+     * including copies due to cardinality. This iterator is fail-fast
+     * and will not tolerate concurrent modifications.
+     *
+     * @return iterator over all elements in the MultiSet
+     */
+    @Override
+    Iterator<E> iterator();
+
+    /**
+     * Returns the total number of items in the MultiSet.
+     *
+     * @return the total size of the multiset
+     */
+    @Override
+    int size();
+
+    /**
+     * Returns <code>true</code> if the MultiSet contains at least one
+     * occurrence for each element contained in the given collection.
+     *
+     * @param coll  the collection to check against
+     * @return <code>true</code> if the MultiSet contains all the collection
+     */
+    @Override
+    boolean containsAll(Collection<?> coll);
+
+    /**
+     * Remove all occurrences of all elements from this MultiSet represented
+     * in the given collection.
+     *
+     * @param coll  the collection of elements to remove
+     * @return <code>true</code> if this call changed the multiset
+     */
+    @Override
+    boolean removeAll(Collection<?> coll);
+
+    /**
+     * Remove any elements of this MultiSet that are not contained in the
+     * given collection.
+     *
+     * @param coll  the collection of elements to retain
+     * @return <code>true</code> if this call changed the multiset
+     */
+    @Override
+    boolean retainAll(Collection<?> coll);
+
+    /**
+     * Compares this MultiSet to another object.
+     * <p>
+     * This MultiSet equals another object if it is also a MultiSet
+     * that contains the same number of occurrences of the same elements.
+     *
+     * @param obj  the object to compare to
+     * @return true if equal
+     */
+    @Override
+    boolean equals(Object obj);
+
+    /**
+     * Gets a hash code for the MultiSet compatible with the definition of equals.
+     * The hash code is defined as the sum total of a hash code for each element.
+     * The per element hash code is defined as
+     * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>.
+     *
+     * @return the hash code of the MultiSet
+     */
+    @Override
+    int hashCode();
+
+    /**
+     * An unmodifiable entry for an element and its occurrence as contained in a MultiSet.
+     * <p>
+     * The {@link MultiSet#entrySet()} method returns a view of the multiset whose elements
+     * implements this interface.
+     *
+     * @param <E>  the element type
+     */
+    interface Entry<E> {
+
+        /**
+         * Returns the element corresponding to this entry.
+         *
+         * @return the element corresponding to this entry
+         */
+        E getElement();
+
+        /**
+         * Returns the number of occurrences for the element of this entry.
+         *
+         * @return the number of occurrences of the element
+         */
+        int getCount();
+
+        /**
+         * Compares the specified object with this entry for equality.
+         * Returns true if the given object is also a multiset entry
+         * and the two entries represent the same element with the same
+         * number of occurrences.
+         * <p>
+         * More formally, two entries <tt>e1</tt> and <tt>e2</tt> represent
+         * the same mapping if
+         * <pre>
+         *     (e1.getElement()==null ? e2.getElement()==null
+         *                            : e1.getElement().equals(e2.getElement())) &amp;&amp;
+         *     (e1.getCount()==e2.getCount())
+         * </pre>
+         *
+         * @param o object to be compared for equality with this multiset entry
+         * @return true if the specified object is equal to this multiset entry
+         */
+        @Override
+        boolean equals(Object o);
+
+        /**
+         * Returns the hash code value for this multiset entry.
+         * <p>
+         * The hash code of a multiset entry <tt>e</tt> is defined to be:
+         * <pre>
+         *      (e==null ? 0 : e.hashCode()) ^ noOccurances)
+         * </pre>
+         *
+         * @return the hash code value for this multiset entry
+         */
+        @Override
+        int hashCode();
+    }
+
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/MultiSet.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java?rev=1684969&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java Thu Jun 11 20:30:39 2015
@@ -0,0 +1,781 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.commons.collections4.multiset;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.lang.reflect.Array;
+import java.util.AbstractCollection;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.commons.collections4.MultiSet;
+import org.apache.commons.collections4.collection.AbstractCollectionDecorator;
+import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
+
+/**
+ * Abstract implementation of the {@link MultiSet} interface to simplify the
+ * creation of subclass implementations.
+ * <p>
+ * Subclasses specify a Map implementation to use as the internal storage. The
+ * map will be used to map multiset elements to a number; the number represents the
+ * number of occurrences of that element in the multiset.
+ *
+ * @since 4.1
+ * @version $Id$
+ */
+public abstract class AbstractMapMultiSet<E> extends AbstractCollection<E> implements MultiSet<E> {
+
+    /** The map to use to store the data */
+    private transient Map<E, MutableInteger> map;
+    /** The current total size of the multiset */
+    private transient int size;
+    /** The modification count for fail fast iterators */
+    private transient int modCount;
+    /** View of the elements */
+    private transient Set<E> uniqueSet;
+    /** View of the entries */
+    private transient Set<Entry<E>> entrySet;
+
+    /**
+     * Constructor needed for subclass serialisation.
+     */
+    protected AbstractMapMultiSet() {
+        super();
+    }
+
+    /**
+     * Constructor that assigns the specified Map as the backing store. The map
+     * must be empty and non-null.
+     *
+     * @param map the map to assign
+     */
+    protected AbstractMapMultiSet(final Map<E, MutableInteger> map) {
+        super();
+        this.map = map;
+    }
+
+    /**
+     * Utility method for implementations to access the map that backs this multiset.
+     * Not intended for interactive use outside of subclasses.
+     *
+     * @return the map being used by the Bag
+     */
+    protected Map<E, MutableInteger> getMap() {
+        return map;
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Returns the number of elements in this multiset.
+     *
+     * @return current size of the multiset
+     */
+    @Override
+    public int size() {
+        return size;
+    }
+
+    /**
+     * Returns true if the underlying map is empty.
+     *
+     * @return true if multiset is empty
+     */
+    @Override
+    public boolean isEmpty() {
+        return map.isEmpty();
+    }
+
+    /**
+     * Returns the number of occurrence of the given element in this multiset by
+     * looking up its count in the underlying map.
+     *
+     * @param object the object to search for
+     * @return the number of occurrences of the object, zero if not found
+     */
+    @Override
+    public int getCount(final Object object) {
+        final MutableInteger count = map.get(object);
+        if (count != null) {
+            return count.value;
+        }
+        return 0;
+    }
+
+    @Override
+    public int setCount(final E object, final int count) {
+        if (count < 0) {
+            throw new IllegalArgumentException("Count must not be negative.");
+        }
+
+        int oldCount = getCount(object);
+        if (oldCount < count) {
+            add(object, count - oldCount);
+        } else {
+            remove(object, oldCount - count);
+        }
+        return oldCount;
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Determines if the multiset contains the given element by checking if the
+     * underlying map contains the element as a key.
+     *
+     * @param object the object to search for
+     * @return true if the multiset contains the given element
+     */
+    @Override
+    public boolean contains(final Object object) {
+        return map.containsKey(object);
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Gets an iterator over the multiset elements. Elements present in the
+     * MultiSet more than once will be returned repeatedly.
+     *
+     * @return the iterator
+     */
+    @Override
+    public Iterator<E> iterator() {
+        return new MultiSetIterator<E>(this);
+    }
+
+    /**
+     * Inner class iterator for the MultiSet.
+     */
+    static class MultiSetIterator<E> implements Iterator<E> {
+        private final AbstractMapMultiSet<E> parent;
+        private final Iterator<Map.Entry<E, MutableInteger>> entryIterator;
+        private Map.Entry<E, MutableInteger> current;
+        private int itemCount;
+        private final int mods;
+        private boolean canRemove;
+
+        /**
+         * Constructor.
+         *
+         * @param parent the parent multiset
+         */
+        public MultiSetIterator(final AbstractMapMultiSet<E> parent) {
+            this.parent = parent;
+            this.entryIterator = parent.map.entrySet().iterator();
+            this.current = null;
+            this.mods = parent.modCount;
+            this.canRemove = false;
+        }
+
+        /** {@inheritDoc} */
+        @Override
+        public boolean hasNext() {
+            return itemCount > 0 || entryIterator.hasNext();
+        }
+
+        /** {@inheritDoc} */
+        @Override
+        public E next() {
+            if (parent.modCount != mods) {
+                throw new ConcurrentModificationException();
+            }
+            if (itemCount == 0) {
+                current = entryIterator.next();
+                itemCount = current.getValue().value;
+            }
+            canRemove = true;
+            itemCount--;
+            return current.getKey();
+        }
+
+        /** {@inheritDoc} */
+        @Override
+        public void remove() {
+            if (parent.modCount != mods) {
+                throw new ConcurrentModificationException();
+            }
+            if (canRemove == false) {
+                throw new IllegalStateException();
+            }
+            final MutableInteger mut = current.getValue();
+            if (mut.value > 1) {
+                mut.value--;
+            } else {
+                entryIterator.remove();
+            }
+            parent.size--;
+            canRemove = false;
+        }
+    }
+
+    //-----------------------------------------------------------------------
+    @Override
+    public boolean add(final E object) {
+        add(object, 1);
+        return true;
+    }
+
+    @Override
+    public int add(final E object, final int occurrences) {
+        if (occurrences < 0) {
+            throw new IllegalArgumentException("Occurrences must not be negative.");
+        }
+
+        final MutableInteger mut = map.get(object);
+        int oldCount = mut != null ? mut.value : 0;
+
+        if (occurrences > 0) {
+            modCount++;
+            size += occurrences;
+            if (mut == null) {
+                map.put(object, new MutableInteger(occurrences));
+            } else {
+                mut.value += occurrences;
+            }
+        }
+        return oldCount;
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Clears the multiset by clearing the underlying map.
+     */
+    @Override
+    public void clear() {
+        modCount++;
+        map.clear();
+        size = 0;
+    }
+
+    @Override
+    public boolean remove(final Object object) {
+        final MutableInteger mut = map.get(object);
+        if (mut == null) {
+            return false;
+        }
+        modCount++;
+        map.remove(object);
+        size -= mut.value;
+        return true;
+    }
+
+    @Override
+    public int remove(final Object object, final int occurrences) {
+        if (occurrences < 0) {
+            throw new IllegalArgumentException("Occurrences must not be negative.");
+        }
+
+        final MutableInteger mut = map.get(object);
+        if (mut == null) {
+            return 0;
+        }
+        int oldCount = mut.value;
+        if (occurrences > 0) {
+            modCount++;
+            if (occurrences < mut.value) {
+                mut.value -= occurrences;
+                size -= occurrences;
+            } else {
+                map.remove(object);
+                size -= mut.value;
+            }
+        }
+        return oldCount;
+    }
+
+    @Override
+    public boolean removeAll(final Collection<?> coll) {
+        boolean result = false;
+        final Iterator<?> i = coll.iterator();
+        while (i.hasNext()) {
+            final Object obj = i.next();
+            final boolean changed = remove(obj, getCount(obj)) != 0;
+            result = result || changed;
+        }
+        return result;
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Mutable integer class for storing the data.
+     */
+    protected static class MutableInteger {
+        /** The value of this mutable. */
+        protected int value;
+
+        /**
+         * Constructor.
+         * @param value the initial value
+         */
+        MutableInteger(final int value) {
+            this.value = value;
+        }
+
+        @Override
+        public boolean equals(final Object obj) {
+            if (obj instanceof MutableInteger == false) {
+                return false;
+            }
+            return ((MutableInteger) obj).value == value;
+        }
+
+        @Override
+        public int hashCode() {
+            return value;
+        }
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Returns an array of all of this multiset's elements.
+     *
+     * @return an array of all of this multiset's elements
+     */
+    @Override
+    public Object[] toArray() {
+        final Object[] result = new Object[size()];
+        int i = 0;
+        final Iterator<E> it = map.keySet().iterator();
+        while (it.hasNext()) {
+            final E current = it.next();
+            for (int index = getCount(current); index > 0; index--) {
+                result[i++] = current;
+            }
+        }
+        return result;
+    }
+
+    /**
+     * Returns an array of all of this multiset's elements.
+     * If the input array has more elements than are in the multiset,
+     * trailing elements will be set to null.
+     *
+     * @param <T> the type of the array elements
+     * @param array the array to populate
+     * @return an array of all of this multiset's elements
+     * @throws ArrayStoreException if the runtime type of the specified array is not
+     *   a supertype of the runtime type of the elements in this list
+     * @throws NullPointerException if the specified array is null
+     */
+    @Override
+    public <T> T[] toArray(T[] array) {
+        final int size = size();
+        if (array.length < size) {
+            @SuppressWarnings("unchecked") // safe as both are of type T
+            final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
+            array = unchecked;
+        }
+
+        int i = 0;
+        final Iterator<E> it = map.keySet().iterator();
+        while (it.hasNext()) {
+            final E current = it.next();
+            for (int index = getCount(current); index > 0; index--) {
+                // unsafe, will throw ArrayStoreException if types are not compatible, see javadoc
+                @SuppressWarnings("unchecked")
+                final T unchecked = (T) current;
+                array[i++] = unchecked;
+            }
+        }
+        while (i < array.length) {
+            array[i++] = null;
+        }
+        return array;
+    }
+
+    /**
+     * Returns a view of the underlying map's key set.
+     *
+     * @return the set of unique elements in this multiset
+     */
+    @Override
+    public Set<E> uniqueSet() {
+        if (uniqueSet == null) {
+            uniqueSet = new UniqueSet<E>(this);
+        }
+        return uniqueSet;
+    }
+
+    /**
+     * Creates a unique set iterator.
+     * Subclasses can override this to return iterators with different properties.
+     *
+     * @param iterator  the iterator to decorate
+     * @return the uniqueSet iterator
+     */
+    protected Iterator<E> createUniqueSetIterator(final Iterator<E> iterator) {
+        return new UniqueSetIterator<E>(iterator, this);
+    }
+
+    /**
+     * Returns an unmodifiable view of the underlying map's key set.
+     *
+     * @return the set of unique elements in this multiset
+     */
+    @Override
+    public Set<Entry<E>> entrySet() {
+        if (entrySet == null) {
+            entrySet = new EntrySet<E>(this);
+        }
+        return entrySet;
+    }
+
+    /**
+     * Creates an entry set iterator.
+     * Subclasses can override this to return iterators with different properties.
+     *
+     * @param iterator  the iterator to decorate
+     * @return the entrySet iterator
+     */
+    protected Iterator<Entry<E>> createEntrySetIterator(final Iterator<Map.Entry<E, MutableInteger>> iterator) {
+        return new EntrySetIterator<E>(iterator, this);
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Inner class UniqueSet.
+     */
+    protected static class UniqueSet<E> extends AbstractCollectionDecorator<E> implements Set<E> {
+
+        /** Serialization version */
+        private static final long serialVersionUID = 20150610L;
+
+        /** The parent multiset */
+        protected final AbstractMapMultiSet<E> parent;
+
+        /**
+         * Constructs a new unique element view of the MultiSet.
+         *
+         * @param parent  the parent MultiSet
+         */
+        protected UniqueSet(final AbstractMapMultiSet<E> parent) {
+            super(parent.map.keySet());
+            this.parent = parent;
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return parent.createUniqueSetIterator(super.iterator());
+        }
+
+        @Override
+        public boolean contains(final Object key) {
+            return parent.contains(key);
+        }
+
+        @Override
+        public boolean remove(final Object key) {
+            return parent.remove(key, parent.getCount(key)) != 0;
+        }
+
+        @Override
+        public boolean equals(final Object object) {
+            return object == this || decorated().equals(object);
+        }
+
+        @Override
+        public int hashCode() {
+            return decorated().hashCode();
+        }
+
+        @Override
+        public void clear() {
+            parent.clear();
+        }
+    }
+
+    /**
+     * Inner class UniqueSetIterator.
+     */
+    protected static class UniqueSetIterator<E> extends AbstractIteratorDecorator<E> {
+
+        /** The parent multiset */
+        protected final AbstractMapMultiSet<E> parent;
+
+        /** The last returned element */
+        protected E lastElement = null;
+
+        /** Whether remove is allowed at present */
+        protected boolean canRemove = false;
+
+        /**
+         * Constructor.
+         * @param iterator  the iterator to decorate
+         * @param parent  the parent multiset
+         */
+        protected UniqueSetIterator(final Iterator<E> iterator, final AbstractMapMultiSet<E> parent) {
+            super(iterator);
+            this.parent = parent;
+        }
+
+        @Override
+        public E next() {
+            lastElement = super.next();
+            canRemove = true;
+            return lastElement;
+        }
+
+        @Override
+        public void remove() {
+            if (canRemove == false) {
+                throw new IllegalStateException("Iterator remove() can only be called once after next()");
+            }
+            final int count = parent.getCount(lastElement);
+            super.remove();
+            parent.remove(lastElement, count);
+            lastElement = null;
+            canRemove = false;
+        }
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Inner class EntrySet.
+     */
+    protected static class EntrySet<E> extends AbstractSet<Entry<E>> {
+
+        private final AbstractMapMultiSet<E> parent;
+
+        /**
+         * Constructs a new view of the BidiMap.
+         *
+         * @param parent  the parent BidiMap
+         */
+        protected EntrySet(final AbstractMapMultiSet<E> parent) {
+            this.parent = parent;
+        }
+
+        @Override
+        public int size() {
+            return parent.entrySet.size();
+        }
+
+        @Override
+        public Iterator<Entry<E>> iterator() {
+            return parent.createEntrySetIterator(parent.map.entrySet().iterator());
+        }
+
+        @Override
+        public boolean contains(final Object obj) {
+            if (obj instanceof Entry<?> == false) {
+                return false;
+            }
+            final Entry<?> entry = (Entry<?>) obj;
+            final Object element = entry.getElement();
+            return parent.getCount(element) == entry.getCount();
+        }
+
+        @Override
+        public boolean remove(final Object obj) {
+            if (obj instanceof Entry<?> == false) {
+                return false;
+            }
+            final Entry<?> entry = (Entry<?>) obj;
+            final Object element = entry.getElement();
+            if (parent.contains(element)) {
+                final int count = parent.getCount(element);
+                if (entry.getCount() == count) {
+                    parent.remove(element, count);
+                    return true;
+                }
+            }
+            return false;
+        }
+    }
+
+    /**
+     * Inner class EntrySetIterator.
+     */
+    protected static class EntrySetIterator<E> implements Iterator<Entry<E>> {
+
+        /** The parent map */
+        protected final AbstractMapMultiSet<E> parent;
+
+        protected final Iterator<Map.Entry<E, MutableInteger>> decorated;
+
+        /** The last returned entry */
+        protected Entry<E> last = null;
+
+        /** Whether remove is allowed at present */
+        protected boolean canRemove = false;
+
+        /**
+         * Constructor.
+         * @param iterator  the iterator to decorate
+         * @param parent  the parent multiset
+         */
+        protected EntrySetIterator(final Iterator<Map.Entry<E, MutableInteger>> iterator,
+                                   final AbstractMapMultiSet<E> parent) {
+            this.decorated = iterator;
+            this.parent = parent;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return decorated.hasNext();
+        }
+
+        @Override
+        public Entry<E> next() {
+            last = new MultiSetEntry<E>(decorated.next());
+            canRemove = true;
+            return last;
+        }
+
+        @Override
+        public void remove() {
+            if (canRemove == false) {
+                throw new IllegalStateException("Iterator remove() can only be called once after next()");
+            }
+            decorated.remove();
+            last = null;
+            canRemove = false;
+        }
+    }
+
+    /**
+     * Inner class MultiSetEntry.
+     */
+    protected static class MultiSetEntry<E> implements Entry<E> {
+
+        protected final Map.Entry<E, MutableInteger> parentEntry;
+
+        /**
+         * Constructor.
+         * @param entry  the entry to decorate
+         * @param parent  the parent map
+         */
+        protected MultiSetEntry(final Map.Entry<E, MutableInteger> parentEntry) {
+            this.parentEntry = parentEntry;
+        }
+
+        @Override
+        public E getElement() {
+            return parentEntry.getKey();
+        }
+
+        @Override
+        public int getCount() {
+            return parentEntry.getValue().value;
+        }
+
+        @Override
+        public String toString() {
+            return String.format("%s:%d", getElement(), getCount());
+        }
+        
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Write the map out using a custom routine.
+     * @param out the output stream
+     * @throws IOException any of the usual I/O related exceptions
+     */
+    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
+        out.writeInt(map.size());
+        for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) {
+            out.writeObject(entry.getKey());
+            out.writeInt(entry.getValue().value);
+        }
+    }
+
+    /**
+     * Read the map in using a custom routine.
+     * @param map the map to use
+     * @param in the input stream
+     * @throws IOException any of the usual I/O related exceptions
+     * @throws ClassNotFoundException if the stream contains an object which class can not be loaded
+     * @throws ClassCastException if the stream does not contain the correct objects
+     */
+    protected void doReadObject(final Map<E, MutableInteger> map, final ObjectInputStream in)
+            throws IOException, ClassNotFoundException {
+        this.map = map;
+        final int entrySize = in.readInt();
+        for (int i = 0; i < entrySize; i++) {
+            @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
+            final E obj = (E) in.readObject();
+            final int count = in.readInt();
+            map.put(obj, new MutableInteger(count));
+            size += count;
+        }
+    }
+
+    //-----------------------------------------------------------------------
+    @Override
+    public boolean equals(final Object object) {
+        if (object == this) {
+            return true;
+        }
+        if (object instanceof MultiSet == false) {
+            return false;
+        }
+        final MultiSet<?> other = (MultiSet<?>) object;
+        if (other.size() != size()) {
+            return false;
+        }
+        for (final E element : map.keySet()) {
+            if (other.getCount(element) != getCount(element)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    @Override
+    public int hashCode() {
+        int total = 0;
+        for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) {
+            final E element = entry.getKey();
+            final MutableInteger count = entry.getValue();
+            total += (element == null ? 0 : element.hashCode()) ^ count.value;
+        }
+        return total;
+    }
+
+    /**
+     * Implement a toString() method suitable for debugging.
+     *
+     * @return a debugging toString
+     */
+    @Override
+    public String toString() {
+        if (size() == 0) {
+            return "[]";
+        }
+        final StringBuilder buf = new StringBuilder();
+        buf.append('[');
+        final Iterator<E> it = uniqueSet().iterator();
+        while (it.hasNext()) {
+            final Object current = it.next();
+            final int count = getCount(current);
+            buf.append(current);
+            buf.append(':');
+            buf.append(count);
+            if (it.hasNext()) {
+                buf.append(", ");
+            }
+        }
+        buf.append(']');
+        return buf.toString();
+    }
+
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMapMultiSet.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java?rev=1684969&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java Thu Jun 11 20:30:39 2015
@@ -0,0 +1,107 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.commons.collections4.multiset;
+
+import java.util.Set;
+
+import org.apache.commons.collections4.MultiSet;
+import org.apache.commons.collections4.collection.AbstractCollectionDecorator;
+
+/**
+ * Decorates another <code>MultSet</code> to provide additional behaviour.
+ * <p>
+ * Methods are forwarded directly to the decorated multiset.
+ *
+ * @since 4.1
+ * @version $Id$
+ */
+public abstract class AbstractMultiSetDecorator<E>
+        extends AbstractCollectionDecorator<E> implements MultiSet<E> {
+
+    /** Serialization version */
+    private static final long serialVersionUID = 20150610L;
+
+    /**
+     * Constructor only used in deserialization, do not use otherwise.
+     */
+    protected AbstractMultiSetDecorator() {
+        super();
+    }
+
+    /**
+     * Constructor that wraps (not copies).
+     *
+     * @param multiset  the multiset to decorate, must not be null
+     * @throws IllegalArgumentException if multiset is null
+     */
+    protected AbstractMultiSetDecorator(final MultiSet<E> multiset) {
+        super(multiset);
+    }
+
+    /**
+     * Gets the multiset being decorated.
+     *
+     * @return the decorated multiset
+     */
+    @Override
+    protected MultiSet<E> decorated() {
+        return (MultiSet<E>) super.decorated();
+    }
+
+    @Override
+    public boolean equals(final Object object) {
+        return object == this || decorated().equals(object);
+    }
+
+    @Override
+    public int hashCode() {
+        return decorated().hashCode();
+    }
+
+    //-----------------------------------------------------------------------
+
+    @Override
+    public int getCount(final Object object) {
+        return decorated().getCount(object);
+    }
+
+    @Override
+    public int setCount(E object, int count) {
+        return decorated().setCount(object, count);
+    }
+
+    @Override
+    public int add(final E object, final int count) {
+        return decorated().add(object, count);
+    }
+
+    @Override
+    public int remove(final Object object, final int count) {
+        return decorated().remove(object, count);
+    }
+
+    @Override
+    public Set<E> uniqueSet() {
+        return decorated().uniqueSet();
+    }
+
+    @Override
+    public Set<Entry<E>> entrySet() {
+        return decorated().entrySet();
+    }
+    
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/AbstractMultiSetDecorator.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java?rev=1684969&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java Thu Jun 11 20:30:39 2015
@@ -0,0 +1,78 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.commons.collections4.multiset;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.HashMap;
+
+import org.apache.commons.collections4.MultiSet;
+
+/**
+ * Implements {@link MultiSet}, using a {@link HashMap} to provide the
+ * data storage. This is the standard implementation of a multiset.
+ * <p>
+ * A {@link MultiSet} stores each object in the collection together with a
+ * count of occurrences. Extra methods on the interface allow multiple copies
+ * of an object to be added or removed at once.
+ *
+ * @since 4.1
+ * @version $Id$
+ */
+public class HashMultiSet<E> extends AbstractMapMultiSet<E> implements Serializable {
+
+    /** Serial version lock */
+    private static final long serialVersionUID = 20150610L;
+
+    /**
+     * Constructs an empty {@link HashMultiSet}.
+     */
+    public HashMultiSet() {
+        super(new HashMap<E, MutableInteger>());
+    }
+
+    /**
+     * Constructs a bag containing all the members of the given collection.
+     *
+     * @param coll  a collection to copy into this bag
+     */
+    public HashMultiSet(final Collection<? extends E> coll) {
+        this();
+        addAll(coll);
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Write the bag out using a custom routine.
+     */
+    private void writeObject(final ObjectOutputStream out) throws IOException {
+        out.defaultWriteObject();
+        super.doWriteObject(out);
+    }
+
+    /**
+     * Read the bag in using a custom routine.
+     */
+    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
+        in.defaultReadObject();
+        super.doReadObject(new HashMap<E, MutableInteger>(), in);
+    }
+
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/HashMultiSet.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java?rev=1684969&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java Thu Jun 11 20:30:39 2015
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+/**
+ * This package contains implementations of the
+ * {@link org.apache.commons.collections4.MultiSet MultiSet} and
+ * {@link org.apache.commons.collections4.SortedMultiSet SortedMultiSet} interfaces.
+ * A multiset stores an object and a count of the number of occurrences of the object.
+ * <p>
+ * The following implementations are provided in the package:
+ * <ul>
+ *   <li>HashMultiSet - implementation that uses a HashMap to store the data
+ *   <li>TreeMultiSet - implementation that uses a TreeMap to store the data
+ * </ul>
+ * <p>
+ * The following decorators are provided in the package:
+ * <ul>
+ *   <li>Synchronized - synchronizes method access for multi-threaded environments
+ *   <li>Unmodifiable - ensures the multiset cannot be altered
+ *   <li>Predicated - ensures that only elements that are valid according to a predicate can be added
+ *   <li>Transformed - transforms each element added to the multiset
+ * </ul>
+ *
+ * @version $Id$
+ */
+package org.apache.commons.collections4.multiset;

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/multiset/package-info.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain