public class FastList<E> extends MutableList<E> implements java.util.List<E>, Reusable
This class represents a linked list with real-time behavior; smooth capacity increase and no memory allocation as long as the list size does not exceed its initial capacity.
All of the operations perform as could be expected for a doubly-linked
list (insertion/deletion
at the end of the list are nonetheless the fastest).
Operations that index into the list will traverse the list from
the begining or the end whichever is closer to the specified index.
Random access operations can be significantly accelerated by
splitting the list into smaller ones.
FastList (as for any FastCollection sub-class) supports
fast iterations without using iterators.
FastList<String> list = new FastList<String>();
for (FastList.Node<String> n = list.head(), end = list.tail(); (n = n.getNext()) != end;) {
String value = n.getValue(); // No typecast necessary.
}
FastList are reusable, they maintain
internal pools of nodes objects. When a node is removed
from its list, it is automatically restored to its pool.
Custom list implementations may override the newNode() method
in order to return their own FastList.Node implementation (with
additional fields for example).
| Modifier and Type | Class and Description |
|---|---|
static class |
FastList.Node<E>
|
FastCollection.Record| Constructor and Description |
|---|
FastList()
Creates a list of small initial capacity.
|
FastList(java.util.Collection<? extends E> values)
Creates a list containing the specified values, in the order they
are returned by the collection's iterator.
|
FastList(int capacity)
Creates a list of specified initial capacity; unless the list size
reaches the specified capacity, operations on this list will not allocate
memory (no lazy object creation).
|
FastList(java.lang.String id)
Creates a persistent list associated to the specified unique identifier
(convenience method).
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
add(E o)
Appends the specified value to the end of this list
(equivalent to
addLast(E)). |
void |
add(int index,
E value)
Inserts the specified value at the specified position in this list.
|
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
list at the specified position.
|
void |
addBefore(FastList.Node<E> next,
E value)
Inserts the specified value before the specified Node.
|
void |
addFirst(E value)
Inserts the specified value at the beginning of this list.
|
void |
addLast(E value)
Appends the specified value to the end of this list (fast).
|
void |
clear()
Removes all of the values from this collection (optional operation).
|
boolean |
contains(java.lang.Object o)
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 value at the specified position in this list.
|
E |
getFirst()
Returns the first value of this list.
|
E |
getLast()
Returns the last value of this list.
|
FastComparator<? super E> |
getValueComparator()
Returns the value comparator for this collection (default
FastComparator.DEFAULT). |
FastList.Node<E> |
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 list of the first occurrence of the specified
value, or -1 if this list does not contain this value.
|
boolean |
isEmpty()
Indicates if this collection is empty.
|
java.util.Iterator<E> |
iterator()
Returns a simple 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 list of the last occurrence of the specified
value, or -1 if this list 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> FastList<E> |
newInstance()
Returns a new, preallocated or
recycled list instance
(on the stack when executing in a StackContext). |
protected FastList.Node<E> |
newNode()
Returns a new node for this list; this method can be overriden by
custom list implementation.
|
static void |
recycle(FastList instance)
Recycles a list
instance immediately
(on the stack when executing in a StackContext). |
E |
remove(int index)
Removes the value at the specified position in this list.
|
boolean |
remove(java.lang.Object o)
Removes the first occurrence in this collection of the specified value
(optional operation).
|
E |
removeFirst()
Removes and returns the first value of this list.
|
E |
removeLast()
Removes and returns the last value of this list (fast).
|
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 list with the
specified value.
|
FastList<E> |
setValueComparator(FastComparator<? super E> comparator)
Sets the comparator to use for value equality.
|
FastList<E> |
shared()
Returns a thread-safe read-write view of this collection.
|
int |
size()
Returns the number of values in this collection.
|
java.util.List<E> |
subList(int fromIndex,
int toIndex)
Returns a view of the portion of this list between the specified
indexes (allocated from the "stack" when executing in a
StackContext). |
FastList.Node<E> |
tail()
Returns the tail record of this collection; it is the record such as
tail().getPrevious() holds the last collection value. |
FastList<E> |
unmodifiable()
Returns the unmodifiable view associated to this collection.
|
E |
valueOf(FastCollection.Record record)
Returns the collection value for the specified record.
|
containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray, toString, toTextclone, finalize, getClass, notify, notifyAll, wait, wait, waitpublic FastList()
public FastList(java.lang.String id)
id - the unique identifier for this map.java.lang.IllegalArgumentException - if the identifier is not unique.PersistentContext.Referencepublic FastList(int capacity)
capacity - the initial capacity.public FastList(java.util.Collection<? extends E> values)
values - the values to be placed into this list.public static <E> FastList<E> newInstance()
recycled list instance
(on the stack when executing in a StackContext).public static void recycle(FastList instance)
instance immediately
(on the stack when executing in a StackContext).public int size()
FastCollectionsize in interface java.util.Collection<E>size in interface java.util.List<E>size in class MutableList<E>public boolean isEmpty()
FastCollectionisEmpty in interface java.util.Collection<E>isEmpty in interface java.util.List<E>isEmpty in class MutableList<E>true if this collection contains no value;
false otherwise.public boolean contains(java.lang.Object o)
FastCollectioncontains in interface java.util.Collection<E>contains in interface java.util.List<E>contains in class MutableList<E>o - the value whose presence in this collection
is to be tested.true if this collection contains the specified
value;false otherwise.public java.util.Iterator<E> iterator()
StackContext).public boolean add(E o)
addLast(E)).add in interface java.util.Collection<E>add in interface java.util.List<E>add in class MutableList<E>o - the value to be appended to this list.true (as per the general contract of the
Collection.add method).public boolean remove(java.lang.Object o)
FastCollectionremove in interface java.util.Collection<E>remove in interface java.util.List<E>remove in class MutableList<E>o - the value to be removed from this collection.true if this collection contained the specified
value; false otherwise.public boolean addAll(java.util.Collection<? extends E> values)
addAll in interface java.util.Collection<E>addAll in interface java.util.List<E>addAll in class MutableList<E>c - collection containing elements to be added to this listtrue if this list changed as a result of the calljava.lang.NullPointerException - if the specified collection is nullpublic boolean addAll(int index,
java.util.Collection<? extends E> values)
addAll in interface java.util.List<E>addAll in class MutableList<E>index - the index at which to insert first value from the specified
collection.values - the values to be inserted into this list.true if this list changed as a result of the call;
false otherwise.java.lang.IndexOutOfBoundsException - if (index < 0) ||
(index > size())public void clear()
FastCollectionclear in interface java.util.Collection<E>clear in interface java.util.List<E>clear in class MutableList<E>public E get(int index)
get in interface java.util.List<E>get in class MutableList<E>index - the index of value to return.java.lang.IndexOutOfBoundsException - if (index < 0) ||
(index >= size())public E set(int index, E value)
set in interface java.util.List<E>set in class MutableList<E>index - the index of value to replace.value - the value to be stored at the specified position.java.lang.IndexOutOfBoundsException - if (index < 0) ||
(index >= size())public void add(int index,
E value)
add in interface java.util.List<E>add in class MutableList<E>index - the index at which the specified value is to be inserted.value - the value to be inserted.java.lang.IndexOutOfBoundsException - if (index < 0) ||
(index > size())public E remove(int index)
remove in interface java.util.List<E>remove in class MutableList<E>index - the index of the value to removed.java.lang.IndexOutOfBoundsException - if (index < 0) ||
(index >= size())public int indexOf(java.lang.Object o)
indexOf in interface java.util.List<E>indexOf in class MutableList<E>o - the value to search for.public int lastIndexOf(java.lang.Object o)
lastIndexOf in interface java.util.List<E>lastIndexOf in class MutableList<E>o - the value to search for.public java.util.ListIterator<E> listIterator()
StackContext).listIterator in interface java.util.List<E>listIterator in class MutableList<E>public java.util.ListIterator<E> listIterator(int index)
StackContext).
The specified index indicates the first value that would be returned by
an initial call to the next method. An initial call to
the previous method would return the value with the
specified index minus one.listIterator in interface java.util.List<E>listIterator in class MutableList<E>index - index of first value to be returned from the
list iterator (by a call to the next method).java.lang.IndexOutOfBoundsException - if the index is out of range
(index < 0 || index > size())
public java.util.List<E> subList(int fromIndex, int toIndex)
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).subList in interface java.util.List<E>subList in class MutableList<E>fromIndex - low endpoint (inclusive) of the subList.toIndex - high endpoint (exclusive) of the subList.java.lang.IndexOutOfBoundsException - if (fromIndex < 0 ||
toIndex > size || fromIndex < toIndex)public FastList.Node<E> head()
FastCollectionhead().getNext() holds the first collection value.head in class MutableList<E>public FastList.Node<E> tail()
FastCollectiontail().getPrevious() holds the last collection value.tail in class MutableList<E>public E valueOf(FastCollection.Record record)
FastCollectionvalueOf in class MutableList<E>record - the record whose current value is returned.public void delete(FastCollection.Record record)
FastCollectionImplementation 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).
delete in class MutableList<E>record - the record to be removed.public E getFirst()
java.util.NoSuchElementException - if this list is empty.public E getLast()
java.util.NoSuchElementException - if this list is empty.public void addFirst(E value)
value - the value to be inserted.public void addLast(E value)
value - the value to be inserted.public E removeFirst()
java.util.NoSuchElementException - if this list is empty.public E removeLast()
java.util.NoSuchElementException - if this list is empty.public void addBefore(FastList.Node<E> next, E value)
next - the Node before which this value is inserted.value - the value to be inserted.public FastList<E> setValueComparator(FastComparator<? super E> comparator)
comparator - the value comparator.thispublic FastComparator<? super E> getValueComparator()
FastCollectionFastComparator.DEFAULT).getValueComparator in class FastCollection<E>public FastList<E> unmodifiable()
FastCollectionUnsupportedOperationException being thrown.unmodifiable in class MutableList<E>public FastList<E> shared()
FastCollectionReturns 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).
shared in class MutableList<E>protected FastList.Node<E> newNode()
Copyright © 2005 - 2007 Javolution.