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