javolution.util

Class FastTable<E>

java.lang.Object

javolution.util.FastCollection<E>

javolution.util.MutableList<E>

javolution.util.FastTable<E>

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>, java.util.RandomAccess, Realtime, Reusable, XMLSerializable

public class FastTable<E>
extends MutableList<E>
implements java.util.List<E>, Reusable, java.util.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:

• No large array allocation (for large collections multi-dimensional arrays are employed). The garbage collector is not stressed with large chunk of memory to allocate (likely to trigger a full garbage collection due to memory fragmentation).
• Support concurrent access/iteration/modification without synchronization if marked shared.

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

      FastTable<String> table = new FastTable<String>();
      for (int i = 0, n = table.size(); i < n; ++i) {
          String value = 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 javolution.util.FastCollection

FastCollection.Record

Constructor Summary

Constructors

Constructor and Description
FastTable() Creates a table of small initial capacity.
FastTable(java.util.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(java.lang.String id) Creates a persistent table associated to the specified unique identifier (convenience method).

Method Summary

Modifier and Type	Method and Description
boolean	add(E o) 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(java.util.Collection<? extends E> values) 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.
boolean	addAll(int index, java.util.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(java.lang.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(java.lang.Object o) Returns the index in this table of the first occurrence of the specified value, or -1 if this table does not contain this value.
boolean	isEmpty() Indicates if this collection is empty.
java.util.Iterator<E>	iterator() Returns an iterator over the elements in this list (allocated on the stack when executed in a StackContext).
int	lastIndexOf(java.lang.Object o) Returns the index in this table of the last occurrence of the specified value, or -1 if this table does not contain this value.
java.util.ListIterator<E>	listIterator() Returns a list iterator over the elements in this list (allocated on the stack when executed in a StackContext).
java.util.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.
boolean	remove(java.lang.Object o) Removes the first occurrence in this collection of the specified value (optional operation).
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()).
FastTable<E>	shared() Returns a thread-safe read-write view of this collection.
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).
java.util.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).
FastTable<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 javolution.util.FastCollection

containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray, toString, toText

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

containsAll, equals, hashCode, removeAll, replaceAll, retainAll, sort, spliterator, toArray, toArray

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

FastTable

public FastTable()

Creates a table of small initial capacity.

FastTable

public FastTable(java.lang.String id)

Creates a persistent table associated to the specified unique identifier (convenience method).

Parameters:

id - the unique identifier for this map.

Throws:

java.lang.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(java.util.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).

size

public int size()

Description copied from class: FastCollection

Returns the number of values in this collection.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.List<E>

Specified by:

size in class MutableList<E>

Returns:

the number of values.

isEmpty

public boolean isEmpty()

Description copied from class: FastCollection

Indicates if this collection is empty.

Specified by:

isEmpty in interface java.util.Collection<E>

Specified by:

isEmpty in interface java.util.List<E>

Specified by:

isEmpty in class MutableList<E>

Returns:

true if this collection contains no value; false otherwise.

contains

public boolean contains(java.lang.Object value)

Description copied from class: FastCollection

Indicates if this collection contains the specified value.

Specified by:

contains in interface java.util.Collection<E>

Specified by:

contains in interface java.util.List<E>

Specified by:

contains in class MutableList<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.

iterator

public java.util.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 java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in interface java.util.List<E>

Specified by:

iterator in class MutableList<E>

Returns:

an iterator over this list values.

add

public boolean add(E o)

Appends the specified value to the end of this table.

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Specified by:

add in class MutableList<E>

Parameters:

o - the value to be appended to this table.

Returns:

true (as per the general contract of the Collection.add method).

remove

public boolean remove(java.lang.Object o)

Description copied from class: FastCollection

Removes the first occurrence in this collection of the specified value (optional operation).

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.List<E>

Specified by:

remove in class MutableList<E>

Parameters:

o - the value to be removed from this collection.

Returns:

true if this collection contained the specified value; false otherwise.

addAll

public boolean addAll(java.util.Collection<? extends E> values)

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. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this list, and this list is nonempty.)

Specified by:

addAll in interface java.util.Collection<E>

Specified by:

addAll in interface java.util.List<E>

Specified by:

addAll in class MutableList<E>

Parameters:

c - collection containing elements to be added to this list

Returns:

true if this list changed as a result of the call

Throws:

java.lang.NullPointerException - if the specified collection is null

addAll

public boolean addAll(int index,
                      java.util.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 java.util.List<E>

Specified by:

addAll in class MutableList<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:

java.lang.IndexOutOfBoundsException - if (index < 0) || (index > size())

clear

public void clear()

Description copied from class: FastCollection

Removes all of the values from this collection (optional operation).

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.List<E>

Specified by:

clear in class MutableList<E>

get

public E get(int index)

Returns the element at the specified index.

Specified by:

get in interface java.util.List<E>

Specified by:

get in class MutableList<E>

Parameters:

index - index of value to return.

Returns:

the value at the specified position in this list.

Throws:

java.lang.IndexOutOfBoundsException - if (index < 0) || (index >= size())

set

public 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 java.util.List<E>

Specified by:

set in class MutableList<E>

Parameters:

index - index of value to replace.

value - value to be stored at the specified position.

Returns:

previous value.

Throws:

java.lang.IndexOutOfBoundsException - if (index < 0) || (index >= size())

add

public 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 java.util.List<E>

Specified by:

add in class MutableList<E>

Parameters:

index - the index at which the specified value is to be inserted.

value - the value to be inserted.

Throws:

java.lang.IndexOutOfBoundsException - if (index < 0) || (index > size())

remove

public 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 java.util.List<E>

Specified by:

remove in class MutableList<E>

Parameters:

index - the index of the value to removed.

Returns:

the value previously at the specified position.

Throws:

java.lang.IndexOutOfBoundsException - if (index < 0) || (index >= size())

indexOf

public int indexOf(java.lang.Object o)

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 java.util.List<E>

Specified by:

indexOf in class MutableList<E>

Parameters:

o - 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 int lastIndexOf(java.lang.Object o)

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 java.util.List<E>

Specified by:

lastIndexOf in class MutableList<E>

Parameters:

o - 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.

listIterator

public java.util.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 java.util.List<E>

Specified by:

listIterator in class MutableList<E>

Returns:

an iterator over this list values.

listIterator

public java.util.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 java.util.List<E>

Specified by:

listIterator in class MutableList<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:

java.lang.IndexOutOfBoundsException - if the index is out of range

(index < 0 || index > size())

subList

public java.util.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 java.util.List<E>

Specified by:

subList in class MutableList<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:

java.lang.IndexOutOfBoundsException - if

(fromIndex < 0 ||
          toIndex > size || fromIndex > toIndex)

head

public 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 MutableList<E>

Returns:

the head record.

tail

public 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 MutableList<E>

Returns:

the tail record.

valueOf

public E valueOf(FastCollection.Record record)

Description copied from class: FastCollection

Returns the collection value for the specified record.

Specified by:

valueOf in class MutableList<E>

Parameters:

record - the record whose current value is returned.

Returns:

the current value.

delete

public 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 MutableList<E>

Parameters:

record - the record to be removed.

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.

getFirst

public E getFirst()

Returns the first value of this table.

Returns:

this table first value.

Throws:

java.util.NoSuchElementException - if this table is empty.

getLast

public E getLast()

Returns the last value of this table.

Returns:

this table last value.

Throws:

java.util.NoSuchElementException - if this table is empty.

addLast

public void addLast(E value)

Appends the specified value to the end of this table (fast).

Parameters:

value - the value to be added.

removeLast

public E removeLast()

Removes and returns the last value of this table (fast).

Returns:

this table's last value before this call.

Throws:

java.util.NoSuchElementException - if this table is empty.

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

removeRange

public 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:

java.lang.IndexOutOfBoundsException - if (fromIndex < 0) || (toIndex < 0) || (fromIndex > toIndex) || (toIndex > this.size())

trimToSize

public void trimToSize()

Reduces the capacity of this table to the current size (minimize storage space).

sort

public 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)

unmodifiable

public FastTable<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 MutableList<E>

Returns:

the unmodifiable view over this collection.

shared

public FastTable<E> shared()

Description copied from class: FastCollection

Returns a thread-safe read-write view of this collection.

The default implementation performs synchronization on read and write. Sub-classes may provide more efficient implementation (e.g. only synchronizing on writes modifying the internal data structure).

Having a shared collection does not mean that modifications made by onethread are automatically viewed by others thread. Which in practice is not an issue. In a well-behaved system, threads need to synchronize only at predetermined synchronization points (the fewer the better).

Overrides:

shared in class MutableList<E>

Returns:

a thread-safe collection.

getCapacity

protected final int getCapacity()

Returns the current capacity of this table.

Returns:

this table's capacity.