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 */ 017package org.apache.commons.collections4.set; 018 019import java.util.ArrayList; 020import java.util.Collection; 021import java.util.HashSet; 022import java.util.List; 023import java.util.ListIterator; 024import java.util.Objects; 025import java.util.Set; 026import java.util.function.Predicate; 027 028import org.apache.commons.collections4.CollectionUtils; 029import org.apache.commons.collections4.OrderedIterator; 030import org.apache.commons.collections4.functors.UniquePredicate; 031import org.apache.commons.collections4.iterators.AbstractIteratorDecorator; 032import org.apache.commons.collections4.list.UnmodifiableList; 033 034/** 035 * Decorates another {@code Set} to ensure that the order of addition is 036 * retained and used by the iterator. 037 * <p> 038 * If an object is added to the set for a second time, it will remain in the 039 * original position in the iteration. The order can be observed from the set 040 * via the iterator or toArray methods. 041 * </p> 042 * <p> 043 * The ListOrderedSet also has various useful direct methods. These include many 044 * from {@code List}, such as {@code get(int)}, 045 * {@code remove(int)} and {@code indexOf(int)}. An unmodifiable 046 * {@code List} view of the set can be obtained via {@code asList()}. 047 * </p> 048 * <p> 049 * This class cannot implement the {@code List} interface directly as 050 * various interface methods (notably equals/hashCode) are incompatible with a 051 * set. 052 * </p> 053 * <p> 054 * This class is Serializable from Commons Collections 3.1. 055 * </p> 056 * 057 * @param <E> the type of the elements in this set 058 * @since 3.0 059 */ 060public class ListOrderedSet<E> 061 extends AbstractSerializableSetDecorator<E> { 062 063 /** 064 * Internal iterator handle remove. 065 */ 066 static class OrderedSetIterator<E> 067 extends AbstractIteratorDecorator<E> 068 implements OrderedIterator<E> { 069 070 /** Object we iterate on */ 071 private final Collection<E> set; 072 073 /** Last object retrieved */ 074 private E last; 075 076 private OrderedSetIterator(final ListIterator<E> iterator, final Collection<E> set) { 077 super(iterator); 078 this.set = set; 079 } 080 081 @Override 082 public boolean hasPrevious() { 083 return ((ListIterator<E>) getIterator()).hasPrevious(); 084 } 085 086 @Override 087 public E next() { 088 last = getIterator().next(); 089 return last; 090 } 091 092 @Override 093 public E previous() { 094 last = ((ListIterator<E>) getIterator()).previous(); 095 return last; 096 } 097 098 @Override 099 public void remove() { 100 set.remove(last); 101 getIterator().remove(); 102 last = null; 103 } 104 } 105 106 /** Serialization version */ 107 private static final long serialVersionUID = -228664372470420141L; 108 109 /** 110 * Factory method to create an ordered set using the supplied list to retain order. 111 * <p> 112 * A {@code HashSet} is used for the set behavior. 113 * </p> 114 * <p> 115 * NOTE: If the list contains duplicates, the duplicates are removed, 116 * altering the specified list. 117 * </p> 118 * 119 * @param <E> the element type 120 * @param list the list to decorate, must not be null 121 * @return a new ordered set 122 * @throws NullPointerException if list is null 123 * @since 4.0 124 */ 125 public static <E> ListOrderedSet<E> listOrderedSet(final List<E> list) { 126 Objects.requireNonNull(list, "list"); 127 CollectionUtils.filter(list, UniquePredicate.uniquePredicate()); 128 final Set<E> set = new HashSet<>(list); 129 130 return new ListOrderedSet<>(set, list); 131 } 132 133 /** 134 * Factory method to create an ordered set. 135 * <p> 136 * An {@code ArrayList} is used to retain order. 137 * </p> 138 * 139 * @param <E> the element type 140 * @param set the set to decorate, must not be null 141 * @return a new ordered set 142 * @throws NullPointerException if set is null 143 * @since 4.0 144 */ 145 public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set) { 146 return new ListOrderedSet<>(set); 147 } 148 149 /** 150 * Factory method to create an ordered set specifying the list and set to use. 151 * <p> 152 * The list and set must both be empty. 153 * </p> 154 * 155 * @param <E> the element type 156 * @param set the set to decorate, must be empty and not null 157 * @param list the list to decorate, must be empty and not null 158 * @return a new ordered set 159 * @throws NullPointerException if set or list is null 160 * @throws IllegalArgumentException if either the set or list is not empty 161 * @since 4.0 162 */ 163 public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set, final List<E> list) { 164 Objects.requireNonNull(set, "set"); 165 Objects.requireNonNull(list, "list"); 166 if (!set.isEmpty() || !list.isEmpty()) { 167 throw new IllegalArgumentException("Set and List must be empty"); 168 } 169 return new ListOrderedSet<>(set, list); 170 } 171 172 /** Internal list to hold the sequence of objects */ 173 private final List<E> setOrder; 174 175 /** 176 * Constructs a new empty {@code ListOrderedSet} using a 177 * {@code HashSet} and an {@code ArrayList} internally. 178 * 179 * @since 3.1 180 */ 181 public ListOrderedSet() { 182 super(new HashSet<>()); 183 setOrder = new ArrayList<>(); 184 } 185 186 /** 187 * Constructor that wraps (not copies). 188 * 189 * @param set the set to decorate, must not be null 190 * @throws NullPointerException if set is null 191 */ 192 protected ListOrderedSet(final Set<E> set) { 193 super(set); 194 setOrder = new ArrayList<>(set); 195 } 196 197 /** 198 * Constructor that wraps (not copies) the Set and specifies the list to 199 * use. 200 * <p> 201 * The set and list must both be correctly initialized to the same elements. 202 * </p> 203 * 204 * @param set the set to decorate, must not be null 205 * @param list the list to decorate, must not be null 206 * @throws NullPointerException if set or list is null 207 */ 208 protected ListOrderedSet(final Set<E> set, final List<E> list) { 209 super(set); 210 setOrder = Objects.requireNonNull(list, "list"); 211 } 212 213 @Override 214 public boolean add(final E object) { 215 if (decorated().add(object)) { 216 setOrder.add(object); 217 return true; 218 } 219 return false; 220 } 221 222 /** 223 * Inserts the specified element at the specified position if it is not yet 224 * contained in this ordered set (optional operation). Shifts the element 225 * currently at this position and any subsequent elements to the right. 226 * 227 * @param index the index at which the element is to be inserted 228 * @param object the element to be inserted 229 * @see List#add(int, Object) 230 */ 231 public void add(final int index, final E object) { 232 if (!contains(object)) { 233 decorated().add(object); 234 setOrder.add(index, object); 235 } 236 } 237 238 @Override 239 public boolean addAll(final Collection<? extends E> coll) { 240 boolean result = false; 241 for (final E e : coll) { 242 result |= add(e); 243 } 244 return result; 245 } 246 247 /** 248 * Inserts all elements in the specified collection not yet contained in the 249 * ordered set at the specified position (optional operation). Shifts the 250 * element currently at the position and all subsequent elements to the 251 * right. 252 * 253 * @param index the position to insert the elements 254 * @param coll the collection containing the elements to be inserted 255 * @return {@code true} if this ordered set changed as a result of the call 256 * @see List#addAll(int, Collection) 257 */ 258 public boolean addAll(final int index, final Collection<? extends E> coll) { 259 boolean changed = false; 260 // collect all elements to be added for performance reasons 261 final List<E> toAdd = new ArrayList<>(); 262 for (final E e : coll) { 263 if (contains(e)) { 264 continue; 265 } 266 decorated().add(e); 267 toAdd.add(e); 268 changed = true; 269 } 270 271 if (changed) { 272 setOrder.addAll(index, toAdd); 273 } 274 275 return changed; 276 } 277 278 /** 279 * Gets an unmodifiable view of the order of the Set. 280 * 281 * @return an unmodifiable list view 282 */ 283 public List<E> asList() { 284 return UnmodifiableList.unmodifiableList(setOrder); 285 } 286 287 @Override 288 public void clear() { 289 decorated().clear(); 290 setOrder.clear(); 291 } 292 293 /** 294 * Gets the element at the specified position in this ordered set. 295 * 296 * @param index the position of the element in the ordered {@link Set}. 297 * @return the element at position {@code index} 298 * @see List#get(int) 299 */ 300 public E get(final int index) { 301 return setOrder.get(index); 302 } 303 304 /** 305 * Returns the index of the first occurrence of the specified element in 306 * ordered set. 307 * 308 * @param object the element to search for 309 * @return the index of the first occurrence of the object, or {@code -1} if 310 * this ordered set does not contain this object 311 * @see List#indexOf(Object) 312 */ 313 public int indexOf(final Object object) { 314 return setOrder.indexOf(object); 315 } 316 317 @Override 318 public OrderedIterator<E> iterator() { 319 return new OrderedSetIterator<>(setOrder.listIterator(), decorated()); 320 } 321 322 /** 323 * Removes the element at the specified position from the ordered set. 324 * Shifts any subsequent elements to the left. 325 * 326 * @param index the index of the element to be removed 327 * @return the element that has been remove from the ordered set 328 * @see List#remove(int) 329 */ 330 public E remove(final int index) { 331 final E obj = setOrder.remove(index); 332 remove(obj); 333 return obj; 334 } 335 336 @Override 337 public boolean remove(final Object object) { 338 final boolean result = decorated().remove(object); 339 if (result) { 340 setOrder.remove(object); 341 } 342 return result; 343 } 344 345 @Override 346 public boolean removeAll(final Collection<?> coll) { 347 boolean result = false; 348 for (final Object name : coll) { 349 result |= remove(name); 350 } 351 return result; 352 } 353 354 /** 355 * @since 4.4 356 */ 357 @Override 358 public boolean removeIf(final Predicate<? super E> filter) { 359 if (Objects.isNull(filter)) { 360 return false; 361 } 362 final boolean result = decorated().removeIf(filter); 363 if (result) { 364 setOrder.removeIf(filter); 365 } 366 return result; 367 } 368 369 /** 370 * {@inheritDoc} 371 * <p> 372 * This implementation iterates over the elements of this set, checking 373 * each element in turn to see if it's contained in {@code coll}. 374 * If it's not contained, it's removed from this set. As a consequence, 375 * it is advised to use a collection type for {@code coll} that provides 376 * a fast (for example O(1)) implementation of {@link Collection#contains(Object)}. 377 * </p> 378 */ 379 @Override 380 public boolean retainAll(final Collection<?> coll) { 381 final boolean result = decorated().retainAll(coll); 382 if (!result) { 383 return false; 384 } 385 if (decorated().isEmpty()) { 386 setOrder.clear(); 387 } else { 388 setOrder.removeIf(e -> !decorated().contains(e)); 389 } 390 return result; 391 } 392 393 @Override 394 public Object[] toArray() { 395 return setOrder.toArray(); 396 } 397 398 @Override 399 public <T> T[] toArray(final T[] a) { 400 return setOrder.toArray(a); 401 } 402 403 /** 404 * Uses the underlying List's toString so that order is achieved. This means 405 * that the decorated Set's toString is not used, so any custom toStrings 406 * will be ignored. 407 * 408 * @return a string representation of the ordered set 409 */ 410 // Fortunately List.toString and Set.toString look the same 411 @Override 412 public String toString() { 413 return setOrder.toString(); 414 } 415 416}