ptolemy.actor.gt.data
Class FastLinkedList<E>

java.lang.Object
  ptolemy.actor.gt.data.FastLinkedList<E>

Type Parameters:

E - The element type of this linked list.

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>

Direct Known Subclasses:

GraphAnalyzer.IndexedLists, GraphMatcher.LookbackList, GraphMatcher.ObjectList

public class FastLinkedList<E>
extends java.lang.Object
implements java.util.Collection<E>

A linked list that provides efficient add and removal functions.

Since:

Ptolemy II 8.0

Version:

$Id: FastLinkedList.java 57046 2010-01-27 23:35:53Z cxh $

Author:

Thomas Huining Feng

Accepted Rating:

Red (tfeng)

Proposed Rating:

Yellow (tfeng)

Nested Class Summary

class

FastLinkedList.Entry An entry in this linked list that contains an element.

Field Summary

private FastLinkedList.Entry	_head The head of this linked list.
private boolean	_recalculateSize Whether the _size field is an inaccurate size of this linked list.
private int	_size The size of this linked list.
private FastLinkedList.Entry	_tail The tail of this linked list.

Constructor Summary

FastLinkedList()

Method Summary

boolean	add(E element) Add an element to the end of this linked list.
boolean	addAll(java.util.Collection<? extends E> collection) Add all the elements of the given collection to the end of this linked list.
void	addEntryAfter(FastLinkedList.Entry entry, FastLinkedList.Entry previousEntry) Add an entry after previousEntry, or add the entry to the head if previousEntry is null.
void	addEntryBefore(FastLinkedList.Entry entry, FastLinkedList.Entry nextEntry) Add an entry before nextEntry, or add the entry to the tail if nextEntry is null.
void	addEntryToHead(FastLinkedList.Entry entry) Add an entry to the head of this linked list.
void	addEntryToTail(FastLinkedList.Entry entry) Add an entry to the tail of this linked list.
void	clear() Clear this linked list.
boolean	contains(java.lang.Object element) Test whether this linked list has the given element in an entry.
boolean	containsAll(java.util.Collection<?> collection) Test whether this linked list has all the elements of the given collection.
FastLinkedList.Entry	findEntry(E element) Find an entry with the given element and return it.
FastLinkedList.Entry	getHead() Get the head entry.
FastLinkedList.Entry	getTail() Get the tail entry.
boolean	isEmpty() Test whether this collection is empty.
java.util.Iterator<E>	iterator() Not implemented.
boolean	remove(java.lang.Object element) Remove the first entry that has the given element.
boolean	removeAll(java.util.Collection<?> collection) Remove all the elements of the collection from this linked list.
boolean	removeAllAfter(FastLinkedList.Entry entry) Remove all entries after the given entry.
boolean	removeAllBefore(FastLinkedList.Entry entry) Remove all entries before the given entry.
boolean	retainAll(java.util.Collection<?> collection) Retain all elements of the given collection, but remove entries whose elements are not in the collection.
int	size() Get the size of this linked list.
java.lang.Object[]	toArray() Return an array that contains all the elements in this linked list.
<T> T[]	toArray(T[] array) Store all the elements in this linked list into the given array if its size is enough for the storage, or create a new array of the same type as the given array for the storage and return it.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode

Field Detail

_head

private FastLinkedList.Entry _head

The head of this linked list.

_recalculateSize

private boolean _recalculateSize

Whether the _size field is an inaccurate size of this linked list.

_size

private int _size

The size of this linked list.

_tail

private FastLinkedList.Entry _tail

The tail of this linked list.

Constructor Detail

FastLinkedList

public FastLinkedList()

Method Detail

add

public boolean add(E element)

Add an element to the end of this linked list.

Specified by:

add in interface java.util.Collection<E>

Parameters:

element - The element to be added.

Returns:

Always true.

addAll

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

Add all the elements of the given collection to the end of this linked list.

Specified by:

addAll in interface java.util.Collection<E>

Parameters:

collection - The collection.

Returns:

Always true.

addEntryAfter

public void addEntryAfter(FastLinkedList.Entry entry,
                          FastLinkedList.Entry previousEntry)

Add an entry after previousEntry, or add the entry to the head if previousEntry is null.

Parameters:

entry - The entry to be added.

previousEntry - The previous entry.

addEntryBefore

public void addEntryBefore(FastLinkedList.Entry entry,
                           FastLinkedList.Entry nextEntry)

Add an entry before nextEntry, or add the entry to the tail if nextEntry is null.

Parameters:

entry - The entry to be added.

nextEntry - The next entry.

addEntryToHead

public void addEntryToHead(FastLinkedList.Entry entry)

Add an entry to the head of this linked list.

Parameters:

entry - The entry to be added.

addEntryToTail

public void addEntryToTail(FastLinkedList.Entry entry)

Add an entry to the tail of this linked list.

Parameters:

entry - The entry to be added.

clear

public void clear()

Clear this linked list.

Specified by:

clear in interface java.util.Collection<E>

contains

public boolean contains(java.lang.Object element)

Test whether this linked list has the given element in an entry.

Specified by:

contains in interface java.util.Collection<E>

Parameters:

element - The element.

Returns:

true if the element is found.

containsAll

public boolean containsAll(java.util.Collection<?> collection)

Test whether this linked list has all the elements of the given collection.

Specified by:

containsAll in interface java.util.Collection<E>

Parameters:

collection - The collection.

Returns:

true if all the elements are found.

findEntry

public FastLinkedList.Entry findEntry(E element)

Find an entry with the given element and return it. Return null if not found.

Parameters:

element - The element.

Returns:

The entry.

getHead

public FastLinkedList.Entry getHead()

Get the head entry.

Returns:

The head entry.

getTail

public FastLinkedList.Entry getTail()

Get the tail entry.

Returns:

The tail entry.

isEmpty

public boolean isEmpty()

Test whether this collection is empty.

Specified by:

isEmpty in interface java.util.Collection<E>

Returns:

true if this collection is empty.

iterator

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

Not implemented.

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Returns:

The iterator to iterate elements in this linked list.

remove

public boolean remove(java.lang.Object element)

Remove the first entry that has the given element.

Specified by:

remove in interface java.util.Collection<E>

Parameters:

element - The element.

Returns:

true if an entry is removed, or false if an entry cannot be found.

removeAll

public boolean removeAll(java.util.Collection<?> collection)

Remove all the elements of the collection from this linked list.

Specified by:

removeAll in interface java.util.Collection<E>

Parameters:

collection - The collection.

Returns:

true if this linked list is altered, or false if no entry is removed.

removeAllAfter

public boolean removeAllAfter(FastLinkedList.Entry entry)

Remove all entries after the given entry.

Parameters:

entry - The entry, which must be contained in this linked list.

Returns:

true if this linked list is altered, or false if no entry is removed.

removeAllBefore

public boolean removeAllBefore(FastLinkedList.Entry entry)

Remove all entries before the given entry.

Parameters:

entry - The entry, which must be contained in this linked list.

Returns:

true if this linked list is altered, or false if no entry is removed.

retainAll

public boolean retainAll(java.util.Collection<?> collection)

Retain all elements of the given collection, but remove entries whose elements are not in the collection.

Specified by:

retainAll in interface java.util.Collection<E>

Parameters:

collection - The collection.

Returns:

true if this linked list is altered, or false if no entry is removed.

size

public int size()

Get the size of this linked list.

Specified by:

size in interface java.util.Collection<E>

Returns:

The size.

toArray

public java.lang.Object[] toArray()

Return an array that contains all the elements in this linked list.

Specified by:

toArray in interface java.util.Collection<E>

Returns:

The array.

toArray

public <T> T[] toArray(T[] array)

Store all the elements in this linked list into the given array if its size is enough for the storage, or create a new array of the same type as the given array for the storage and return it.

Specified by:

toArray in interface java.util.Collection<E>

Type Parameters:

T - The element type of the array.

Parameters:

array - The array.

Returns:

The given array, or a new array if the given array is not big enough.