001: /*
002: * Copyright 2003-2005 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.set;
017:
018: import java.util.ArrayList;
019: import java.util.Collection;
020: import java.util.HashSet;
021: import java.util.Iterator;
022: import java.util.List;
023: import java.util.Set;
024:
025: import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
026: import org.apache.commons.collections.list.UnmodifiableList;
027:
028: /**
029: * Decorates another <code>Set</code> to ensure that the order of addition
030: * is retained and used by the iterator.
031: * <p>
032: * If an object is added to the set for a second time, it will remain in the
033: * original position in the iteration.
034: * The order can be observed from the set via the iterator or toArray methods.
035: * <p>
036: * The ListOrderedSet also has various useful direct methods. These include many
037: * from <code>List</code>, such as <code>get(int)</code>, <code>remove(int)</code>
038: * and <code>indexOf(int)</code>. An unmodifiable <code>List</code> view of
039: * the set can be obtained via <code>asList()</code>.
040: * <p>
041: * This class cannot implement the <code>List</code> interface directly as
042: * various interface methods (notably equals/hashCode) are incompatable with a set.
043: * <p>
044: * This class is Serializable from Commons Collections 3.1.
045: *
046: * @since Commons Collections 3.0
047: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
048: *
049: * @author Stephen Colebourne
050: * @author Henning P. Schmiedehausen
051: */
052: public class ListOrderedSet extends AbstractSerializableSetDecorator
053: implements Set {
054:
055: /** Serialization version */
056: private static final long serialVersionUID = -228664372470420141L;
057:
058: /** Internal list to hold the sequence of objects */
059: protected final List setOrder;
060:
061: /**
062: * Factory method to create an ordered set specifying the list and set to use.
063: * <p>
064: * The list and set must both be empty.
065: *
066: * @param set the set to decorate, must be empty and not null
067: * @param list the list to decorate, must be empty and not null
068: * @throws IllegalArgumentException if set or list is null
069: * @throws IllegalArgumentException if either the set or list is not empty
070: * @since Commons Collections 3.1
071: */
072: public static ListOrderedSet decorate(Set set, List list) {
073: if (set == null) {
074: throw new IllegalArgumentException("Set must not be null");
075: }
076: if (list == null) {
077: throw new IllegalArgumentException("List must not be null");
078: }
079: if (set.size() > 0 || list.size() > 0) {
080: throw new IllegalArgumentException(
081: "Set and List must be empty");
082: }
083: return new ListOrderedSet(set, list);
084: }
085:
086: /**
087: * Factory method to create an ordered set.
088: * <p>
089: * An <code>ArrayList</code> is used to retain order.
090: *
091: * @param set the set to decorate, must not be null
092: * @throws IllegalArgumentException if set is null
093: */
094: public static ListOrderedSet decorate(Set set) {
095: return new ListOrderedSet(set);
096: }
097:
098: /**
099: * Factory method to create an ordered set using the supplied list to retain order.
100: * <p>
101: * A <code>HashSet</code> is used for the set behaviour.
102: * <p>
103: * NOTE: If the list contains duplicates, the duplicates are removed,
104: * altering the specified list.
105: *
106: * @param list the list to decorate, must not be null
107: * @throws IllegalArgumentException if list is null
108: */
109: public static ListOrderedSet decorate(List list) {
110: if (list == null) {
111: throw new IllegalArgumentException("List must not be null");
112: }
113: Set set = new HashSet(list);
114: list.retainAll(set);
115:
116: return new ListOrderedSet(set, list);
117: }
118:
119: //-----------------------------------------------------------------------
120: /**
121: * Constructs a new empty <code>ListOrderedSet</code> using
122: * a <code>HashSet</code> and an <code>ArrayList</code> internally.
123: *
124: * @since Commons Collections 3.1
125: */
126: public ListOrderedSet() {
127: super (new HashSet());
128: setOrder = new ArrayList();
129: }
130:
131: /**
132: * Constructor that wraps (not copies).
133: *
134: * @param set the set to decorate, must not be null
135: * @throws IllegalArgumentException if set is null
136: */
137: protected ListOrderedSet(Set set) {
138: super (set);
139: setOrder = new ArrayList(set);
140: }
141:
142: /**
143: * Constructor that wraps (not copies) the Set and specifies the list to use.
144: * <p>
145: * The set and list must both be correctly initialised to the same elements.
146: *
147: * @param set the set to decorate, must not be null
148: * @param list the list to decorate, must not be null
149: * @throws IllegalArgumentException if set or list is null
150: */
151: protected ListOrderedSet(Set set, List list) {
152: super (set);
153: if (list == null) {
154: throw new IllegalArgumentException("List must not be null");
155: }
156: setOrder = list;
157: }
158:
159: //-----------------------------------------------------------------------
160: /**
161: * Gets an unmodifiable view of the order of the Set.
162: *
163: * @return an unmodifiable list view
164: */
165: public List asList() {
166: return UnmodifiableList.decorate(setOrder);
167: }
168:
169: //-----------------------------------------------------------------------
170: public void clear() {
171: collection.clear();
172: setOrder.clear();
173: }
174:
175: public Iterator iterator() {
176: return new OrderedSetIterator(setOrder.iterator(), collection);
177: }
178:
179: public boolean add(Object object) {
180: if (collection.contains(object)) {
181: // re-adding doesn't change order
182: return collection.add(object);
183: } else {
184: // first add, so add to both set and list
185: boolean result = collection.add(object);
186: setOrder.add(object);
187: return result;
188: }
189: }
190:
191: public boolean addAll(Collection coll) {
192: boolean result = false;
193: for (Iterator it = coll.iterator(); it.hasNext();) {
194: Object object = it.next();
195: result = result | add(object);
196: }
197: return result;
198: }
199:
200: public boolean remove(Object object) {
201: boolean result = collection.remove(object);
202: setOrder.remove(object);
203: return result;
204: }
205:
206: public boolean removeAll(Collection coll) {
207: boolean result = false;
208: for (Iterator it = coll.iterator(); it.hasNext();) {
209: Object object = it.next();
210: result = result | remove(object);
211: }
212: return result;
213: }
214:
215: public boolean retainAll(Collection coll) {
216: boolean result = collection.retainAll(coll);
217: if (result == false) {
218: return false;
219: } else if (collection.size() == 0) {
220: setOrder.clear();
221: } else {
222: for (Iterator it = setOrder.iterator(); it.hasNext();) {
223: Object object = it.next();
224: if (collection.contains(object) == false) {
225: it.remove();
226: }
227: }
228: }
229: return result;
230: }
231:
232: public Object[] toArray() {
233: return setOrder.toArray();
234: }
235:
236: public Object[] toArray(Object a[]) {
237: return setOrder.toArray(a);
238: }
239:
240: //-----------------------------------------------------------------------
241: public Object get(int index) {
242: return setOrder.get(index);
243: }
244:
245: public int indexOf(Object object) {
246: return setOrder.indexOf(object);
247: }
248:
249: public void add(int index, Object object) {
250: if (contains(object) == false) {
251: collection.add(object);
252: setOrder.add(index, object);
253: }
254: }
255:
256: public boolean addAll(int index, Collection coll) {
257: boolean changed = false;
258: for (Iterator it = coll.iterator(); it.hasNext();) {
259: Object object = it.next();
260: if (contains(object) == false) {
261: collection.add(object);
262: setOrder.add(index, object);
263: index++;
264: changed = true;
265: }
266: }
267: return changed;
268: }
269:
270: public Object remove(int index) {
271: Object obj = setOrder.remove(index);
272: remove(obj);
273: return obj;
274: }
275:
276: /**
277: * Uses the underlying List's toString so that order is achieved.
278: * This means that the decorated Set's toString is not used, so
279: * any custom toStrings will be ignored.
280: */
281: // Fortunately List.toString and Set.toString look the same
282: public String toString() {
283: return setOrder.toString();
284: }
285:
286: //-----------------------------------------------------------------------
287: /**
288: * Internal iterator handle remove.
289: */
290: static class OrderedSetIterator extends AbstractIteratorDecorator {
291:
292: /** Object we iterate on */
293: protected final Collection set;
294: /** Last object retrieved */
295: protected Object last;
296:
297: private OrderedSetIterator(Iterator iterator, Collection set) {
298: super (iterator);
299: this .set = set;
300: }
301:
302: public Object next() {
303: last = iterator.next();
304: return last;
305: }
306:
307: public void remove() {
308: set.remove(last);
309: iterator.remove();
310: last = null;
311: }
312: }
313:
314: }
|