ptolemy.graph
Class LabeledList

java.lang.Object
  ptolemy.graph.LabeledList

All Implemented Interfaces:

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

Direct Known Subclasses:

ElementList

public class LabeledList
extends java.lang.Object
implements java.util.List

A list of unique objects (elements) with a mapping from the elements into consecutive integer labels. The labels are consecutive integers between 0 and N-1 inclusive, where N is the total number of elements in the list. This list features O(1) list insertion, O(1) testing for membership in the list, O(1) access of a list element from its associated label, and O(1) access of a label from its corresponding element. Removal from the list is, however, an O(1) operation. The element labels are useful, for example, in creating mappings from list elements into elements of arbitrary arrays. More generally, element labels can be used to maintain arbitrary m-dimensional matrices that are indexed by the list elements (via the associated element labels).

Element labels maintain their consistency (remain constant) during periods when no elements are removed from the list. When elements are removed, the labels assigned to the remaining elements may change (see remove(Object) for details).

Elements themselves must be non-null and distinct, as determined by the equals method.

This class supports all required operations of the List interface, except for the List.subList(int, int) operation, which results in an UnsupportedOperationException.

Since:

Ptolemy II 2.0

Version:

$Id: LabeledList.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Shuvra S. Bhattacharyya

Accepted Rating:

Red (cxh)

Proposed Rating:

Red (cxh)

Field Summary

private java.util.ArrayList	_elements The elements that are associated with this list.
private java.util.HashMap	_labels Translation from list element to label.

Constructor Summary

LabeledList()
Construct an empty list.

LabeledList(int size)
Construct an empty list with enough storage allocated to hold the specified number of elements.

Method Summary

private java.lang.String	_elementDump(java.lang.Object element) Return a dump of a list element that is suitable for inclusion in an error message.
private void	_labelElements(int startIndex) Fill in the labels map with the appropriate indices of the array list, starting at a specified index.
void	add(int index, java.lang.Object element) Unsupported optional method of the List interface.
boolean	add(java.lang.Object element) Add an element to the list.
boolean	addAll(java.util.Collection collection) Unsupported optional method of the List interface.
boolean	addAll(int index, java.util.Collection collection) Unsupported optional method of the List interface.
void	clear() Clear all of the elements in this list.
boolean	contains(java.lang.Object object) Return true if the specified object is an element of this list.
boolean	containsAll(java.util.Collection collection) Returns true if this list contains all of the elements of the specified collection.
boolean	equals(java.lang.Object object) Compares the specified object with this list for equality.
java.lang.Object	get(int label) Return the element that has a specified label.
int	hashCode() Return the hash code value for this list.
int	indexOf(java.lang.Object element) Return the label in this list of the specified element; return -1 if the element is null or this list does not contain the element.
boolean	isEmpty() Returns true if this list contains no elements.
java.util.Iterator	iterator() Return an iterator over the elements in the list.
int	label(java.lang.Object element) Return the label of the specified element.
int	lastIndexOf(java.lang.Object element) 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() Return a list iterator over the elements in the list.
java.util.ListIterator	listIterator(int index) Return a list iterator over the elements in this list, starting at a specified position in the list.
java.lang.Object	remove(int label) Remove and return an element with a specified label from this list.
boolean	remove(java.lang.Object element) Remove an element from this list.
boolean	removeAll(java.util.Collection collection) Unsupported optional method of the List interface.
boolean	retainAll(java.util.Collection collection) Unsupported optional method of the List interface.
java.lang.Object	set(int index, java.lang.Object element) Unsupported optional method of the List interface.
int	size() Return the number of elements in this list.
java.util.List	subList(int fromIndex, int toIndex) Unsupported method of the List interface.
java.lang.Object[]	toArray() Returns an array containing all of the elements in this list in proper sequence.
java.lang.Object[]	toArray(java.lang.Object[] array) Returns an array containing all of the elements in this list in proper sequence; the runtime type of the returned array is that of the specified array.
java.lang.String	toString() Return a string representation of this list with elements separated by new lines, and element labels omitted from the representation.
java.lang.String	toString(java.lang.String delimiter, boolean includeLabels) Return a string representation of this list, given a delimiter for separating successive elements, and a flag that indicates whether element labels should be included in the string.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

_elements

private java.util.ArrayList _elements

The elements that are associated with this list.

_labels

private java.util.HashMap _labels

Translation from list element to label. The keys of this HashMap are list elements (instances of Object), and the values are the corresponding element labels (instances of Integer). This translation can also be done with indexOf(), but a HashMap is faster.

Constructor Detail

LabeledList

public LabeledList()

Construct an empty list.

LabeledList

public LabeledList(int size)

Construct an empty list with enough storage allocated to hold the specified number of elements. Memory management is more efficient with this constructor (assuming the number of elements is known).

Parameters:

size - The number of elements.

Method Detail

add

public boolean add(java.lang.Object element)

Add an element to the list. The label assigned to this element will be equal to the number of elements in the list prior to insertion of the element.

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.List

Parameters:

element - The element to insert.

Returns:

True unconditionally (assuming an exception does not occur).

Throws:

java.lang.IllegalArgumentException - If the specified element is null, or if it already exists in the list.

add

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

Unsupported optional method of the List interface.

Specified by:

add in interface java.util.List

Parameters:

index - Unused.

element - Unused.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

addAll

public boolean addAll(java.util.Collection collection)

Unsupported optional method of the List interface.

Specified by:

addAll in interface java.util.Collection

Specified by:

addAll in interface java.util.List

Parameters:

collection - Unused.

Returns:

never returns.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

addAll

public boolean addAll(int index,
                      java.util.Collection collection)

Unsupported optional method of the List interface.

Specified by:

addAll in interface java.util.List

Parameters:

index - Unused.

collection - Unused.

Returns:

never returns.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

clear

public void clear()

Clear all of the elements in this list.

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

contains

public boolean contains(java.lang.Object object)

Return true if the specified object is an element of this list.

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.List

Parameters:

object - The specified object.

Returns:

True if the specified object is an element of this list; false if the object is null or is not in the list.

containsAll

public boolean containsAll(java.util.Collection collection)

Returns true if this list contains all of the elements of the specified collection.

Specified by:

containsAll in interface java.util.Collection

Specified by:

containsAll in interface java.util.List

Parameters:

collection - The specified collection.

Returns:

True if this list contains all of the elements of the specified collection.

equals

public boolean equals(java.lang.Object object)

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

Parameters:

object - The object.

Returns:

True if the specified object is equal to this list.

get

public java.lang.Object get(int label)

Return the element that has a specified label.

Specified by:

get in interface java.util.List

Parameters:

label - The label.

Returns:

The element.

Throws:

java.lang.IndexOutOfBoundsException - If there is no element that has the specified label.

hashCode

public int hashCode()

Return 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

Returns:

The hash code value.

indexOf

public int indexOf(java.lang.Object element)

Return the label in this list of the specified element; return -1 if the element is null or this list does not contain the element.

Specified by:

indexOf in interface java.util.List

Parameters:

element - The element.

Returns:

The label of the element.

See Also:

label(Object)

isEmpty

public boolean isEmpty()

Returns true if this list contains no elements.

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface java.util.List

Returns:

True if this list contains no elements.

iterator

public java.util.Iterator iterator()

Return an iterator over the elements in the list. The iterator returned is safe in that it cannot be used to modify the list. FIXME: what happens when you try to modify the list.

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.List

Returns:

An iterator over the elements in the list;

label

public final int label(java.lang.Object element)

Return the label of the specified element.

Parameters:

element - The specified element.

Returns:

The corresponding label.

Throws:

java.lang.IllegalArgumentException - If the specified element is not in this list.

java.lang.NullPointerException - If the specified element is null.

See Also:

indexOf(Object)

lastIndexOf

public int lastIndexOf(java.lang.Object element)

Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element. Since elements in a labeled list are distinct, this is the same as indexOf(Object), and is maintained only for conformance with the list interface.

Specified by:

lastIndexOf in interface java.util.List

listIterator

public java.util.ListIterator listIterator()

Return a list iterator over the elements in the list. The iterator returned is safe in that it cannot be used to modify the list.

Specified by:

listIterator in interface java.util.List

Returns:

A list iterator over the elements in the list;

listIterator

public java.util.ListIterator listIterator(int index)

Return a list iterator over the elements in this list, starting at a specified position in the list. The iterator returned is safe in that it cannot be used to modify the list.

Specified by:

listIterator in interface java.util.List

Parameters:

index - The specified starting position.

Returns:

A list iterator over the elements in the list;

remove

public boolean remove(java.lang.Object element)

Remove an element from this list. Elements that have higher-valued labels than this element will have their labels reduced in value by one. All other element labels will remain unchanged. If the specified element is not in the list, the list will be unchanged. FIXME: leave indices indeterminate after removal.

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.List

Parameters:

element - The element.

Returns:

True If this list contained the element.

remove

public java.lang.Object remove(int label)

Remove and return an element with a specified label from this list. Elements that have higher-valued labels than this element will have their labels reduced in value by one. All other element labels will remain unchanged.

Specified by:

remove in interface java.util.List

Parameters:

label - The specified label.

Returns:

The element that is removed.

Throws:

java.lang.IndexOutOfBoundsException - If there is no element with the specified label.

removeAll

public boolean removeAll(java.util.Collection collection)

Unsupported optional method of the List interface.

Specified by:

removeAll in interface java.util.Collection

Specified by:

removeAll in interface java.util.List

Parameters:

collection - Unused.

Returns:

never returns.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

retainAll

public boolean retainAll(java.util.Collection collection)

Unsupported optional method of the List interface.

Specified by:

retainAll in interface java.util.Collection

Specified by:

retainAll in interface java.util.List

Parameters:

collection - Unused.

Returns:

never returns.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

set

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

Unsupported optional method of the List interface.

Specified by:

set in interface java.util.List

Parameters:

index - Unused.

element - Unused.

Returns:

never returns.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

size

public int size()

Return the number of elements in this list.

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.List

Returns:

The number of elements.

subList

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

Unsupported method of the List interface.

Specified by:

subList in interface java.util.List

Parameters:

fromIndex - Unused.

toIndex - Unused.

Returns:

never returns.

Throws:

java.lang.UnsupportedOperationException - Always thrown.

toArray

public java.lang.Object[] toArray()

Returns an array containing all of the elements in this list in proper sequence.

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

Returns:

An array containing all of the elements in this list.

toArray

public java.lang.Object[] toArray(java.lang.Object[] array)

Returns an array containing all of the elements in this list in proper sequence; the runtime type of the returned array is that of the specified array.

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

Parameters:

array - The specified array.

Returns:

An array containing all of the elements in this list.

toString

public java.lang.String toString(java.lang.String delimiter,
                                 boolean includeLabels)

Return a string representation of this list, given a delimiter for separating successive elements, and a flag that indicates whether element labels should be included in the string. The string representation is constructed by concatenating the string representations of the individual elements, according to the order of their labels. The element strings are separated by the specified delimiter, and are optionally preceded by the associated labels.

Parameters:

delimiter - The delimiter that separates elements in the generated string.

includeLabels - If this is true, then precede each element with its label (followed by a colon and space) in the generated string; otherwise, omit the labels.

Returns:

A string representation of this list.

toString

public java.lang.String toString()

Return a string representation of this list with elements separated by new lines, and element labels omitted from the representation. The string representation is constructed by the concatenating string representations of the individual elements, according to the order of their labels. The element strings are separated by newlines. The element labels are not included in the string representation.

Overrides:

toString in class java.lang.Object

Returns:

A string representation of this list.

_elementDump

private java.lang.String _elementDump(java.lang.Object element)

Return a dump of a list element that is suitable for inclusion in an error message.

_labelElements

private void _labelElements(int startIndex)

Fill in the labels map with the appropriate indices of the array list, starting at a specified index.