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    }