com.tangosol.util
Class SafeLinkedList

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractList
          com.tangosol.util.SafeLinkedList

All Implemented Interfaces:

Serializable, Cloneable, Iterable, Collection, List

Direct Known Subclasses:

RecyclingLinkedList

public class SafeLinkedList
extends AbstractList
implements List, Cloneable, Serializable

Implementation of the Collection Framework interface "List" using a linked list algorithm. Read-only operations avoid synchronizing. Some operations appear to be read-only but have side-effects, such as indexed operations against the List, because the List caches the last index used and the Node that it located (to facilitate processes that access the list sequentially using indexes etc.). Other operations, even if read-only, require the data structures to remain unchanged for the duration of the call to avoid potential exceptions (such as a NullPointerException if a reference is cleared).

Author:

cp 08/18/99

Nested Class Summary

protected static class

SafeLinkedList.Node A Node in the List.

Field Summary

protected int	m_cNodes The size of the List.
protected SafeLinkedList.Node	m_current The Node at the "cached position" in the List.
protected SafeLinkedList.Node	m_head The first Node in the List (or null if empty).
protected int	m_iPos The "cached position" in the List.
protected SafeLinkedList.Node	m_tail The last Node in the List (or null if empty).

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

SafeLinkedList()
Construct an empty List.

SafeLinkedList(Collection collection)
Construct a List containing the elements of the specified Collection.

Method Summary

void	add(int i, Object o) Inserts the specified element at the specified position in this List.
boolean	add(Object o) Appends the specified element to the end of this List.
boolean	addAll(Collection collection) 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 i, Collection collection) Inserts all of the elements in the specified collection at the specified location in this List.
void	clear() Removes all of the elements from this List.
Object	clone() Create a clone of the SafeLinkedList.
boolean	contains(Object o) Returns true if this List contains the specified element.
boolean	containsAll(Collection collection) Returns true if this List contains all of the elements of the specified collection.
Object	get(int i) Returns the element at the specified position in this List.
protected SafeLinkedList.Node	getNode(int i) Find and return the specified Node.
int	indexOf(Object o) Returns the index in this List of the first occurrence of the specified element, or -1 if this List does not contain this element.
protected SafeLinkedList.Node	instantiateNode(Object o) Instantiate a Node.
int	lastIndexOf(Object o) Returns the index in this List of the last occurrence of the specified element, or -1 if this List does not contain this element.
static void	main(String[] asArg) Self-test for SafeLinkedList.
protected void	markPosition(int i, SafeLinkedList.Node node) Remember that a certain Node occurs at a certain index.
Object	remove(int i) Removes the element at the specified position in this List.
boolean	remove(Object o) Removes the first occurrence in this List of the specified element.
protected void	reset() Completely reset the state of the List.
Object	set(int i, Object o) Replaces the element at the specified position in this List with the specified element.
int	size() Returns the number of elements in this List.
Object[]	toArray() Returns an array containing all of the elements in this List in the order that the elements occur in the List.
Object[]	toArray(Object[] a) Returns an array with a runtime type is that of the specified array and that contains all of the elements in this List.

Methods inherited from class java.util.AbstractList

equals, hashCode, iterator, listIterator, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

isEmpty, removeAll, retainAll, toString

Methods inherited from interface java.util.List

equals, hashCode, isEmpty, iterator, listIterator, listIterator, removeAll, retainAll, subList

Field Detail

m_head

protected SafeLinkedList.Node m_head

The first Node in the List (or null if empty).

m_tail

protected SafeLinkedList.Node m_tail

The last Node in the List (or null if empty).

m_cNodes

protected volatile int m_cNodes

The size of the List.

m_iPos

protected transient int m_iPos

The "cached position" in the List.

m_current

protected transient SafeLinkedList.Node m_current

The Node at the "cached position" in the List.

Constructor Detail

SafeLinkedList

public SafeLinkedList()

Construct an empty List.

SafeLinkedList

public SafeLinkedList(Collection collection)

Construct a List containing the elements of the specified Collection.

Parameters:

collection - the Collection to fill this List from

Method Detail

size

public int size()

Returns the number of elements in this List. This method is not synchronized; it returns a snapshot of the size of the List. To ensure that the List has not changed its size by the time this method returns, the List must be synchronized on before calling this method:

synchronized(list) { int c = list.size() ... }

Specified by:

size in interface Collection

Specified by:

size in interface List

Specified by:

size in class AbstractCollection

Returns:

the number of elements in this List

add

public boolean add(Object o)

Appends the specified element to the end of this List. Null values are supported.

Specified by:

add in interface Collection

Specified by:

add in interface List

Overrides:

add in class AbstractList

Parameters:

o - element to be appended to this List

Returns:

true because the List is modified

remove

public boolean remove(Object o)

Removes the first occurrence in this List of the specified element. If this List does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists).

Specified by:

remove in interface Collection

Specified by:

remove in interface List

Overrides:

remove in class AbstractCollection

Parameters:

o - element to be removed from this List, if present

Returns:

true if this List contained the specified element

contains

public boolean contains(Object o)

Returns true if this List contains the specified element. More formally, returns true if and only if this List contains at least one element e such that (o==null ? e==null : o.equals(e)). To ensure that the List still definitely contains (or does not contain) the element after this method returns, the List must be synchronized on before calling this method: synchronized(list) { if list.contains(o) { ... } }

Specified by:

contains in interface Collection

Specified by:

contains in interface List

Overrides:

contains in class AbstractCollection

Parameters:

o - element whose presence in this List is to be tested

Returns:

true if this List contains the specified element

containsAll

public boolean containsAll(Collection collection)

Returns true if this List contains all of the elements of the specified collection. This method is not synchronized. To ensure that the List still definitely contains (or does not contain) the elements after this method returns, the List must be synchronized on before calling this method: synchronized(list) { if list.containsAll(o) { ... } }

Specified by:

containsAll in interface Collection

Specified by:

containsAll in interface List

Overrides:

containsAll in class AbstractCollection

Parameters:

collection - collection to be checked for containment in this List

Returns:

true if this List contains all of the elements of the specified collection

indexOf

public int indexOf(Object o)

Returns the index in this List of the first occurrence of the specified element, or -1 if this List does not contain this element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

Specified by:

indexOf in interface List

Overrides:

indexOf in class AbstractList

Parameters:

o - element to search for.

Returns:

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

lastIndexOf

public int lastIndexOf(Object o)

Returns the index in this List of the last occurrence of the specified element, or -1 if this List does not contain this element. More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

Specified by:

lastIndexOf in interface List

Overrides:

lastIndexOf in class AbstractList

Parameters:

o - element to search for.

Returns:

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

add

public void add(int i,
                Object o)

Inserts the specified element at the specified position in this List. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Specified by:

add in interface List

Overrides:

add in class AbstractList

Parameters:

i - the index at which to insert the specified element

o - element to be inserted

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).

remove

public Object remove(int i)

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

Specified by:

remove in interface List

Overrides:

remove in class AbstractList

Parameters:

i - the index of the element to removed

Returns:

the element previously at the specified position

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).

get

public Object get(int i)

Returns the element at the specified position in this List.

Specified by:

get in interface List

Specified by:

get in class AbstractList

Parameters:

i - the index of the element to return

Returns:

the element at the specified position in this List

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).

set

public Object set(int i,
                  Object o)

Replaces the element at the specified position in this List with the specified element.

Specified by:

set in interface List

Overrides:

set in class AbstractList

Parameters:

i - the index of the element to replace

o - the value to be stored at the specified position

Returns:

the value previously at the specified position

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())

addAll

public boolean addAll(int i,
                      Collection collection)

Inserts all of the elements in the specified collection at the specified location in this List. The elements are inserted in the order that they are returned by the specified collection's iterator.

Specified by:

addAll in interface List

Overrides:

addAll in class AbstractList

Parameters:

i - the index at which insertion will occur

collection - a collection whose elements are to be inserted into this List

Returns:

true if this list changed as a result of the call

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).

addAll

public boolean addAll(Collection collection)

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.

Specified by:

addAll in interface Collection

Specified by:

addAll in interface List

Overrides:

addAll in class AbstractCollection

Parameters:

collection - a collection whose elements are to be added to this List

Returns:

true if this list changed as a result of the call

clear

public void clear()

Removes all of the elements from this List. This List will be empty after this call returns.

Specified by:

clear in interface Collection

Specified by:

clear in interface List

Overrides:

clear in class AbstractList

toArray

public Object[] toArray()

Returns an array containing all of the elements in this List in the order that the elements occur in the List. The returned array will be "safe" in that no references to it are maintained by the List. The caller is thus free to modify the returned array.

Specified by:

toArray in interface Collection

Specified by:

toArray in interface List

Overrides:

toArray in class AbstractCollection

Returns:

an array containing all of the elements in this List

toArray

public Object[] toArray(Object[] a)

Returns an array with a runtime type is that of the specified array and that contains all of the elements in this List. If the elements all fit in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this List.

If the List fits in the specified array with room to spare (i.e., the array has more elements than the List), the element in the array immediately following the end of the last element is set to null. This is useful in determining the length of the List only if the caller knows that the List does not contain any null elements.)

Specified by:

toArray in interface Collection

Specified by:

toArray in interface List

Overrides:

toArray in class AbstractCollection

Parameters:

a - the array into which the elements of the List are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose

Returns:

an array containing the elements of the List

Throws:

ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this List

clone

public Object clone()

Create a clone of the SafeLinkedList.

Returns:

a clone of the SafeLinkedList

markPosition

protected void markPosition(int i,
                            SafeLinkedList.Node node)

Remember that a certain Node occurs at a certain index.

Parameters:

i - the index

node - the Node

reset

protected void reset()

Completely reset the state of the List.

instantiateNode

protected SafeLinkedList.Node instantiateNode(Object o)

Instantiate a Node. (Factory pattern.) This method is over-ridden by inheriting implementations if the inheriting implementation extends the inner Node class.

Parameters:

o - the value for the Node

getNode

protected SafeLinkedList.Node getNode(int i)

Find and return the specified Node.

Parameters:

i - the Node index

Returns:

the Node

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).

main

public static void main(String[] asArg)
                 throws Exception

Self-test for SafeLinkedList.

Throws:

Exception