001 /* AbstractCollection.java -- Abstract implementation of most of Collection 002 Copyright (C) 1998, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 003 004 This file is part of GNU Classpath. 005 006 GNU Classpath is free software; you can redistribute it and/or modify 007 it under the terms of the GNU General Public License as published by 008 the Free Software Foundation; either version 2, or (at your option) 009 any later version. 010 011 GNU Classpath is distributed in the hope that it will be useful, but 012 WITHOUT ANY WARRANTY; without even the implied warranty of 013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 General Public License for more details. 015 016 You should have received a copy of the GNU General Public License 017 along with GNU Classpath; see the file COPYING. If not, write to the 018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 019 02110-1301 USA. 020 021 Linking this library statically or dynamically with other modules is 022 making a combined work based on this library. Thus, the terms and 023 conditions of the GNU General Public License cover the whole 024 combination. 025 026 As a special exception, the copyright holders of this library give you 027 permission to link this library with independent modules to produce an 028 executable, regardless of the license terms of these independent 029 modules, and to copy and distribute the resulting executable under 030 terms of your choice, provided that you also meet, for each linked 031 independent module, the terms and conditions of the license of that 032 module. An independent module is a module which is not derived from 033 or based on this library. If you modify this library, you may extend 034 this exception to your version of the library, but you are not 035 obligated to do so. If you do not wish to do so, delete this 036 exception statement from your version. */ 037 038 039 package java.util; 040 041 import java.lang.reflect.Array; 042 043 /** 044 * A basic implementation of most of the methods in the Collection interface to 045 * make it easier to create a collection. To create an unmodifiable Collection, 046 * just subclass AbstractCollection and provide implementations of the 047 * iterator() and size() methods. The Iterator returned by iterator() need only 048 * provide implementations of hasNext() and next() (that is, it may throw an 049 * UnsupportedOperationException if remove() is called). To create a modifiable 050 * Collection, you must in addition provide an implementation of the 051 * add(Object) method and the Iterator returned by iterator() must provide an 052 * implementation of remove(). Other methods should be overridden if the 053 * backing data structure allows for a more efficient implementation. The 054 * precise implementation used by AbstractCollection is documented, so that 055 * subclasses can tell which methods could be implemented more efficiently. 056 * <p> 057 * 058 * The programmer should provide a no-argument constructor, and one that 059 * accepts another Collection, as recommended by the Collection interface. 060 * Unfortunately, there is no way to enforce this in Java. 061 * 062 * @author Original author unknown 063 * @author Bryce McKinlay 064 * @author Eric Blake (ebb9@email.byu.edu) 065 * @author Tom Tromey (tromey@redhat.com) 066 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 067 * @see Collection 068 * @see AbstractSet 069 * @see AbstractList 070 * @since 1.2 071 * @status updated to 1.4 072 */ 073 public abstract class AbstractCollection<E> 074 implements Collection<E>, Iterable<E> 075 { 076 /** 077 * The main constructor, for use by subclasses. 078 */ 079 protected AbstractCollection() 080 { 081 } 082 083 /** 084 * Return an Iterator over this collection. The iterator must provide the 085 * hasNext and next methods and should in addition provide remove if the 086 * collection is modifiable. 087 * 088 * @return an iterator 089 */ 090 public abstract Iterator<E> iterator(); 091 092 /** 093 * Return the number of elements in this collection. If there are more than 094 * Integer.MAX_VALUE elements, return Integer.MAX_VALUE. 095 * 096 * @return the size 097 */ 098 public abstract int size(); 099 100 /** 101 * Add an object to the collection (optional operation). This implementation 102 * always throws an UnsupportedOperationException - it should be 103 * overridden if the collection is to be modifiable. If the collection 104 * does not accept duplicates, simply return false. Collections may specify 105 * limitations on what may be added. 106 * 107 * @param o the object to add 108 * @return true if the add operation caused the Collection to change 109 * @throws UnsupportedOperationException if the add operation is not 110 * supported on this collection 111 * @throws NullPointerException if the collection does not support null 112 * @throws ClassCastException if the object is of the wrong type 113 * @throws IllegalArgumentException if some aspect of the object prevents 114 * it from being added 115 */ 116 public boolean add(E o) 117 { 118 throw new UnsupportedOperationException(); 119 } 120 121 /** 122 * Add all the elements of a given collection to this collection (optional 123 * operation). This implementation obtains an Iterator over the given 124 * collection and iterates over it, adding each element with the 125 * add(Object) method (thus this method will fail with an 126 * UnsupportedOperationException if the add method does). The behavior is 127 * unspecified if the specified collection is modified during the iteration, 128 * including the special case of trying addAll(this) on a non-empty 129 * collection. 130 * 131 * @param c the collection to add the elements of to this collection 132 * @return true if the add operation caused the Collection to change 133 * @throws UnsupportedOperationException if the add operation is not 134 * supported on this collection 135 * @throws NullPointerException if the specified collection is null 136 * @throws ClassCastException if the type of any element in c is 137 * not a valid type for addition. 138 * @throws IllegalArgumentException if some aspect of any element 139 * in c prevents it being added. 140 * @throws NullPointerException if any element in c is null and this 141 * collection doesn't allow null values. 142 * @see #add(Object) 143 */ 144 public boolean addAll(Collection<? extends E> c) 145 { 146 Iterator<? extends E> itr = c.iterator(); 147 boolean modified = false; 148 int pos = c.size(); 149 while (--pos >= 0) 150 modified |= add(itr.next()); 151 return modified; 152 } 153 154 /** 155 * Remove all elements from the collection (optional operation). This 156 * implementation obtains an iterator over the collection and calls next 157 * and remove on it repeatedly (thus this method will fail with an 158 * UnsupportedOperationException if the Iterator's remove method does) 159 * until there are no more elements to remove. 160 * Many implementations will have a faster way of doing this. 161 * 162 * @throws UnsupportedOperationException if the Iterator returned by 163 * iterator does not provide an implementation of remove 164 * @see Iterator#remove() 165 */ 166 public void clear() 167 { 168 Iterator<E> itr = iterator(); 169 int pos = size(); 170 while (--pos >= 0) 171 { 172 itr.next(); 173 itr.remove(); 174 } 175 } 176 177 /** 178 * Test whether this collection contains a given object. That is, if the 179 * collection has an element e such that (o == null ? e == null : 180 * o.equals(e)). This implementation obtains an iterator over the collection 181 * and iterates over it, testing each element for equality with the given 182 * object. If it is equal, true is returned. Otherwise false is returned when 183 * the end of the collection is reached. 184 * 185 * @param o the object to remove from this collection 186 * @return true if this collection contains an object equal to o 187 */ 188 public boolean contains(Object o) 189 { 190 Iterator<E> itr = iterator(); 191 int pos = size(); 192 while (--pos >= 0) 193 if (equals(o, itr.next())) 194 return true; 195 return false; 196 } 197 198 /** 199 * Tests whether this collection contains all the elements in a given 200 * collection. This implementation iterates over the given collection, 201 * testing whether each element is contained in this collection. If any one 202 * is not, false is returned. Otherwise true is returned. 203 * 204 * @param c the collection to test against 205 * @return true if this collection contains all the elements in the given 206 * collection 207 * @throws NullPointerException if the given collection is null 208 * @see #contains(Object) 209 */ 210 public boolean containsAll(Collection<?> c) 211 { 212 Iterator<?> itr = c.iterator(); 213 int pos = c.size(); 214 while (--pos >= 0) 215 if (!contains(itr.next())) 216 return false; 217 return true; 218 } 219 220 /** 221 * Test whether this collection is empty. This implementation returns 222 * size() == 0. 223 * 224 * @return true if this collection is empty. 225 * @see #size() 226 */ 227 public boolean isEmpty() 228 { 229 return size() == 0; 230 } 231 232 /** 233 * Remove a single instance of an object from this collection (optional 234 * operation). That is, remove one element e such that 235 * <code>(o == null ? e == null : o.equals(e))</code>, if such an element 236 * exists. This implementation obtains an iterator over the collection 237 * and iterates over it, testing each element for equality with the given 238 * object. If it is equal, it is removed by the iterator's remove method 239 * (thus this method will fail with an UnsupportedOperationException if 240 * the Iterator's remove method does). After the first element has been 241 * removed, true is returned; if the end of the collection is reached, false 242 * is returned. 243 * 244 * @param o the object to remove from this collection 245 * @return true if the remove operation caused the Collection to change, or 246 * equivalently if the collection did contain o. 247 * @throws UnsupportedOperationException if this collection's Iterator 248 * does not support the remove method 249 * @see Iterator#remove() 250 */ 251 public boolean remove(Object o) 252 { 253 Iterator<E> itr = iterator(); 254 int pos = size(); 255 while (--pos >= 0) 256 if (equals(o, itr.next())) 257 { 258 itr.remove(); 259 return true; 260 } 261 return false; 262 } 263 264 /** 265 * Remove from this collection all its elements that are contained in a given 266 * collection (optional operation). This implementation iterates over this 267 * collection, and for each element tests if it is contained in the given 268 * collection. If so, it is removed by the Iterator's remove method (thus 269 * this method will fail with an UnsupportedOperationException if the 270 * Iterator's remove method does). 271 * 272 * @param c the collection to remove the elements of 273 * @return true if the remove operation caused the Collection to change 274 * @throws UnsupportedOperationException if this collection's Iterator 275 * does not support the remove method 276 * @throws NullPointerException if the collection, c, is null. 277 * @see Iterator#remove() 278 */ 279 public boolean removeAll(Collection<?> c) 280 { 281 return removeAllInternal(c); 282 } 283 284 /** 285 * Remove from this collection all its elements that are contained in a given 286 * collection (optional operation). This implementation iterates over this 287 * collection, and for each element tests if it is contained in the given 288 * collection. If so, it is removed by the Iterator's remove method (thus 289 * this method will fail with an UnsupportedOperationException if the 290 * Iterator's remove method does). This method is necessary for ArrayList, 291 * which cannot publicly override removeAll but can optimize this call. 292 * 293 * @param c the collection to remove the elements of 294 * @return true if the remove operation caused the Collection to change 295 * @throws UnsupportedOperationException if this collection's Iterator 296 * does not support the remove method 297 * @throws NullPointerException if the collection, c, is null. 298 * @see Iterator#remove() 299 */ 300 // Package visible for use throughout java.util. 301 boolean removeAllInternal(Collection<?> c) 302 { 303 Iterator<E> itr = iterator(); 304 boolean modified = false; 305 int pos = size(); 306 while (--pos >= 0) 307 if (c.contains(itr.next())) 308 { 309 itr.remove(); 310 modified = true; 311 } 312 return modified; 313 } 314 315 /** 316 * Remove from this collection all its elements that are not contained in a 317 * given collection (optional operation). This implementation iterates over 318 * this collection, and for each element tests if it is contained in the 319 * given collection. If not, it is removed by the Iterator's remove method 320 * (thus this method will fail with an UnsupportedOperationException if 321 * the Iterator's remove method does). 322 * 323 * @param c the collection to retain the elements of 324 * @return true if the remove operation caused the Collection to change 325 * @throws UnsupportedOperationException if this collection's Iterator 326 * does not support the remove method 327 * @throws NullPointerException if the collection, c, is null. 328 * @see Iterator#remove() 329 */ 330 public boolean retainAll(Collection<?> c) 331 { 332 return retainAllInternal(c); 333 } 334 335 /** 336 * Remove from this collection all its elements that are not contained in a 337 * given collection (optional operation). This implementation iterates over 338 * this collection, and for each element tests if it is contained in the 339 * given collection. If not, it is removed by the Iterator's remove method 340 * (thus this method will fail with an UnsupportedOperationException if 341 * the Iterator's remove method does). This method is necessary for 342 * ArrayList, which cannot publicly override retainAll but can optimize 343 * this call. 344 * 345 * @param c the collection to retain the elements of 346 * @return true if the remove operation caused the Collection to change 347 * @throws UnsupportedOperationException if this collection's Iterator 348 * does not support the remove method 349 * @throws NullPointerException if the collection, c, is null. 350 * @see Iterator#remove() 351 */ 352 // Package visible for use throughout java.util. 353 boolean retainAllInternal(Collection<?> c) 354 { 355 Iterator<E> itr = iterator(); 356 boolean modified = false; 357 int pos = size(); 358 while (--pos >= 0) 359 if (!c.contains(itr.next())) 360 { 361 itr.remove(); 362 modified = true; 363 } 364 return modified; 365 } 366 367 /** 368 * Return an array containing the elements of this collection. This 369 * implementation creates an Object array of size size() and then iterates 370 * over the collection, setting each element of the array from the value 371 * returned by the iterator. The returned array is safe, and is not backed 372 * by the collection. 373 * 374 * @return an array containing the elements of this collection 375 */ 376 public Object[] toArray() 377 { 378 Iterator<E> itr = iterator(); 379 int size = size(); 380 Object[] a = new Object[size]; 381 for (int pos = 0; pos < size; pos++) 382 a[pos] = itr.next(); 383 return a; 384 } 385 386 /** 387 * Copy the collection into a given array if it will fit, or into a 388 * dynamically created array of the same run-time type as the given array if 389 * not. If there is space remaining in the array, the first element after the 390 * end of the collection is set to null (this is only useful if the 391 * collection is known to contain no null elements, however). This 392 * implementation first tests whether the given array is large enough to hold 393 * all the elements of the collection. If not, the reflection API is used to 394 * allocate a new array of the same run-time type. Next an iterator is 395 * obtained over the collection and the elements are placed in the array as 396 * they are returned by the iterator. Finally the first spare element, if 397 * any, of the array is set to null, and the created array is returned. 398 * The returned array is safe; it is not backed by the collection. Note that 399 * null may not mark the last element, if the collection allows null 400 * elements. 401 * 402 * @param a the array to copy into, or of the correct run-time type 403 * @return the array that was produced 404 * @throws NullPointerException if the given array is null 405 * @throws ArrayStoreException if the type of the array precludes holding 406 * one of the elements of the Collection 407 */ 408 public <T> T[] toArray(T[] a) 409 { 410 int size = size(); 411 if (a.length < size) 412 a = (T[]) Array.newInstance(a.getClass().getComponentType(), 413 size); 414 else if (a.length > size) 415 a[size] = null; 416 417 Iterator<E> itr = iterator(); 418 for (int pos = 0; pos < size; pos++) 419 a[pos] = (T) (itr.next()); 420 return a; 421 } 422 423 /** 424 * Creates a String representation of the Collection. The string returned is 425 * of the form "[a, b, ...]" where a and b etc are the results of calling 426 * toString on the elements of the collection. This implementation obtains an 427 * Iterator over the Collection and adds each element to a StringBuffer as it 428 * is returned by the iterator. "<this>" is inserted when the collection 429 * contains itself (only works for direct containment, not for collections 430 * inside collections). 431 * 432 * @return a String representation of the Collection 433 */ 434 public String toString() 435 { 436 Iterator itr = iterator(); 437 StringBuffer r = new StringBuffer("["); 438 boolean hasNext = itr.hasNext(); 439 while (hasNext) 440 { 441 Object o = itr.next(); 442 if (o == this) 443 r.append("<this>"); 444 else 445 r.append(o); 446 hasNext = itr.hasNext(); 447 if (hasNext) 448 r.append(", "); 449 } 450 r.append("]"); 451 return r.toString(); 452 } 453 454 /** 455 * Compare two objects according to Collection semantics. 456 * 457 * @param o1 the first object 458 * @param o2 the second object 459 * @return o1 == null ? o2 == null : o1.equals(o2) 460 */ 461 // Package visible for use throughout java.util. 462 // It may be inlined since it is final. 463 static final boolean equals(Object o1, Object o2) 464 { 465 return o1 == null ? o2 == null : o1.equals(o2); 466 } 467 468 /** 469 * Hash an object according to Collection semantics. 470 * 471 * @param o the object to hash 472 * @return o1 == null ? 0 : o1.hashCode() 473 */ 474 // Package visible for use throughout java.util. 475 // It may be inlined since it is final. 476 static final int hashCode(Object o) 477 { 478 return o == null ? 0 : o.hashCode(); 479 } 480 }