jme3/util/SafeArrayList.java

/*
 * Copyright (c) 2009-2011 jMonkeyEngine
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
 *   may be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package com.jme3.util;

import java.util.*;

/**
 *  <p>Provides a list with similar modification semantics to java.util.concurrent's
 *  CopyOnWriteArrayList except that it is not concurrent and also provides
 *  direct access to the current array.  This List allows modification of the
 *  contents while iterating as any iterators will be looking at a snapshot of
 *  the list at the time they were created.  Similarly, access the raw internal
 *  array is only presenting a snap shot and so can be safely iterated while
 *  the list is changing.</p>
 *
 *  <p>All modifications, including set() operations will cause a copy of the
 *  data to be created that replaces the old version.  Because this list is
 *  not designed for threading concurrency it further optimizes the "many modifications"
 *  case by buffering them as a normal ArrayList until the next time the contents
 *  are accessed.</p>
 *
 *  <p>Normal list modification performance should be equal to ArrayList in a
 *  many situations and always better than CopyOnWriteArrayList.  Optimum usage
 *  is when modifications are done infrequently or in batches... as is often the
 *  case in a scene graph.  Read operations perform superior to all other methods
 *  as the array can be accessed directly.</p>
 *
 *  <p>Important caveats over normal java.util.Lists:</p>
 *  <ul>
 *  <li>Even though this class supports modifying the list, the subList() method
 *  returns a read-only list.  This technically breaks the List contract.</li>
 *  <li>The ListIterators returned by this class only support the remove()
 *  modification method.  add() and set() are not supported on the iterator.
 *  Even after ListIterator.remove() or Iterator.remove() is called, this change
 *  is not reflected in the iterator instance as it is still refering to its
 *  original snapshot.
 *  </ul>
 *
 *  @version   $Revision: 8940 $
 *  @author    Paul Speed
 */
public class SafeArrayList<E> implements List<E> {

    // Implementing List directly to avoid accidentally acquiring
    // incorrect or non-optimal behavior from AbstractList.  For
    // example, the default iterator() method will not work for
    // this list.

    // Note: given the particular use-cases this was intended,
    //       it would make sense to nerf the public mutators and
    //       make this publicly act like a read-only list.
    //       SafeArrayList-specific methods could then be exposed
    //       for the classes like Node and Spatial to use to manage
    //       the list.  This was the callers couldn't remove a child
    //       without it being detached properly, for example.

    private Class<E> elementType;
    private List<E> buffer;
    private E[] backingArray;
    private int size = 0;

    public SafeArrayList(Class<E> elementType) {
        this.elementType = elementType;
    }

    public SafeArrayList(Class<E> elementType, Collection<? extends E> c) {
        this.elementType = elementType;
        addAll(c);
    }

    protected final <T> T[] createArray(Class<T> type, int size) {
        return (T[])java.lang.reflect.Array.newInstance(type, size);
    }

    protected final E[] createArray(int size) {
        return createArray(elementType, size);
    }

    /**
     *  Returns a current snapshot of this List's backing array that
     *  is guaranteed not to change through further List manipulation.
     *  Changes to this array may or may not be reflected in the list and
     *  should be avoided.
     */
    public final E[] getArray() {
        if( backingArray != null )
            return backingArray;

        if( buffer == null ) {
            backingArray = createArray(0);
        } else {
            // Only keep the array or the buffer but never both at
            // the same time.  1) it saves space, 2) it keeps the rest
            // of the code safer.
            backingArray = buffer.toArray( createArray(buffer.size()) );
            buffer = null;
        }
        return backingArray;
    }

    protected final List<E> getBuffer() {
        if( buffer != null )
            return buffer;

        if( backingArray == null ) {
            buffer = new ArrayList();
        } else {
            // Only keep the array or the buffer but never both at
            // the same time.  1) it saves space, 2) it keeps the rest
            // of the code safer.
            buffer = new ArrayList( Arrays.asList(backingArray) );
            backingArray = null;
        }
        return buffer;
    }

    public final int size() {
        return size;
    }

    public final boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public Object[] toArray() {
        return getArray();
    }

    public <T> T[] toArray(T[] a) {

        E[] array = getArray();
        if (a.length < array.length) {
            return (T[])Arrays.copyOf(array, array.length, a.getClass());
        }

        System.arraycopy( array, 0, a, 0, array.length );

        if (a.length > array.length) {
            a[array.length] = null;
        }

        return a;
    }

    public boolean add(E e) {
        boolean result = getBuffer().add(e);
        size = getBuffer().size();
        return result;
    }

    public boolean remove(Object o) {
        boolean result = getBuffer().remove(o);
        size = getBuffer().size();
        return result;
    }

    public boolean containsAll(Collection<?> c) {
        return Arrays.asList(getArray()).containsAll(c);
    }

    public boolean addAll(Collection<? extends E> c) {
        boolean result = getBuffer().addAll(c);
        size = getBuffer().size();
        return result;
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        boolean result = getBuffer().addAll(index, c);
        size = getBuffer().size();
        return result;
    }

    public boolean removeAll(Collection<?> c) {
        boolean result = getBuffer().removeAll(c);
        size = getBuffer().size();
        return result;
    }

    public boolean retainAll(Collection<?> c) {
        boolean result = getBuffer().retainAll(c);
        size = getBuffer().size();
        return result;
    }

    public void clear() {
        getBuffer().clear();
        size = 0;
    }

    public boolean equals(Object o) {
        if( o == this )
            return true;
        if( !(o instanceof List) ) //covers null too
            return false;
        List other = (List)o;
        Iterator i1 = iterator();
        Iterator i2 = other.iterator();
        while( i1.hasNext() && i2.hasNext() ) {
            Object o1 = i1.next();
            Object o2 = i2.next();
            if( o1 == o2 )
                continue;
            if( o1 == null || !o1.equals(o2) )
                return false;
        }
        return !(i1.hasNext() || !i2.hasNext());
    }

    public int hashCode() {
        // Exactly the hash code described in the List interface, basically
        E[] array = getArray();
        int result = 1;
        for( E e : array ) {
            result = 31 * result + (e == null ? 0 : e.hashCode());
        }
        return result;
    }

    public final E get(int index) {
        if( backingArray != null )
            return backingArray[index];
        if( buffer != null )
            return buffer.get(index);
        throw new IndexOutOfBoundsException( "Index:" + index + ", Size:0" );
    }

    public E set(int index, E element) {
        return getBuffer().set(index, element);
    }

    public void add(int index, E element) {
        getBuffer().add(index, element);
        size = getBuffer().size();
    }

    public E remove(int index) {
        E result = getBuffer().remove(index);
        size = getBuffer().size();
        return result;
    }

    public int indexOf(Object o) {
        E[] array = getArray();
        for( int i = 0; i < array.length; i++ ) {
            E element = array[i];
            if( element == o ) {
                return i;
            }
            if( element != null && element.equals(o) ) {
                return i;
            }
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        E[] array = getArray();
        for( int i = array.length - 1; i >= 0; i-- ) {
            E element = array[i];
            if( element == o ) {
                return i;
            }
            if( element != null && element.equals(o) ) {
                return i;
            }
        }
        return -1;
    }

    public ListIterator<E> listIterator() {
        return new ArrayIterator<E>(getArray(), 0);
    }

    public ListIterator<E> listIterator(int index) {
        return new ArrayIterator<E>(getArray(), index);
    }

    public List<E> subList(int fromIndex, int toIndex) {

        // So far JME doesn't use subList that I can see so I'm nerfing it.
        List<E> raw =  Arrays.asList(getArray()).subList(fromIndex, toIndex);
        return Collections.unmodifiableList(raw);
    }

    public String toString() {

        E[] array = getArray();
        if( array.length == 0 ) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for( int i = 0; i < array.length; i++ ) {
            if( i > 0 )
                sb.append( ", " );
            E e = array[i];
            sb.append( e == this ? "(this Collection)" : e );
        }
        sb.append(']');
        return sb.toString();
    }

    protected class ArrayIterator<E> implements ListIterator<E> {
        private E[] array;
        private int next;
        private int lastReturned;

        protected ArrayIterator( E[] array, int index ) {
            this.array = array;
            this.next = index;
            this.lastReturned = -1;
        }

        public boolean hasNext() {
            return next != array.length;
        }

        public E next() {
            if( !hasNext() )
                throw new NoSuchElementException();
            lastReturned = next++;
            return array[lastReturned];
        }

        public boolean hasPrevious() {
            return next != 0;
        }

        public E previous() {
            if( !hasPrevious() )
                throw new NoSuchElementException();
            lastReturned = --next;
            return array[lastReturned];
        }

        public int nextIndex() {
            return next;
        }

        public int previousIndex() {
            return next - 1;
        }

        public void remove() {
            // This operation is not so easy to do but we will fake it.
            // The issue is that the backing list could be completely
            // different than the one this iterator is a snapshot of.
            // We'll just remove(element) which in most cases will be
            // correct.  If the list had earlier .equals() equivalent
            // elements then we'll remove one of those instead.  Either
            // way, none of those changes are reflected in this iterator.
            SafeArrayList.this.remove( array[lastReturned] );
        }

        public void set(E e) {
            throw new UnsupportedOperationException();
        }

        public void add(E e) {
            throw new UnsupportedOperationException();
        }
    }
}