/*
    * Copyright (c) 2003-2008 by Cosylab d. d.
    *
    * This file is part of Java-Common.
    *
    * Java-Common is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
   *
   * Java-Common is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * You should have received a copy of the GNU General Public License
   * along with Java-Common.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  package com.cosylab.util;
  
  import java.io.Serializable;
  import java.lang.reflect.Array;
  
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.List;
  import java.util.ListIterator;
  import java.util.NoSuchElementException;
  
  
  /**
   * A simple resizable threadsafe array. Offers minimal capability and overhead
   * for all operations except <code>toArray(Class)</code>. The main cost of the
   * array maintainance is in the addition and removal of the elements. The
   * potential traversals are very fast,  because they can occur outside the
   * synchronized blocks of code through normal arrays.  The arrays returned by
   * the <code>toArray</code> methods are of the correct runtime type. If, for
   * example, the type of the list was specified to be <code>X</code>, the
   * following cast is permitted:
   * 
   * <p>
   * <code>X[] array = (X[])list.toArray()</code>
   * </p>
   * Only one type cast is thus needed to obtain the final array for traversals.
   *
   * @author <a href="mailto:gasper.tkacik@cosylab.com">Gasper Tkacik</a>
   * @author <a href="mailto:gasper.pajor@cosylab.com">Gasper Pajor</a>
   * @version $id$
   */
  public class ObjectList implements List, Serializable
  {
  	private static final long serialVersionUID = 2766482196760164880L;
  	private Class type = null;
  	private Object[] array = null;
  
  	private class ArrayIterator implements ListIterator
  	{
  		private Object[] array;
  		private int index = 0;
  
  		/**
  		 * Creates a new ArrayIterator object.
  		 *
  		 * @param o the array for which the iterator is created
  		 * @param index DOCUMENT ME!
  		 *
  		 * @throws NullPointerException when object is null
  		 */
  		public ArrayIterator(Object[] o, int index)
  		{
  			if (o == null) {
  				throw new NullPointerException();
  			}
  
  			array = o;
  			this.index = index;
  		}
  
  		/* (non-Javadoc)
  		 * @see java.util.Iterator#hasNext()
  		 */
  		public boolean hasNext()
  		{
  			return index < array.length;
  		}
  
  		/* (non-Javadoc)
  		 * @see java.util.Iterator#next()
  		 */
  		public Object next()
  		{
  			if (index == array.length) {
  				throw new NoSuchElementException();
  			}
  
  			return array[index++];
  		}
  
 		/**
 		 * DOCUMENT ME!
 		 *
 		 * @throws UnsupportedOperationException when invoked
 		 *
 		 * @see java.util.Iterator#remove()
 		 * @deprecated uniplemented
 		 */
 		public void remove()
 		{
 			throw new UnsupportedOperationException();
 		}
 
 		/* (non-Javadoc)
 		 * @see java.util.ListIterator#nextIndex()
 		 */
 		public int nextIndex()
 		{
 			if (index == array.length) {
 				throw new NoSuchElementException();
 			}
 
 			return index;
 		}
 
 		/* (non-Javadoc)
 		 * @see java.util.ListIterator#previousIndex()
 		 */
 		public int previousIndex()
 		{
 			if (index == 0) {
 				throw new NoSuchElementException();
 			}
 
 			return index - 1;
 		}
 
 		/* (non-Javadoc)
 		 * @see java.util.ListIterator#hasPrevious()
 		 */
 		public boolean hasPrevious()
 		{
 			return index > 0;
 		}
 
 		/* (non-Javadoc)
 		 * @see java.util.ListIterator#previous()
 		 */
 		public Object previous()
 		{
 			if (index == 0) {
 				throw new NoSuchElementException();
 			}
 
 			index--;
 
 			return array[index];
 		}
 
 		/* (non-Javadoc)
 		 * @see java.util.ListIterator#add(java.lang.Object)
 		 */
 		public void add(Object o)
 		{
 			throw new UnsupportedOperationException();
 		}
 
 		/**
 		 * DOCUMENT ME!
 		 *
 		 * @param o DOCUMENT ME!
 		 *
 		 * @throws UnsupportedOperationException when invoked
 		 *
 		 * @see java.util.ListIterator#set(java.lang.Object)
 		 * @deprecated uniplemented
 		 */
 		public void set(Object o)
 		{
 			throw new UnsupportedOperationException();
 		}
 	}
 
 	/**
 	 * Creates a new ObjectList object.
 	 *
 	 * @param type the type of objects this list will hold
 	 *
 	 * @throws NullPointerException if the type is <code>null</code>
 	 */
 	public ObjectList(Class type)
 	{
 		super();
 
 		if (type == null) {
 			throw new NullPointerException("type");
 		}
 
 		this.type = type;
 		array = (Object[])Array.newInstance(type, 0);
 	}
 
 	/**
 	 * Adds an object to this list. This list can contain multiple entries of
 	 * the same object.
 	 *
 	 * @param o object to add to the collection
 	 * @param index where the object should be inserted
 	 *
 	 * @deprecated replaced by {@link #add(int, Object)}
 	 */
 	public void add(Object o, int index)
 	{
 		add(index, o);
 	}
 
 	/**
 	 * Adds an object to this list. This list can contain multiple entries of
 	 * the same object.
 	 *
 	 * @param o object to add to the collection
 	 *
 	 * @return true
 	 *
 	 * @see java.util.List#add(Object)
 	 */
 	public boolean add(Object o)
 	{
 		add(o, array.length);
 
 		return true;
 	}
 
 	/**
 	 * Removes an element from the list. If there is more than one reference to
 	 * the same object in the array, this method will remove only one
 	 * reference.
 	 *
 	 * @param o element to be removed from this list, if present.
 	 *
 	 * @return <tt>true</tt> if this list contained the specified element.
 	 *
 	 * @see java.util.List#remove(java.lang.Object)
 	 */
 	public boolean remove(Object o)
 	{
 		if (o == null) {
 			return false;
 		}
 
 		if (!type.isAssignableFrom(o.getClass())) {
 			return false;
 		}
 
 		synchronized (this) {
 			int index = -1;
 
 			for (int i = 0; i < array.length; i++) {
 				if (array[i] == o) {
 					index = i;
 
 					break;
 				}
 			}
 
 			if (index == -1) {
 				return false;
 			}
 
 			int length = array.length;
 			Object els = Array.newInstance(type, length - 1);
 			System.arraycopy(array, 0, els, 0, index);
 			System.arraycopy(array, index + 1, els, index, length - index - 1);
 			array = (Object[])els;
 		}
 
 		return true;
 	}
 
 	/**
 	 * Returns the size of the list.
 	 *
 	 * @return int list size
 	 */
 	public int size()
 	{
 		return array.length;
 	}
 
 	/**
 	 * Returns all objects in the list which are subtypes of the
 	 * <code>class</code> parameter. This necessitates the construction of a
 	 * new array which must occur in a synchronized block of code. This method
 	 * therefore takes some time to  execute.
 	 *
 	 * @param type the type of the objects to look for
 	 *
 	 * @return Object[] an array containing only those elements of the list,
 	 *         which are  a subtype of <code>type</code>
 	 *
 	 * @throws NullPointerException when type is <code>null</code>
 	 * @exception IllegalArgumentException if <code>type</code> is not a
 	 *            subtype of the type specified as the constructor parameter
 	 */
 	public Object[] toArray(Class type)
 	{
 		if (type == null) {
 			throw new NullPointerException("type");
 		}
 
 		if (!this.type.isAssignableFrom(type)) {
 			throw new IllegalArgumentException("Type '" + type
 			    + "' is not a subtype of '" + this.type + "'. Cannot cast.");
 		}
 
 		synchronized (this) {
 			int count = 0;
 
 			for (int i = 0; i < array.length; i++) {
 				if (type.isAssignableFrom(array[i].getClass())) {
 					count++;
 				}
 			}
 
 			Object retVal = Array.newInstance(type, count);
 			count = 0;
 
 			for (int i = 0; i < array.length; i++) {
 				if (type.isAssignableFrom(array[i].getClass())) {
 					Array.set(retVal, count, array[i]);
 					count++;
 				}
 			}
 
 			return (Object[])retVal;
 		}
 	}
 
 	/**
 	 * Returns the elements of this list. <b>Do not modify this array in any
 	 * way.</b>. List membership must only be affected through
 	 * <code>add</code> and <code>remove()</code> methods of this class.
 	 *
 	 * @return an array of stored objects, of the run time type specified by
 	 *         the constructor argument
 	 */
 	public Object[] toArray()
 	{
 		return array;
 	}
 
 	/**
 	 * Checks if the list contains a given element. Comparison with <code>equals</code>.
 	 * Uses linear search.
 	 *
 	 * @param o the object to look for
 	 *
 	 * @return <code>true</code> iff the list contains object <code>o</code>.
 	 */
 	public boolean contains(Object o)
 	{
 		if (array == null || array.length == 0) {
 			return false;
 		}
 
 		for (int i = 0; i < array.length; i++) {
 			if (array[i]==null ? o==null : array[i].equals(o)) {
 				return true;
 			}
 		}
 
 		return false;
 	}
 
 	/**
 	 * Returns the object at the specified index
 	 *
 	 * @param index the index of the requested object
 	 *
 	 * @return the object at the specified index.
 	 */
 	public Object get(int index)
 	{
 		return array[index];
 	}
 
 	/**
 	 * Searches for the first occurence of the given argument, testing  for
 	 * equality using the <tt>equals</tt> method.
 	 *
 	 * @param o an object.
 	 *
 	 * @return the index of the first occurrence of the argument in this list;
 	 *         returns <tt>-1</tt> if the object is not found.
 	 *
 	 * @see Object#equals(Object)
 	 */
 	public int indexOf(Object o)
 	{
 		for (int i = 0; i < array.length; i++) {
 			if (o.equals(array[i])) {
 				return i;
 			}
 		}
 
 		return -1;
 	}
 
 	/**
 	 * Produces a string rendering of this instance by enumerating all members.
 	 * Contract of <code>Object.toString</code>.
 	 *
 	 * @return String all members
 	 */
 	public String toString()
 	{
 		StringBuffer sb = new StringBuffer(500);
 		sb.append("ObjectList (size ");
 		sb.append(toArray().length);
 		sb.append(") = { ");
 
 		Object[] array = toArray();
 
 		for (int i = 0; i < array.length; i++) {
 			if (array[i] == null) {
 				continue;
 			}
 
 			sb.append(array[i].toString());
 			sb.append(' ');
 		}
 
 		sb.append('}');
 
 		return new String(sb);
 	}
 
 	/**
 	 * Empties this list. References to contained elementsw are released.
 	 */
 	public synchronized void clear()
 	{
 		array = (Object[])Array.newInstance(type, 0);
 	}
 
 	/**
 	 * Returns iterator which iterates over elements, which was contained in
 	 * list at the moment iterator was called. Iteration does not fail, if
 	 * elements are added or removed during the iteration.
 	 *
 	 * @return non-failing iterator with copy of elements
 	 */
 	public Iterator iterator()
 	{
 		return new ArrayIterator(array, 0);
 	}
 
 	/**
 	 * Tests if this list has no elements.
 	 *
 	 * @return <tt>true</tt> if this list has no elements; <tt>false</tt>
 	 *         otherwise.
 	 */
 	public boolean isEmpty()
 	{
 		return array.length == 0;
 	}
 
 	/**
 	 * Removes the element at the specified position in this list (optional
 	 * operation).  Shifts any subsequent elements to the left (subtracts one
 	 * from their indices).  Returns the element that was removed from the
 	 * list.
 	 *
 	 * @param index the index of the element to removed.
 	 *
 	 * @return the element previously at the specified position.
 	 *
 	 * @throws IndexOutOfBoundsException DOCUMENT ME!
 	 */
 	public Object remove(int index)
 	{
 		if (index < 0 || index > array.length) {
 			throw new IndexOutOfBoundsException("Index: " + index);
 		}
 
 		Object retObj = array[index];
 
 		synchronized (this) {
 			int length = array.length;
 			Object els = Array.newInstance(type, length - 1);
 			System.arraycopy(array, 0, els, 0, index);
 			System.arraycopy(array, index + 1, els, index, length - index - 1);
 			array = (Object[])els;
 		}
 
 		return retObj;
 	}
 
 	/**
 	 * Adds an object to this list. This list can contain multiple entries of
 	 * the same object.
 	 *
 	 * @param index where the object should be inserted
 	 * @param o object to add to the collection
 	 *
 	 * @throws NullPointerException
 	 * @exception ClassCastException if the RTT of o is not assignable to the
 	 *            type specified in the constructor
 	 *
 	 * @see java.util.List#add(int, Object)
 	 */
 	public void add(int index, Object o)
 	{
 		if (o == null) {
 			throw new NullPointerException("o");
 		}
 
 		if (type.isAssignableFrom(o.getClass()) == false) {
 			throw new ClassCastException("Object '" + o + "' !instanceof '"
 			    + type + "'.");
 		}
 
 		synchronized (this) {
 			int length = array.length;
 			Object els = Array.newInstance(type, length + 1);
 			index = index > length ? length : index;
 			
 			if (index == length) {
 				System.arraycopy(array, 0, els, 0, length);
 				Array.set(els, length, o);
 			} else {
 				System.arraycopy(array, 0, els, 0, index);
 				Array.set(els, index, o);
 				System.arraycopy(array, index, els, index + 1, length - index);
 			}
 
 			array = (Object[])els;
 		}
 	}
 
 	/**
 	 * Returns the index of the last occurrence of the specified object in this
 	 * list.
 	 *
 	 * @param elem the desired element.
 	 *
 	 * @return the index of the last occurrence of the specified object in this
 	 *         list; returns -1 if the object is not found.
 	 *
 	 * @see java.util.List#lastIndexOf(java.lang.Object)
 	 */
 	public int lastIndexOf(Object elem)
 	{
 		if (elem == null) {
 			for (int i = array.length - 1; i >= 0; i--) {
 				if (array[i] == null) {
 					return i;
 				}
 			}
 		} else {
 			for (int i = array.length - 1; i >= 0; i--) {
 				if (elem.equals(array[i])) {
 					return i;
 				}
 			}
 		}
 
 		return -1;
 	}
 
 	/**
 	 * Inserts all of the elements in the specified Collection into this list,
 	 * starting at the specified position.  Shifts the element currently at
 	 * that position (if any) and any subsequent elements to the right
 	 * (increases their indices).  The new elements will appear in the list in
 	 * the order that they are returned by the specified Collection's
 	 * iterator.
 	 *
 	 * @param index index at which to insert first element from the specified
 	 *        collection.
 	 * @param c elements to be inserted into this list.
 	 *
 	 * @return <tt>true</tt> if this list changed as a result of the call.
 	 *
 	 * @see java.util.List#addAll(int, java.util.Collection)
 	 */
 	public boolean addAll(int index, Collection c)
 	{
 		Object[] a = c.toArray();
 		int numNew = a.length;
 
 		synchronized (this) {
 			int length = array.length;
 			Object nArray = Array.newInstance(type, length + a.length);
 
 			//if (index == length) {
 			//	System.arraycopy(array, 0, nArray, 0, length);
 			//	Array.set(nArray, length, o);
 			//} else {
 			System.arraycopy(array, 0, nArray, 0, index);
 			System.arraycopy(a, 0, nArray, index, a.length);
 
 			//Array.set(els, index, o);
 			System.arraycopy(array, index, nArray, index + a.length,
 			    length - index);
 
 			//}
 			array = (Object[])nArray;
 		}
 
 		return numNew != 0;
 	}
 
 	/**
 	 * Appends all of the elements in the specified Collection to the end of
 	 * this list, in the order that they are returned by the specified
 	 * Collection's Iterator.
 	 *
 	 * @param c the elements to be inserted into this list.
 	 *
 	 * @return <tt>true</tt> if this list changed as a result of the call.
 	 *
 	 * @see java.util.List#addAll(java.util.Collection)
 	 */
 	public boolean addAll(Collection c)
 	{
 		Object[] a = c.toArray();
 		int numNew = a.length;
 
 		for (int i = 0; i < a.length; i++) {
 			add(a[i]);
 		}
 
 		return numNew != 0;
 	}
 
 	/**
 	 * Returns <tt>true</tt> if this collection contains all of the elements in
 	 * the specified collection.
 	 * 
 	 * <p>
 	 * This implementation iterates over the specified collection, checking
 	 * each element returned by the iterator in turn to see if it's contained
 	 * in this collection.  If all elements are so contained <tt>true</tt> is
 	 * returned, otherwise <tt>false</tt>.
 	 * </p>
 	 *
 	 * @param c collection to be checked for containment in this collection.
 	 *
 	 * @return <tt>true</tt> if this collection contains all of the elements in
 	 *         the specified collection.
 	 *
 	 * @see #contains(Object)
 	 * @see java.util.List#containsAll(java.util.Collection)
 	 */
 	public boolean containsAll(Collection c)
 	{
 		Iterator e = c.iterator();
 
 		while (e.hasNext()) {
 			if (!contains(e.next())) {
 				return false;
 			}
 		}
 
 		return true;
 	}
 
 	/**
 	 * Removes the elements that are contained in the collection.
 	 *
 	 * @param c the collection of elements to be removed
 	 *
 	 * @return <code>true</code> if at least one element is removed
 	 *
 	 * @see java.util.List#removeAll(java.util.Collection)
 	 */
 	public boolean removeAll(Collection c)
 	{
 		boolean modified = false;
 
 		for (int i = 0; i < array.length; i++) {
 			if (c.contains(array[i])) {
 				remove(i);
 				i = i - 1;
 				modified = true;
 			}
 		}
 
 		return modified;
 	}
 
 	/**
 	 * Removes all elements but those contained in the collection.
 	 *
 	 * @param c the collection of elements to keep
 	 *
 	 * @return <code>true</code> if at lest one element is removed
 	 *
 	 * @see java.util.List#retainAll(java.util.Collection)
 	 */
 	public boolean retainAll(Collection c)
 	{
 		boolean modified = false;
 
 		for (int i = 0; i < array.length; i++) {
 			if (!c.contains(array[i])) {
 				remove(i);
 				i = i - 1;
 				modified = true;
 			}
 		}
 
 		return modified;
 	}
 
 	/**
 	 * DOCUMENT ME!
 	 *
 	 * @param fromIndex DOCUMENT ME!
 	 * @param toIndex DOCUMENT ME!
 	 *
 	 * @return DOCUMENT ME!
 	 *
 	 * @throws UnsupportedOperationException when invoked
 	 *
 	 * @see java.util.List#subList(int, int)
 	 * @deprecated This method is not implemented.
 	 */
 	public List subList(int fromIndex, int toIndex)
 	{
 		/*
 		 * to implement this method, a new extended class should be made from object list,
 		 * where all methods that change the elements would need to reflect the change onto
 		 * the referenced (this) object list.
 		 */
 		/*if (fromIndex < 0 || toIndex > array.length || fromIndex>toIndex) throw new IllegalArgumentException();
 
 		ObjectList ol = new ObjectList(type);
 		for (int i = fromIndex; i < toIndex; i++) {
 		    ol.add(i, array[i]);
 
 		}
 		return ol;
 		*/
 		throw new UnsupportedOperationException();
 	}
 
 	/**
 	 * Returns iterator which iterates over elements, which was contained in
 	 * list at the moment iterator was called. Iteration does not fail, if
 	 * elements are added or removed during the iteration.
 	 *
 	 * @param index index of the first element to be returned from the list
 	 *        iterator (by a call to the <tt>next</tt> method).
 	 *
 	 * @return a list iterator of the elements in this list, starting at the
 	 *         specified position in the list.
 	 *
 	 * @throws IndexOutOfBoundsException if the specified index is out of range
 	 *         (<tt>index &lt; 0 || index &gt; size()</tt>).
 	 *
 	 * @see java.util.List#listIterator(int)
 	 */
 	public ListIterator listIterator(final int index)
 	{
 		if (index < 0 || index > array.length) {
 			throw new IndexOutOfBoundsException("Index: " + index);
 		}
 
 		return new ArrayIterator(array, index);
 	}
 
 	/**
 	 * Sets the element at specified index to specified object.
 	 *
 	 * @param index the index of object to set
 	 * @param element the object to be set to the index
 	 *
 	 * @return the element previously at the specified position
 	 *
 	 * @throws NullPointerException DOCUMENT ME!
 	 * @throws ClassCastException DOCUMENT ME!
 	 *
 	 * @see java.util.List#set(int, Object)
 	 */
 	public Object set(int index, Object element)
 	{
 		if (element == null) {
 			throw new NullPointerException("element");
 		}
 
 		if (type.isAssignableFrom(element.getClass()) == false) {
 			throw new ClassCastException("Object '" + element
 			    + "' !instanceof '" + type + "'.");
 		}
 
 		Object retObj = null;
 
 		synchronized (this) {
 			retObj = array[index];
 			array[index] = element;
 		}
 
 		return retObj;
 	}
 
 	/**
 	 * Returns an array containing all of the elements in this list.
 	 *
 	 * @param a the array into which the elements of this list are to be
 	 *        stored, if it is big enough; otherwise, a new array  is
 	 *        allocated for this purpose.
 	 *
 	 * @return an array containing the elements of this list.
 	 *
 	 * @throws NullPointerException if the specified array is <tt>null</tt>.
 	 * @throws ArrayStoreException if the runtime type of the specified array
 	 *         is not a supertype of the runtime type of every element in this
 	 *         list.
 	 *
 	 * @see java.util.List#toArray(java.lang.Object[])
 	 */
 	public Object[] toArray(Object[] a)
 	{
 		if (a == null) {
 			throw new NullPointerException("o");
 		}
 
 		if (type.isAssignableFrom(a.getClass().getComponentType()) == false) {
 			throw new ArrayStoreException("Object '" + a + "' !instanceof '"
 			    + type + "'.");
 		}
 
 		return (Object[])toArray();
 	}
 
 	/**
 	 * Returns a list iterator of the elements in this list, iterator will
 	 * iterate over the elements, which were in list at the moment iterator
 	 * was created thus iteration will not fail if list is modified during
 	 * iteration.
 	 *
 	 * @return a list iterator of the elements in this list
 	 *
 	 * @see java.util.List#listIterator(int)
 	 */
 	public ListIterator listIterator()
 	{
 		return new ArrayIterator(array, 0);
 	}
 }
 
 /* __oOo__ */