import java.util.*;

public class MultiSet<E> extends AbstractCollection<E> {
    private HashMap<E, Integer> elements = new HashMap<E, Integer>();

    public MultiSet() {}

    public MultiSet(Collection<E> c) {
        addAll(c);
    }

    public boolean add(E e) {
        int offset = 0;

        if(elements.keySet().contains(e)) {
            offset = elements.get(e);
        }

        elements.put(e, offset + 1);

        return true;
    }

    private void removeElement(E e) {
        if(elements.keySet().contains(e)) {
            int value = elements.get(e);

            if(value == 1) {
                elements.remove(e);
            } else {
                elements.put(e, value - 1);
            }
        }
    }

    public int size() {
        int sum = 0;

        for(E i : this)
            sum++;

        return sum;
    }

    public boolean equals(Object other) {
        if(other == null) return false;
        if(getClass() != other.getClass()) return false;

        MultiSet<?> otherMS = (MultiSet<?>)other;
        return otherMS.elements.equals(elements);
    }

    public int hashCode() {
        return elements.hashCode();
    }

    public String toString() {
        return elements.entrySet().toString();
    }

    public Iterator iterator() {
        ArrayList<E> entries = new ArrayList<E>();
        Iterator<E> it = elements.keySet().iterator();

        while(it.hasNext()) {
            E key = it.next();
            int value = elements.get(key);

            for(int i = 0; i < value; i++)
                entries.add(key);
        }

        return new Iterator() {
            private Iterator<E> internalIt = entries.iterator();
            private E current = null;

            public boolean hasNext() {
                return internalIt.hasNext();
            }

            public E next() {
                current = internalIt.next();
                return current;
            }

            public void remove() {
                if(current != null) removeElement(current);
            }
        };
    }
}