This page is part of an archival collection and is no longer actively maintained.

It may contain outdated information and may not meet current or future WCAG accessibility standards. We provide this content, its subpages, and associated links for historical reference only. If you need assistance, please contact support@cs.washington.edu

com.dautelle.util
Class FastList

java.lang.Object
  com.dautelle.realtime.RealtimeObject
      com.dautelle.util.FastList

All Implemented Interfaces:

java.util.Collection, java.util.List, Realtime, java.io.Serializable

public class FastList

extends RealtimeObject

implements java.util.Collection, java.util.List

This class represents a linked-list with real-time behavior (nodes allocated from the "stack" when executing in a PoolContext).

Instances of this class can be used to implement dynamically sized real-time objects (no expensive resizing operations) or for throw-away collections allocated from the stack. Iterators upon instances of this class are real-time compliant as well.

The list is single-linked in forward direction (that is, forward iteration is much faster than backward iteration). Access to the last element is optimized, so that insertion to the end of the list is as fast as to the head.

subList(int, int) is implemented effectively, so that, for example, splitting the big list into several smaller ones will speed up random (indexed) access.

This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized externally.

This class is public domain (not copyrighted).

Version:

6.1, July 24 2004

Author:

Artem Aleksandrovich Kozarezov

See Also:

Serialized Form

Nested Class Summary

Nested classes inherited from class com.dautelle.realtime.RealtimeObject

RealtimeObject.Factory

Constructor Summary

FastList()
Allocates a heap-only list.

Method Summary

void	add(int index, java.lang.Object element) Inserts the given element at the specified position.
boolean	add(java.lang.Object obj) Adds an object into the end of the list.
boolean	addAll(java.util.Collection col) Adds all objects from the collection to the end of the list.
boolean	addAll(int index, java.util.Collection col) Inserts all elements from the given collection starting at the specified position.
void	addFirst(java.lang.Object obj) Inserts the object into the head of the list.
void	addLast(java.lang.Object obj) Appends the object into the tail of the list.
void	clear() Removes all objects from the list.
boolean	contains(java.lang.Object obj) Searches for the object starting from the beginning of the list.
boolean	containsAll(java.util.Collection col) Returns true if this list contains all of the elements of the specified collection.
java.lang.Object	export() Exports the list and all contained Realtime objects.
java.lang.Object	get(int index) Returns the element residing at the specified position.
java.lang.Object	getFirst() Returns the first element of the list (the head).
java.lang.Object	getLast() Returns the last element of the list (the tail).
int	indexOf(java.lang.Object obj) Searches for the equal object and return it's position in the list.
boolean	isEmpty() Returns true if this list contains no elements.
java.util.Iterator	iterator() An iterator over the list elements, starting from the first.
int	lastIndexOf(java.lang.Object obj) Searches for the equal object and return it's last occurence in the list.
java.util.ListIterator	listIterator() An iterator over the list elements, starting from the first.
java.util.ListIterator	listIterator(int index) An iterator over the list elements, starting from the specified one.
static FastList	newInstance() Allocates a PoolContext-enabled list.
java.lang.Object	remove(int index) Removes the element at specified position.
boolean	remove(java.lang.Object obj) Searches for the given object in the list and remove the object (once).
boolean	removeAll(java.util.Collection col) Removes all the elements that are contained in the given collection.
java.lang.Object	removeFirst() Removes and returns the first element of the list (the head).
boolean	retainAll(java.util.Collection col) Leaves only elements which are also contained in the given collection.
java.lang.Object	set(int index, java.lang.Object element) Sets the value of an element existing at the specified position.
int	size() Amount of elements in the list.
java.util.List	subList(int fromIndex, int toIndex) A transparent portion of the list (sub-list).
java.lang.Object[]	toArray() Copies list contents into the array.
java.lang.Object[]	toArray(java.lang.Object[] array) Copies list contents into the array.
FastString	toFastString(java.lang.CharSequence begin, java.lang.CharSequence end, java.lang.CharSequence separator, int capacity) Stringifies the list into FastString.
FastString	toFastString(int capacity) Stringify the list into FastString.
java.lang.Object	toHeap() Relocates the list and all contained Realtime objects to the GC heap.
java.lang.Object[]	toPoolArray() Copies list contents into the array.
java.lang.String	toString() The list stringified.

Methods inherited from class com.dautelle.realtime.RealtimeObject

clone, isLocalObject, isPoolObject, recycle

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

Methods inherited from interface java.util.List

equals, hashCode

Constructor Detail

FastList

public FastList()

Allocates a heap-only list. Entries, iterators - all is allocated from the GC heap, independed from any PoolContext.

Method Detail

newInstance

public static FastList newInstance()

Allocates a PoolContext-enabled list. If the PoolContext is entered, then all is allocated "on the stack" - to be used outside of the PoolContext the list should be "exported". If a PoolContext is not available during the list allocation, then the list will be using the GC heap for all subsequent operations, even if a PoolContext is available later (in the same way as when using the FastList() constructor).

See Also:

PoolContext

size

public final int size()

Amount of elements in the list.

Specified by:

size in interface java.util.Collection

export

public java.lang.Object export()

Exports the list and all contained Realtime objects. Existing iterators are not exported; if you wish to export an iterator, export the list before acquiring the iterator.

Specified by:

export in interface Realtime

Overrides:

export in class RealtimeObject

toHeap

public java.lang.Object toHeap()

Relocates the list and all contained Realtime objects to the GC heap. Existing iterators are not relocated; if you wish to use a heap iterator, move the list to the heap before acquiring the iterator.

Specified by:

toHeap in interface Realtime

Overrides:

toHeap in class RealtimeObject

toString

public java.lang.String toString()

The list stringified. If FastList was allocated on the GC heap, then StringBuffer is used, otherwise the FastString is used. See also toFastString(int).

toFastString

public FastString toFastString(int capacity)

Stringify the list into FastString. See also toFastString(CharSequence, CharSequence, CharSequence, int).

toFastString

public FastString toFastString(java.lang.CharSequence begin,
                               java.lang.CharSequence end,
                               java.lang.CharSequence separator,
                               int capacity)

Stringifies the list into FastString. For example: aList.toFastString( "[", "]", ", ", aList.size() * 10 ).

add

public final boolean add(java.lang.Object obj)

Adds an object into the end of the list. null pointers are not allowed.

Specified by:

add in interface java.util.Collection

addAll

public boolean addAll(java.util.Collection col)

Adds all objects from the collection to the end of the list. Null pointers in the collection are ignored (not inserted into the list).

Specified by:

addAll in interface java.util.Collection

clear

public void clear()

Removes all objects from the list. Allocated list capacity is retained.

Specified by:

clear in interface java.util.Collection

contains

public boolean contains(java.lang.Object obj)

Searches for the object starting from the beginning of the list. Objects are compared using "Object#equals".

Specified by:

contains in interface java.util.Collection

containsAll

public boolean containsAll(java.util.Collection col)

Returns true if this list contains all of the elements of the specified collection. Each element of the collection is searched for in the list. If the element is not found in the list, then false is returned. Method contains(Object) is used to search for an element. Null pointers from the collection are ignored (as if they were present in the list).

Specified by:

containsAll in interface java.util.Collection

isEmpty

public boolean isEmpty()

Returns true if this list contains no elements.

Specified by:

isEmpty in interface java.util.Collection

iterator

public java.util.Iterator iterator()

An iterator over the list elements, starting from the first.

Specified by:

iterator in interface java.util.Collection

remove

public boolean remove(java.lang.Object obj)

Searches for the given object in the list and remove the object (once). Objects are compared using Object.equals(java.lang.Object).

Specified by:

remove in interface java.util.Collection

Returns:

true if equal object was found and removed.

removeAll

public boolean removeAll(java.util.Collection col)

Removes all the elements that are contained in the given collection.

Specified by:

removeAll in interface java.util.Collection

Returns:

true if the list was modified as a result.

See Also:

remove( Object ), contains( Object )

retainAll

public boolean retainAll(java.util.Collection col)

Leaves only elements which are also contained in the given collection.

Specified by:

retainAll in interface java.util.Collection

toPoolArray

public java.lang.Object[] toPoolArray()

Copies list contents into the array. If the list is pool-allocated, then ArrayPool is used. Therefore the length of the returned array may exceed the size of the list.

toArray

public java.lang.Object[] toArray()

Copies list contents into the array. A new array is allocated from the GC heap, with exactly the size of the list. This is required to conform with the collections framework API, otherwise methods such as Collections.sort will throw exceptions.

Specified by:

toArray in interface java.util.Collection

toArray

public java.lang.Object[] toArray(java.lang.Object[] array)

Copies list contents into the array. If the list does not fit into the array, then a new array is allocated from the GC heap, with exactly the size of the list. This is required to conform with the collections framework API, otherwise methods such as Collections.sort will throw exceptions.

Specified by:

toArray in interface java.util.Collection

add

public void add(int index,
                java.lang.Object element)

Inserts the given element at the specified position. Index examples: list.add(0,element) will make the new element the first element of the list; list.add(list.size(),element) will made the new element the last element of the list.

Specified by:

add in interface java.util.List

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0 or greater than size().

addAll

public boolean addAll(int index,
                      java.util.Collection col)

Inserts all elements from the given collection starting at the specified position.

Specified by:

addAll in interface java.util.List

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0 or greater than size().

get

public java.lang.Object get(int index)

Returns the element residing at the specified position.

Specified by:

get in interface java.util.List

Returns:

the index-th element

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0 or greater than size() - 1.

indexOf

public int indexOf(java.lang.Object obj)

Searches for the equal object and return it's position in the list.

Specified by:

indexOf in interface java.util.List

Returns:

-1 if there is no such object in the list.

lastIndexOf

public int lastIndexOf(java.lang.Object obj)

Searches for the equal object and return it's last occurence in the list.

Specified by:

lastIndexOf in interface java.util.List

Returns:

-1 if there is no such object in the list.

listIterator

public java.util.ListIterator listIterator()

An iterator over the list elements, starting from the first.

Specified by:

listIterator in interface java.util.List

listIterator

public java.util.ListIterator listIterator(int index)

An iterator over the list elements, starting from the specified one. ListIterator is pointed so that the next element returned will be the index-th element of the list.

Specified by:

listIterator in interface java.util.List

Parameters:

index - may be from 0 till the list size().

remove

public java.lang.Object remove(int index)

Removes the element at specified position.

Specified by:

remove in interface java.util.List

Returns:

an object which were present at the index-th position.

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0 or greater than size() - 1.

set

public java.lang.Object set(int index,
                            java.lang.Object element)

Sets the value of an element existing at the specified position.

Specified by:

set in interface java.util.List

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0 or greater than size() - 1.

subList

public java.util.List subList(int fromIndex,
                              int toIndex)

A transparent portion of the list (sub-list). Sub-list is working directly on the main list, thus modifications made to the sub-list will affect the original list. For example, list.subList(10,14).clear() will remove 10th, 11th, 12th and 13th elements from the list. You can use several sub-lists at the same time (even from different threads) as long as there is at least one position of space between them:

 runThread( list.subList( 0, 10 ) ); runThread( list.subList( 10, 20 ); // Wrong!
 runThread( list.subList( 0, 9 ) ); runThread( list.subList( 10, 19 ) ); // Ok.
 

You should not use the main list while using one of it's sub-lists.

Specified by:

subList in interface java.util.List

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0 or greater than size().

removeFirst

public final java.lang.Object removeFirst()

Removes and returns the first element of the list (the head).

Throws:

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

getFirst

public final java.lang.Object getFirst()

Returns the first element of the list (the head).

Throws:

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

getLast

public final java.lang.Object getLast()

Returns the last element of the list (the tail).

Throws:

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

addFirst

public final void addFirst(java.lang.Object obj)

Inserts the object into the head of the list.

addLast

public final void addLast(java.lang.Object obj)

Appends the object into the tail of the list.