Package com.tangosol.util

Class 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
    See Also:
    Serialized Form

    • Field Detail

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

      • removeFirst

        public Object removeFirst()
        Removes and returns the first element in the list.
        Returns:
        the removed element, or null if the list was empty

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

      • getFirst

        public Object getFirst()
        Returns the first element in the list, or null if empty.
        Returns:
        the first element in the list, or null if empty

      • 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.
        Overrides:
        clone in class Object
        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; the marker is updated only if the index is greater than zero and less than size() - 1
        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()).