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.set;
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.Set;
025    
026    import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
027    import org.apache.commons.collections.list.UnmodifiableList;
028    
029    /**
030     * Decorates another <code>Set</code> to ensure that the order of addition
031     * is retained and used by the iterator.
032     * <p>
033     * If an object is added to the set for a second time, it will remain in the
034     * original position in the iteration.
035     * The order can be observed from the set via the iterator or toArray methods.
036     * <p>
037     * The ListOrderedSet also has various useful direct methods. These include many
038     * from <code>List</code>, such as <code>get(int)</code>, <code>remove(int)</code>
039     * and <code>indexOf(int)</code>. An unmodifiable <code>List</code> view of 
040     * the set can be obtained via <code>asList()</code>.
041     * <p>
042     * This class cannot implement the <code>List</code> interface directly as
043     * various interface methods (notably equals/hashCode) are incompatable with a set.
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 Stephen Colebourne
051     * @author Henning P. Schmiedehausen
052     */
053    public class ListOrderedSet extends AbstractSerializableSetDecorator implements Set {
054    
055        /** Serialization version */
056        private static final long serialVersionUID = -228664372470420141L;
057    
058        /** Internal list to hold the sequence of objects */
059        protected final List setOrder;
060    
061        /**
062         * Factory method to create an ordered set specifying the list and set to use.
063         * <p>
064         * The list and set must both be empty.
065         * 
066         * @param set  the set to decorate, must be empty and not null
067         * @param list  the list to decorate, must be empty and not null
068         * @throws IllegalArgumentException if set or list is null
069         * @throws IllegalArgumentException if either the set or list is not empty
070         * @since Commons Collections 3.1
071         */
072        public static ListOrderedSet decorate(Set set, List list) {
073            if (set == null) {
074                throw new IllegalArgumentException("Set must not be null");
075            }
076            if (list == null) {
077                throw new IllegalArgumentException("List must not be null");
078            }
079            if (set.size() > 0 || list.size() > 0) {
080                throw new IllegalArgumentException("Set and List must be empty");
081            }
082            return new ListOrderedSet(set, list);
083        }
084    
085        /**
086         * Factory method to create an ordered set.
087         * <p>
088         * An <code>ArrayList</code> is used to retain order.
089         * 
090         * @param set  the set to decorate, must not be null
091         * @throws IllegalArgumentException if set is null
092         */
093        public static ListOrderedSet decorate(Set set) {
094            return new ListOrderedSet(set);
095        }
096    
097        /**
098         * Factory method to create an ordered set using the supplied list to retain order.
099         * <p>
100         * A <code>HashSet</code> is used for the set behaviour.
101         * <p>
102         * NOTE: If the list contains duplicates, the duplicates are removed,
103         * altering the specified list.
104         * 
105         * @param list  the list to decorate, must not be null
106         * @throws IllegalArgumentException if list is null
107         */
108        public static ListOrderedSet decorate(List list) {
109            if (list == null) {
110                throw new IllegalArgumentException("List must not be null");
111            }
112            Set set = new HashSet(list);
113            list.retainAll(set);
114            
115            return new ListOrderedSet(set, list);
116        }
117    
118        //-----------------------------------------------------------------------
119        /**
120         * Constructs a new empty <code>ListOrderedSet</code> using
121         * a <code>HashSet</code> and an <code>ArrayList</code> internally.
122         * 
123         * @since Commons Collections 3.1
124         */
125        public ListOrderedSet() {
126            super(new HashSet());
127            setOrder = new ArrayList();
128        }
129    
130        /**
131         * Constructor that wraps (not copies).
132         * 
133         * @param set  the set to decorate, must not be null
134         * @throws IllegalArgumentException if set is null
135         */
136        protected ListOrderedSet(Set set) {
137            super(set);
138            setOrder = new ArrayList(set);
139        }
140    
141        /**
142         * Constructor that wraps (not copies) the Set and specifies the list to use.
143         * <p>
144         * The set and list must both be correctly initialised to the same elements.
145         * 
146         * @param set  the set to decorate, must not be null
147         * @param list  the list to decorate, must not be null
148         * @throws IllegalArgumentException if set or list is null
149         */
150        protected ListOrderedSet(Set set, List list) {
151            super(set);
152            if (list == null) {
153                throw new IllegalArgumentException("List must not be null");
154            }
155            setOrder = list;
156        }
157    
158        //-----------------------------------------------------------------------
159        /**
160         * Gets an unmodifiable view of the order of the Set.
161         * 
162         * @return an unmodifiable list view
163         */
164        public List asList() {
165            return UnmodifiableList.decorate(setOrder);
166        }
167    
168        //-----------------------------------------------------------------------
169        public void clear() {
170            collection.clear();
171            setOrder.clear();
172        }
173    
174        public Iterator iterator() {
175            return new OrderedSetIterator(setOrder.iterator(), collection);
176        }
177    
178        public boolean add(Object object) {
179            if (collection.contains(object)) {
180                // re-adding doesn't change order
181                return collection.add(object);
182            } else {
183                // first add, so add to both set and list
184                boolean result = collection.add(object);
185                setOrder.add(object);
186                return result;
187            }
188        }
189    
190        public boolean addAll(Collection coll) {
191            boolean result = false;
192            for (Iterator it = coll.iterator(); it.hasNext();) {
193                Object object = it.next();
194                result = result | add(object);
195            }
196            return result;
197        }
198    
199        public boolean remove(Object object) {
200            boolean result = collection.remove(object);
201            setOrder.remove(object);
202            return result;
203        }
204    
205        public boolean removeAll(Collection coll) {
206            boolean result = false;
207            for (Iterator it = coll.iterator(); it.hasNext();) {
208                Object object = it.next();
209                result = result | remove(object);
210            }
211            return result;
212        }
213    
214        public boolean retainAll(Collection coll) {
215            boolean result = collection.retainAll(coll);
216            if (result == false) {
217                return false;
218            } else if (collection.size() == 0) {
219                setOrder.clear();
220            } else {
221                for (Iterator it = setOrder.iterator(); it.hasNext();) {
222                    Object object = it.next();
223                    if (collection.contains(object) == false) {
224                        it.remove();
225                    }
226                }
227            }
228            return result;
229        }
230    
231        public Object[] toArray() {
232            return setOrder.toArray();
233        }
234    
235        public Object[] toArray(Object a[]) {
236            return setOrder.toArray(a);
237        }
238    
239        //-----------------------------------------------------------------------
240        public Object get(int index) {
241            return setOrder.get(index);
242        }
243    
244        public int indexOf(Object object) {
245            return setOrder.indexOf(object);
246        }
247    
248        public void add(int index, Object object) {
249            if (contains(object) == false) {
250                collection.add(object);
251                setOrder.add(index, object);
252            }
253        }
254    
255        public boolean addAll(int index, Collection coll) {
256            boolean changed = false;
257            for (Iterator it = coll.iterator(); it.hasNext();) {
258                Object object = it.next();
259                if (contains(object) == false) {
260                    collection.add(object);
261                    setOrder.add(index, object);
262                    index++;
263                    changed = true;
264                }
265            }
266            return changed;
267        }
268    
269        public Object remove(int index) {
270            Object obj = setOrder.remove(index);
271            remove(obj);
272            return obj;
273        }
274    
275        /**
276         * Uses the underlying List's toString so that order is achieved. 
277         * This means that the decorated Set's toString is not used, so 
278         * any custom toStrings will be ignored. 
279         */
280        // Fortunately List.toString and Set.toString look the same
281        public String toString() {
282            return setOrder.toString();
283        }
284    
285        //-----------------------------------------------------------------------
286        /**
287         * Internal iterator handle remove.
288         */
289        static class OrderedSetIterator extends AbstractIteratorDecorator {
290            
291            /** Object we iterate on */
292            protected final Collection set;
293            /** Last object retrieved */
294            protected Object last;
295    
296            private OrderedSetIterator(Iterator iterator, Collection set) {
297                super(iterator);
298                this.set = set;
299            }
300    
301            public Object next() {
302                last = iterator.next();
303                return last;
304            }
305    
306            public void remove() {
307                set.remove(last);
308                iterator.remove();
309                last = null;
310            }
311        }
312    
313    }