001: /*
002: * Copyright 2001-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.list;
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.ListIterator;
024: import java.util.Set;
025:
026: import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
027: import org.apache.commons.collections.iterators.AbstractListIteratorDecorator;
028: import org.apache.commons.collections.set.UnmodifiableSet;
029:
030: /**
031: * Decorates a <code>List</code> to ensure that no duplicates are present
032: * much like a <code>Set</code>.
033: * <p>
034: * The <code>List</code> interface makes certain assumptions/requirements.
035: * This implementation breaks these in certain ways, but this is merely the
036: * result of rejecting duplicates.
037: * Each violation is explained in the method, but it should not affect you.
038: * Bear in mind that Sets require immutable objects to function correctly.
039: * <p>
040: * The {@link org.apache.commons.collections.set.ListOrderedSet ListOrderedSet}
041: * class provides an alternative approach, by wrapping an existing Set and
042: * retaining insertion order in the iterator.
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 Matthew Hawthorne
050: * @author Stephen Colebourne
051: * @author Tom Dunham
052: */
053: public class SetUniqueList extends AbstractSerializableListDecorator {
054:
055: /** Serialization version */
056: private static final long serialVersionUID = 7196982186153478694L;
057:
058: /**
059: * Internal Set to maintain uniqueness.
060: */
061: protected final Set set;
062:
063: /**
064: * Factory method to create a SetList using the supplied list to retain order.
065: * <p>
066: * If the list contains duplicates, these are removed (first indexed one kept).
067: * A <code>HashSet</code> is used for the set behaviour.
068: *
069: * @param list the list to decorate, must not be null
070: * @throws IllegalArgumentException if list is null
071: */
072: public static SetUniqueList decorate(List list) {
073: if (list == null) {
074: throw new IllegalArgumentException("List must not be null");
075: }
076: if (list.isEmpty()) {
077: return new SetUniqueList(list, new HashSet());
078: } else {
079: List temp = new ArrayList(list);
080: list.clear();
081: SetUniqueList sl = new SetUniqueList(list, new HashSet());
082: sl.addAll(temp);
083: return sl;
084: }
085: }
086:
087: //-----------------------------------------------------------------------
088: /**
089: * Constructor that wraps (not copies) the List and specifies the set to use.
090: * <p>
091: * The set and list must both be correctly initialised to the same elements.
092: *
093: * @param set the set to decorate, must not be null
094: * @param list the list to decorate, must not be null
095: * @throws IllegalArgumentException if set or list is null
096: */
097: protected SetUniqueList(List list, Set set) {
098: super (list);
099: if (set == null) {
100: throw new IllegalArgumentException("Set must not be null");
101: }
102: this .set = set;
103: }
104:
105: //-----------------------------------------------------------------------
106: /**
107: * Gets an unmodifiable view as a Set.
108: *
109: * @return an unmodifiable set view
110: */
111: public Set asSet() {
112: return UnmodifiableSet.decorate(set);
113: }
114:
115: //-----------------------------------------------------------------------
116: /**
117: * Adds an element to the list if it is not already present.
118: * <p>
119: * <i>(Violation)</i>
120: * The <code>List</code> interface requires that this method returns
121: * <code>true</code> always. However this class may return <code>false</code>
122: * because of the <code>Set</code> behaviour.
123: *
124: * @param object the object to add
125: * @return true if object was added
126: */
127: public boolean add(Object object) {
128: // gets initial size
129: final int sizeBefore = size();
130:
131: // adds element if unique
132: add(size(), object);
133:
134: // compares sizes to detect if collection changed
135: return (sizeBefore != size());
136: }
137:
138: /**
139: * Adds an element to a specific index in the list if it is not already present.
140: * <p>
141: * <i>(Violation)</i>
142: * The <code>List</code> interface makes the assumption that the element is
143: * always inserted. This may not happen with this implementation.
144: *
145: * @param index the index to insert at
146: * @param object the object to add
147: */
148: public void add(int index, Object object) {
149: // adds element if it is not contained already
150: if (set.contains(object) == false) {
151: super .add(index, object);
152: set.add(object);
153: }
154: }
155:
156: /**
157: * Adds an element to the end of the list if it is not already present.
158: * <p>
159: * <i>(Violation)</i>
160: * The <code>List</code> interface makes the assumption that the element is
161: * always inserted. This may not happen with this implementation.
162: *
163: * @param coll the collection to add
164: */
165: public boolean addAll(Collection coll) {
166: return addAll(size(), coll);
167: }
168:
169: /**
170: * Adds a collection of objects to the end of the list avoiding duplicates.
171: * <p>
172: * Only elements that are not already in this list will be added, and
173: * duplicates from the specified collection will be ignored.
174: * <p>
175: * <i>(Violation)</i>
176: * The <code>List</code> interface makes the assumption that the elements
177: * are always inserted. This may not happen with this implementation.
178: *
179: * @param index the index to insert at
180: * @param coll the collection to add in iterator order
181: * @return true if this collection changed
182: */
183: public boolean addAll(int index, Collection coll) {
184: // gets initial size
185: final int sizeBefore = size();
186:
187: // adds all elements
188: for (final Iterator it = coll.iterator(); it.hasNext();) {
189: add(it.next());
190: }
191:
192: // compares sizes to detect if collection changed
193: return sizeBefore != size();
194: }
195:
196: //-----------------------------------------------------------------------
197: /**
198: * Sets the value at the specified index avoiding duplicates.
199: * <p>
200: * The object is set into the specified index.
201: * Afterwards, any previous duplicate is removed
202: * If the object is not already in the list then a normal set occurs.
203: * If it is present, then the old version is removed.
204: *
205: * @param index the index to insert at
206: * @param object the object to set
207: * @return the previous object
208: */
209: public Object set(int index, Object object) {
210: int pos = indexOf(object);
211: Object removed = super .set(index, object);
212: if (pos == -1 || pos == index) {
213: return removed;
214: }
215:
216: // the object is already in the uniq list
217: // (and it hasn't been swapped with itself)
218: super .remove(pos); // remove the duplicate by index
219: set.remove(removed); // remove the item deleted by the set
220: return removed; // return the item deleted by the set
221: }
222:
223: public boolean remove(Object object) {
224: boolean result = super .remove(object);
225: set.remove(object);
226: return result;
227: }
228:
229: public Object remove(int index) {
230: Object result = super .remove(index);
231: set.remove(result);
232: return result;
233: }
234:
235: public boolean removeAll(Collection coll) {
236: boolean result = super .removeAll(coll);
237: set.removeAll(coll);
238: return result;
239: }
240:
241: public boolean retainAll(Collection coll) {
242: boolean result = super .retainAll(coll);
243: set.retainAll(coll);
244: return result;
245: }
246:
247: public void clear() {
248: super .clear();
249: set.clear();
250: }
251:
252: public boolean contains(Object object) {
253: return set.contains(object);
254: }
255:
256: public boolean containsAll(Collection coll) {
257: return set.containsAll(coll);
258: }
259:
260: public Iterator iterator() {
261: return new SetListIterator(super .iterator(), set);
262: }
263:
264: public ListIterator listIterator() {
265: return new SetListListIterator(super .listIterator(), set);
266: }
267:
268: public ListIterator listIterator(int index) {
269: return new SetListListIterator(super .listIterator(index), set);
270: }
271:
272: public List subList(int fromIndex, int toIndex) {
273: return new SetUniqueList(super .subList(fromIndex, toIndex), set);
274: }
275:
276: //-----------------------------------------------------------------------
277: /**
278: * Inner class iterator.
279: */
280: static class SetListIterator extends AbstractIteratorDecorator {
281:
282: protected final Set set;
283: protected Object last = null;
284:
285: protected SetListIterator(Iterator it, Set set) {
286: super (it);
287: this .set = set;
288: }
289:
290: public Object next() {
291: last = super .next();
292: return last;
293: }
294:
295: public void remove() {
296: super .remove();
297: set.remove(last);
298: last = null;
299: }
300: }
301:
302: /**
303: * Inner class iterator.
304: */
305: static class SetListListIterator extends
306: AbstractListIteratorDecorator {
307:
308: protected final Set set;
309: protected Object last = null;
310:
311: protected SetListListIterator(ListIterator it, Set set) {
312: super (it);
313: this .set = set;
314: }
315:
316: public Object next() {
317: last = super .next();
318: return last;
319: }
320:
321: public Object previous() {
322: last = super .previous();
323: return last;
324: }
325:
326: public void remove() {
327: super .remove();
328: set.remove(last);
329: last = null;
330: }
331:
332: public void add(Object object) {
333: if (set.contains(object) == false) {
334: super .add(object);
335: set.add(object);
336: }
337: }
338:
339: public void set(Object object) {
340: throw new UnsupportedOperationException(
341: "ListIterator does not support set");
342: }
343: }
344:
345: }
|