001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2003-2006, Geotools Project Managment Committee (PMC)
005: * (C) 2001, Institut de Recherche pour le Développement
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation; either
010: * version 2.1 of the License, or (at your option) any later version.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.util;
018:
019: // Collections
020: import java.util.AbstractSet;
021: import java.util.Collection;
022: import java.util.Iterator;
023: import java.util.LinkedHashMap;
024: import java.util.Map;
025: import java.util.NoSuchElementException;
026: import java.util.Set;
027: import java.io.Serializable;
028:
029: /**
030: * A set which is disjoint from others {@code DisjointSet}s. Two sets are
031: * disjoint (or <em>mutually exclusive</em) if their intersection is the empty
032: * set. Adding an element to a {@code DisjointSet} remove it from any other
033: * mutually exclusive {@code DisjointSet}. Optionnaly, {@code DisjointSet}s
034: * may also have a trash set receiving removed elements. The example below
035: * creates 3 mutually exclusive sets with a trash:
036: *
037: * <blockquote><pre>
038: * DisjointSet set0 = new DisjointSet(true); // Used as the trash set.
039: * DisjointSet set1 = new DisjointSet(set0);
040: * DisjointSet set2 = new DisjointSet(set0);
041: * </pre></blockquote>
042: *
043: * Disjoint sets are thread-safe.
044: *
045: * @since 2.0
046: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/metadata/src/main/java/org/geotools/util/DisjointSet.java $
047: * @version $Id: DisjointSet.java 22482 2006-10-31 02:58:00Z desruisseaux $
048: * @author Martin Desruisseaux
049: */
050: public class DisjointSet extends AbstractSet implements Serializable {
051: /**
052: * Serial number for interoperability with different versions.
053: */
054: private static final long serialVersionUID = -7933552571588598563L;
055:
056: /**
057: * The underlying map. {@code add} and {@code remove} operations
058: * on this set are translated into {@link Map} operations as below:
059: * <p>
060: * <strong>Adding a new element to this {@link Set}:</strong>
061: * <ul>
062: * <li>Puts the corresponding key-value pair in the underlying {@link Map}, where:
063: * <ul>
064: * <li>the key is the element to add;</li>
065: * <li>the value is this {@code DisjointSet}.</li>
066: * </ul>
067: * If an other value was mapped to the key, the old value is discarted.
068: * This is equivalents to removing the element from an other {@code DisjointSet}
069: * prior to add it to this set (in other words, moving the element).</li>
070: * </ul>
071: * <p>
072: * <strong>Removing an element from this {@link Set}:</strong>
073: * <ul>
074: * <li>If the element is not an existing key in the underlying map, nothing is done.</li>
075: * <li>Otherwise, if the element is a key mapping a different value than this
076: * {@code DisjointSet}, then the element is assumed to belongs to an
077: * other {@code DisjointSet} and nothing is done.</li>
078: * <li>Otherwise, puts the key-value pair with the {@code trash} value
079: * in the underlying {@link Map}. This is equivalent to moving the
080: * element from this set to the "trash" set. Note that if the operation
081: * is applied on the "trash" set itself or if this set doesn't have a
082: * trash ({@code trash==null}), then the element is effectively
083: * removed from the underlying map.</li>
084: * </ul>
085: */
086: private final Map map;
087:
088: /**
089: * The set where to move removed elements,
090: * or {@code null} if there is none.
091: */
092: private final DisjointSet trash;
093:
094: /**
095: * Construct a initially empty set. There is initially no other set mutually
096: * exclusive with this one. Mutually exclusive sets must be created using the
097: * {@code DisjointSet(DisjointSet)} constructor with this newly created
098: * set as argument.
099: * <p>
100: * {@code DisjointSet}s constructed using this constructor has no trash.
101: * All remove operations on this set really remove all references to the
102: * removed element, like a usual {@link Set}. This is opposed to moving the
103: * element to a "trash" set, which is allowed by the {@code DisjointSet(true)}
104: * constructor.
105: */
106: public DisjointSet() {
107: this (false);
108: }
109:
110: /**
111: * Construct a initially empty set with an optional trash set. There is initially
112: * no other set mutually exclusive with this one. Mutually exclusive sets must be
113: * created using the {@code DisjointSet(DisjointSet)} constructor with this
114: * newly created set as argument.
115: *
116: * @param hasTrash If {@code true}, all {@linkplain #remove remove} operations
117: * will add removed elements to a trash set (thus, really just moving the
118: * element to the trash). If {@code false}, there is no trash and this
119: * constructor behave like the no-argument constructor.
120: * @see #getTrash
121: */
122: public DisjointSet(final boolean hasTrash) {
123: map = new LinkedHashMap();
124: trash = (hasTrash) ? new DisjointSet(map) : null;
125: }
126:
127: /**
128: * Construct a new set mutually exclusive with the specified set. All sets mutually
129: * exclusive with {@code disjointSet} will also be mutually exclusive with the
130: * newly created set. If {@code disjointSet} has a trash set, the newly created
131: * set will use the same trash (i.e. all {@code remove} operations will really
132: * move the element to the trash set). Otherwise, the new {@code DisjointSet}
133: * have no trash.
134: *
135: * @param disjointSet The set to be disjoint from.
136: */
137: public DisjointSet(final DisjointSet disjointSet) {
138: map = disjointSet.map;
139: trash = disjointSet.trash;
140: }
141:
142: /**
143: * Construct a trash set.
144: */
145: private DisjointSet(final Map map) {
146: this .map = map;
147: trash = null;
148: }
149:
150: /**
151: * Returns the trash set, or {@code null} if there is none.
152: * The trash set receive all elements removed from this set.
153: */
154: public Set getTrash() {
155: return trash;
156: }
157:
158: /**
159: * Returns the number of elements in this set. The size of this set may
160: * change as a result of adding elements to a mutually exclusive set.
161: */
162: public int size() {
163: synchronized (map) {
164: int count = 0;
165: for (final Iterator it = map.values().iterator(); it
166: .hasNext();) {
167: if (it.next() == this ) {
168: count++;
169: }
170: }
171: return count;
172: }
173: }
174:
175: /**
176: * Returns {@code true} if this set contains the specified element.
177: *
178: * @param element Object to be checked for containment in this set.
179: * @return {@code true} if this set contains the specified element.
180: */
181: public boolean contains(final Object element) {
182: synchronized (map) {
183: return map.get(element) == this ;
184: }
185: }
186:
187: /**
188: * Ensures that this collection contains the specified element.
189: * Adding an element to this set will remove it from any mutually
190: * exclusive set.
191: *
192: * @param element Element whose presence in this set is to be ensured.
193: * @return {@code true} if the set changed as a result of the call.
194: */
195: public boolean add(final Object element) {
196: synchronized (map) {
197: return map.put(element, this ) != this ;
198: }
199: }
200:
201: /**
202: * Removes a single instance of the specified element from this set,
203: * if it is present. If this {@code DisjointSet} has a trash set,
204: * the removed element will be added to the trash set.
205: *
206: * @param element Element to be removed from this set.
207: * @return {@code true} if the set changed as a result of the call.
208: */
209: public boolean remove(final Object element) {
210: synchronized (map) {
211: if (map.get(element) != this ) {
212: return false; // The element do not belongs to this set.
213: } else if (trash != null) {
214: // Do not remove. Move it to the "trash" set.
215: return map.put(element, trash) != trash;
216: } else {
217: // Completly remove the element from the set.
218: return map.remove(element) != null;
219: }
220: }
221: }
222:
223: /**
224: * Returns {@code true} if this set contains
225: * all of the elements in the specified collection.
226: *
227: * @param c collection to be checked for containment in this collection.
228: * @return {@code true} if this set contains all of the elements in
229: * the specified collection.
230: */
231: public boolean containsAll(final Collection c) {
232: synchronized (map) {
233: return super .containsAll(c);
234: }
235: }
236:
237: /**
238: * Adds all of the elements in the specified collection to this set.
239: * All of the elements will be removed from mutually exclusive sets.
240: *
241: * @param c collection whose elements are to be added to this set.
242: * @return {@code true} if this set changed as a result of the call.
243: */
244: public boolean addAll(final Collection c) {
245: synchronized (map) {
246: return super .addAll(c);
247: }
248: }
249:
250: /**
251: * Removes from this set all of its elements that are contained in
252: * the specified collection. If this {@code DisjointSet} has
253: * a trash set, all removed elements will be added to the trash set.
254: *
255: * @param c elements to be removed from this set.
256: * @return {@code true} if this set changed as a result of the call.
257: */
258: public boolean removeAll(final Collection c) {
259: synchronized (map) {
260: return super .removeAll(c);
261: }
262: }
263:
264: /**
265: * Retains only the elements in this set that are contained in the specified
266: * collection. If this {@code DisjointSet} has a trash set, all removed
267: * elements will be added to the trash set.
268: *
269: * @param c elements to be retained in this collection.
270: * @return {@code true} if this collection changed as a result of the call.
271: */
272: public boolean retainAll(final Collection c) {
273: synchronized (map) {
274: return super .retainAll(c);
275: }
276: }
277:
278: /**
279: * Removes all of the elements from this set. If this {@code DisjointSet}
280: * has a trash set, all removed elements will be added to the trash set.
281: */
282: public void clear() {
283: synchronized (map) {
284: super .clear();
285: }
286: }
287:
288: /**
289: * Returns an iterator over the elements in this collection.
290: */
291: public Iterator iterator() {
292: synchronized (map) {
293: return new Iter();
294: }
295: }
296:
297: /**
298: * Returns an array containing all of the elements in this collection.
299: *
300: * @return an array containing all of the elements in this set.
301: */
302: public Object[] toArray() {
303: synchronized (map) {
304: return super .toArray();
305: }
306: }
307:
308: /**
309: * Returns an array containing all of the elements in this collection.
310: *
311: * @param a The array into which the elements of the set are to be
312: * stored, if it is big enough; otherwise, a new array of
313: * the same runtime type is allocated for this purpose.
314: * @return an array containing the elements of the set.
315: */
316: public Object[] toArray(final Object[] a) {
317: synchronized (map) {
318: return super .toArray(a);
319: }
320: }
321:
322: /**
323: * Returns a string representation of this set.
324: */
325: public String toString() {
326: synchronized (map) {
327: return super .toString();
328: }
329: }
330:
331: /**
332: * Returns an hash value for this set.
333: */
334: public int hashCode() {
335: synchronized (map) {
336: return super .hashCode();
337: }
338: }
339:
340: /**
341: * Compare this set with the specified object for equality.
342: */
343: public boolean equals(final Object set) {
344: synchronized (map) {
345: return super .equals(set);
346: }
347: }
348:
349: /**
350: * The iterator for {@link DisjointSet}.
351: *
352: * @version 1.0
353: * @author Martin Desruisseaux
354: */
355: private final class Iter implements Iterator {
356: /**
357: * The iterator over the entries of the underlying {@link Map} object.
358: */
359: private final Iterator iterator;
360:
361: /**
362: * Entry for the next element to return, or
363: * {@code null} if there is no more element.
364: */
365: private Map.Entry prefetch;
366:
367: /**
368: * Entry to remove if the {@link #remove} operation is invoked,
369: * or {@code null} if this iterator is not in a legal state
370: * for element removing. An element can be removed only after a
371: * {@link #next} call and only if this call still synchronized
372: * with the {@link Iterator#next} call on the underlying map's
373: * iterator.
374: */
375: private Map.Entry toRemove;
376:
377: /**
378: * Construct a new iterator.
379: */
380: private Iter() {
381: iterator = map.entrySet().iterator();
382: }
383:
384: /**
385: * Returns the {@link #prefetch} entry. If this entry was
386: * {@code null}, fetch the next entry. If there is no
387: * more entries, returns {@code null}.
388: */
389: private Map.Entry prefetch() {
390: toRemove = null;
391: if (prefetch == null) {
392: while (iterator.hasNext()) {
393: final Map.Entry next = (Map.Entry) iterator.next();
394: if (next.getValue() == DisjointSet.this ) {
395: prefetch = next;
396: break;
397: }
398: }
399: }
400: return prefetch;
401: }
402:
403: /**
404: * Returns {@code true} if the iteration has more elements.
405: */
406: public boolean hasNext() {
407: return prefetch() != null;
408: }
409:
410: /**
411: * Returns the next element in the iteration.
412: */
413: public Object next() {
414: toRemove = prefetch();
415: prefetch = null;
416: if (toRemove != null) {
417: return toRemove.getKey();
418: } else {
419: throw new NoSuchElementException();
420: }
421: }
422:
423: /**
424: * Removes from the underlying set the
425: * last element returned by the iterator.
426: */
427: public void remove() {
428: if (toRemove != null) {
429: if (trash != null) {
430: // Move to the trash set.
431: toRemove.setValue(trash);
432: } else {
433: iterator.remove();
434: }
435: toRemove = null;
436: } else {
437: throw new IllegalStateException();
438: }
439: }
440: }
441: }
|