001: /*
002: **********************************************************************
003: * Copyright (c) 2002-2006, International Business Machines
004: * Corporation and others. All Rights Reserved.
005: **********************************************************************
006: * Author: Mark Davis
007: **********************************************************************
008: */package com.ibm.icu.dev.test.util;
009:
010: import java.util.Collection;
011: import java.util.Comparator;
012: import java.util.HashSet;
013: import java.util.Iterator;
014: import java.util.Map;
015: import java.util.Set;
016: import java.util.TreeMap;
017:
018: /**
019: * A collection that is like a sorted set, except that it allows
020: * multiple elements that compare as equal
021: * @author medavis
022: */
023: // TODO replace use of Set with a collection that takes an Equator
024: public class SortedBag implements Collection {
025: /**
026: * A map of sets, where each corresponds to one sorted element.
027: * The sets are never empty
028: */
029: private Map m;
030: private int size;
031:
032: public SortedBag(Comparator c) {
033: m = new TreeMap(c);
034: }
035:
036: public boolean add(Object s) {
037: Set o = (Set) m.get(s);
038: if (o == null) {
039: o = new HashSet(1);
040: m.put(s, o);
041: }
042: boolean result = o.add(s);
043: if (result)
044: size++;
045: return result;
046: }
047:
048: public Iterator iterator() {
049: return new MyIterator();
050: }
051:
052: static Iterator EMPTY_ITERATOR = new HashSet().iterator();
053:
054: private class MyIterator implements Iterator {
055: private Iterator mapIterator = m.keySet().iterator();
056: private Iterator setIterator = null;
057:
058: private MyIterator() {
059: mapIterator = m.keySet().iterator();
060: setIterator = getSetIterator();
061: }
062:
063: private Iterator getSetIterator() {
064: if (!mapIterator.hasNext())
065: return EMPTY_ITERATOR;
066: return ((Set) m.get(mapIterator.next())).iterator();
067: }
068:
069: public boolean hasNext() {
070: return setIterator.hasNext() || mapIterator.hasNext();
071: }
072:
073: public Object next() {
074: if (!setIterator.hasNext()) {
075: setIterator = getSetIterator();
076: }
077: return setIterator.next();
078: }
079:
080: public void remove() {
081: throw new UnsupportedOperationException();
082: }
083: }
084:
085: /**
086: *
087: */
088: public void clear() {
089: m.clear();
090: }
091:
092: public int size() {
093: return size;
094: }
095:
096: public boolean isEmpty() {
097: return size == 0;
098: }
099:
100: public boolean contains(Object o) {
101: Set set = (Set) m.get(o);
102: if (set == null)
103: return false;
104: return set.contains(o);
105: }
106:
107: public Object[] toArray() {
108: return toArray(new Object[size]);
109: }
110:
111: public Object[] toArray(Object[] a) {
112: int count = 0;
113: for (Iterator it = iterator(); it.hasNext();) {
114: a[count++] = it.next();
115: }
116: return a;
117: }
118:
119: /* (non-Javadoc)
120: * @see java.util.Collection#remove(java.lang.Object)
121: */
122: public boolean remove(Object o) {
123: Set set = (Set) m.get(o);
124: if (set == null)
125: return false;
126: if (!set.remove(o))
127: return false;
128: if (set.size() == 0)
129: m.remove(o);
130: size--;
131: return true;
132: }
133:
134: public boolean containsAll(Collection c) {
135: for (Iterator it = c.iterator(); it.hasNext();) {
136: if (!contains(it.next()))
137: return false;
138: }
139: return true;
140: }
141:
142: public boolean addAll(Collection c) {
143: boolean result = false;
144: for (Iterator it = c.iterator(); it.hasNext();) {
145: if (add(it.next()))
146: result = true;
147: }
148: return result;
149: }
150:
151: public boolean removeAll(Collection c) {
152: boolean result = false;
153: for (Iterator it = c.iterator(); it.hasNext();) {
154: if (remove(it.next()))
155: result = true;
156: }
157: return result;
158: }
159:
160: public boolean retainAll(Collection c) {
161: // WARNING: this may not work if the comparator does not distinguish
162: // all items that are equals().
163: Set stuffToRemove = new HashSet(); // have to do this since iterator may not allow removal!
164: for (Iterator it = iterator(); it.hasNext();) {
165: Object item = it.next();
166: if (!c.contains(item))
167: stuffToRemove.add(item);
168: }
169: return removeAll(stuffToRemove);
170: }
171: }
|