y.base
Class YList

java.lang.Object
  |
  +--y.base.YList

All Implemented Interfaces:

Collection

Direct Known Subclasses:

BendList, EdgeList, NodeList

public class YList

extends Object

implements Collection

YList is an implementation of a doubly linked list. This implementation provides access to the cells (links) of the list, which are represented by the class ListCell. Only objects that are non-null may be added to this list implementation.

Nested Class Summary

class

YList.ListCursorImpl Cursor implementation for ylists

Constructor Summary

YList()
Creates an empty doubly linked list.

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

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

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 YCursor c.

YList(YCursor c, DataProvider predicate)
Creates a list containing the objects accessible via the given cursor and for which the given data provider returns true upon calling its getBool method.

Method Summary

boolean	add(Object o) Same as addLast(Object o).
boolean	addAll(Collection collection) Adds a collection of items to the list.
void	addAll(YCursor c) Appends objects provided by given cursor to this list.
ListCell	addFirst(Object o) Inserts Object o at the head of this list.
void	addFirstCell(ListCell cell) Adds a formerly removed ListCell at the head of this list.
ListCell	addLast(Object o) Inserts Object o at the tail of this list.
void	addLastCell(ListCell cell) Adds a formerly removed ListCell 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 the elements given by a collection.
YCursor	cursor() Returns a cursor for this list.
ListCell	cyclicPred(ListCell c) Returns the cyclic predecessor cell of ListCell c.
ListCell	cyclicSucc(ListCell c) Returns the cyclic successor cell of ListCell c.
Object	elementAt(int i) Returns the i-th element in this list.
ListCell	findCell(Object o) Returns the cell where Object o is stored.
Object	first() Returns the first element in this list.
ListCell	firstCell() Returns the first cell in this list.
Object	getInfo(ListCell c) Returns the element stored in the given ListCell.
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 to this list.
ListCell	insertBefore(Object o, ListCell refCell) Inserts the given object to this list.
void	insertCellAfter(ListCell cellToInsert, ListCell refCell) Inserts a formerly removed ListCell at the specified position.
void	insertCellBefore(ListCell cellToInsert, ListCell refCell) Inserts a formerly removed ListCell at the specified position.
boolean	isEmpty() Checks whether this list contains elements
Iterator	iterator() Returns an iterator for that list.
Object	last() Returns the last element in this list.
ListCell	lastCell() Returns the last cell in this list.
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 ListCell c.
ListCell	push(Object o) Equivalent to addFirst
boolean	remove(Object o) Removes Object o from this list.
boolean	removeAll(Collection collection) Removes a collection of objects from the list.
Object	removeAt(YCursor c) Removes the element pointed at by the given YCursor.
Object	removeCell(ListCell c) Removes the ListCell c and the element stored in it from this list.
boolean	retainAll(Collection collection) Retains only the nodes in the collection which are contained in the specified collection.
void	reverse() Reverses the sequence of elements in this list.
void	setInfo(ListCell c, Object value) Updates the element residing in the given ListCell.
int	size() Returns the number of elements in this list
void	sort() Sorts the specified array of objects into ascending order, according to the natural ordering of its elements.
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.
ListCell	succCell(ListCell c) Returns the successor cell of ListCell c.
Object[]	toArray() Returns an array representation of this List.
Object[]	toArray(Object[] a) Returns an array containing all of the elements in this list 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, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

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 Collection c.

YList

public YList(Iterator it)

Creates a list that is initialized with the elements provided by the Iterator it.

YList

public YList(YCursor c)

Creates a list that is initialized with the elements provided by the YCursor c.

YList

public YList(YCursor c,
             DataProvider predicate)

Creates a list containing the objects accessible via the given cursor and for which the given data provider returns true upon calling its getBool method.

Parameters:

c - A cursor providing objects that are initially entered into this list.

predicate - a dataprovider that acts as a inclusion predicate for each object accessible from the edge 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 Object o at the head of this list.

Returns:

the ListCell where the Object o is stored.

addLast

public ListCell addLast(Object o)

Inserts Object o at the tail of this list.

Returns:

the ListCell where the Object o is stored.

addLastCell

public void addLastCell(ListCell cell)

Adds a formerly removed ListCell at the tail of this list. Attention: If the ListCell is still part of a list, this 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 at the head of this list. Attention: If the ListCell is still part of a list, this 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 o).

Specified by:

add in interface Collection

addAll

public boolean addAll(Collection collection)

Adds a collection of items to the list.

Specified by:

addAll in interface Collection

addAll

public void addAll(YCursor c)

Appends objects provided by given cursor to this list. The cursor will be moved from its given position to the end. Note that aList.append(aList.cursor()) will induce an infinite recursion.

insertBefore

public ListCell insertBefore(Object o,
                             ListCell refCell)

Inserts the given object to this list. The newly created ListCell will be inserted to this list immediatelly before refCell. If refCell == null the given object is appended to the list.

Parameters:

o - the object to be inserted

refCell - the cell used to reference the position

Returns:

the newly created ListCell, which contains o

insertCellBefore

public void insertCellBefore(ListCell cellToInsert,
                             ListCell refCell)

Inserts a formerly removed ListCell at the specified position. Attention: If the ListCell is still part of a list, this list will be corrupted afterwards.

Parameters:

cellToInsert - A list cell that is not part of any other list.

refCell - A list cell that is contained in this list

insertCellAfter

public void insertCellAfter(ListCell cellToInsert,
                            ListCell refCell)

Inserts a formerly removed ListCell at the specified position. Attention: If the ListCell is still part of a list, this list will be corrupted afterwards.

Parameters:

cellToInsert - A list cell that is not part of any list.

refCell - A list cell that is contained in this list.

insertAfter

public ListCell insertAfter(Object o,
                            ListCell refCell)

Inserts the given object to this list. The newly created ListCell will be inserted to this list immediatelly after refCell. If refCell == null the given object is inserted at the head of the list.

Parameters:

o - the object to be inserted

refCell - the cell used to reference the position

Returns:

the newly created ListCell, which contains o

size

public int size()

Returns the number of elements in this list

Specified by:

size in interface Collection

isEmpty

public boolean isEmpty()

Checks whether this list contains elements

Specified by:

isEmpty in interface Collection

clear

public void clear()

Removes all elements from this list.

Specified by:

clear in interface Collection

first

public Object first()

Returns the first element in 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

peek

public Object peek()

Equivalent to first

last

public Object last()

Returns the last element in 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 in 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.

firstCell

public ListCell firstCell()

Returns the first cell in this list. Precondition: !isEmpty().

lastCell

public ListCell lastCell()

Returns the last cell in this list. Precondition: !isEmpty().

succCell

public ListCell succCell(ListCell c)

Returns the successor cell of ListCell c.

predCell

public ListCell predCell(ListCell c)

Returns the predecessor cell of ListCell c.

cyclicSucc

public ListCell cyclicSucc(ListCell c)

Returns the cyclic successor cell of ListCell c.

cyclicPred

public ListCell cyclicPred(ListCell c)

Returns the cyclic predecessor cell of ListCell c.

getInfo

public Object getInfo(ListCell c)

Returns the element stored in the given ListCell.

setInfo

public void setInfo(ListCell c,
                    Object value)

Updates the element residing in the given ListCell.

remove

public boolean remove(Object o)

Removes Object o from this list. Only the first element for which equality to o holds gets removed. This operation has time complexity O(size()).

Specified by:

remove in interface Collection

removeAll

public boolean removeAll(Collection collection)

Removes a collection of objects from the list.

Specified by:

removeAll in interface Collection

retainAll

public boolean retainAll(Collection collection)

Retains only the nodes in the collection which are contained in the specified collection. This operation has running time O(max(m,n)), were m,n are the sizes of this list and the specified list.

Specified by:

retainAll in interface Collection

removeCell

public Object removeCell(ListCell c)

Removes the ListCell c and the element stored in it from this list. This operation has time complexity O(1). Precondition: c is a cell of this list.

Returns:

element the resided in removed cell

removeAt

public Object removeAt(YCursor c)

Removes the element pointed at by the given YCursor. Precondition:
- contains(c.current())
- c is a YCursor that has been created by a call to this list's cursor() method.

Since:

yFiles-1.4

Returns:

the removed element

cursor

public YCursor cursor()

Returns a cursor for this list. All cursor operations are supported.

iterator

public Iterator iterator()

Returns an iterator for that list. The remove operation is not supported on the iterator.

Specified by:

iterator in interface Collection

contains

public boolean contains(Object o)

Whether or not this list contains the given element. Equality of elements is defined by the isEqual method.

Specified by:

contains in interface Collection

containsAll

public boolean containsAll(Collection collection)

Whether or not this list contains the elements given by a collection. Equality of elements is defined by the isEqual method.

Specified by:

containsAll in interface Collection

findCell

public ListCell findCell(Object o)

Returns the cell where Object o is stored. This operation returns null, if no such cell exists.

toString

public String toString()

Returns a string representation of this List. Right now only the size of the list is returned.

Overrides:

toString in class Object

toArray

public Object[] toArray()

Returns an array representation of this List.

Specified by:

toArray in interface Collection

toArray

public Object[] toArray(Object[] a)

Returns an array containing all of the elements in this list in the correct order. The runtime type of the returned array is that of the specified array. If the list fits 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 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

Throws:

ArrayStoreException - if the runtime type of a is not a supertype of the runtime type of every element in this 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.

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 ListCells by this method.

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

sort

public void sort()

Sorts the specified array of objects into ascending order, according to the natural ordering of its elements. All elements in the array must implement the Comparable interface. Furthermore, all elements in the list must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the list). NOTE: The elements will be assigned to different ListCells 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 will be created by this operation.

Complexity:: O(1)