Search this API

y.base
Class YList

java.lang.Object
  extended by y.base.YList
All Implemented Interfaces:
Iterable, Collection, List
Direct Known Subclasses:
BendList, EdgeList, NodeList

public class YList
extends Object
implements List

An implementation of a doubly linked list that provides direct access to the cells that store the elements. The cells are represented by class ListCell.

This class supports fast access and removal operations, specifically, it is possible to remove an element in constant time (i.e. O(1)) given a reference to its list cell.

Class YList supports iteration over the elements either by using the list cells directly (methods firstCell()/lastCell() together with succCell(ListCell)/predCell(ListCell), respectively) or by means of a cursor (cursor()).

Furthermore, YList offers its own sort() method. Note that this class also provides all relevant methods to use the list like a stack data type.

This implementation permits null as values. It implements the List interface but does not support the subList(int, int) method. The implementation of this method will throw an UnsupportedOperationException if invoked. The iterator()s returned by instances of this class are fail fast, however the cursor() implementation is not.

 

Nested Class Summary
 class YList.ListCursorImpl
          Cursor implementation for class YList.
 
Constructor Summary
YList()
          Creates an empty doubly linked list.
YList(Collection c)
          Creates a list that is initialized with the elements provided by the given Collection object.
YList(Iterator it)
          Creates a list that is initialized with the elements provided by the given Iterator object.
YList(Object[] a)
          Creates a list that is initialized with the elements provided by the given array of objects.
YList(YCursor c)
          Creates a list that is initialized with the elements provided by the given YCursor object.
YList(YCursor c, DataProvider predicate)
          Creates a list that is initialized with those elements from the given YCursor object for which the given data provider returns true upon calling its getBool method.
 
Method Summary
 void add(int index, Object element)
           
 boolean add(Object o)
          Same as addLast(Object).
 boolean addAll(Collection collection)
          Appends all elements provided by the given collection to this list.
 boolean addAll(int index, Collection c)
           
 void addAll(YCursor c)
          Appends all elements provided by the given cursor to this list.
 ListCell addFirst(Object o)
          Inserts the given object at the head of this list.
 void addFirstCell(ListCell cell)
          Adds a formerly removed ListCell object at the head of this list.
 ListCell addLast(Object o)
          Inserts the given object at the tail of this list.
 void addLastCell(ListCell cell)
          Adds a formerly removed ListCell object at the tail of this list.
 void clear()
          Removes all elements from this list.
 boolean contains(Object o)
          Whether or not this list contains the given element.
 boolean containsAll(Collection collection)
          Whether or not this list contains all the elements in the given collection.
 YCursor cursor()
          Returns a cursor for this list.
 ListCell cyclicPred(ListCell c)
          Returns the cyclic predecessor cell of the given list cell.
 ListCell cyclicSucc(ListCell c)
          Returns the cyclic successor cell of the given list cell.
 Object elementAt(int i)
          Returns the i-th element of this list.
 boolean equals(Object other)
           
 ListCell findCell(Object o)
          Returns the ListCell where object o is stored.
 Object first()
          Returns the first element of this list.
 ListCell firstCell()
          Returns the first cell of this list.
 Object get(int index)
           
 ListCell getCell(int index)
          Gets the cell at the given index.
 Object getInfo(ListCell c)
          Returns the element stored in the given list cell.
 int hashCode()
           
 int indexOf(Object obj)
          Returns the zero-based index of the given element in this list.
 ListCell insertAfter(Object o, ListCell refCell)
          Inserts the given object into this list with respect to a given reference list cell.
 ListCell insertBefore(Object o, ListCell refCell)
          Inserts the given object into this list with respect to a given reference list cell.
 void insertCellAfter(ListCell cellToInsert, ListCell refCell)
          Inserts a formerly removed ListCell object into this list with respect to a given reference list cell.
 void insertCellBefore(ListCell cellToInsert, ListCell refCell)
          Inserts a formerly removed ListCell object into this list with respect to a given reference list cell.
 boolean isEmpty()
          Checks whether this list contains elements.
 Iterator iterator()
          Returns an iterator for that list.
 Object last()
          Returns the last element of this list.
 ListCell lastCell()
          Returns the last cell of this list.
 int lastIndexOf(Object o)
           
 ListIterator listIterator()
           
 ListIterator listIterator(int index)
           
 Object peek()
          Equivalent to first().
 Object pop()
          Removes the first element from this list and returns it.
 Object popLast()
          Removes the last element from this list and returns it.
 ListCell predCell(ListCell c)
          Returns the predecessor cell of the given list cell.
 ListCell push(Object o)
          Equivalent to addFirst(Object).
 Object remove(int index)
           
 boolean remove(Object o)
          Removes the given object from this list.
 boolean removeAll(Collection collection)
          Removes the given collection of objects from this list.
 Object removeAt(YCursor c)
          Removes the element pointed to by the given YCursor object.
 Object removeCell(ListCell c)
          Removes the given list cell, and hence the element stored in it, from this list.
 boolean retainAll(Collection collection)
          Retains only those elements in this list which are contained in the given collection.
 void reverse()
          Reverses the sequence of elements in this list.
 Object set(int index, Object element)
           
 void setInfo(ListCell c, Object value)
          Updates the element stored in the given list cell with the given object.
 int size()
          Returns the number of elements in this list.
 void sort()
          Sorts the elements in this list into ascending order, according to their natural ordering.
 void sort(Comparator comp)
          Sorts the elements in this list according to the given comparator.
 void splice(YList list)
          Transfers the contents of the given list to the end of this list.
 List subList(int fromIndex, int toIndex)
           
 ListCell succCell(ListCell c)
          Returns the successor cell of the given list cell.
 Object[] toArray()
          Returns an array representation of this list.
 Object[] toArray(Object[] a)
          Returns an array containing all list elements in the correct order.
 String toString()
          Returns a string representation of this List.
 Vector toVector()
          Returns a Vector representation of this list.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

YList

public YList()
Creates an empty doubly linked list.


YList

public YList(Collection c)
Creates a list that is initialized with the elements provided by the given Collection object.


YList

public YList(Iterator it)
Creates a list that is initialized with the elements provided by the given Iterator object.


YList

public YList(YCursor c)
Creates a list that is initialized with the elements provided by the given YCursor object.


YList

public YList(YCursor c,
             DataProvider predicate)
Creates a list that is initialized with those elements from the given YCursor object for which the given data provider returns true upon calling its getBool method.

Parameters:
c - A cursor providing objects that should be added to this list.
predicate - A data provider that acts as a inclusion predicate for each object accessible by the given cursor.

YList

public YList(Object[] a)
Creates a list that is initialized with the elements provided by the given array of objects.

Method Detail

addFirst

public ListCell addFirst(Object o)
Inserts the given object at the head of this list.

Returns:
The newly created ListCell object that stores the given object.

addLast

public ListCell addLast(Object o)
Inserts the given object at the tail of this list.

Returns:
The newly created ListCell object that stores the given object.

addLastCell

public void addLastCell(ListCell cell)
Adds a formerly removed ListCell object at the tail of this list.

Attention: If the ListCell object is still part of any list, then that list will be corrupted afterwards.

Parameters:
cell - A list cell which is not part of any list.

addFirstCell

public void addFirstCell(ListCell cell)
Adds a formerly removed ListCell object at the head of this list.

Attention: If the ListCell object is still part of any list, then that list will be corrupted afterwards.

Parameters:
cell - A list cell which is not part of any list.

add

public boolean add(Object o)
Same as addLast(Object).

Specified by:
add in interface Collection
Specified by:
add in interface List
Returns:
true

addAll

public boolean addAll(Collection collection)
Appends all elements provided by the given collection to this list.

Specified by:
addAll in interface Collection
Specified by:
addAll in interface List
Returns:
Whether there have been elements appended.

addAll

public void addAll(YCursor c)
Appends all elements provided by the given cursor to this list. The cursor will be moved from its given position to the end.

Be aware that a statement like aList.append(aList.cursor()) results in an infinite recursion.


insertBefore

public ListCell insertBefore(Object o,
                             ListCell refCell)
Inserts the given object into this list with respect to a given reference list cell. The (newly created) list cell that stores the object is inserted right before the reference list cell refCell.

If refCell == null, the given object is appended to the list.

Precondition:
refCell must be part of this list.
Parameters:
o - The object to be inserted.
refCell - The list cell used to reference the position.
Returns:
The newly created ListCell object that stores object o.

insertCellBefore

public void insertCellBefore(ListCell cellToInsert,
                             ListCell refCell)
Inserts a formerly removed ListCell object into this list with respect to a given reference list cell. The ListCell object is inserted right before the reference list cell refCell.

Attention: If the ListCell object is still part of any list, then that list will be corrupted afterwards.

Precondition:
refCell must be part of this list.
Parameters:
cellToInsert - A list cell which is not part of any list.
refCell - The list cell used to reference the position.

insertCellAfter

public void insertCellAfter(ListCell cellToInsert,
                            ListCell refCell)
Inserts a formerly removed ListCell object into this list with respect to a given reference list cell. The ListCell object is inserted right after the reference list cell refCell.

Attention: If the ListCell object is still part of any list, then that list will be corrupted afterwards.

Precondition:
refCell must be part of this list.
Parameters:
cellToInsert - A list cell which is not part of any list.
refCell - The list cell used to reference the position.

insertAfter

public ListCell insertAfter(Object o,
                            ListCell refCell)
Inserts the given object into this list with respect to a given reference list cell. The (newly created) list cell that stores the object is inserted right after the reference list cell refCell.

If refCell == null, the given object is inserted at the head of the list.

Precondition:
refCell must be part of this list.
Parameters:
o - The object to be inserted.
refCell - The list cell used to reference the position.
Returns:
The newly created ListCell object that stores object o.

size

public int size()
Returns the number of elements in this list.

Specified by:
size in interface Collection
Specified by:
size in interface List

isEmpty

public boolean isEmpty()
Checks whether this list contains elements.

Specified by:
isEmpty in interface Collection
Specified by:
isEmpty in interface List

clear

public void clear()
Removes all elements from this list.

Specified by:
clear in interface Collection
Specified by:
clear in interface List

first

public Object first()
Returns the first element of this list.

Precondition:
!isEmpty().

pop

public Object pop()
Removes the first element from this list and returns it.


push

public ListCell push(Object o)
Equivalent to addFirst(Object).


peek

public Object peek()
Equivalent to first().


last

public Object last()
Returns the last element of this list.

Precondition:
!isEmpty().

popLast

public Object popLast()
Removes the last element from this list and returns it.


elementAt

public Object elementAt(int i)
Returns the i-th element of this list.

Precondition:
i is a valid index, i.e., i >= 0 && i < size().

indexOf

public int indexOf(Object obj)
Returns the zero-based index of the given element in this list. If the given element is not in the list, -1 is returned.

Specified by:
indexOf in interface List

firstCell

public ListCell firstCell()
Returns the first cell of this list.

Precondition:
!isEmpty().

lastCell

public ListCell lastCell()
Returns the last cell of this list.

Precondition:
!isEmpty().

succCell

public ListCell succCell(ListCell c)
Returns the successor cell of the given list cell.


predCell

public ListCell predCell(ListCell c)
Returns the predecessor cell of the given list cell.


cyclicSucc

public ListCell cyclicSucc(ListCell c)
Returns the cyclic successor cell of the given list cell.

The first cell is returned as the cyclic successor of the last list cell.


cyclicPred

public ListCell cyclicPred(ListCell c)
Returns the cyclic predecessor cell of the given list cell.

The last cell is returned as the cyclic predecessor of the first list cell.


getInfo

public Object getInfo(ListCell c)
Returns the element stored in the given list cell.


setInfo

public void setInfo(ListCell c,
                    Object value)
Updates the element stored in the given list cell with the given object.


remove

public boolean remove(Object o)
Removes the given object from this list. Only the first element for which equality to o holds gets removed.

Specified by:
remove in interface Collection
Specified by:
remove in interface List
Complexity:
O(size())

removeAll

public boolean removeAll(Collection collection)
Removes the given collection of objects from this list.

Specified by:
removeAll in interface Collection
Specified by:
removeAll in interface List
Returns:
Whether there have been elements removed.

retainAll

public boolean retainAll(Collection collection)
Retains only those elements in this list which are contained in the given collection.

Specified by:
retainAll in interface Collection
Specified by:
retainAll in interface List
Complexity:
This operation has running time O(max(m, n)), were m and n are the sizes of this list and the given collection, respectively.
Returns:
Whether there have been elements removed.

removeCell

public Object removeCell(ListCell c)
Removes the given list cell, and hence the element stored in it, from this list.

Precondition:
The given list cell is part of this list.
Complexity:
O(1)
Returns:
The element that is stored in the removed cell.

removeAt

public Object removeAt(YCursor c)
Removes the element pointed to by the given YCursor object.

Precondition:
The given cursor has been created by a call to this list's cursor() method and the element pointed to by it is contained in this list.
Returns:
The removed element.

cursor

public YCursor cursor()
Returns a cursor for this list. All cursor operations are supported. This cursor implementation is not fail-fast and continues to work if this list is modified during the traversal as long as the current ListCell the cursor points at is this in this list or has been removed from this list but has not been added to another instance since then.


iterator

public Iterator iterator()
Returns an iterator for that list. The remove operation is supported on the iterator. This iterator instance is fail-fast.

Specified by:
iterator in interface Iterable
Specified by:
iterator in interface Collection
Specified by:
iterator in interface List

listIterator

public ListIterator listIterator()
Specified by:
listIterator in interface List

contains

public boolean contains(Object o)
Whether or not this list contains the given element. Equality of elements is defined by the Object.equals(Object) method.

Specified by:
contains in interface Collection
Specified by:
contains in interface List

containsAll

public boolean containsAll(Collection collection)
Whether or not this list contains all the elements in the given collection. Equality of elements is defined by the Object.equals(Object) method.

Specified by:
containsAll in interface Collection
Specified by:
containsAll in interface List

findCell

public ListCell findCell(Object o)
Returns the ListCell where object o is stored. This operation returns null, if no such cell exists. Equality of elements is defined by the Object.equals(Object) method. The first element in the list that matches that criteria is returned.

Returns:
the ListCell that contains the element or null if no such ListCell was found

toString

public String toString()
Returns a string representation of this List.

Overrides:
toString in class Object

toArray

public Object[] toArray()
Returns an array representation of this list.

Specified by:
toArray in interface Collection
Specified by:
toArray in interface List

toArray

public Object[] toArray(Object[] a)
Returns an array containing all list elements in the correct order. The runtime type of the returned array is that of the given array.

If the list does not fit in the specified array, 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 collection 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
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 a is not a supertype of the runtime type of every element in this list.

toVector

public Vector toVector()
Returns a Vector representation of this list.


reverse

public void reverse()
Reverses the sequence of elements in this list.


sort

public void sort(Comparator comp)
Sorts the elements in this list according to the given comparator.

NOTE: The elements will be assigned to different list cells by this method.

Complexity:
O(size() * log(size()))

sort

public void sort()
Sorts the elements in this list into ascending order, according to their natural ordering. All elements must implement the Comparable interface. Furthermore, all elements in this list must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in this list).

NOTE: The elements will be assigned to different list cells by this method.

Complexity:
O(size() * log(size()))

splice

public void splice(YList list)
Transfers the contents of the given list to the end of this list. The given list will be empty after this operation.

Note that this operation transfers the list cells of the given list to this list. No new list cells are created by this operation.

Complexity:
O(1)

addAll

public boolean addAll(int index,
                      Collection c)
Specified by:
addAll in interface List

getCell

public final ListCell getCell(int index)
Gets the cell at the given index.

Parameters:
index - the zero-based index of the cell in this list.
Returns:
The cell.
Throws:
IndexOutOfBoundsException - if the index is negative or greater or equal than the size()

lastIndexOf

public int lastIndexOf(Object o)
Specified by:
lastIndexOf in interface List

set

public Object set(int index,
                  Object element)
Specified by:
set in interface List

remove

public Object remove(int index)
Specified by:
remove in interface List

listIterator

public ListIterator listIterator(int index)
Specified by:
listIterator in interface List

get

public Object get(int index)
Specified by:
get in interface List

add

public void add(int index,
                Object element)
Specified by:
add in interface List

subList

public List subList(int fromIndex,
                    int toIndex)
Specified by:
subList in interface List

equals

public boolean equals(Object other)
Specified by:
equals in interface Collection
Specified by:
equals in interface List
Overrides:
equals in class Object

hashCode

public int hashCode()
Specified by:
hashCode in interface Collection
Specified by:
hashCode in interface List
Overrides:
hashCode in class Object

© Copyright 2000-2017,
yWorks GmbH.
All rights reserved.