View Javadoc

1   /*
2    *  Copyright 2001-2004 The Apache Software Foundation
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package net.sf.collections15.list;
17  
18  import java.util.ArrayList;
19  import java.util.Collection;
20  import java.util.HashSet;
21  import java.util.Iterator;
22  import java.util.List;
23  import java.util.ListIterator;
24  import java.util.Set;
25  
26  import net.sf.collections15.iterators.AbstractIteratorDecorator;
27  import net.sf.collections15.iterators.AbstractListIteratorDecorator;
28  import net.sf.collections15.set.UnmodifiableSet;
29  
30  /***
31   * Decorates a <code>List</code> to ensure that no duplicates are present
32   * much like a <code>Set</code>.
33   * <p>
34   * The <code>List</code> interface makes certain assumptions/requirements.
35   * This implementation breaks these in certain ways, but this is merely the
36   * result of rejecting duplicates.
37   * Each violation is explained in the method, but it should not affect you.
38   * <p>
39   * The {@link org.apache.commons.collections.set.ListOrderedSet ListOrderedSet}
40   * class provides an alternative approach, by wrapping an existing Set and
41   * retaining insertion order in the iterator.
42   * <p>
43   * This class is Serializable from Commons Collections 3.1.
44   *
45   * @since Commons Collections 3.0
46   * @version $Revision: 1.1 $ $Date: 2005/05/03 22:45:38 $
47   * 
48   * @author Matthew Hawthorne
49   * @author Stephen Colebourne
50   */
51  public class SetUniqueList<E> extends AbstractSerializableListDecorator<E> {
52  
53  	/*** Serialization version */
54  	private static final long serialVersionUID = 3617289047501191473L;
55   
56      /***
57       * Internal Set to maintain uniqueness.
58       */
59      protected final Set<E> set;
60  
61      /***
62       * Factory method to create a SetList using the supplied list to retain order.
63       * <p>
64       * If the list contains duplicates, these are removed (first indexed one kept).
65       * A <code>HashSet</code> is used for the set behaviour.
66       * 
67       * @param list  the list to decorate, must not be null
68       * @throws IllegalArgumentException if list is null
69       */
70      public static <T> SetUniqueList<T> decorate(List<T> list) {
71          if (list == null) {
72              throw new IllegalArgumentException("List must not be null");
73          }
74          if (list.isEmpty()) {
75              return new SetUniqueList<T>(list, new HashSet<T>());
76          } else {
77              List<T> temp = new ArrayList<T>(list);
78              list.clear();
79              SetUniqueList<T> sl = new SetUniqueList<T>(list, new HashSet<T>());
80              sl.addAll(temp);
81              return sl;
82          }
83      }
84  
85      //-----------------------------------------------------------------------
86      /***
87       * Constructor that wraps (not copies) the List and specifies the set to use.
88       * <p>
89       * The set and list must both be correctly initialised to the same elements.
90       * 
91       * @param set  the set to decorate, must not be null
92       * @param list  the list to decorate, must not be null
93       * @throws IllegalArgumentException if set or list is null
94       */
95      protected SetUniqueList(List<E> list, Set<E> set) {
96          super(list);
97          if (set == null) {
98              throw new IllegalArgumentException("Set must not be null");
99          }
100         this.set = set;
101     }
102 
103     //-----------------------------------------------------------------------
104     /***
105      * Gets an unmodifiable view as a Set.
106      * 
107      * @return an unmodifiable set view
108      */
109     public Set<E> asSet() {
110         return UnmodifiableSet.<E>decorate(set);
111     }
112 
113     //-----------------------------------------------------------------------
114     /***
115      * Adds an element to the list if it is not already present.
116      * <p>
117      * <i>(Violation)</i>
118      * The <code>List</code> interface requires that this method returns
119      * <code>true</code> always. However this class may return <code>false</code>
120      * because of the <code>Set</code> behaviour.
121      * 
122      * @param object the object to add
123      * @return true if object was added
124      */
125     public boolean add(E object) {
126         // gets initial size
127         final int sizeBefore = size();
128 
129         // adds element if unique
130         add(size(), object);
131 
132         // compares sizes to detect if collection changed
133         return (sizeBefore != size());
134     }
135 
136     /***
137      * Adds an element to a specific index in the list if it is not already present.
138      * <p>
139      * <i>(Violation)</i>
140      * The <code>List</code> interface makes the assumption that the element is
141      * always inserted. This may not happen with this implementation.
142      * 
143      * @param index  the index to insert at
144      * @param object  the object to add
145      */
146     public void add(int index, E object) {
147         // adds element if it is not contained already
148         if (set.contains(object) == false) {
149             super.add(index, object);
150             set.add(object);
151         }
152     }
153 
154     /***
155      * Adds an element to the end of the list if it is not already present.
156      * <p>
157      * <i>(Violation)</i>
158      * The <code>List</code> interface makes the assumption that the element is
159      * always inserted. This may not happen with this implementation.
160      * 
161      * @param coll  the collection to add
162      */
163     public boolean addAll(Collection<? extends E> coll) {
164         return addAll(size(), coll);
165     }
166 
167     /***
168      * Adds a collection of objects to the end of the list avoiding duplicates.
169      * <p>
170      * Only elements that are not already in this list will be added, and
171      * duplicates from the specified collection will be ignored.
172      * <p>
173      * <i>(Violation)</i>
174      * The <code>List</code> interface makes the assumption that the elements
175      * are always inserted. This may not happen with this implementation.
176      * 
177      * @param index  the index to insert at
178      * @param coll  the collection to add in iterator order
179      * @return true if this collection changed
180      */
181     public boolean addAll(int index, Collection<? extends E> coll) {
182         // gets initial size
183         final int sizeBefore = size();
184 
185         // adds all elements
186         for( E object : coll ) {
187             add(object);
188         }
189 
190         // compares sizes to detect if collection changed
191         return sizeBefore != size();
192     }
193 
194     //-----------------------------------------------------------------------
195     /***
196      * Sets the value at the specified index avoiding duplicates.
197      * <p>
198      * The object is set into the specified index.
199      * Afterwards, any previous duplicate is removed
200      * If the object is not already in the list then a normal set occurs.
201      * If it is present, then the old version is removed and re-added at this index
202      * 
203      * @param index  the index to insert at
204      * @param object  the object to set
205      * @return the previous object
206      */
207     public E set(int index, E object) {
208         int pos = indexOf(object);
209         E result = super.set(index, object);
210         if (pos == -1 || pos == index) {
211             return result;
212         }
213         return remove(pos);
214     }
215 
216     public boolean remove(Object object) {
217         boolean result = super.remove(object);
218         set.remove(object);
219         return result;
220     }
221 
222     public E remove(int index) {
223         E result = super.remove(index);
224         set.remove(result);
225         return result;
226     }
227 
228     public boolean removeAll(Collection<?> coll) {
229         boolean result = super.removeAll(coll);
230         set.removeAll(coll);
231         return result;
232     }
233 
234     public boolean retainAll(Collection<?> coll) {
235         boolean result = super.retainAll(coll);
236         set.retainAll(coll);
237         return result;
238     }
239 
240     public void clear() {
241         super.clear();
242         set.clear();
243     }
244 
245     public boolean contains(Object object) {
246         return set.contains(object);
247     }
248 
249     public boolean containsAll(Collection<?> coll) {
250         return set.containsAll(coll);
251     }
252 
253     public Iterator<E> iterator() {
254         return new SetListIterator<E>(super.iterator(), set);
255     }
256 
257     public ListIterator<E> listIterator() {
258         return new SetListListIterator<E>(super.listIterator(), set);
259     }
260 
261     public ListIterator<E> listIterator(int index) {
262         return new SetListListIterator<E>(super.listIterator(index), set);
263     }
264 
265     public List<E> subList(int fromIndex, int toIndex) {
266         return new SetUniqueList<E>(super.subList(fromIndex, toIndex), set);
267     }
268 
269     //-----------------------------------------------------------------------
270     /***
271      * Inner class iterator.
272      */
273     static class SetListIterator<T> extends AbstractIteratorDecorator<T> {
274         
275         protected final Set<T> set;
276         protected T last = null;
277         
278         protected SetListIterator(Iterator<T> it, Set<T> set) {
279             super(it);
280             this.set = set;
281         }
282         
283         public T next() {
284             last = super.next();
285             return last;
286         }
287 
288         public void remove() {
289             super.remove();
290             set.remove(last);
291             last = null;
292         }
293     }
294     
295     /***
296      * Inner class iterator.
297      */
298     static class SetListListIterator<T> extends AbstractListIteratorDecorator<T> {
299         
300         protected final Set<T> set;
301         protected T last = null;
302         
303         protected SetListListIterator(ListIterator<T> it, Set<T> set) {
304             super(it);
305             this.set = set;
306         }
307         
308         public T next() {
309             last = super.next();
310             return last;
311         }
312 
313         public T previous() {
314             last = super.previous();
315             return last;
316         }
317 
318         public void remove() {
319             super.remove();
320             set.remove(last);
321             last = null;
322         }
323 
324         public void add(T object) {
325             if (set.contains(object) == false) {
326                 super.add(object);
327                 set.add(object);
328             }
329         }
330         
331         public void set(T object) {
332             throw new UnsupportedOperationException("ListIterator does not support set");
333         }
334     }
335     
336 }