benchmark and example included
package game.custom;
import java.util.*;
/**
* eine (viel) schnellere variante der arrayList.
* unterschiede :
ein einfaches remove nimmt das letze element und setzt es an die stelle des gelöschten objektes
*
der enthaltene array ist von dem typ, der beim konstruktor übergeben wird. er kann per getter geholt werden,
* und muss dann in den entsprechenden typ gecastet werden. die einzelnen elemente können dann ohne probleme durchiteriert
* werden
* änderungen in der liste sind gleichzeitig auch in den geholten array vorhanden
*/
public class FastVector extends AbstractList implements List, Cloneable,
java.io.Serializable
{
private Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
private boolean useTypeArray = true;
/**
* @param type array der länge 0, der der liste sagt, welchen datentyp sie enthalten soll
* @param initialCapacity anfangsgröße des arrays
*/
public FastVector(Object[] type, int initialCapacity)
{
if (type.length != 0)
{
throw new IllegalArgumentException("don't waste memory. the object[] won't be used, set its size to 0");
}
this.elementData = (Object[]) java.lang.reflect.Array.newInstance(type.getClass().getComponentType(), initialCapacity);
size = 0;
}
/**
* @param type array der länge 0, der der liste sagt, welchen datentyp sie enthalten soll
*/
public FastVector(Object[] type)
{
this(type, 10);
}
public FastVector(Collection c)
{
size = c.size();
elementData = new Object[(size * 110) / 100]; // Allow 10% room for growth
c.toArray(elementData);
}
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to
* minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize()
{
int oldCapacity = elementData.length;
if (size < oldCapacity)
{
Object oldData[] = elementData;
if (useTypeArray)
{
elementData = (Object[]) java.lang.reflect.Array.newInstance(elementData.getClass().getComponentType(), size);
} else
{
elementData = new Object[size];
}
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list.
*/
public int size()
{
return size;
}
/**
* 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 size == 0;
}
/**
* Returns <tt>true</tt> if this list contains the specified element.
*
* @param elem element whose presence in this List is to be tested.
*/
public boolean contains(Object elem)
{
return indexOf(elem) >= 0;
}
/**
* Searches for the first occurence of the given argument, testing
* for equality using the <tt>equals</tt> method.
*
* @param elem 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 elem)
{
if (elem == null)
{
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else
{
for (int i = 0; i < size; i++)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 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.
*/
public int lastIndexOf(Object elem)
{
if (elem == null)
{
for (int i = size - 1; i >= 0; i--)
if (elementData[i] == null)
return i;
} else
{
for (int i = size - 1; i >= 0; i--)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
* @return a clone of this <tt>ArrayList</tt> instance.
*/
public Object clone()
{
try
{
FastVector v = (FastVector) super.clone();
v.elementData = (Object[]) java.lang.reflect.Array.newInstance(elementData.getClass().getComponentType(), size);
System.arraycopy(elementData, 0, v.elementData, 0, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e)
{
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
/**
* Returns an array containing all of the elements in this list
* in the correct order.
*
* @return an array containing all of the elements in this list
* in the correct order.
*/
public Object[] toArray()
{
Object[] result = new Object[size];
System.arraycopy(elementData, 0, result, 0, size);
return result;
}
public Object[] toArray(Object a[])
{
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;//endmarkierung
return a;
}
// Positional Access Operations
public Object get(int index)
{
if (index < size)
{
return elementData[index];
} else
{
throw new ArrayIndexOutOfBoundsException();
}
}
public Object getImmediate(int index)
{
return elementData[index];
}
public Object set(int index, Object element)
{
if (index < size)
{
Object oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
throw new ArrayIndexOutOfBoundsException();
}
public void setImmediate(int index, Object element)
{
elementData[index] = element;
}
public boolean add(Object o)
{
ensureCapacity(size + 1);
elementData[size++] = o;
return true;
}
public void addImmediate(Object o)
{
try
{
elementData[size++] = o;
} catch (Exception e)
{
ensureCapacity(size);
elementData[size] = o;
}
}
/**
* fügt das übergebene element an die angegebene stelle. das aktuell dort
* befindliche objekt
* wird ans ende der liste verschoben
*/
public void add(int index, Object element)
{
int oldCapacity = elementData.length;
if (++size > oldCapacity)
{
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < size)
newCapacity = size;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size - 1);
}
Object o = elementData[index];
elementData[index] = element;
elementData[size] = o;
}
/**
* verschiebt das letze element der liste auf den angegebenen index und
* reduziert die länge der liste
* um 1
*
* @return das gelöscht objekt
*/
public Object removeIgnoreOrder(int index)
{
if (index < size - 1)
{
Object oldValue = elementData[index];
elementData[index] = elementData[size--];
elementData[size + 1] = null;
return oldValue;
} else
{
Object oldValue = elementData[--size - 1];
elementData[size - 1] = null;
return oldValue;
}
}
/**
* ersetzt ein objekt der liste mit null
*/
public void replaceByNull(int index)
{
elementData[index] = null; // Let gc do its work
}
/**
* löscht das objekt am übergebenen index, und schiebt den rest des
* arrays um eine stelle nach hinten
*
* @return das gelöschte objekt
*/
public Object remove(int index)
{
Object oldValue = elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}