001: /*
002: * This file is part of PFIXCORE.
003: *
004: * PFIXCORE is free software; you can redistribute it and/or modify
005: * it under the terms of the GNU Lesser General Public License as published by
006: * the Free Software Foundation; either version 2 of the License, or
007: * (at your option) any later version.
008: *
009: * PFIXCORE is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public License
015: * along with PFIXCORE; if not, write to the Free Software
016: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
017: */
018:
019: package de.schlund.pfixxml.util;
020:
021: import java.util.ArrayList;
022: import java.util.Collection;
023: import java.util.HashMap;
024: import java.util.Iterator;
025: import java.util.LinkedList;
026: import java.util.List;
027: import java.util.Map;
028: import java.util.TreeMap;
029:
030: /**
031: * A collection that stores a counter for each object. adding the same Object more than once will
032: * increase the counter, removing it will decrease the counter until it reaches 0, in that case the
033: * whole entry will be removed from the map. This implementation is backed by a HashMap, use
034: * SortedRefCountingCollection for an implementation that uses a TreeMap.
035: *
036: * Note that the iterator that is given will iterate over the distinct elements, regardless of their
037: * cardinality. The Iterator is implemented by the class RefCountingCollectionIterator, which
038: * features the additional method remove(int count) which works like removing from the collection
039: * itself, while the usual Iterator.remove() will remove the whole element, regardles of cardinality
040: * to be consistent with next() and hasNext().
041: *
042: * Created: Wed Nov 16 00:18:45 2005
043: *
044: * @author <a href="mailto:jtl@schlund.de">Jens Lautenbacher</a>
045: * @version 1.0
046: */
047: public class RefCountingCollection<E> implements Collection<E> {
048: private Map<E, Integer> map;
049: int fullsize;
050:
051: public RefCountingCollection() {
052: init(false);
053: }
054:
055: public RefCountingCollection(Collection<? extends E> collection) {
056: init(false);
057: addAll(collection);
058: }
059:
060: protected final void init(boolean sorted) {
061: fullsize = 0;
062: if (sorted) {
063: map = new TreeMap<E, Integer>();
064: } else {
065: map = new HashMap<E, Integer>();
066: }
067: }
068:
069: // Special methods
070:
071: public final boolean add(final E object, final int cardinality) {
072: if (cardinality < 0) {
073: throw new RuntimeException(
074: "Can't add an element with a negative cardinality");
075: }
076:
077: if (cardinality == 0) {
078: return false;
079: }
080:
081: int newcount = cardinality;
082: if (map.containsKey(object)) {
083: newcount = newcount + map.get(object);
084: }
085:
086: map.put(object, newcount);
087: fullsize = fullsize + cardinality;
088:
089: return true;
090: }
091:
092: public final boolean removeElement(final Object object) {
093: if (!contains(object)) {
094: return false;
095: }
096: return remove(object, map.get(object));
097: }
098:
099: @SuppressWarnings("unchecked")
100: public final boolean remove(final Object object, int cardinality) {
101: if (cardinality < 0) {
102: throw new RuntimeException(
103: "Can't remove an element with a negative cardinality");
104: }
105:
106: if (cardinality == 0 || !map.containsKey(object)) {
107: return false;
108: }
109: int count = map.get(object);
110: if (cardinality >= count) {
111: map.remove(object);
112: fullsize = fullsize - count;
113: } else {
114: // This cast is OK, as we already know that object is in the map.
115: map.put((E) object, count - cardinality);
116: fullsize = fullsize - cardinality;
117: }
118: return true;
119: }
120:
121: public final int getCardinality(final Object object) {
122: int retval = 0;
123: if (map.containsKey(object)) {
124: retval = map.get(object);
125: }
126: return retval;
127: }
128:
129: public final String toString() {
130: StringBuffer buff = new StringBuffer("[");
131: for (Iterator<E> i = iterator(); i.hasNext();) {
132: E key = i.next();
133: int count = getCardinality(key);
134: buff.append(key + " [" + count + "] ");
135: }
136: buff.append(" FS: " + fullsize + "]");
137: return buff.toString();
138: }
139:
140: protected final boolean isInternalMapEqualToMap(Map<?, ?> map) {
141: return this .map.equals(map);
142: }
143:
144: // Implementation of java.util.Collection
145:
146: public final boolean add(final E object) {
147: return add(object, 1);
148: }
149:
150: public final void clear() {
151: map.clear();
152: }
153:
154: public final boolean contains(final Object object) {
155: if (object == null) {
156: throw new NullPointerException(
157: "Object to test must be null");
158: }
159: return map.containsKey(object);
160: }
161:
162: @SuppressWarnings("unchecked")
163: public final boolean addAll(final Collection<? extends E> collection) {
164: for (Iterator<? extends E> i = collection.iterator(); i
165: .hasNext();) {
166: E item = i.next();
167:
168: int cardinality = 1;
169: if (collection instanceof RefCountingCollection) {
170: cardinality = ((RefCountingCollection<E>) collection)
171: .getCardinality(item);
172: }
173: add(item, cardinality);
174: }
175: return true;
176: }
177:
178: public final int size() {
179: return map.keySet().size();
180: }
181:
182: public final boolean remove(final Object object) {
183: return remove(object, 1);
184: }
185:
186: public final boolean isEmpty() {
187: return map.isEmpty();
188: }
189:
190: public final Iterator<E> iterator() {
191: return new RefCountingCollectionIterator<E>(this , map);
192: }
193:
194: public final int hashCode() {
195: return map.hashCode();
196: }
197:
198: public final boolean equals(final Object object) {
199: RefCountingCollection<?> incoll;
200: try {
201: incoll = (RefCountingCollection<?>) object;
202: } catch (ClassCastException e) {
203: return false;
204: }
205: return incoll.isInternalMapEqualToMap(map);
206: }
207:
208: public final boolean containsAll(final Collection<?> collection) {
209: for (Iterator<?> i = collection.iterator(); i.hasNext();) {
210: if (!contains(i.next())) {
211: return false;
212: }
213: }
214: return true;
215: }
216:
217: public final boolean removeAll(final Collection<?> collection) {
218: boolean retval = false;
219: boolean is_rcc = collection instanceof RefCountingCollection;
220:
221: for (Iterator<?> i = collection.iterator(); i.hasNext();) {
222: if (is_rcc) {
223: Object obj = i.next();
224: int count = ((RefCountingCollection<?>) collection)
225: .getCardinality(obj);
226: if (remove(obj, count)) {
227: retval = true;
228: }
229: } else {
230: if (remove(i.next())) {
231: retval = true;
232: }
233: }
234: }
235: return retval;
236: }
237:
238: public final boolean retainAll(final Collection<?> collection) {
239: boolean retval = false;
240: boolean is_rcc = collection instanceof RefCountingCollection;
241: for (Iterator<E> i = iterator(); i.hasNext();) {
242: E obj = i.next();
243: if (!collection.contains(obj)) {
244: i.remove();
245: retval = true;
246: } else if (is_rcc) {
247: int count = ((RefCountingCollection<?>) collection)
248: .getCardinality(obj);
249: if (count < getCardinality(obj)) {
250: map.put(obj, count);
251: retval = true;
252: }
253: }
254: }
255: return retval;
256: }
257:
258: public Object[] toArray() {
259: Object[] retval = new Object[fullsize];
260: if (fullsize == 0) {
261: return retval;
262: }
263: int index = 0;
264: for (Iterator<E> i = iterator(); i.hasNext();) {
265: E obj = i.next();
266: int count = getCardinality(obj);
267: for (int j = 0; j < count; j++) {
268: retval[index++] = obj;
269: }
270: }
271: return retval;
272: }
273:
274: @SuppressWarnings("unchecked")
275: public final <T> T[] toArray(T[] array) {
276: if (array.length < fullsize) {
277: array = (T[]) java.lang.reflect.Array.newInstance(array
278: .getClass().getComponentType(), fullsize);
279: }
280: int index = 0;
281: for (Iterator<E> i = iterator(); i.hasNext();) {
282: E obj = i.next();
283: int count = getCardinality(obj);
284: for (int j = 0; j < count; j++) {
285: array[index++] = (T) obj;
286: }
287: }
288: if (array.length > fullsize) {
289: array[fullsize] = null;
290: }
291: return array;
292: }
293:
294: // ============================================== END of class =================================
295:
296: public static void main(String[] args) {
297: RefCountingCollection<String> coll = new SortedRefCountingCollection<String>();
298: coll.add("Hallo", 5);
299: coll.add("Foo", 2);
300: coll.add("Bar");
301: coll.add("Baz", 3);
302: coll.add("Baz");
303:
304: System.out.println(coll);
305: System.out.println("-------");
306:
307: coll.remove("Foo");
308: System.out.println("Removing Foo:\n" + coll);
309: System.out.println("-------");
310:
311: coll.remove("Baz", 4);
312: System.out.println("Remove 4 x Baz:\n" + coll);
313: System.out.println("-------");
314:
315: Collection<String> testcol = new LinkedList<String>();
316: testcol.add("XXX");
317: testcol.add("YYY");
318: testcol.add("XXX");
319: testcol.add("ZZZ");
320: coll.addAll(testcol);
321: System.out.println("AddAll (XXX YYY XXX ZZZ): ");
322: System.out.println(coll);
323: System.out.println("-------");
324: System.out.println("Size: " + coll.size());
325: System.out.println("Contains ZZZ: " + coll.contains("ZZZ"));
326: System.out.println("Contains Baz: " + coll.contains("Baz"));
327: System.out.println("-------");
328:
329: testcol.clear();
330: testcol.add("ZZZ");
331: testcol.add("Baz");
332: System.out.println("ContainsAll (ZZZ Baz): "
333: + coll.containsAll(testcol));
334: System.out.println("-------");
335:
336: testcol.clear();
337: testcol.add("XXX");
338: testcol.add("Foo");
339: System.out.println("ContainsAll (XXX Foo): "
340: + coll.containsAll(testcol));
341: System.out.println("-------");
342:
343: coll.removeAll(testcol);
344: System.out.println("RemoveAll (XXX Foo):");
345: System.out.println(coll);
346: System.out.println("-------");
347:
348: RefCountingCollection<String> test = new RefCountingCollection<String>();
349: test.add("Hallo", 2);
350: test.add("Bar");
351: test.add("TTT", 10);
352: coll.removeAll(test);
353: System.out.println("RemoveAll " + test);
354: System.out.println(coll);
355: System.out.println("-------");
356:
357: Object[] array = coll.toArray();
358: System.out.print("[ ");
359: for (int i = 0; i < array.length; i++) {
360: System.out.print(array[i] + " ");
361: }
362: System.out.println("]");
363: System.out.println("-------");
364:
365: String[] str_array = coll.toArray(new String[] {});
366: System.out.print("[ ");
367: for (int i = 0; i < str_array.length; i++) {
368: System.out.print(str_array[i] + " ");
369: }
370: System.out.println("]");
371: System.out.println("-------");
372:
373: for (Iterator<String> i = coll.iterator(); i.hasNext();) {
374: String obj = i.next();
375: System.out.println("Objekt:" + obj);
376: System.out.println(" K:" + coll.getCardinality(obj));
377: RefCountingCollectionIterator<String> iter = (RefCountingCollectionIterator<String>) i;
378: iter.remove(1);
379: System.out
380: .println(" -> removing via iterator.remove(1)");
381: }
382: System.out.println("-------");
383: System.out.println("After remove(1) on iterator:\n" + coll);
384: System.out.println("-------");
385:
386: RefCountingCollection<String> blah = new RefCountingCollection<String>();
387: blah.add("A");
388: blah.add("A");
389: blah.add("B");
390: List<Integer> fasel = new ArrayList<Integer>();
391: fasel.add(1);
392: fasel.add(1);
393: fasel.add(10);
394:
395: blah.removeAll(fasel);
396: System.out.println("-------");
397: System.out.println("After remove(fasel):\n" + blah);
398: System.out.println("-------");
399:
400: }
401: }
|