byucc.jhdl.base.list
Class VectorList

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

All Implemented Interfaces:

List

Direct Known Subclasses:

ArgBlockList, CellList, ConnectionList, InitializeableList, ObservableList, PortRecordList, PropertyList, SimulatorCallbackList, WireList

public class VectorList

extends java.lang.Object

implements List

This is a variation of the original byucc.jhdl.base.list.LinkedList, that provides improved efficiency of memory usage and access time by utilizing java.util.Vector. Since Vector includes capacityIncrement, but only uses it when 'growing' the data array with methods like addElement(), I use (or is that abuse) this field instead of spending more memory on another field to keep track of the current element. VectorLists are ideal for small lists, and favors insert. Large lists, however, are better implemented with LinkedLists, since the cost of resizing the vector and the wasted space are worse than the savings in speed of insert and traversal. Traversal is O(1), insert is between O(1) and O(log n) since every time the list doubles a larger chunk of memory must be allocated and the vector's data relocated, append is O(n log n) by the same reasoning, random access could be added as O(1), inList, deleteCurrent, delete, intersect, and appendList are O(n); but for small lists, almost all of these methods are faster than their counterparts in LinkedList.

Author:

Eric Blake

Constructor Summary

VectorList()

Method Summary

protected void	append(java.lang.Object elt) Appends element to list, for FIFO behavior; not as efficient as insert.
protected void	appendList(VectorList lst) Appends contents of argument to calling list (this), in same order.
boolean	atEnd() Checks if more elements remain for list traversal.
boolean	delete(java.lang.Object elt) Deletes all occurances of element within a list, and reinitializes list.
void	deleteAll() Erases the list.
void	deleteCurrent() Deletes element at current position in list.
int	elementCount() Returns size of list.
boolean	empty() Checks if the list has elements.
protected VectorList	filter(Predicate pred) Filters a list in place, preserving only the elements for which Predicate.accept() returns true.
protected java.lang.Object	getElt() Returns element at current list position, or null if at list end.
void	init() Initializes the list so that the current pointer is on the list head (if the list is built with insert(), this is the most recent insert()).
boolean	inList(java.lang.Object o) Checks if object appears in the list.
protected void	insert(java.lang.Object elt) Inserts element in the list in chronological order, for LIFO behavior.
protected void	insertAfterCurrent(java.lang.Object elt) Inserts element after current element of list, appending if current is at end of list.
protected void	insertBeforeCurrent(java.lang.Object elt) Inserts element before current pointer, appending if at the end of the list.
protected void	insertList(VectorList lst) Inserts contents of argument to calling list (this), in reverse order.
protected VectorList	intersect(VectorList ret_list, VectorList lst) Returns the intersection of argument and calling list (this), without modifying either calling list or argument.
java.util.Iterator	iterator()
protected void	merge(VectorList other_list)
void	next() Advances the current pointer to the next element.
void	prev() Advances the current pointer to the previous element.
int	size() Returns the size of the list
java.lang.String	toString() Prints out a representation of the contents of this list

Methods inherited from class java.lang.Object

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

Constructor Detail

VectorList

public VectorList()

Method Detail

init

public void init()

Initializes the list so that the current pointer is on the list head (if the list is built with insert(), this is the most recent insert()).

Specified by:

init in interface List

Returns:

an Iterator for simultaneous traversal

iterator

public java.util.Iterator iterator()

empty

public final boolean empty()

Checks if the list has elements.

Returns:

true if no elements in list, false if elements exist.

next

public void next()

Advances the current pointer to the next element. Does nothing if already at the end.

Specified by:

next in interface List

prev

public void prev()

Advances the current pointer to the previous element. Does nothing if already at front.

Specified by:

prev in interface List

getElt

protected final java.lang.Object getElt()

Returns element at current list position, or null if at list end. Override this method to allow typed lists.

Returns:

current element.

atEnd

public boolean atEnd()

Checks if more elements remain for list traversal.

Specified by:

atEnd in interface List

Returns:

true if no more elements, false otherwise.

inList

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

Checks if object appears in the list.

Specified by:

inList in interface List

Parameters:

o - object to look for.

Returns:

true if object found.

deleteCurrent

public final void deleteCurrent()

Deletes element at current position in list. The current pointer is left on the next element (or end of the list).

insert

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

Inserts element in the list in chronological order, for LIFO behavior. The current pointer is on the newly inserted element. Override this method to allow typed inserts.

Parameters:

elt - the object to insert.

append

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

Appends element to list, for FIFO behavior; not as efficient as insert. The current pointer is on the newly appended element. Override this method to allow typed appends.

Parameters:

elt - the object to append.

insertAfterCurrent

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

Inserts element after current element of list, appending if current is at end of list. The current pointer is on the newly inserted element. Not as efficient as insert.

Parameters:

elt - the object to insert.

insertBeforeCurrent

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

Inserts element before current pointer, appending if at the end of the list. The current pointer is left on the newly inserted element. Not as efficient as insert.

Parameters:

elt - the object to insert

intersect

protected final VectorList intersect(VectorList ret_list,
                                     VectorList lst)

Returns the intersection of argument and calling list (this), without modifying either calling list or argument. Override for typed List instersection.

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 second list of intersection.

Returns:

a new list with entries for every element on both calling list (this) and lst, in the order they appear on the calling list.

appendList

protected final void appendList(VectorList lst)

Appends contents of argument to calling list (this), in same order. Override for typed List appends.

Parameters:

lst - The list to append, will not be modified.

Returns:

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

insertList

protected final void insertList(VectorList lst)

Inserts contents of argument to calling list (this), in reverse order. Really just a faster way to do for (lst.init(); !lst.atEnd(); lst.next()) this.insert(lst.getElt());. Override for typed List inserts.

Parameters:

lst - The list to insert, will not be modified, but will be read in reverse order.

Returns:

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

deleteAll

public final void deleteAll()

Erases the list.

delete

public final boolean delete(java.lang.Object elt)

Deletes all occurances of element within a list, and reinitializes list.

Parameters:

elt - the element to delete.

Returns:

true if elt was found and removed, false if elt not found to begin with.

elementCount

public final int elementCount()

Returns size of list.

Specified by:

elementCount in interface List

Returns:

list size.

merge

protected void merge(VectorList other_list)

toString

public java.lang.String toString()

Prints out a representation of the contents of this list

Returns:

the string

filter

protected VectorList 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

size

public int size()

Returns the size of the list

Returns:

the current list size