001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.list;
018
019 import java.util.ArrayList;
020 import java.util.Collection;
021 import java.util.HashSet;
022 import java.util.Iterator;
023 import java.util.List;
024 import java.util.ListIterator;
025 import java.util.Set;
026
027 import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
028 import org.apache.commons.collections.iterators.AbstractListIteratorDecorator;
029 import org.apache.commons.collections.set.UnmodifiableSet;
030
031 /**
032 * Decorates a <code>List</code> to ensure that no duplicates are present
033 * much like a <code>Set</code>.
034 * <p>
035 * The <code>List</code> interface makes certain assumptions/requirements.
036 * This implementation breaks these in certain ways, but this is merely the
037 * result of rejecting duplicates.
038 * Each violation is explained in the method, but it should not affect you.
039 * Bear in mind that Sets require immutable objects to function correctly.
040 * <p>
041 * The {@link org.apache.commons.collections.set.ListOrderedSet ListOrderedSet}
042 * class provides an alternative approach, by wrapping an existing Set and
043 * retaining insertion order in the iterator.
044 * <p>
045 * This class is Serializable from Commons Collections 3.1.
046 *
047 * @since Commons Collections 3.0
048 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
049 *
050 * @author Matthew Hawthorne
051 * @author Stephen Colebourne
052 * @author Tom Dunham
053 */
054 public class SetUniqueList extends AbstractSerializableListDecorator {
055
056 /** Serialization version */
057 private static final long serialVersionUID = 7196982186153478694L;
058
059 /**
060 * Internal Set to maintain uniqueness.
061 */
062 protected final Set set;
063
064 /**
065 * Factory method to create a SetList using the supplied list to retain order.
066 * <p>
067 * If the list contains duplicates, these are removed (first indexed one kept).
068 * A <code>HashSet</code> is used for the set behaviour.
069 *
070 * @param list the list to decorate, must not be null
071 * @throws IllegalArgumentException if list is null
072 */
073 public static SetUniqueList decorate(List list) {
074 if (list == null) {
075 throw new IllegalArgumentException("List must not be null");
076 }
077 if (list.isEmpty()) {
078 return new SetUniqueList(list, new HashSet());
079 } else {
080 List temp = new ArrayList(list);
081 list.clear();
082 SetUniqueList sl = new SetUniqueList(list, new HashSet());
083 sl.addAll(temp);
084 return sl;
085 }
086 }
087
088 //-----------------------------------------------------------------------
089 /**
090 * Constructor that wraps (not copies) the List and specifies the set to use.
091 * <p>
092 * The set and list must both be correctly initialised to the same elements.
093 *
094 * @param set the set to decorate, must not be null
095 * @param list the list to decorate, must not be null
096 * @throws IllegalArgumentException if set or list is null
097 */
098 protected SetUniqueList(List list, Set set) {
099 super(list);
100 if (set == null) {
101 throw new IllegalArgumentException("Set must not be null");
102 }
103 this.set = set;
104 }
105
106 //-----------------------------------------------------------------------
107 /**
108 * Gets an unmodifiable view as a Set.
109 *
110 * @return an unmodifiable set view
111 */
112 public Set asSet() {
113 return UnmodifiableSet.decorate(set);
114 }
115
116 //-----------------------------------------------------------------------
117 /**
118 * Adds an element to the list if it is not already present.
119 * <p>
120 * <i>(Violation)</i>
121 * The <code>List</code> interface requires that this method returns
122 * <code>true</code> always. However this class may return <code>false</code>
123 * because of the <code>Set</code> behaviour.
124 *
125 * @param object the object to add
126 * @return true if object was added
127 */
128 public boolean add(Object object) {
129 // gets initial size
130 final int sizeBefore = size();
131
132 // adds element if unique
133 add(size(), object);
134
135 // compares sizes to detect if collection changed
136 return (sizeBefore != size());
137 }
138
139 /**
140 * Adds an element to a specific index in the list if it is not already present.
141 * <p>
142 * <i>(Violation)</i>
143 * The <code>List</code> interface makes the assumption that the element is
144 * always inserted. This may not happen with this implementation.
145 *
146 * @param index the index to insert at
147 * @param object the object to add
148 */
149 public void add(int index, Object object) {
150 // adds element if it is not contained already
151 if (set.contains(object) == false) {
152 super.add(index, object);
153 set.add(object);
154 }
155 }
156
157 /**
158 * Adds an element to the end of the list if it is not already present.
159 * <p>
160 * <i>(Violation)</i>
161 * The <code>List</code> interface makes the assumption that the element is
162 * always inserted. This may not happen with this implementation.
163 *
164 * @param coll the collection to add
165 */
166 public boolean addAll(Collection coll) {
167 return addAll(size(), coll);
168 }
169
170 /**
171 * Adds a collection of objects to the end of the list avoiding duplicates.
172 * <p>
173 * Only elements that are not already in this list will be added, and
174 * duplicates from the specified collection will be ignored.
175 * <p>
176 * <i>(Violation)</i>
177 * The <code>List</code> interface makes the assumption that the elements
178 * are always inserted. This may not happen with this implementation.
179 *
180 * @param index the index to insert at
181 * @param coll the collection to add in iterator order
182 * @return true if this collection changed
183 */
184 public boolean addAll(int index, Collection coll) {
185 // gets initial size
186 final int sizeBefore = size();
187
188 // adds all elements
189 for (final Iterator it = coll.iterator(); it.hasNext();) {
190 add(it.next());
191 }
192
193 // compares sizes to detect if collection changed
194 return sizeBefore != size();
195 }
196
197 //-----------------------------------------------------------------------
198 /**
199 * Sets the value at the specified index avoiding duplicates.
200 * <p>
201 * The object is set into the specified index.
202 * Afterwards, any previous duplicate is removed
203 * If the object is not already in the list then a normal set occurs.
204 * If it is present, then the old version is removed.
205 *
206 * @param index the index to insert at
207 * @param object the object to set
208 * @return the previous object
209 */
210 public Object set(int index, Object object) {
211 int pos = indexOf(object);
212 Object removed = super.set(index, object);
213 if (pos == -1 || pos == index) {
214 return removed;
215 }
216
217 // the object is already in the uniq list
218 // (and it hasn't been swapped with itself)
219 super.remove(pos); // remove the duplicate by index
220 set.remove(removed); // remove the item deleted by the set
221 return removed; // return the item deleted by the set
222 }
223
224 public boolean remove(Object object) {
225 boolean result = super.remove(object);
226 set.remove(object);
227 return result;
228 }
229
230 public Object remove(int index) {
231 Object result = super.remove(index);
232 set.remove(result);
233 return result;
234 }
235
236 public boolean removeAll(Collection coll) {
237 boolean result = super.removeAll(coll);
238 set.removeAll(coll);
239 return result;
240 }
241
242 public boolean retainAll(Collection coll) {
243 boolean result = super.retainAll(coll);
244 set.retainAll(coll);
245 return result;
246 }
247
248 public void clear() {
249 super.clear();
250 set.clear();
251 }
252
253 public boolean contains(Object object) {
254 return set.contains(object);
255 }
256
257 public boolean containsAll(Collection coll) {
258 return set.containsAll(coll);
259 }
260
261 public Iterator iterator() {
262 return new SetListIterator(super.iterator(), set);
263 }
264
265 public ListIterator listIterator() {
266 return new SetListListIterator(super.listIterator(), set);
267 }
268
269 public ListIterator listIterator(int index) {
270 return new SetListListIterator(super.listIterator(index), set);
271 }
272
273 public List subList(int fromIndex, int toIndex) {
274 return new SetUniqueList(super.subList(fromIndex, toIndex), set);
275 }
276
277 //-----------------------------------------------------------------------
278 /**
279 * Inner class iterator.
280 */
281 static class SetListIterator extends AbstractIteratorDecorator {
282
283 protected final Set set;
284 protected Object last = null;
285
286 protected SetListIterator(Iterator it, Set set) {
287 super(it);
288 this.set = set;
289 }
290
291 public Object next() {
292 last = super.next();
293 return last;
294 }
295
296 public void remove() {
297 super.remove();
298 set.remove(last);
299 last = null;
300 }
301 }
302
303 /**
304 * Inner class iterator.
305 */
306 static class SetListListIterator extends 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("ListIterator does not support set");
341 }
342 }
343
344 }