1 /* 2 * Copyright (c) 2009-2011 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 package com.jme3.util; 34 35 import java.util.*; 36 37 /** 38 * <p>Provides a list with similar modification semantics to java.util.concurrent's 39 * CopyOnWriteArrayList except that it is not concurrent and also provides 40 * direct access to the current array. This List allows modification of the 41 * contents while iterating as any iterators will be looking at a snapshot of 42 * the list at the time they were created. Similarly, access the raw internal 43 * array is only presenting a snap shot and so can be safely iterated while 44 * the list is changing.</p> 45 * 46 * <p>All modifications, including set() operations will cause a copy of the 47 * data to be created that replaces the old version. Because this list is 48 * not designed for threading concurrency it further optimizes the "many modifications" 49 * case by buffering them as a normal ArrayList until the next time the contents 50 * are accessed.</p> 51 * 52 * <p>Normal list modification performance should be equal to ArrayList in a 53 * many situations and always better than CopyOnWriteArrayList. Optimum usage 54 * is when modifications are done infrequently or in batches... as is often the 55 * case in a scene graph. Read operations perform superior to all other methods 56 * as the array can be accessed directly.</p> 57 * 58 * <p>Important caveats over normal java.util.Lists:</p> 59 * <ul> 60 * <li>Even though this class supports modifying the list, the subList() method 61 * returns a read-only list. This technically breaks the List contract.</li> 62 * <li>The ListIterators returned by this class only support the remove() 63 * modification method. add() and set() are not supported on the iterator. 64 * Even after ListIterator.remove() or Iterator.remove() is called, this change 65 * is not reflected in the iterator instance as it is still refering to its 66 * original snapshot. 67 * </ul> 68 * 69 * @version $Revision: 8940 $ 70 * @author Paul Speed 71 */ 72 public class SafeArrayList<E> implements List<E> { 73 74 // Implementing List directly to avoid accidentally acquiring 75 // incorrect or non-optimal behavior from AbstractList. For 76 // example, the default iterator() method will not work for 77 // this list. 78 79 // Note: given the particular use-cases this was intended, 80 // it would make sense to nerf the public mutators and 81 // make this publicly act like a read-only list. 82 // SafeArrayList-specific methods could then be exposed 83 // for the classes like Node and Spatial to use to manage 84 // the list. This was the callers couldn't remove a child 85 // without it being detached properly, for example. 86 87 private Class<E> elementType; 88 private List<E> buffer; 89 private E[] backingArray; 90 private int size = 0; 91 92 public SafeArrayList(Class<E> elementType) { 93 this.elementType = elementType; 94 } 95 96 public SafeArrayList(Class<E> elementType, Collection<? extends E> c) { 97 this.elementType = elementType; 98 addAll(c); 99 } 100 101 protected final <T> T[] createArray(Class<T> type, int size) { 102 return (T[])java.lang.reflect.Array.newInstance(type, size); 103 } 104 105 protected final E[] createArray(int size) { 106 return createArray(elementType, size); 107 } 108 109 /** 110 * Returns a current snapshot of this List's backing array that 111 * is guaranteed not to change through further List manipulation. 112 * Changes to this array may or may not be reflected in the list and 113 * should be avoided. 114 */ 115 public final E[] getArray() { 116 if( backingArray != null ) 117 return backingArray; 118 119 if( buffer == null ) { 120 backingArray = createArray(0); 121 } else { 122 // Only keep the array or the buffer but never both at 123 // the same time. 1) it saves space, 2) it keeps the rest 124 // of the code safer. 125 backingArray = buffer.toArray( createArray(buffer.size()) ); 126 buffer = null; 127 } 128 return backingArray; 129 } 130 131 protected final List<E> getBuffer() { 132 if( buffer != null ) 133 return buffer; 134 135 if( backingArray == null ) { 136 buffer = new ArrayList(); 137 } else { 138 // Only keep the array or the buffer but never both at 139 // the same time. 1) it saves space, 2) it keeps the rest 140 // of the code safer. 141 buffer = new ArrayList( Arrays.asList(backingArray) ); 142 backingArray = null; 143 } 144 return buffer; 145 } 146 147 public final int size() { 148 return size; 149 } 150 151 public final boolean isEmpty() { 152 return size == 0; 153 } 154 155 public boolean contains(Object o) { 156 return indexOf(o) >= 0; 157 } 158 159 public Iterator<E> iterator() { 160 return listIterator(); 161 } 162 163 public Object[] toArray() { 164 return getArray(); 165 } 166 167 public <T> T[] toArray(T[] a) { 168 169 E[] array = getArray(); 170 if (a.length < array.length) { 171 return (T[])Arrays.copyOf(array, array.length, a.getClass()); 172 } 173 174 System.arraycopy( array, 0, a, 0, array.length ); 175 176 if (a.length > array.length) { 177 a[array.length] = null; 178 } 179 180 return a; 181 } 182 183 public boolean add(E e) { 184 boolean result = getBuffer().add(e); 185 size = getBuffer().size(); 186 return result; 187 } 188 189 public boolean remove(Object o) { 190 boolean result = getBuffer().remove(o); 191 size = getBuffer().size(); 192 return result; 193 } 194 195 public boolean containsAll(Collection<?> c) { 196 return Arrays.asList(getArray()).containsAll(c); 197 } 198 199 public boolean addAll(Collection<? extends E> c) { 200 boolean result = getBuffer().addAll(c); 201 size = getBuffer().size(); 202 return result; 203 } 204 205 public boolean addAll(int index, Collection<? extends E> c) { 206 boolean result = getBuffer().addAll(index, c); 207 size = getBuffer().size(); 208 return result; 209 } 210 211 public boolean removeAll(Collection<?> c) { 212 boolean result = getBuffer().removeAll(c); 213 size = getBuffer().size(); 214 return result; 215 } 216 217 public boolean retainAll(Collection<?> c) { 218 boolean result = getBuffer().retainAll(c); 219 size = getBuffer().size(); 220 return result; 221 } 222 223 public void clear() { 224 getBuffer().clear(); 225 size = 0; 226 } 227 228 public boolean equals(Object o) { 229 if( o == this ) 230 return true; 231 if( !(o instanceof List) ) //covers null too 232 return false; 233 List other = (List)o; 234 Iterator i1 = iterator(); 235 Iterator i2 = other.iterator(); 236 while( i1.hasNext() && i2.hasNext() ) { 237 Object o1 = i1.next(); 238 Object o2 = i2.next(); 239 if( o1 == o2 ) 240 continue; 241 if( o1 == null || !o1.equals(o2) ) 242 return false; 243 } 244 return !(i1.hasNext() || !i2.hasNext()); 245 } 246 247 public int hashCode() { 248 // Exactly the hash code described in the List interface, basically 249 E[] array = getArray(); 250 int result = 1; 251 for( E e : array ) { 252 result = 31 * result + (e == null ? 0 : e.hashCode()); 253 } 254 return result; 255 } 256 257 public final E get(int index) { 258 if( backingArray != null ) 259 return backingArray[index]; 260 if( buffer != null ) 261 return buffer.get(index); 262 throw new IndexOutOfBoundsException( "Index:" + index + ", Size:0" ); 263 } 264 265 public E set(int index, E element) { 266 return getBuffer().set(index, element); 267 } 268 269 public void add(int index, E element) { 270 getBuffer().add(index, element); 271 size = getBuffer().size(); 272 } 273 274 public E remove(int index) { 275 E result = getBuffer().remove(index); 276 size = getBuffer().size(); 277 return result; 278 } 279 280 public int indexOf(Object o) { 281 E[] array = getArray(); 282 for( int i = 0; i < array.length; i++ ) { 283 E element = array[i]; 284 if( element == o ) { 285 return i; 286 } 287 if( element != null && element.equals(o) ) { 288 return i; 289 } 290 } 291 return -1; 292 } 293 294 public int lastIndexOf(Object o) { 295 E[] array = getArray(); 296 for( int i = array.length - 1; i >= 0; i-- ) { 297 E element = array[i]; 298 if( element == o ) { 299 return i; 300 } 301 if( element != null && element.equals(o) ) { 302 return i; 303 } 304 } 305 return -1; 306 } 307 308 public ListIterator<E> listIterator() { 309 return new ArrayIterator<E>(getArray(), 0); 310 } 311 312 public ListIterator<E> listIterator(int index) { 313 return new ArrayIterator<E>(getArray(), index); 314 } 315 316 public List<E> subList(int fromIndex, int toIndex) { 317 318 // So far JME doesn't use subList that I can see so I'm nerfing it. 319 List<E> raw = Arrays.asList(getArray()).subList(fromIndex, toIndex); 320 return Collections.unmodifiableList(raw); 321 } 322 323 public String toString() { 324 325 E[] array = getArray(); 326 if( array.length == 0 ) { 327 return "[]"; 328 } 329 330 StringBuilder sb = new StringBuilder(); 331 sb.append('['); 332 for( int i = 0; i < array.length; i++ ) { 333 if( i > 0 ) 334 sb.append( ", " ); 335 E e = array[i]; 336 sb.append( e == this ? "(this Collection)" : e ); 337 } 338 sb.append(']'); 339 return sb.toString(); 340 } 341 342 protected class ArrayIterator<E> implements ListIterator<E> { 343 private E[] array; 344 private int next; 345 private int lastReturned; 346 347 protected ArrayIterator( E[] array, int index ) { 348 this.array = array; 349 this.next = index; 350 this.lastReturned = -1; 351 } 352 353 public boolean hasNext() { 354 return next != array.length; 355 } 356 357 public E next() { 358 if( !hasNext() ) 359 throw new NoSuchElementException(); 360 lastReturned = next++; 361 return array[lastReturned]; 362 } 363 364 public boolean hasPrevious() { 365 return next != 0; 366 } 367 368 public E previous() { 369 if( !hasPrevious() ) 370 throw new NoSuchElementException(); 371 lastReturned = --next; 372 return array[lastReturned]; 373 } 374 375 public int nextIndex() { 376 return next; 377 } 378 379 public int previousIndex() { 380 return next - 1; 381 } 382 383 public void remove() { 384 // This operation is not so easy to do but we will fake it. 385 // The issue is that the backing list could be completely 386 // different than the one this iterator is a snapshot of. 387 // We'll just remove(element) which in most cases will be 388 // correct. If the list had earlier .equals() equivalent 389 // elements then we'll remove one of those instead. Either 390 // way, none of those changes are reflected in this iterator. 391 SafeArrayList.this.remove( array[lastReturned] ); 392 } 393 394 public void set(E e) { 395 throw new UnsupportedOperationException(); 396 } 397 398 public void add(E e) { 399 throw new UnsupportedOperationException(); 400 } 401 } 402 } 403
