Package ptolemy.kernel.util

Class CrossRefList

  • public final class CrossRefList
extends java.lang.Object
    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$
    Author:
    Geroncio Galicia, Contributor: Edward A. Lee
    Pt.AcceptedRating:
    Green (bart)
    Pt.ProposedRating:
    Green (eal)

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected class  CrossRefList.CrossRef
      Objects of this type form the elements of the list.

    • Constructor Summary

      Constructors 
      Constructor Description
      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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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

    • 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).