byucc.jhdl.base.list
Class LinkedList

java.lang.Object
  byucc.jhdl.base.list.LinkedList

All Implemented Interfaces:

List

Direct Known Subclasses:

CountingLinkedList, CountingLinkedList, CountingLinkedList, CountingLinkedList, HierarchicalMappedCellList, PlacedCellList, SelectedCellList, TMCellList, TMCellList, TMCellList, TMCellList, XC4000PlacementInfoList

public class LinkedList

extends java.lang.Object

implements List

It is assumed that this class will always be subclassed and that insert and some get function will be defined based on insert() and getElt(). All of the other functions for deletion, iteration, etc., are available for use by anyone accessing the subclass. The intention is to keep the user from putting things in the list that don't belong there and to avoid corruption of the list. I don't try and keep the the user from doing weird things with stuff they get out of the list. In-order traversal is as simple as for(list.init(); !list.atEnd(); list.next()) { ... list.getElt(); ... }. This implements a doubly-linked list, with root pointing backward to tail, last element pointing forward to null, allowing easy append() and atEnd(). Also, LinkedListElt has package-visible fields for faster access. LinkedLists are ideal for large lists, lists built primarily by appends, and lists with frequent deletes using in-order traversal. In-order traversal, insert, append, and deleteCurrent are all O(1), inList, delete, intersect, and appendList are O(n).

Author:

Brad Hutchings, Eric Blake

Constructor Summary

LinkedList()

Method Summary

protected void	append(java.lang.Object elt) Append just puts the new element at the end of the list.
protected void	appendList(LinkedList lst) Modifies calling list by appending contents of argument onto tail end, maintaing the order of elements from the argument.
boolean	atBegin() Returns true if the current pointer is at the beginning of the list during reverse traversal.
boolean	atEnd() Returns true if the current pointer is at the end of the list
boolean	delete(java.lang.Object elt) Deletes all references to elt in the list, and reinitializes list.
void	deleteAll() Deletes all elements of the list
void	deleteCurrent() During iteration this just deletes whatever current is pointing to.
int	elementCount() Count the number of elements in a list.
boolean	empty() Returns true if the list is empty
protected LinkedList	filter(Predicate pred) Filters a list in place, preserving only the elements for which Predicate.accept() returns true.
LinkedListElt	getCurrent() Returns the LinkedListElt that current is pointing to.
protected java.lang.Object	getElt() Returns the current element, or null if beyond list end
void	init() Initializes the list for traversal, so that the current pointer is at the front of the list
void	initReverse() Initialize the list for traversal, so that the current pointer is at the back of the list
boolean	inList(java.lang.Object o) Returns true if the object is currently in the list at least once.
protected void	insert(java.lang.Object elt) Insert just puts the new element at the top of the list, moving everyone else down.
protected void	insertAfterCurrent(java.lang.Object elt) Inserts element after the current one, appending if at the end of the list.
protected void	insertBeforeCurrent(java.lang.Object elt) Inserts element before the current one, appending if at the end of the list.
protected void	insertList(LinkedList lst) Modifies calling list by inserting contents of argument in reverse order at head.
protected LinkedList	intersect(LinkedList ret_list, LinkedList lst) Returns the intersection of two lists, the argument and this.
protected void	merge(LinkedList other_list) Merges other_list onto the end of this.
void	next() Advances the current pointer to the next element; if already at the end does nothing
void	prev() Reverses the current pointer to the prior element; if already at the front does nothing
java.lang.String	toString() Provides a String representation for use in debug.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LinkedList

public LinkedList()

Method Detail

init

public final void init()

Initializes the list for traversal, so that the current pointer is at the front of the list

Specified by:

init in interface List

Returns:

an Iterator for simultaneous traversal

initReverse

public final void initReverse()

Initialize the list for traversal, so that the current pointer is at the back of the list

empty

public final boolean empty()

Returns true if the list is empty

Returns:

true if empty

next

public final void next()

Advances the current pointer to the next element; if already at the end does nothing

Specified by:

next in interface List

prev

public final void prev()

Reverses the current pointer to the prior element; if already at the front does nothing

Specified by:

prev in interface List

getElt

protected java.lang.Object getElt()

Returns the current element, or null if beyond list end

Returns:

the current element

atEnd

public final boolean atEnd()

Returns true if the current pointer is at the end of the list

Specified by:

atEnd in interface List

Returns:

true if at the end

atBegin

public final boolean atBegin()

Returns true if the current pointer is at the beginning of the list during reverse traversal.

Returns:

true if at the beginning

inList

public final boolean inList(java.lang.Object o)

Returns true if the object is currently in the list at least once.

Specified by:

inList in interface List

Returns:

true if the object was found

deleteCurrent

public final void deleteCurrent()

During iteration this just deletes whatever current is pointing to. The current pointer is moved to the next element in the list (or the list end).

insert

protected final void insert(java.lang.Object elt)

Insert just puts the new element at the top of the list, moving everyone else down. The current pointer is on the newly inserted element.

Parameters:

elt - the object to insert

append

protected final void append(java.lang.Object elt)

Append just puts the new element at the end of the list. The current pointer is on the newly appended element.

Parameters:

elt - the object to append

insertAfterCurrent

protected final void insertAfterCurrent(java.lang.Object elt)

Inserts element after the current one, appending if at the end of the list. The current pointer is on the newly inserted element.

Parameters:

elt - the object to insert

insertBeforeCurrent

protected final void insertBeforeCurrent(java.lang.Object elt)

Inserts element before the current one, appending if at the end of the list. The current pointer is on the newly inserted element.

Parameters:

elt - the object to insert

intersect

protected LinkedList intersect(LinkedList ret_list,
                               LinkedList lst)

Returns the intersection of two lists, the argument and this.

Parameters:

ret_list - The empty list that will be returned with the result (must be passed a list, because reflection cannot always generate the correct list type)

lst - The list to check along with bound list (this).

Returns:

A new list containing elements only on both this and lst.

appendList

protected void appendList(LinkedList lst)

Modifies calling list by appending contents of argument onto tail end, maintaing the order of elements from the argument. The appended portion is a clone; so the argument list is not modified.

Parameters:

lst - The list to grab elements from, unmodified.

Returns:

Nothing is returned, but calling list has elements appended to it.

insertList

protected void insertList(LinkedList lst)

Modifies calling list by inserting contents of argument in reverse order at head. Slightly faster than the counterpart of for (lst.init(); !lst.atEnd(); lst.next()) this.insert(lst.getElt());.

Parameters:

lst - The list to insert, unmodified, but read in reverse order.

Returns:

Nothing is returned, but calling list (this) is modified.

deleteAll

public void deleteAll()

Deletes all elements of the list

delete

public boolean delete(java.lang.Object elt)

Deletes all references to elt in the list, and reinitializes list.

Parameters:

elt - the element to delete

Returns:

true if something was deleted

elementCount

public int elementCount()

Count the number of elements in a list.

Specified by:

elementCount in interface List

Returns:

the number of elements in the list.

getCurrent

public LinkedListElt getCurrent()

Returns the LinkedListElt that current is pointing to.

Returns:

current.

merge

protected void merge(LinkedList other_list)

Merges other_list onto the end of this.

Parameters:

other_list - list to merge

toString

public java.lang.String toString()

Provides a String representation for use in debug. Just calls toString on all the elements in the list. Restore the state of the string before this is called so calling it in the debugger won't cause problems.

Returns:

a String representation of the list.

filter

protected LinkedList filter(Predicate pred)

Filters a list in place, preserving only the elements for which Predicate.accept() returns true. Speeds up processes like delete by traversing the list only once.

Parameters:

pred - the predicate for determining list membership

Returns:

this list, filtered so that only elements accepted by the predicate remain