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 }