dev/util/SortedBag.java

/*
**********************************************************************
* Copyright (c) 2002-2012, International Business Machines
* Corporation and others.  All Rights Reserved.
**********************************************************************
* Author: Mark Davis
**********************************************************************
*/package com.ibm.icu.dev.util;

import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * A collection that is like a sorted set, except that it allows
 * multiple elements that compare as equal
 * @author medavis
 */
// TODO replace use of Set with a collection that takes an Equator
public class SortedBag implements Collection {
    /**
     * A map of sets, where each corresponds to one sorted element.
     * The sets are never empty
     */
    private Map m;
    private int size;

    public SortedBag(Comparator c) {
        m = new TreeMap(c);
    }
    public boolean add(Object s) {
        Set o = (Set)m.get(s);
        if (o == null) {
            o = new HashSet(1);
            m.put(s,o);
        }
        boolean result = o.add(s);
        if (result) size++;
        return result;
    }
    public Iterator iterator() {
        return new MyIterator();
    }
    static Iterator EMPTY_ITERATOR = new HashSet().iterator();
    private class MyIterator implements Iterator {
        private Iterator mapIterator = m.keySet().iterator();
        private Iterator setIterator = null;

        private MyIterator() {
            mapIterator = m.keySet().iterator();
            setIterator = getSetIterator();
        }
        private Iterator getSetIterator() {
            if (!mapIterator.hasNext()) return EMPTY_ITERATOR;
            return ((Set)m.get(mapIterator.next())).iterator();
        }
        public boolean hasNext() {
            return setIterator.hasNext() || mapIterator.hasNext();
        }
        public Object next() {
            if (!setIterator.hasNext()) {
                setIterator = getSetIterator();
            }
            return setIterator.next();
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    /**
     *
     */
    public void clear() {
        m.clear();
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public boolean contains(Object o) {
        Set set = (Set)m.get(o);
        if (set == null) return false;
        return set.contains(o);
    }
    public Object[] toArray() {
        return toArray(new Object[size]);
    }
    public Object[] toArray(Object[] a) {
        int count = 0;
        for (Iterator it = iterator(); it.hasNext();) {
            a[count++] = it.next();
        }
        return a;
    }
    /* (non-Javadoc)
     * @see java.util.Collection#remove(java.lang.Object)
     */
    public boolean remove(Object o) {
        Set set = (Set)m.get(o);
        if (set == null) return false;
        if (!set.remove(o)) return false;
        if (set.size() == 0) m.remove(o);
        size--;
        return true;
    }
    public boolean containsAll(Collection c) {
        for (Iterator it = c.iterator(); it.hasNext(); ) {
            if (!contains(it.next())) return false;
        }
        return true;
    }
    public boolean addAll(Collection c) {
        boolean result = false;
        for (Iterator it = c.iterator(); it.hasNext(); ) {
            if (add(it.next())) result = true;
        }
        return result;
    }
    public boolean removeAll(Collection c) {
        boolean result = false;
        for (Iterator it = c.iterator(); it.hasNext(); ) {
            if (remove(it.next())) result = true;
        }
        return result;
    }
    public boolean retainAll(Collection c) {
        // WARNING: this may not work if the comparator does not distinguish
        // all items that are equals().
        Set stuffToRemove = new HashSet(); // have to do this since iterator may not allow removal!
        for (Iterator it = iterator(); it.hasNext(); ) {
            Object item = it.next();
            if (!c.contains(item)) stuffToRemove.add(item);
        }
        return removeAll(stuffToRemove);
    }
}