y.base
Class YList

java.lang.Object
  y.base.YList

All Implemented Interfaces:

java.lang.Iterable, java.util.Collection, java.util.List

Direct Known Subclasses:

BendList, EdgeList, NodeList

public class YList
extends java.lang.Object
implements java.util.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.

It also 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, this list 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(java.util.Collection c)
Creates a list that is initialized with the elements provided by the given Collection object.

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

YList(java.lang.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, java.lang.Object element) Inserts the specified element at the specified position in this list.
boolean	add(java.lang.Object o) Appends the specified element to the end of this list.
boolean	addAll(java.util.Collection collection) Appends all elements provided by the given collection to this list.
boolean	addAll(int index, java.util.Collection c) Adds all elements provided by the given collection to this list at the specified position.
void	addAll(YCursor c) Appends all elements provided by the given cursor to this list.
void	addFirstCell(ListCell cell) Adds a formerly removed ListCell object at the head 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(java.lang.Object o) Whether or not this list contains the given element.
boolean	containsAll(java.util.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.
java.lang.Object	elementAt(int i) Returns the i-th element of this list.
boolean	equals(java.lang.Object other) Compares the specified object with this list for equality.
ListCell	findCell(java.lang.Object o) Returns the ListCell where object o is stored.
java.lang.Object	first() Returns the first element of this list.
ListCell	firstCell() Returns the first cell of this list.
java.lang.Object	get(int index) Returns the element at the specified position in this list.
ListCell	getCell(int index) Gets the cell at the given index.
java.lang.Object	getInfo(ListCell c) Returns the element stored in the given list cell.
int	hashCode() Returns the hash code value for this list.
int	indexOf(java.lang.Object obj) Returns the zero-based index of the given element in this list.
ListCell	insertAfter(java.lang.Object o, ListCell refCell) Inserts the given object into this list with respect to a given reference list cell.
ListCell	insertBefore(java.lang.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.
java.util.Iterator	iterator() Returns an iterator for that list.
java.lang.Object	last() Returns the last element of this list.
ListCell	lastCell() Returns the last cell of this list.
int	lastIndexOf(java.lang.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.
java.util.ListIterator	listIterator() Returns a list iterator of the elements in this list.
java.util.ListIterator	listIterator(int index) Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.
java.lang.Object	peek() Equivalent to first().
java.lang.Object	pop() Removes the first element from this list and returns it.
java.lang.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(java.lang.Object o) Inserts the given object at the head of this list.
ListCell	pushLast(java.lang.Object o) Inserts the given object at the tail of this list.
java.lang.Object	remove(int index) Removes the element at the specified position in this list.
boolean	remove(java.lang.Object o) Removes the given object from this list.
boolean	removeAll(java.util.Collection collection) Removes the given collection of objects from this list.
java.lang.Object	removeAt(YCursor c) Removes the element pointed to by the given YCursor object.
java.lang.Object	removeCell(ListCell c) Removes the given list cell, and hence the element stored in it, from this list.
boolean	retainAll(java.util.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.
java.lang.Object	set(int index, java.lang.Object element) Replaces the element at the specified position in this list with the specified element.
void	setInfo(ListCell c, java.lang.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(java.util.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.
java.util.List	subList(int fromIndex, int toIndex) Inserts the specified element at the specified position in this list.
ListCell	succCell(ListCell c) Returns the successor cell of the given list cell.
java.lang.Object[]	toArray() Returns an array representation of this list.
java.lang.Object[]	toArray(java.lang.Object[] a) Returns an array containing all list elements in the correct order.
java.lang.String	toString() Returns a string representation of this List.
java.util.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(java.util.Collection c)

Creates a list that is initialized with the elements provided by the given Collection object.

YList

public YList(java.util.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(java.lang.Object[] a)

Creates a list that is initialized with the elements provided by the given array of objects.

Method Detail

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(java.lang.Object o)

Appends the specified element to the end of this list.

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.List

addAll

public boolean addAll(java.util.Collection collection)

Appends all elements provided by the given collection to this list.

Specified by:

addAll in interface java.util.Collection

Specified by:

addAll in interface java.util.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(java.lang.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(java.lang.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 java.util.Collection

Specified by:

size in interface java.util.List

isEmpty

public boolean isEmpty()

Checks whether this list contains elements.

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface java.util.List

clear

public void clear()

Removes all elements from this list.

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

first

public java.lang.Object first()

Returns the first element of this list.

Precondition:

!isEmpty().

pop

public java.lang.Object pop()

Removes the first element from this list and returns it.

push

public ListCell push(java.lang.Object o)

Inserts the given object at the head of this list.

Invoking this method is equivalent to calling add(0, o) and retrieving the first list cell afterwards.

Returns:

The newly created ListCell object that stores the given object.

pushLast

public ListCell pushLast(java.lang.Object o)

Inserts the given object at the tail of this list.

Invoking this method is equivalent to calling add(o) and retrieving the last list cell afterwards.

Returns:

The newly created ListCell object that stores the given object.

peek

public java.lang.Object peek()

Equivalent to first().

last

public java.lang.Object last()

Returns the last element of this list.

Precondition:

!isEmpty().

popLast

public java.lang.Object popLast()

Removes the last element from this list and returns it.

elementAt

public java.lang.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(java.lang.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 java.util.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 java.lang.Object getInfo(ListCell c)

Returns the element stored in the given list cell.

setInfo

public void setInfo(ListCell c,
                    java.lang.Object value)

Updates the element stored in the given list cell with the given object.

remove

public boolean remove(java.lang.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 java.util.Collection

Specified by:

remove in interface java.util.List

Complexity:

O(size())

removeAll

public boolean removeAll(java.util.Collection collection)

Removes the given collection of objects from this list.

Specified by:

removeAll in interface java.util.Collection

Specified by:

removeAll in interface java.util.List

Returns:

Whether there have been elements removed.

retainAll

public boolean retainAll(java.util.Collection collection)

Retains only those elements in this list which are contained in the given collection.

Specified by:

retainAll in interface java.util.Collection

Specified by:

retainAll in interface java.util.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 java.lang.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 java.lang.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 java.util.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 java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.List

listIterator

public java.util.ListIterator listIterator()

Returns a list iterator of the elements in this list.

Specified by:

listIterator in interface java.util.List

contains

public boolean contains(java.lang.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 java.util.Collection

Specified by:

contains in interface java.util.List

containsAll

public boolean containsAll(java.util.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 java.util.Collection

Specified by:

containsAll in interface java.util.List

findCell

public ListCell findCell(java.lang.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 java.lang.String toString()

Returns a string representation of this List.

Overrides:

toString in class java.lang.Object

toArray

public java.lang.Object[] toArray()

Returns an array representation of this list.

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

toArray

public java.lang.Object[] toArray(java.lang.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 java.util.Collection

Specified by:

toArray in interface java.util.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:

java.lang.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 java.util.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(java.util.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,
                      java.util.Collection c)

Adds all elements provided by the given collection to this list at the specified position. Elements currently at that position are shifted to the right.

Specified by:

addAll in interface java.util.List

Parameters:

index - index at which the first element of the specified collection is placed

c - the collection that contains the elements to be added

Returns:

true if this list was changed, false otherwise

Throws:

java.lang.IndexOutOfBoundsException - if the index is out of range, that is, negative or larger than the size of this 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:

java.lang.IndexOutOfBoundsException - if the index is negative or greater or equal than the size()

lastIndexOf

public int lastIndexOf(java.lang.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.

Specified by:

lastIndexOf in interface java.util.List

set

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

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

Specified by:

set in interface java.util.List

remove

public java.lang.Object remove(int index)

Removes the element at the specified position in this list.

Specified by:

remove in interface java.util.List

listIterator

public java.util.ListIterator listIterator(int index)

Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.

Specified by:

listIterator in interface java.util.List

get

public java.lang.Object get(int index)

Returns the element at the specified position in this list.

Specified by:

get in interface java.util.List

add

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

Inserts the specified element at the specified position in this list.

Specified by:

add in interface java.util.List

subList

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

Inserts the specified element at the specified position in this list.

Specified by:

subList in interface java.util.List

equals

public boolean equals(java.lang.Object other)

Compares the specified object with this list for equality.

Specified by:

equals in interface java.util.Collection

Specified by:

equals in interface java.util.List

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Returns the hash code value for this list.

Specified by:

hashCode in interface java.util.Collection

Specified by:

hashCode in interface java.util.List

Overrides:

hashCode in class java.lang.Object