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 }