1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
127 final int sizeBefore = size();
128
129
130 add(size(), object);
131
132
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
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
183 final int sizeBefore = size();
184
185
186 for( E object : coll ) {
187 add(object);
188 }
189
190
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 }