ptolemy.kernel.util
Class CrossRefList

java.lang.Object
  ptolemy.kernel.util.CrossRefList

All Implemented Interfaces:

java.io.Serializable

public final class CrossRefList
extends java.lang.Object
implements java.io.Serializable

CrossRefList is a list that maintains pointers to other CrossRefLists. CrossRefList is meant to be used to keep track of links between ports and relations in Ptolemy II. It is a highly specialized form of a list. An instance has a container (an Object), which is immutable, meaning that the container cannot be changed after the instance is constructed. CrossRefList enumerators and query methods do not return references to other CrossRefLists; instead, references to the containers of the CrossRefLists (which can be any Object) are returned.

For efficiency, CrossRefList maintains a list of pairwise links between Objects (CrossRefs). That is, each member of a set of objects has a list of references to other members of the set, and each reference has a similar list that contains a corresponding back reference. Each reference list is an instance of . The class is used as if it were a simple list of references to objects, but it ensures the symmetry of the references, and supports efficient removal of links. Removing a reference in one list automatically updates N back-references in O(N) time, independent of the sizes of the cross-referenced lists.

It is possible to create links at specified points in the list (called the index number). This may result in gaps in the list at lower index numbers. Gaps are representing by null in an enumeration of the list.

Since:

Ptolemy II 0.2

Version:

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

Author:

Geroncio Galicia, Contributor: Edward A. Lee

See Also:

Serialized Form

Accepted Rating:

Green (bart)

Proposed Rating:

Green (eal)

Nested Class Summary

protected class	CrossRefList.CrossRef Objects of this type form the elements of the list.
private class	CrossRefList.CrossRefEnumeration Enumerate the objects pointed to by the list.

Field Summary

private java.lang.Object	_container
private CrossRefList.CrossRef	_headNode
private CrossRefList.CrossRef	_lastNode
private long	_listVersion
private int	_size

Constructor Summary

CrossRefList(java.lang.Object container)
Construct a list with the specified container.

CrossRefList(java.lang.Object container, CrossRefList originalList)
Create a new CrossRefList that is linked to the same CrossRefLists as the original CrossRefList except that this new one has a new container.

Method Summary

java.lang.Object	first() Return the first container linked to this list, or null if the list is empty.
java.lang.Object	get(int index) Get the container at the specified index.
java.util.Enumeration	getContainers() Enumerate the containers linked to this list.
void	insertLink(int index, CrossRefList farList) Insert a link to the specified CrossRefList (farList) at the specified position (index).
boolean	isLinked(java.lang.Object obj) Return true if the specified container is linked to this list.
void	link(CrossRefList farList) Link this list to a different CrossRefList (farList).
int	size() Return size of this list.
void	unlink(int index) Delete the link at the specified index.
void	unlink(java.lang.Object obj) Delete all links to the specified container.
void	unlinkAll() Delete all cross references.

Methods inherited from class java.lang.Object

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

Field Detail

_listVersion

private long _listVersion

_size

private int _size

_headNode

private CrossRefList.CrossRef _headNode

_lastNode

private CrossRefList.CrossRef _lastNode

_container

private java.lang.Object _container

Constructor Detail

CrossRefList

public CrossRefList(java.lang.Object container)

Construct a list with the specified container. The container is immutable (it cannot be changed). If the argument is null, then a null pointer exception will result (eventually).

Parameters:

container - The container of the object to be constructed.

CrossRefList

public CrossRefList(java.lang.Object container,
                    CrossRefList originalList)

Create a new CrossRefList that is linked to the same CrossRefLists as the original CrossRefList except that this new one has a new container. This method synchronizes on the original list. Note that this behaves like a copy constructor, except that the remote list is affected so that it will now point back to both lists. If either argument is null, then a null pointer exception will be thrown.

Parameters:

container - The container of the object to be constructed.

originalList - The model to copy.

Method Detail

first

public java.lang.Object first()

Return the first container linked to this list, or null if the list is empty. Note that we may also return null if the list is not empty, but the first link happens to not point anywhere. Thus, do not use this method to check to see whether the list is empty. Time complexity: O(1).

Returns:

The first entry, or null if there is none.

get

public java.lang.Object get(int index)

Get the container at the specified index. If there is no such container, return null. Indices begin with 0.

Parameters:

index - The index of the container to return.

Returns:

The container at the specified index.

getContainers

public java.util.Enumeration getContainers()

Enumerate the containers linked to this list. The enumeration returns the container object itself and not the CrossRefList instance in this list that the object owns or contains. Note that an object may be enumerated more than once if more than one link to it has been established. Also, there may be elements in the list that are null, indicating that nothing is linked at that index position. Time complexity: O(1). NOTE: This method is not well named, since it returns the containers of other instances of CrossRefList that are linked to this one, and not the container of this one.

Returns:

An enumeration of remote referenced objects.

insertLink

public void insertLink(int index,
                       CrossRefList farList)
                throws IllegalActionException

Insert a link to the specified CrossRefList (farList) at the specified position (index). The index can be any non-negative integer. If the index is greater than or equal to the size of this list, then null links are created to make the list big enough. If there are already links with indices equal to or larger than index, then their indices become one larger. This method creates a back reference in the far list, unless the farList argument is null. That back reference is appended to the end of the far list.

Note that this method specifies the index on the local reference list, but not on the remote reference list. There is no mechanism provided to specify both indices. This is because this class is used to linked ports to relations, and indices of links have no meaning in relations. Thus, there is no need for a richer interface.

Note that this method does not synchronize on the remote object. Thus, this method should be called within a write-synchronization of the common workspace.

Parameters:

index - The position in the list at which to insert this link.

farList - The cross reference list contained by the remote object.

Throws:

IllegalActionException - If this list tries linking to itself.

isLinked

public boolean isLinked(java.lang.Object obj)

Return true if the specified container is linked to this list. If no container is passed or if this CrossRefList has no links then just return. Time complexity: O(n).

Parameters:

obj - An object that might be referenced.

Returns:

A boolean indicating whether the object is referenced.

link

public void link(CrossRefList farList)
          throws IllegalActionException

Link this list to a different CrossRefList (farList). The link is appended at the end of the list. This action additionally creates a back-reference in the far list, also at the end, unless the farList argument is null, in which case the new link is a null link. Redundant entries are allowed; that is, you can link more than once to the same remote list. Note that this method does not synchronize on the remote object. Thus, this method should be called within a write-synchronization of the common workspace. Time complexity: O(1).

Parameters:

farList - The cross reference list contained by the remote object.

Throws:

IllegalActionException - If this list tries linking to itself.

size

public int size()

Return size of this list. Time complexity: O(1).

Returns:

A non-negative integer.

unlink

public void unlink(int index)

Delete the link at the specified index. If there is no such link, ignore. Back references are likewise updated. Note that the index numbers of any links at higher indices will decrease by one. Time complexity: O(n).

Parameters:

index - The index of the link to delete.

unlink

public void unlink(java.lang.Object obj)

Delete all links to the specified container. If there is no such link, ignore. Back references are likewise updated. In the case of redundant links this deletes the first link to that container. Time complexity: O(n).

Parameters:

obj - The object to delete.

unlinkAll

public void unlinkAll()

Delete all cross references. Time complexity: O(n).