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.list; 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.ListIterator; 025 import java.util.Set; 026 027 import org.apache.commons.collections.iterators.AbstractIteratorDecorator; 028 import org.apache.commons.collections.iterators.AbstractListIteratorDecorator; 029 import org.apache.commons.collections.set.UnmodifiableSet; 030 031 /** 032 * Decorates a <code>List</code> to ensure that no duplicates are present 033 * much like a <code>Set</code>. 034 * <p> 035 * The <code>List</code> interface makes certain assumptions/requirements. 036 * This implementation breaks these in certain ways, but this is merely the 037 * result of rejecting duplicates. 038 * Each violation is explained in the method, but it should not affect you. 039 * Bear in mind that Sets require immutable objects to function correctly. 040 * <p> 041 * The {@link org.apache.commons.collections.set.ListOrderedSet ListOrderedSet} 042 * class provides an alternative approach, by wrapping an existing Set and 043 * retaining insertion order in the iterator. 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 Matthew Hawthorne 051 * @author Stephen Colebourne 052 * @author Tom Dunham 053 */ 054 public class SetUniqueList extends AbstractSerializableListDecorator { 055 056 /** Serialization version */ 057 private static final long serialVersionUID = 7196982186153478694L; 058 059 /** 060 * Internal Set to maintain uniqueness. 061 */ 062 protected final Set set; 063 064 /** 065 * Factory method to create a SetList using the supplied list to retain order. 066 * <p> 067 * If the list contains duplicates, these are removed (first indexed one kept). 068 * A <code>HashSet</code> is used for the set behaviour. 069 * 070 * @param list the list to decorate, must not be null 071 * @throws IllegalArgumentException if list is null 072 */ 073 public static SetUniqueList decorate(List list) { 074 if (list == null) { 075 throw new IllegalArgumentException("List must not be null"); 076 } 077 if (list.isEmpty()) { 078 return new SetUniqueList(list, new HashSet()); 079 } else { 080 List temp = new ArrayList(list); 081 list.clear(); 082 SetUniqueList sl = new SetUniqueList(list, new HashSet()); 083 sl.addAll(temp); 084 return sl; 085 } 086 } 087 088 //----------------------------------------------------------------------- 089 /** 090 * Constructor that wraps (not copies) the List and specifies the set to use. 091 * <p> 092 * The set and list must both be correctly initialised to the same elements. 093 * 094 * @param set the set to decorate, must not be null 095 * @param list the list to decorate, must not be null 096 * @throws IllegalArgumentException if set or list is null 097 */ 098 protected SetUniqueList(List list, Set set) { 099 super(list); 100 if (set == null) { 101 throw new IllegalArgumentException("Set must not be null"); 102 } 103 this.set = set; 104 } 105 106 //----------------------------------------------------------------------- 107 /** 108 * Gets an unmodifiable view as a Set. 109 * 110 * @return an unmodifiable set view 111 */ 112 public Set asSet() { 113 return UnmodifiableSet.decorate(set); 114 } 115 116 //----------------------------------------------------------------------- 117 /** 118 * Adds an element to the list if it is not already present. 119 * <p> 120 * <i>(Violation)</i> 121 * The <code>List</code> interface requires that this method returns 122 * <code>true</code> always. However this class may return <code>false</code> 123 * because of the <code>Set</code> behaviour. 124 * 125 * @param object the object to add 126 * @return true if object was added 127 */ 128 public boolean add(Object object) { 129 // gets initial size 130 final int sizeBefore = size(); 131 132 // adds element if unique 133 add(size(), object); 134 135 // compares sizes to detect if collection changed 136 return (sizeBefore != size()); 137 } 138 139 /** 140 * Adds an element to a specific index in the list if it is not already present. 141 * <p> 142 * <i>(Violation)</i> 143 * The <code>List</code> interface makes the assumption that the element is 144 * always inserted. This may not happen with this implementation. 145 * 146 * @param index the index to insert at 147 * @param object the object to add 148 */ 149 public void add(int index, Object object) { 150 // adds element if it is not contained already 151 if (set.contains(object) == false) { 152 super.add(index, object); 153 set.add(object); 154 } 155 } 156 157 /** 158 * Adds an element to the end of the list if it is not already present. 159 * <p> 160 * <i>(Violation)</i> 161 * The <code>List</code> interface makes the assumption that the element is 162 * always inserted. This may not happen with this implementation. 163 * 164 * @param coll the collection to add 165 */ 166 public boolean addAll(Collection coll) { 167 return addAll(size(), coll); 168 } 169 170 /** 171 * Adds a collection of objects to the end of the list avoiding duplicates. 172 * <p> 173 * Only elements that are not already in this list will be added, and 174 * duplicates from the specified collection will be ignored. 175 * <p> 176 * <i>(Violation)</i> 177 * The <code>List</code> interface makes the assumption that the elements 178 * are always inserted. This may not happen with this implementation. 179 * 180 * @param index the index to insert at 181 * @param coll the collection to add in iterator order 182 * @return true if this collection changed 183 */ 184 public boolean addAll(int index, Collection coll) { 185 // gets initial size 186 final int sizeBefore = size(); 187 188 // adds all elements 189 for (final Iterator it = coll.iterator(); it.hasNext();) { 190 add(it.next()); 191 } 192 193 // compares sizes to detect if collection changed 194 return sizeBefore != size(); 195 } 196 197 //----------------------------------------------------------------------- 198 /** 199 * Sets the value at the specified index avoiding duplicates. 200 * <p> 201 * The object is set into the specified index. 202 * Afterwards, any previous duplicate is removed 203 * If the object is not already in the list then a normal set occurs. 204 * If it is present, then the old version is removed. 205 * 206 * @param index the index to insert at 207 * @param object the object to set 208 * @return the previous object 209 */ 210 public Object set(int index, Object object) { 211 int pos = indexOf(object); 212 Object removed = super.set(index, object); 213 if (pos == -1 || pos == index) { 214 return removed; 215 } 216 217 // the object is already in the uniq list 218 // (and it hasn't been swapped with itself) 219 super.remove(pos); // remove the duplicate by index 220 set.remove(removed); // remove the item deleted by the set 221 return removed; // return the item deleted by the set 222 } 223 224 public boolean remove(Object object) { 225 boolean result = super.remove(object); 226 set.remove(object); 227 return result; 228 } 229 230 public Object remove(int index) { 231 Object result = super.remove(index); 232 set.remove(result); 233 return result; 234 } 235 236 public boolean removeAll(Collection coll) { 237 boolean result = super.removeAll(coll); 238 set.removeAll(coll); 239 return result; 240 } 241 242 public boolean retainAll(Collection coll) { 243 boolean result = super.retainAll(coll); 244 set.retainAll(coll); 245 return result; 246 } 247 248 public void clear() { 249 super.clear(); 250 set.clear(); 251 } 252 253 public boolean contains(Object object) { 254 return set.contains(object); 255 } 256 257 public boolean containsAll(Collection coll) { 258 return set.containsAll(coll); 259 } 260 261 public Iterator iterator() { 262 return new SetListIterator(super.iterator(), set); 263 } 264 265 public ListIterator listIterator() { 266 return new SetListListIterator(super.listIterator(), set); 267 } 268 269 public ListIterator listIterator(int index) { 270 return new SetListListIterator(super.listIterator(index), set); 271 } 272 273 public List subList(int fromIndex, int toIndex) { 274 return new SetUniqueList(super.subList(fromIndex, toIndex), set); 275 } 276 277 //----------------------------------------------------------------------- 278 /** 279 * Inner class iterator. 280 */ 281 static class SetListIterator extends AbstractIteratorDecorator { 282 283 protected final Set set; 284 protected Object last = null; 285 286 protected SetListIterator(Iterator it, Set set) { 287 super(it); 288 this.set = set; 289 } 290 291 public Object next() { 292 last = super.next(); 293 return last; 294 } 295 296 public void remove() { 297 super.remove(); 298 set.remove(last); 299 last = null; 300 } 301 } 302 303 /** 304 * Inner class iterator. 305 */ 306 static class SetListListIterator extends AbstractListIteratorDecorator { 307 308 protected final Set set; 309 protected Object last = null; 310 311 protected SetListListIterator(ListIterator it, Set set) { 312 super(it); 313 this.set = set; 314 } 315 316 public Object next() { 317 last = super.next(); 318 return last; 319 } 320 321 public Object previous() { 322 last = super.previous(); 323 return last; 324 } 325 326 public void remove() { 327 super.remove(); 328 set.remove(last); 329 last = null; 330 } 331 332 public void add(Object object) { 333 if (set.contains(object) == false) { 334 super.add(object); 335 set.add(object); 336 } 337 } 338 339 public void set(Object object) { 340 throw new UnsupportedOperationException("ListIterator does not support set"); 341 } 342 } 343 344 }