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.list; 018 019import java.lang.reflect.InvocationTargetException; 020import java.util.ArrayList; 021import java.util.Collection; 022import java.util.HashSet; 023import java.util.Iterator; 024import java.util.List; 025import java.util.ListIterator; 026import java.util.Objects; 027import java.util.Set; 028import java.util.function.Predicate; 029 030import org.apache.commons.collections4.ListUtils; 031import org.apache.commons.collections4.iterators.AbstractIteratorDecorator; 032import org.apache.commons.collections4.iterators.AbstractListIteratorDecorator; 033import org.apache.commons.collections4.set.UnmodifiableSet; 034 035/** 036 * Decorates a {@code List} to ensure that no duplicates are present much 037 * like a {@code Set}. 038 * <p> 039 * The {@code List} interface makes certain assumptions/requirements. This 040 * implementation breaks these in certain ways, but this is merely the result of 041 * rejecting duplicates. Each violation is explained in the method, but it 042 * should not affect you. Bear in mind that Sets require immutable objects to 043 * function correctly. 044 * </p> 045 * <p> 046 * The {@link org.apache.commons.collections4.set.ListOrderedSet ListOrderedSet} 047 * class provides an alternative approach, by wrapping an existing Set and 048 * retaining insertion order in the iterator. 049 * </p> 050 * <p> 051 * This class is Serializable from Commons Collections 3.1. 052 * </p> 053 * 054 * @since 3.0 055 */ 056public class SetUniqueList<E> extends AbstractSerializableListDecorator<E> { 057 058 /** 059 * Inner class iterator. 060 */ 061 static class SetListIterator<E> extends AbstractIteratorDecorator<E> { 062 063 private final Set<E> set; 064 private E last; 065 066 protected SetListIterator(final Iterator<E> it, final Set<E> set) { 067 super(it); 068 this.set = set; 069 } 070 071 @Override 072 public E next() { 073 last = super.next(); 074 return last; 075 } 076 077 @Override 078 public void remove() { 079 super.remove(); 080 set.remove(last); 081 last = null; 082 } 083 } 084 085 /** 086 * Inner class iterator. 087 */ 088 static class SetListListIterator<E> extends 089 AbstractListIteratorDecorator<E> { 090 091 private final Set<E> set; 092 private E last; 093 094 protected SetListListIterator(final ListIterator<E> it, final Set<E> set) { 095 super(it); 096 this.set = set; 097 } 098 099 @Override 100 public void add(final E object) { 101 if (!set.contains(object)) { 102 super.add(object); 103 set.add(object); 104 } 105 } 106 107 @Override 108 public E next() { 109 last = super.next(); 110 return last; 111 } 112 113 @Override 114 public E previous() { 115 last = super.previous(); 116 return last; 117 } 118 119 @Override 120 public void remove() { 121 super.remove(); 122 set.remove(last); 123 last = null; 124 } 125 126 @Override 127 public void set(final E object) { 128 throw new UnsupportedOperationException("ListIterator does not support set"); 129 } 130 } 131 132 /** Serialization version. */ 133 private static final long serialVersionUID = 7196982186153478694L; 134 135 /** 136 * Factory method to create a SetList using the supplied list to retain order. 137 * <p> 138 * If the list contains duplicates, these are removed (first indexed one 139 * kept). A {@code HashSet} is used for the set behavior. 140 * 141 * @param <E> the element type 142 * @param list the list to decorate, must not be null 143 * @return a new {@link SetUniqueList} 144 * @throws NullPointerException if list is null 145 * @since 4.0 146 */ 147 public static <E> SetUniqueList<E> setUniqueList(final List<E> list) { 148 Objects.requireNonNull(list, "list"); 149 if (list.isEmpty()) { 150 return new SetUniqueList<>(list, new HashSet<>()); 151 } 152 final List<E> temp = new ArrayList<>(list); 153 list.clear(); 154 final SetUniqueList<E> sl = new SetUniqueList<>(list, new HashSet<>()); 155 sl.addAll(temp); 156 return sl; 157 } 158 159 /** Internal Set to maintain uniqueness. */ 160 private final Set<E> set; 161 162 /** 163 * Constructor that wraps (not copies) the List and specifies the set to use. 164 * <p> 165 * The set and list must both be correctly initialized to the same elements. 166 * 167 * @param set the set to decorate, must not be null 168 * @param list the list to decorate, must not be null 169 * @throws NullPointerException if set or list is null 170 */ 171 protected SetUniqueList(final List<E> list, final Set<E> set) { 172 super(list); 173 this.set = Objects.requireNonNull(set, "set"); 174 } 175 176 /** 177 * Adds an element to the list if it is not already present. 178 * <p> 179 * <i>(Violation)</i> The {@code List} interface requires that this 180 * method returns {@code true} always. However, this class may return 181 * {@code false} because of the {@code Set} behavior. 182 * 183 * @param object the object to add 184 * @return true if object was added 185 */ 186 @Override 187 public boolean add(final E object) { 188 // gets initial size 189 final int sizeBefore = size(); 190 191 // adds element if unique 192 add(size(), object); 193 194 // compares sizes to detect if collection changed 195 return sizeBefore != size(); 196 } 197 198 /** 199 * Adds an element to a specific index in the list if it is not already 200 * present. 201 * <p> 202 * <i>(Violation)</i> The {@code List} interface makes the assumption 203 * that the element is always inserted. This may not happen with this 204 * implementation. 205 * 206 * @param index the index to insert at 207 * @param object the object to add 208 */ 209 @Override 210 public void add(final int index, final E object) { 211 // adds element if it is not contained already 212 if (!set.contains(object)) { 213 set.add(object); 214 super.add(index, object); 215 } 216 } 217 218 /** 219 * Adds a collection of objects to the end of the list avoiding duplicates. 220 * <p> 221 * Only elements that are not already in this list will be added, and 222 * duplicates from the specified collection will be ignored. 223 * <p> 224 * <i>(Violation)</i> The {@code List} interface makes the assumption 225 * that the elements are always inserted. This may not happen with this 226 * implementation. 227 * 228 * @param coll the collection to add in iterator order 229 * @return true if this collection changed 230 */ 231 @Override 232 public boolean addAll(final Collection<? extends E> coll) { 233 return addAll(size(), coll); 234 } 235 236 /** 237 * Adds a collection of objects a specific index in the list avoiding 238 * duplicates. 239 * <p> 240 * Only elements that are not already in this list will be added, and 241 * duplicates from the specified collection will be ignored. 242 * <p> 243 * <i>(Violation)</i> The {@code List} interface makes the assumption 244 * that the elements are always inserted. This may not happen with this 245 * implementation. 246 * 247 * @param index the index to insert at 248 * @param coll the collection to add in iterator order 249 * @return true if this collection changed 250 */ 251 @Override 252 public boolean addAll(final int index, final Collection<? extends E> coll) { 253 final List<E> temp = new ArrayList<>(); 254 for (final E e : coll) { 255 if (set.add(e)) { 256 temp.add(e); 257 } 258 } 259 return super.addAll(index, temp); 260 } 261 262 /** 263 * Gets an unmodifiable view as a Set. 264 * 265 * @return an unmodifiable set view 266 */ 267 public Set<E> asSet() { 268 return UnmodifiableSet.unmodifiableSet(set); 269 } 270 271 @Override 272 public void clear() { 273 super.clear(); 274 set.clear(); 275 } 276 277 @Override 278 public boolean contains(final Object object) { 279 return set.contains(object); 280 } 281 282 @Override 283 public boolean containsAll(final Collection<?> coll) { 284 return set.containsAll(coll); 285 } 286 287 /** 288 * Create a new {@link Set} with the same type as the provided {@code set} 289 * and populate it with all elements of {@code list}. 290 * 291 * @param set the {@link Set} to be used as return type, must not be null 292 * @param list the {@link List} to populate the {@link Set} 293 * @return a new {@link Set} populated with all elements of the provided 294 * {@link List} 295 */ 296 protected Set<E> createSetBasedOnList(final Set<E> set, final List<E> list) { 297 Set<E> subSet; 298 if (set.getClass().equals(HashSet.class)) { 299 subSet = new HashSet<>(list.size()); 300 } else { 301 try { 302 subSet = set.getClass().getDeclaredConstructor(set.getClass()).newInstance(set); 303 } catch (final InstantiationException 304 | IllegalAccessException 305 | InvocationTargetException 306 | NoSuchMethodException ie) { 307 subSet = new HashSet<>(); 308 } 309 } 310 subSet.addAll(list); 311 return subSet; 312 } 313 314 @Override 315 public Iterator<E> iterator() { 316 return new SetListIterator<>(super.iterator(), set); 317 } 318 319 @Override 320 public ListIterator<E> listIterator() { 321 return new SetListListIterator<>(super.listIterator(), set); 322 } 323 324 @Override 325 public ListIterator<E> listIterator(final int index) { 326 return new SetListListIterator<>(super.listIterator(index), set); 327 } 328 329 @Override 330 public E remove(final int index) { 331 final E result = super.remove(index); 332 set.remove(result); 333 return result; 334 } 335 336 @Override 337 public boolean remove(final Object object) { 338 final boolean result = set.remove(object); 339 if (result) { 340 super.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 final boolean result = super.removeIf(filter); 360 set.removeIf(filter); 361 return result; 362 } 363 364 /** 365 * {@inheritDoc} 366 * <p> 367 * This implementation iterates over the elements of this list, checking 368 * each element in turn to see if it's contained in {@code coll}. 369 * If it's not contained, it's removed from this list. As a consequence, 370 * it is advised to use a collection type for {@code coll} that provides 371 * a fast (e.g. O(1)) implementation of {@link Collection#contains(Object)}. 372 */ 373 @Override 374 public boolean retainAll(final Collection<?> coll) { 375 final boolean result = set.retainAll(coll); 376 if (!result) { 377 return false; 378 } 379 if (set.isEmpty()) { 380 super.clear(); 381 } else { 382 // use the set as parameter for the call to retainAll to improve performance 383 super.retainAll(set); 384 } 385 return result; 386 } 387 388 /** 389 * Sets the value at the specified index avoiding duplicates. 390 * <p> 391 * The object is set into the specified index. Afterwards, any previous 392 * duplicate is removed. If the object is not already in the list then a 393 * normal set occurs. If it is present, then the old version is removed. 394 * 395 * @param index the index to insert at 396 * @param object the object to set 397 * @return the previous object 398 */ 399 @Override 400 public E set(final int index, final E object) { 401 final int pos = indexOf(object); 402 final E removed = super.set(index, object); 403 404 if (pos != -1 && pos != index) { 405 // the object is already in the unique list 406 // (and it hasn't been swapped with itself) 407 super.remove(pos); // remove the duplicate by index 408 } 409 410 set.remove(removed); // remove the item deleted by the set 411 set.add(object); // add the new item to the unique set 412 413 return removed; // return the item deleted by the set 414 } 415 416 /** 417 * {@inheritDoc} 418 * <p> 419 * NOTE: from 4.0, an unmodifiable list will be returned, as changes to the 420 * subList can invalidate the parent list. 421 */ 422 @Override 423 public List<E> subList(final int fromIndex, final int toIndex) { 424 final List<E> superSubList = super.subList(fromIndex, toIndex); 425 final Set<E> subSet = createSetBasedOnList(set, superSubList); 426 return ListUtils.unmodifiableList(new SetUniqueList<>(superSubList, subSet)); 427 } 428 429}