001 /* 002 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. 003 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 004 * 005 * 006 * 007 * 008 * 009 * 010 * 011 * 012 * 013 * 014 * 015 * 016 * 017 * 018 * 019 * 020 * 021 * 022 * 023 * 024 */ 025 026 package railo.commons.util.mod; 027 028 import java.util.Arrays; 029 import java.util.Collection; 030 import java.util.Iterator; 031 032 public abstract class AbstractCollection<E> implements Collection<E> { 033 /** 034 * Sole constructor. (For invocation by subclass constructors, typically 035 * implicit.) 036 */ 037 protected AbstractCollection() { 038 } 039 040 // Query Operations 041 042 /** 043 * Returns an iterator over the elements contained in this collection. 044 * 045 * @return an iterator over the elements contained in this collection 046 */ 047 public abstract Iterator<E> iterator(); 048 049 public abstract int size(); 050 051 /** 052 * {@inheritDoc} 053 * 054 * <p>This implementation returns <tt>size() == 0</tt>. 055 */ 056 public boolean isEmpty() { 057 return size() == 0; 058 } 059 060 /** 061 * {@inheritDoc} 062 * 063 * <p>This implementation iterates over the elements in the collection, 064 * checking each element in turn for equality with the specified element. 065 * 066 * @throws ClassCastException {@inheritDoc} 067 * @throws NullPointerException {@inheritDoc} 068 */ 069 public boolean contains(Object o) { 070 Iterator<E> it = iterator(); 071 if (o==null) { 072 while (it.hasNext()) 073 if (it.next()==null) 074 return true; 075 } else { 076 while (it.hasNext()) 077 if (o.equals(it.next())) 078 return true; 079 } 080 return false; 081 } 082 083 /** 084 * {@inheritDoc} 085 * 086 * <p>This implementation returns an array containing all the elements 087 * returned by this collection's iterator, in the same order, stored in 088 * consecutive elements of the array, starting with index {@code 0}. 089 * The length of the returned array is equal to the number of elements 090 * returned by the iterator, even if the size of this collection changes 091 * during iteration, as might happen if the collection permits 092 * concurrent modification during iteration. The {@code size} method is 093 * called only as an optimization hint; the correct result is returned 094 * even if the iterator returns a different number of elements. 095 * 096 * <p>This method is equivalent to: 097 * 098 * <pre> {@code 099 * List<E> list = new ArrayList<E>(size()); 100 * for (E e : this) 101 * list.add(e); 102 * return list.toArray(); 103 * }</pre> 104 */ 105 public Object[] toArray() { 106 // Estimate size of array; be prepared to see more or fewer elements 107 Object[] r = new Object[size()]; 108 Iterator<E> it = iterator(); 109 for (int i = 0; i < r.length; i++) { 110 if (! it.hasNext()) // fewer elements than expected 111 return Arrays.copyOf(r, i); 112 r[i] = it.next(); 113 } 114 return it.hasNext() ? finishToArray(r, it) : r; 115 } 116 117 /** 118 * {@inheritDoc} 119 * 120 * <p>This implementation returns an array containing all the elements 121 * returned by this collection's iterator in the same order, stored in 122 * consecutive elements of the array, starting with index {@code 0}. 123 * If the number of elements returned by the iterator is too large to 124 * fit into the specified array, then the elements are returned in a 125 * newly allocated array with length equal to the number of elements 126 * returned by the iterator, even if the size of this collection 127 * changes during iteration, as might happen if the collection permits 128 * concurrent modification during iteration. The {@code size} method is 129 * called only as an optimization hint; the correct result is returned 130 * even if the iterator returns a different number of elements. 131 * 132 * <p>This method is equivalent to: 133 * 134 * <pre> {@code 135 * List<E> list = new ArrayList<E>(size()); 136 * for (E e : this) 137 * list.add(e); 138 * return list.toArray(a); 139 * }</pre> 140 * 141 * @throws ArrayStoreException {@inheritDoc} 142 * @throws NullPointerException {@inheritDoc} 143 */ 144 public <T> T[] toArray(T[] a) { 145 // Estimate size of array; be prepared to see more or fewer elements 146 int size = size(); 147 T[] r = a.length >= size ? a : 148 (T[])java.lang.reflect.Array 149 .newInstance(a.getClass().getComponentType(), size); 150 Iterator<E> it = iterator(); 151 152 for (int i = 0; i < r.length; i++) { 153 if (! it.hasNext()) { // fewer elements than expected 154 if (a != r) 155 return Arrays.copyOf(r, i); 156 r[i] = null; // null-terminate 157 return r; 158 } 159 r[i] = (T)it.next(); 160 } 161 return it.hasNext() ? finishToArray(r, it) : r; 162 } 163 164 /** 165 * The maximum size of array to allocate. 166 * Some VMs reserve some header words in an array. 167 * Attempts to allocate larger arrays may result in 168 * OutOfMemoryError: Requested array size exceeds VM limit 169 */ 170 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 171 172 /** 173 * Reallocates the array being used within toArray when the iterator 174 * returned more elements than expected, and finishes filling it from 175 * the iterator. 176 * 177 * @param r the array, replete with previously stored elements 178 * @param it the in-progress iterator over this collection 179 * @return array containing the elements in the given array, plus any 180 * further elements returned by the iterator, trimmed to size 181 */ 182 private static <T> T[] finishToArray(T[] r, Iterator<?> it) { 183 int i = r.length; 184 while (it.hasNext()) { 185 int cap = r.length; 186 if (i == cap) { 187 int newCap = cap + (cap >> 1) + 1; 188 // overflow-conscious code 189 if (newCap - MAX_ARRAY_SIZE > 0) 190 newCap = hugeCapacity(cap + 1); 191 r = Arrays.copyOf(r, newCap); 192 } 193 r[i++] = (T)it.next(); 194 } 195 // trim if overallocated 196 return (i == r.length) ? r : Arrays.copyOf(r, i); 197 } 198 199 private static int hugeCapacity(int minCapacity) { 200 if (minCapacity < 0) // overflow 201 throw new OutOfMemoryError 202 ("Required array size too large"); 203 return (minCapacity > MAX_ARRAY_SIZE) ? 204 Integer.MAX_VALUE : 205 MAX_ARRAY_SIZE; 206 } 207 208 // Modification Operations 209 210 /** 211 * {@inheritDoc} 212 * 213 * <p>This implementation always throws an 214 * <tt>UnsupportedOperationException</tt>. 215 * 216 * @throws UnsupportedOperationException {@inheritDoc} 217 * @throws ClassCastException {@inheritDoc} 218 * @throws NullPointerException {@inheritDoc} 219 * @throws IllegalArgumentException {@inheritDoc} 220 * @throws IllegalStateException {@inheritDoc} 221 */ 222 public boolean add(E e) { 223 throw new UnsupportedOperationException(); 224 } 225 226 /** 227 * {@inheritDoc} 228 * 229 * <p>This implementation iterates over the collection looking for the 230 * specified element. If it finds the element, it removes the element 231 * from the collection using the iterator's remove method. 232 * 233 * <p>Note that this implementation throws an 234 * <tt>UnsupportedOperationException</tt> if the iterator returned by this 235 * collection's iterator method does not implement the <tt>remove</tt> 236 * method and this collection contains the specified object. 237 * 238 * @throws UnsupportedOperationException {@inheritDoc} 239 * @throws ClassCastException {@inheritDoc} 240 * @throws NullPointerException {@inheritDoc} 241 */ 242 public boolean remove(Object o) { 243 Iterator<E> it = iterator(); 244 if (o==null) { 245 while (it.hasNext()) { 246 if (it.next()==null) { 247 it.remove(); 248 return true; 249 } 250 } 251 } else { 252 while (it.hasNext()) { 253 if (o.equals(it.next())) { 254 it.remove(); 255 return true; 256 } 257 } 258 } 259 return false; 260 } 261 262 263 // Bulk Operations 264 265 @Override 266 public boolean containsAll(Collection<?> c) { 267 for (Object e : c) 268 if (!contains(e)) 269 return false; 270 return true; 271 } 272 273 @Override 274 public boolean addAll(Collection<? extends E> c) { 275 boolean modified = false; 276 for (E e : c) 277 if (add(e)) 278 modified = true; 279 return modified; 280 } 281 282 @Override 283 public boolean removeAll(Collection<?> c) { 284 boolean modified = false; 285 Iterator<?> it = iterator(); 286 while (it.hasNext()) { 287 if (c.contains(it.next())) { 288 it.remove(); 289 modified = true; 290 } 291 } 292 return modified; 293 } 294 295 @Override 296 public boolean retainAll(Collection<?> c) { 297 boolean modified = false; 298 Iterator<E> it = iterator(); 299 while (it.hasNext()) { 300 if (!c.contains(it.next())) { 301 it.remove(); 302 modified = true; 303 } 304 } 305 return modified; 306 } 307 308 /** 309 * {@inheritDoc} 310 * 311 * <p>This implementation iterates over this collection, removing each 312 * element using the <tt>Iterator.remove</tt> operation. Most 313 * implementations will probably choose to override this method for 314 * efficiency. 315 * 316 * <p>Note that this implementation will throw an 317 * <tt>UnsupportedOperationException</tt> if the iterator returned by this 318 * collection's <tt>iterator</tt> method does not implement the 319 * <tt>remove</tt> method and this collection is non-empty. 320 * 321 * @throws UnsupportedOperationException {@inheritDoc} 322 */ 323 public void clear() { 324 Iterator<E> it = iterator(); 325 while (it.hasNext()) { 326 it.next(); 327 it.remove(); 328 } 329 } 330 331 332 // String conversion 333 334 /** 335 * Returns a string representation of this collection. The string 336 * representation consists of a list of the collection's elements in the 337 * order they are returned by its iterator, enclosed in square brackets 338 * (<tt>"[]"</tt>). Adjacent elements are separated by the characters 339 * <tt>", "</tt> (comma and space). Elements are converted to strings as 340 * by {@link String#valueOf(Object)}. 341 * 342 * @return a string representation of this collection 343 */ 344 public String toString() { 345 Iterator<E> it = iterator(); 346 if (! it.hasNext()) 347 return "[]"; 348 349 StringBuilder sb = new StringBuilder(); 350 sb.append('['); 351 for (;;) { 352 E e = it.next(); 353 sb.append(e == this ? "(this Collection)" : e); 354 if (! it.hasNext()) 355 return sb.append(']').toString(); 356 sb.append(',').append(' '); 357 } 358 } 359 360 }