1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.set;
18
19 import java.util.ArrayList;
20 import java.util.Collection;
21 import java.util.HashSet;
22 import java.util.Iterator;
23 import java.util.List;
24 import java.util.ListIterator;
25 import java.util.Set;
26
27 import org.apache.commons.collections.OrderedIterator;
28 import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
29 import org.apache.commons.collections.list.UnmodifiableList;
30
31 /**
32 * Decorates another <code>Set</code> to ensure that the order of addition is
33 * retained and used by the iterator.
34 * <p>
35 * If an object is added to the set for a second time, it will remain in the
36 * original position in the iteration. The order can be observed from the set
37 * via the iterator or toArray methods.
38 * <p>
39 * The ListOrderedSet also has various useful direct methods. These include many
40 * from <code>List</code>, such as <code>get(int)</code>,
41 * <code>remove(int)</code> and <code>indexOf(int)</code>. An unmodifiable
42 * <code>List</code> view of the set can be obtained via <code>asList()</code>.
43 * <p>
44 * This class cannot implement the <code>List</code> interface directly as
45 * various interface methods (notably equals/hashCode) are incompatible with a
46 * set.
47 * <p>
48 * This class is Serializable from Commons Collections 3.1.
49 *
50 * @since 3.0
51 * @version $Id: ListOrderedSet.java 1429905 2013-01-07 17:15:14Z ggregory $
52 */
53 public class ListOrderedSet<E>
54 extends AbstractSerializableSetDecorator<E>
55 implements Set<E> {
56
57 /** Serialization version */
58 private static final long serialVersionUID = -228664372470420141L;
59
60 /** Internal list to hold the sequence of objects */
61 protected final List<E> setOrder;
62
63 /**
64 * Factory method to create an ordered set specifying the list and set to
65 * use.
66 * <p>
67 * The list and set must both be empty.
68 *
69 * @param <E> the element type
70 * @param set the set to decorate, must be empty and not null
71 * @param list the list to decorate, must be empty and not null
72 * @return a new ordered set
73 * @throws IllegalArgumentException if set or list is null
74 * @throws IllegalArgumentException if either the set or list is not empty
75 * @since 3.1
76 */
77 public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set, final List<E> list) {
78 if (set == null) {
79 throw new IllegalArgumentException("Set must not be null");
80 }
81 if (list == null) {
82 throw new IllegalArgumentException("List must not be null");
83 }
84 if (set.size() > 0 || list.size() > 0) {
85 throw new IllegalArgumentException("Set and List must be empty");
86 }
87 return new ListOrderedSet<E>(set, list);
88 }
89
90 /**
91 * Factory method to create an ordered set.
92 * <p>
93 * An <code>ArrayList</code> is used to retain order.
94 *
95 * @param <E> the element type
96 * @param set the set to decorate, must not be null
97 * @return a new ordered set
98 * @throws IllegalArgumentException if set is null
99 */
100 public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set) {
101 return new ListOrderedSet<E>(set);
102 }
103
104 /**
105 * Factory method to create an ordered set using the supplied list to retain
106 * order.
107 * <p>
108 * A <code>HashSet</code> is used for the set behaviour.
109 * <p>
110 * NOTE: If the list contains duplicates, the duplicates are removed,
111 * altering the specified list.
112 *
113 * @param <E> the element type
114 * @param list the list to decorate, must not be null
115 * @return a new ordered set
116 * @throws IllegalArgumentException if list is null
117 */
118 public static <E> ListOrderedSet<E> listOrderedSet(final List<E> list) {
119 if (list == null) {
120 throw new IllegalArgumentException("List must not be null");
121 }
122 final Set<E> set = new HashSet<E>(list);
123 list.retainAll(set);
124
125 return new ListOrderedSet<E>(set, list);
126 }
127
128 // -----------------------------------------------------------------------
129 /**
130 * Constructs a new empty <code>ListOrderedSet</code> using a
131 * <code>HashSet</code> and an <code>ArrayList</code> internally.
132 *
133 * @since 3.1
134 */
135 public ListOrderedSet() {
136 super(new HashSet<E>());
137 setOrder = new ArrayList<E>();
138 }
139
140 /**
141 * Constructor that wraps (not copies).
142 *
143 * @param set the set to decorate, must not be null
144 * @throws IllegalArgumentException if set is null
145 */
146 protected ListOrderedSet(final Set<E> set) {
147 super(set);
148 setOrder = new ArrayList<E>(set);
149 }
150
151 /**
152 * Constructor that wraps (not copies) the Set and specifies the list to
153 * use.
154 * <p>
155 * The set and list must both be correctly initialised to the same elements.
156 *
157 * @param set the set to decorate, must not be null
158 * @param list the list to decorate, must not be null
159 * @throws IllegalArgumentException if set or list is null
160 */
161 protected ListOrderedSet(final Set<E> set, final List<E> list) {
162 super(set);
163 if (list == null) {
164 throw new IllegalArgumentException("List must not be null");
165 }
166 setOrder = list;
167 }
168
169 // -----------------------------------------------------------------------
170 /**
171 * Gets an unmodifiable view of the order of the Set.
172 *
173 * @return an unmodifiable list view
174 */
175 public List<E> asList() {
176 return UnmodifiableList.unmodifiableList(setOrder);
177 }
178
179 // -----------------------------------------------------------------------
180 @Override
181 public void clear() {
182 collection.clear();
183 setOrder.clear();
184 }
185
186 @Override
187 public OrderedIterator<E> iterator() {
188 return new OrderedSetIterator<E>(setOrder.listIterator(), collection);
189 }
190
191 @Override
192 public boolean add(final E object) {
193 if (collection.add(object)) {
194 setOrder.add(object);
195 return true;
196 }
197 return false;
198 }
199
200 @Override
201 public boolean addAll(final Collection<? extends E> coll) {
202 boolean result = false;
203 for (final E e : coll) {
204 result |= add(e);
205 }
206 return result;
207 }
208
209 @Override
210 public boolean remove(final Object object) {
211 final boolean result = collection.remove(object);
212 if (result) {
213 setOrder.remove(object);
214 }
215 return result;
216 }
217
218 @Override
219 public boolean removeAll(final Collection<?> coll) {
220 boolean result = false;
221 for (final Object name : coll) {
222 result |= remove(name);
223 }
224 return result;
225 }
226
227 @Override
228 public boolean retainAll(final Collection<?> coll) {
229 final Set<Object> collectionRetainAll = new HashSet<Object>();
230 for (final Object next : coll) {
231 if (collection.contains(next)) {
232 collectionRetainAll.add(next);
233 }
234 }
235 if (collectionRetainAll.size() == collection.size()) {
236 return false;
237 }
238 if (collectionRetainAll.size() == 0) {
239 clear();
240 } else {
241 for (final Iterator<E> it = iterator(); it.hasNext();) {
242 if (!collectionRetainAll.contains(it.next())) {
243 it.remove();
244 }
245 }
246 }
247 return true;
248 }
249
250 @Override
251 public Object[] toArray() {
252 return setOrder.toArray();
253 }
254
255 @Override
256 public <T> T[] toArray(final T a[]) {
257 return setOrder.toArray(a);
258 }
259
260 // -----------------------------------------------------------------------
261 // Additional methods that comply to the {@link List} interface
262 // -----------------------------------------------------------------------
263
264 /**
265 * Returns the element at the specified position in this ordered set.
266 *
267 * @param index the position of the element in the ordered {@link Set}.
268 * @return the element at position {@code index}
269 * @see List#get(int)
270 */
271 public E get(final int index) {
272 return setOrder.get(index);
273 }
274
275 /**
276 * Returns the index of the first occurrence of the specified element in
277 * ordered set.
278 *
279 * @param object the element to search for
280 * @return the index of the first occurrence of the object, or {@code -1} if
281 * this ordered set does not contain this object
282 * @see List#indexOf(Object)
283 */
284 public int indexOf(final Object object) {
285 return setOrder.indexOf(object);
286 }
287
288 /**
289 * Inserts the specified element at the specified position if it is not yet
290 * contained in this ordered set (optional operation). Shifts the element
291 * currently at this position and any subsequent elements to the right.
292 *
293 * @param index the index at which the element is to be inserted
294 * @param object the element to be inserted
295 * @see List#add(int, Object)
296 */
297 public void add(final int index, final E object) {
298 if (!contains(object)) {
299 collection.add(object);
300 setOrder.add(index, object);
301 }
302 }
303
304 /**
305 * Inserts all elements in the specified collection not yet contained in the
306 * ordered set at the specified position (optional operation). Shifts the
307 * element currently at the position and all subsequent elements to the
308 * right.
309 *
310 * @param index the position to insert the elements
311 * @param coll the collection containing the elements to be inserted
312 * @return {@code true} if this ordered set changed as a result of the call
313 * @see List#addAll(int, Collection)
314 */
315 public boolean addAll(final int index, final Collection<? extends E> coll) {
316 boolean changed = false;
317 // collect all elements to be added for performance reasons
318 final List<E> toAdd = new ArrayList<E>();
319 for (final E e : coll) {
320 if (contains(e)) {
321 continue;
322 }
323 collection.add(e);
324 toAdd.add(e);
325 changed = true;
326 }
327
328 if (changed) {
329 setOrder.addAll(index, toAdd);
330 }
331
332 return changed;
333 }
334
335 /**
336 * Removes the element at the specified position from the ordered set.
337 * Shifts any subsequent elements to the left.
338 *
339 * @param index the index of the element to be removed
340 * @return the element that has been remove from the ordered set
341 * @see List#remove(int)
342 */
343 public Object remove(final int index) {
344 final Object obj = setOrder.remove(index);
345 remove(obj);
346 return obj;
347 }
348
349 /**
350 * Uses the underlying List's toString so that order is achieved. This means
351 * that the decorated Set's toString is not used, so any custom toStrings
352 * will be ignored.
353 *
354 * @return a string representation of the ordered set
355 */
356 // Fortunately List.toString and Set.toString look the same
357 @Override
358 public String toString() {
359 return setOrder.toString();
360 }
361
362 // -----------------------------------------------------------------------
363 /**
364 * Internal iterator handle remove.
365 */
366 static class OrderedSetIterator<E>
367 extends AbstractIteratorDecorator<E>
368 implements OrderedIterator<E> {
369
370 /** Object we iterate on */
371 protected final Collection<E> set;
372
373 /** Last object retrieved */
374 protected E last;
375
376 private OrderedSetIterator(final ListIterator<E> iterator, final Collection<E> set) {
377 super(iterator);
378 this.set = set;
379 }
380
381 @Override
382 public E next() {
383 last = iterator.next();
384 return last;
385 }
386
387 @Override
388 public void remove() {
389 set.remove(last);
390 iterator.remove();
391 last = null;
392 }
393
394 public boolean hasPrevious() {
395 return ((ListIterator<E>) iterator).hasPrevious();
396 }
397
398 public E previous() {
399 last = ((ListIterator<E>) iterator).previous();
400 return last;
401 }
402 }
403
404 }