javolution.util
Class FastTable<E>

Object
  extended by FastCollection<E>
      extended by FastTable<E>
All Implemented Interfaces:
Serializable, Iterable<E>, Collection<E>, List<E>, RandomAccess, Realtime, Reusable, XMLSerializable

public class FastTable<E>
extends FastCollection<E>
implements List<E>, Reusable, RandomAccess

This class represents a random access collection with real-time behavior (smooth capacity increase).

This class has the following advantages over the widely used java.util.ArrayList:

Iterations over the FastTable values are faster when performed using the get(int) method rather than using collection records or iterators:

     for (int i = 0, n = table.size(); i < n; i++) {
          table.get(i);
     }

FastTable supports sorting in place (quick sort) using the value comparator for the table (no object or array allocation when sorting).

Version:
5.4.5, August 20, 2007
Author:
Jean-Marie Dautelle
See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class FastCollection
FastCollection.Record
 
Constructor Summary
FastTable()
          Creates a table of small initial capacity.
FastTable(Collection<? extends E> values)
          Creates a table containing the specified values, in the order they are returned by the collection's iterator.
FastTable(int capacity)
          Creates a table of specified initial capacity; unless the table size reaches the specified capacity, operations on this table will not allocate memory (no lazy object creation).
FastTable(String id)
          Creates a persistent table associated to the specified unique identifier (convenience method).
 
Method Summary
 boolean add(E value)
          Appends the specified value to the end of this table.
 void add(int index, E value)
          Inserts the specified value at the specified position in this table.
 boolean addAll(int index, Collection<? extends E> values)
          Inserts all of the values in the specified collection into this table at the specified position.
 void addLast(E value)
          Appends the specified value to the end of this table (fast).
 void clear()
          Removes all of the values from this collection (optional operation).
 boolean contains(Object value)
          Indicates if this collection contains the specified value.
 void delete(FastCollection.Record record)
          Deletes the specified record from this collection.
 E get(int index)
          Returns the element at the specified index.
protected  int getCapacity()
          Returns the current capacity of this table.
 E getFirst()
          Returns the first value of this table.
 E getLast()
          Returns the last value of this table.
 FastComparator<? super E> getValueComparator()
          Returns the value comparator for this collection (default FastComparator.DEFAULT).
 FastCollection.Record head()
          Returns the head record of this collection; it is the record such as head().getNext() holds the first collection value.
 int indexOf(Object value)
          Returns the index in this table of the first occurrence of the specified value, or -1 if this table does not contain this value.
 Iterator<E> iterator()
          Returns an iterator over the elements in this list (allocated on the stack when executed in a StackContext).
 int lastIndexOf(Object value)
          Returns the index in this table of the last occurrence of the specified value, or -1 if this table does not contain this value.
 ListIterator<E> listIterator()
          Returns a list iterator over the elements in this list (allocated on the stack when executed in a StackContext).
 ListIterator<E> listIterator(int index)
          Returns a list iterator from the specified position (allocated on the stack when executed in a StackContext).
static
<E> FastTable<E>
newInstance()
          Returns a new, preallocated or recycled table instance (on the stack when executing in a StackContext).
static void recycle(FastTable instance)
          Recycles a table instance immediately (on the stack when executing in a StackContext).
 E remove(int index)
          Removes the value at the specified position from this table.
 E removeLast()
          Removes and returns the last value of this table (fast).
 void removeRange(int fromIndex, int toIndex)
          Removes the values between [fromIndex..toIndex[ from this table.
 void reset()
          Resets the internal state of this object to its default values.
 E set(int index, E value)
          Replaces the value at the specified position in this table with the specified value.
 void setSize(int size)
          Sets the size of this table.
 FastTable<E> setValueComparator(FastComparator<? super E> comparator)
          Sets the comparator to use for value equality or comparison if the collection is ordered (see sort()).
 int size()
          Returns the number of values in this collection.
 FastTable<E> sort()
          Sorts this table in place (quick sort) using this table value comparator (smallest first).
 List<E> subList(int fromIndex, int toIndex)
          Returns a view of the portion of this list between the specified indexes (instance of FastList allocated from the "stack" when executing in a StackContext).
 FastCollection.Record tail()
          Returns the tail record of this collection; it is the record such as tail().getPrevious() holds the last collection value.
 void trimToSize()
          Reduces the capacity of this table to the current size (minimize storage space).
 List<E> unmodifiable()
          Returns the unmodifiable view associated to this collection.
 E valueOf(FastCollection.Record record)
          Returns the collection value for the specified record.
 
Methods inherited from class FastCollection
addAll, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, shared, toArray, toArray, toString, toText
 
Methods inherited from class Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface List
addAll, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray
 

Constructor Detail

FastTable

public FastTable()
Creates a table of small initial capacity.


FastTable

public FastTable(String id)
Creates a persistent table associated to the specified unique identifier (convenience method).

Parameters:
id - the unique identifier for this map.
Throws:
IllegalArgumentException - if the identifier is not unique.
See Also:
PersistentContext.Reference

FastTable

public FastTable(int capacity)
Creates a table of specified initial capacity; unless the table size reaches the specified capacity, operations on this table will not allocate memory (no lazy object creation).

Parameters:
capacity - the initial capacity.

FastTable

public FastTable(Collection<? extends E> values)
Creates a table containing the specified values, in the order they are returned by the collection's iterator.

Parameters:
values - the values to be placed into this table.
Method Detail

newInstance

public static <E> FastTable<E> newInstance()
Returns a new, preallocated or recycled table instance (on the stack when executing in a StackContext).

Returns:
a new, preallocated or recycled table instance.

recycle

public static void recycle(FastTable instance)
Recycles a table instance immediately (on the stack when executing in a StackContext).


setSize

public void setSize(int size)
Sets the size of this table. If the specified size is greater than the current size then null elements are added; otherwise the last elements are removed until the desired size is reached.

Parameters:
size - the new size.

get

public final E get(int index)
Returns the element at the specified index.

Specified by:
get in interface List<E>
Parameters:
index - index of value to return.
Returns:
the value at the specified position in this list.
Throws:
IndexOutOfBoundsException - if (index < 0) || (index >= size())

set

public final E set(int index,
                   E value)
Replaces the value at the specified position in this table with the specified value.

Specified by:
set in interface List<E>
Parameters:
index - index of value to replace.
value - value to be stored at the specified position.
Returns:
previous value.
Throws:
IndexOutOfBoundsException - if (index < 0) || (index >= size())

add

public final boolean add(E value)
Appends the specified value to the end of this table.

Specified by:
add in interface Collection<E>
Specified by:
add in interface List<E>
Overrides:
add in class FastCollection<E>
Parameters:
value - the value to be appended to this table.
Returns:
true (as per the general contract of the Collection.add method).

getFirst

public final E getFirst()
Returns the first value of this table.

Returns:
this table first value.
Throws:
NoSuchElementException - if this table is empty.

getLast

public final E getLast()
Returns the last value of this table.

Returns:
this table last value.
Throws:
NoSuchElementException - if this table is empty.

addLast

public final void addLast(E value)
Appends the specified value to the end of this table (fast).

Parameters:
value - the value to be added.

removeLast

public final E removeLast()
Removes and returns the last value of this table (fast).

Returns:
this table's last value before this call.
Throws:
NoSuchElementException - if this table is empty.

clear

public final void clear()
Description copied from class: FastCollection
Removes all of the values from this collection (optional operation).

Specified by:
clear in interface Collection<E>
Specified by:
clear in interface List<E>
Overrides:
clear in class FastCollection<E>

reset

public void reset()
Description copied from interface: Reusable
Resets the internal state of this object to its default values.

Specified by:
reset in interface Reusable

addAll

public final boolean addAll(int index,
                            Collection<? extends E> values)
Inserts all of the values in the specified collection into this table at the specified position. Shifts the value currently at that position (if any) and any subsequent values to the right (increases their indices).

Note: If this method is used concurrent access must be synchronized (the table is no more thread-safe).

Specified by:
addAll in interface List<E>
Parameters:
index - the index at which to insert first value from the specified collection.
values - the values to be inserted into this list.
Returns:
true if this list changed as a result of the call; false otherwise.
Throws:
IndexOutOfBoundsException - if (index < 0) || (index > size())

add

public final void add(int index,
                      E value)
Inserts the specified value at the specified position in this table. Shifts the value currently at that position (if any) and any subsequent values to the right (adds one to their indices).

Note: If this method is used concurrent access must be synchronized (the table is no more thread-safe).

Specified by:
add in interface List<E>
Parameters:
index - the index at which the specified value is to be inserted.
value - the value to be inserted.
Throws:
IndexOutOfBoundsException - if (index < 0) || (index > size())

remove

public final E remove(int index)
Removes the value at the specified position from this table. Shifts any subsequent values to the left (subtracts one from their indices). Returns the value that was removed from the table.

Note: If this method is used concurrent access must be synchronized (the table is no more thread-safe).

Specified by:
remove in interface List<E>
Parameters:
index - the index of the value to removed.
Returns:
the value previously at the specified position.
Throws:
IndexOutOfBoundsException - if (index < 0) || (index >= size())

removeRange

public final void removeRange(int fromIndex,
                              int toIndex)
Removes the values between [fromIndex..toIndex[ from this table.

Note: If this method is used concurrent access must be synchronized (the table is no more thread-safe).

Parameters:
fromIndex - the beginning index, inclusive.
toIndex - the ending index, exclusive.
Throws:
IndexOutOfBoundsException - if (fromIndex < 0) || (toIndex < 0) || (fromIndex > toIndex) || (toIndex > this.size())

indexOf

public final int indexOf(Object value)
Returns the index in this table of the first occurrence of the specified value, or -1 if this table does not contain this value.

Specified by:
indexOf in interface List<E>
Parameters:
value - the value to search for.
Returns:
the index in this table of the first occurrence of the specified value, or -1 if this table does not contain this value.

lastIndexOf

public final int lastIndexOf(Object value)
Returns the index in this table of the last occurrence of the specified value, or -1 if this table does not contain this value.

Specified by:
lastIndexOf in interface List<E>
Parameters:
value - the value to search for.
Returns:
the index in this table of the last occurrence of the specified value, or -1 if this table does not contain this value.

iterator

public Iterator<E> iterator()
Returns an iterator over the elements in this list (allocated on the stack when executed in a StackContext).

Specified by:
iterator in interface Iterable<E>
Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface List<E>
Overrides:
iterator in class FastCollection<E>
Returns:
an iterator over this list values.

listIterator

public ListIterator<E> listIterator()
Returns a list iterator over the elements in this list (allocated on the stack when executed in a StackContext).

Specified by:
listIterator in interface List<E>
Returns:
an iterator over this list values.

listIterator

public ListIterator<E> listIterator(int index)
Returns a list iterator from the specified position (allocated on the stack when executed in a StackContext). The list iterator being returned does not support insertion/deletion.

Specified by:
listIterator in interface List<E>
Parameters:
index - the index of first value to be returned from the list iterator (by a call to the next method).
Returns:
a list iterator of the values in this table starting at the specified position in this list.
Throws:
IndexOutOfBoundsException - if the index is out of range
(index < 0 || index > size())

subList

public final List<E> subList(int fromIndex,
                             int toIndex)
Returns a view of the portion of this list between the specified indexes (instance of FastList allocated from the "stack" when executing in a StackContext). If the specified indexes are equal, the returned list is empty. The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a list can be used as a range operation by passing a subList view instead of a whole list. For example, the following idiom removes a range of values from a list:
 list.subList(from, to).clear();
Similar idioms may be constructed for indexOf and lastIndexOf, and all of the algorithms in the Collections class can be applied to a subList. The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list (structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results).

Specified by:
subList in interface List<E>
Parameters:
fromIndex - low endpoint (inclusive) of the subList.
toIndex - high endpoint (exclusive) of the subList.
Returns:
a view of the specified range within this list.
Throws:
IndexOutOfBoundsException - if
(fromIndex < 0 ||
          toIndex > size || fromIndex > toIndex)

trimToSize

public final void trimToSize()
Reduces the capacity of this table to the current size (minimize storage space).


sort

public final FastTable<E> sort()
Sorts this table in place (quick sort) using this table value comparator (smallest first).

Returns:
this

setValueComparator

public FastTable<E> setValueComparator(FastComparator<? super E> comparator)
Sets the comparator to use for value equality or comparison if the collection is ordered (see sort()).

Parameters:
comparator - the value comparator.
Returns:
this

getValueComparator

public FastComparator<? super E> getValueComparator()
Description copied from class: FastCollection
Returns the value comparator for this collection (default FastComparator.DEFAULT).

Overrides:
getValueComparator in class FastCollection<E>
Returns:
the comparator to use for value equality (or ordering if the collection is ordered)

size

public final int size()
Description copied from class: FastCollection
Returns the number of values in this collection.

Specified by:
size in interface Collection<E>
Specified by:
size in interface List<E>
Specified by:
size in class FastCollection<E>
Returns:
the number of values.

head

public final FastCollection.Record head()
Description copied from class: FastCollection
Returns the head record of this collection; it is the record such as head().getNext() holds the first collection value.

Specified by:
head in class FastCollection<E>
Returns:
the head record.

tail

public final FastCollection.Record tail()
Description copied from class: FastCollection
Returns the tail record of this collection; it is the record such as tail().getPrevious() holds the last collection value.

Specified by:
tail in class FastCollection<E>
Returns:
the tail record.

valueOf

public final E valueOf(FastCollection.Record record)
Description copied from class: FastCollection
Returns the collection value for the specified record.

Specified by:
valueOf in class FastCollection<E>
Parameters:
record - the record whose current value is returned.
Returns:
the current value.

delete

public final void delete(FastCollection.Record record)
Description copied from class: FastCollection
Deletes the specified record from this collection.

Implementation must ensure that removing a record from the collection does not affect in any way the records preceding the record being removed (it might affect the next records though, e.g. in a list collection, the indices of the subsequent records will change).

Specified by:
delete in class FastCollection<E>
Parameters:
record - the record to be removed.

unmodifiable

public List<E> unmodifiable()
Description copied from class: FastCollection
Returns the unmodifiable view associated to this collection. Attempts to modify the returned collection result in an UnsupportedOperationException being thrown.

Overrides:
unmodifiable in class FastCollection<E>
Returns:
the unmodifiable view over this collection.

contains

public final boolean contains(Object value)
Description copied from class: FastCollection
Indicates if this collection contains the specified value.

Specified by:
contains in interface Collection<E>
Specified by:
contains in interface List<E>
Overrides:
contains in class FastCollection<E>
Parameters:
value - the value whose presence in this collection is to be tested.
Returns:
true if this collection contains the specified value;false otherwise.

getCapacity

protected final int getCapacity()
Returns the current capacity of this table.

Returns:
this table's capacity.


Copyright © 2005-2012 Javolution. All Rights Reserved.