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