javolution37.javolution.util

Class FastList<E>

java.lang.Object

javolution37.javolution.realtime.RealtimeObject

javolution37.javolution.util.FastCollection<E>

javolution37.javolution.util.FastList<E>

All Implemented Interfaces:

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

public class FastList<E>
extends FastCollection<E>
implements Reusable, java.util.List<E>

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 thread-safe, 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 fully reusable, they maintain internal pools of nodes objects. When a node is removed from its list, it is automatically restored to its pool.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FastList.Node<E> This class represents a FastList node; it allows for direct iteration over the list values.

Nested classes/interfaces inherited from class javolution37.javolution.util.FastCollection

FastCollection.Record

Nested classes/interfaces inherited from class javolution37.javolution.realtime.RealtimeObject

RealtimeObject.Factory<T extends RealtimeObject>

Nested classes/interfaces inherited from interface javolution37.javolution.realtime.Realtime

Realtime.ObjectSpace

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
boolean	add(E value) 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(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).
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.
int	hashCode() Returns the hash code value for this list.
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 value) Returns the index in this list of the first occurrence of the specified value, or -1 if this list does not contain this value.
java.util.Iterator<E>	iterator() Returns an iterator over the elements in this list (allocated on the stack when executed in a PoolContext).
int	lastIndexOf(java.lang.Object value) 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 PoolContext).
java.util.ListIterator<E>	listIterator(int index) Returns a list iterator from the specified position (allocated on the stack when executed in a PoolContext).
boolean	move(Realtime.ObjectSpace os) Moves this real-time object to the specified object space.
static <E> FastList<E>	newInstance() Returns a list allocated from the stack when executing in a PoolContext).
E	remove(int index) Removes the value at the specified position in this list.
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.
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 PoolContext).
FastList.Node<E>	tail() Returns the tail record of this collection; it is the record such as tail().getPrevious() holds the last collection value.
java.util.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 javolution37.javolution.util.FastCollection

addAll, contains, containsAll, equals, getValueComparator, isEmpty, remove, removeAll, retainAll, setValueComparator, toArray, toArray, toText

Methods inherited from class javolution37.javolution.realtime.RealtimeObject

export, moveHeap, preserve, toString, unpreserve

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

addAll, contains, containsAll, equals, isEmpty, remove, 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

FastList

public FastList()

Creates a list of small initial capacity.

FastList

public FastList(java.lang.String id)

Creates a persistent list 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:

PersistentReference

FastList

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

Parameters:

capacity - the initial capacity.

FastList

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

Parameters:

values - the values to be placed into this list.

Method Detail

newInstance

public static <E> FastList<E> newInstance()

Returns a list allocated from the stack when executing in a PoolContext).

Returns:

a new, preallocated or recycled list instance.

add

public final boolean add(E value)

Appends the specified value to the end of this list (equivalent to addLast(E)).

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Overrides:

add in class FastCollection<E>

Parameters:

value - the value to be appended to this list.

Returns:

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

hashCode

public int hashCode()

Returns the hash code value for this list. The hash code of a list is defined to be the result of the following calculation:

  h = 1;
  Iterator i = list.iterator();
  while (i.hasNext()) {
      Object obj = i.next();
      h = 31 * h +  this.getValueComparator().hashCodeOf(obj);
  }

Specified by:

hashCode in interface java.util.Collection<E>

Specified by:

hashCode in interface java.util.List<E>

Overrides:

hashCode in class FastCollection<E>

Returns:

the hash code value for this list.

get

public final E get(int index)

Returns the value at the specified position in this list.

Specified by:

get in interface java.util.List<E>

Parameters:

index - the 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 final E set(int index,
                   E value)

Replaces the value at the specified position in this list with the specified value.

Specified by:

set in interface java.util.List<E>

Parameters:

index - the index of value to replace.

value - the value to be stored at the specified position.

Returns:

the value previously at the specified position.

Throws:

java.lang.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 list. Shifts the value currently at that position (if any) and any subsequent values to the right (adds one to their indices).

Specified by:

add in interface java.util.List<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())

addAll

public final 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. Shifts the value currently at that position (if any) and any subsequent values to the right (increases their indices).

Specified by:

addAll in interface java.util.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:

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

remove

public final E remove(int index)

Removes the value at the specified position in this list. Shifts any subsequent values to the left (subtracts one from their indices). Returns the value that was removed from the list.

Specified by:

remove in interface java.util.List<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 final int indexOf(java.lang.Object value)

Returns the index in this list of the first occurrence of the specified value, or -1 if this list does not contain this value.

Specified by:

indexOf in interface java.util.List<E>

Parameters:

value - the value to search for.

Returns:

the index in this list of the first occurrence of the specified value, or -1 if this list does not contain this value.

lastIndexOf

public final int lastIndexOf(java.lang.Object value)

Returns the index in this list of the last occurrence of the specified value, or -1 if this list does not contain this value.

Specified by:

lastIndexOf in interface java.util.List<E>

Parameters:

value - the value to search for.

Returns:

the index in this list of the last occurrence of the specified value, or -1 if this list does not contain this value.

iterator

public final java.util.Iterator<E> iterator()

Returns an iterator over the elements in this list (allocated on the stack when executed in a PoolContext).

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>

Overrides:

iterator in class FastCollection<E>

Returns:

an iterator over this list values.

listIterator

public final java.util.ListIterator<E> listIterator()

Returns a list iterator over the elements in this list (allocated on the stack when executed in a PoolContext).

Specified by:

listIterator in interface java.util.List<E>

Returns:

an iterator over this list values.

listIterator

public final java.util.ListIterator<E> listIterator(int index)

Returns a list iterator from the specified position (allocated on the stack when executed in a PoolContext). 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.

Specified by:

listIterator in interface java.util.List<E>

Parameters:

index - index of first value to be returned from the list iterator (by a call to the next method).

Returns:

a list iterator over the values in this list 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 final 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 PoolContext). 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>

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)

getFirst

public final E getFirst()

Returns the first value of this list.

Returns:

this list's first value.

Throws:

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

getLast

public final E getLast()

Returns the last value of this list.

Returns:

this list's last value.

Throws:

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

addFirst

public final void addFirst(E value)

Inserts the specified value at the beginning of this list.

Parameters:

value - the value to be inserted.

addLast

public void addLast(E value)

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

Parameters:

value - the value to be inserted.

removeFirst

public final E removeFirst()

Removes and returns the first value of this list.

Returns:

this list's first value before this call.

Throws:

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

removeLast

public final E removeLast()

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

Returns:

this list's last value before this call.

Throws:

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

addBefore

public final void addBefore(FastList.Node<E> next,
                            E value)

Inserts the specified value before the specified Node.

Parameters:

next - the Node before which this value is inserted.

value - the value to be inserted.

head

public final FastList.Node<E> 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 FastList.Node<E> 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.

size

public final 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 FastCollection<E>

Returns:

the number of values.

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

Specified by:

clear in interface java.util.List<E>

Overrides:

clear in class FastCollection<E>

unmodifiable

public java.util.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. The view is typically part of the collection itself (created only once) and also an instance of FastCollection supporting direct iterations.

Overrides:

unmodifiable in class FastCollection<E>

Returns:

the unmodifiable view over this collection.

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

move

public boolean move(Realtime.ObjectSpace os)

Description copied from interface: Realtime

Moves this real-time object to the specified object space.

Specified by:

move in interface Realtime

Overrides:

move in class RealtimeObject

Parameters:

os - the object space to move this real-time object to.

Returns:

true if the move has to be propagated to external real-time references; false otherwise.