net.walend.digraph.path
Class AbstractListGEPath

java.lang.Object
  |
  +--net.walend.digraph.path.AbstractListGEPath

All Implemented Interfaces:

Digraph, GEDigraph, GEPath, HasState, Path, java.io.Serializable

Direct Known Subclasses:

ListGEPath, MutableListGEPath

public abstract class AbstractListGEPath

extends java.lang.Object

implements GEPath, java.io.Serializable

This abstract class implements the GEPath interface using a List of nodes. It implements all the methods in MutableGEPath as protected, for easy subclassing. By default, it uses an ArrayList, but one constructor allows you to supply the Lists.

Since:

20011023

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

private class	AbstractListGEPath.EdgeCountToken
protected class	AbstractListGEPath.ListEdgeNodeIterator

Field Summary

private static int	DEFAULTCAPACITY
private GEDigraph	digraph
private int	modCount
private java.util.List	nodes

Fields inherited from interface net.walend.digraph.GEDigraph

EMPTY

Constructor Summary

protected	AbstractListGEPath(GEDigraph digraph, java.util.List nodeList) Creates a new path on digraph that has only node in it, using nodeList.
protected	AbstractListGEPath(GEDigraph digraph, java.lang.Object node) Creates a new path on digraph that has only node in it with DEFAULTCAPACITY of 7.
protected	AbstractListGEPath(GEDigraph digraph, java.lang.Object node, int nodeCapacity) Creates a new path on digraph that has only node in it, with a capacity nodeCapacity.
protected	AbstractListGEPath(GEDigraph digraph, java.lang.Object node, java.util.List nodeList) Creates a new path on digraph that has only node in it, using nodeList.
protected	AbstractListGEPath(GEPath path) Create a new path that is a copy of path.
protected	AbstractListGEPath(GEPath path, java.util.List nodeList) Create a new path that is a copy of path, using nodeList.

Method Summary

protected void	addToHead(java.lang.Object node) Adds a node and edge to the beginning of the path.
protected void	addToTail(java.lang.Object node) Adds an edge and node to the end of the path.
private void	checkIndices(int startNodeIndex, int endNodeIndex)
private void	checkSubpathIndices(int startNodeIndex, int endNodeIndex, java.lang.Object startNode, java.lang.Object endNode)
protected void	checkValid() Throw an InvalidPathException if anything is wrong.
protected void	chopList(java.util.List victim, int fromIndex, int toIndex)
boolean	containsEdge(java.lang.Object fromNode, java.lang.Object toNode) Returns true if the digraph contains any edge from fromNode to toNode
boolean	containsGEDigraph(GEDigraph digraph) Returns true if digraph is a subgraph of this GEDigraph.
boolean	containsNode(java.lang.Object node)
boolean	containsNodes(java.util.Set nodes)
int	countInboundEdges(java.lang.Object node) This implementation takes linear time.
int	countOutboundEdges(java.lang.Object node) This implementation takes linear time.
int	edgeCount() This method is wildly inefficient.
EdgeNodeIterator	edgeNodeIterator() Returns an iterator that iterates across pairs of nodes that make edges.
java.util.Set	getFromNodes(java.lang.Object node) Returns the set of nodes that can reach this node by crossing one edge.
java.lang.Object	getHead()
int	getIndexOfNode(java.lang.Object node)
int	getLastIndexOfNode(java.lang.Object node)
java.lang.Object	getNodeAtIndex(int index)
java.util.List	getNodeList() Returns an immutable list of the nodes.
java.util.Set	getNodes()
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
GEPath	getSubpath(int startNodeIndex, int endNodeIndex) Returns a new path, between startNodeIndex and endNodeIndex, inclusive.
GEPath	getSubpathFirst(java.lang.Object startNode, java.lang.Object endNode) Returns a new path, between the first occurence of startNode and the first occurence of endNode, inclusive.
GEPath	getSubpathFirstToLast(java.lang.Object startNode, java.lang.Object endNode) Returns a new path, between the first occurence of startNode and the last occurence of endNode, inclusive.
GEPath	getSubpathLast(java.lang.Object startNode, java.lang.Object endNode) Returns a new path, between the last occurence of startNode and the last occurence of endNode, inclusive.
GEPath	getSubpathLastToFirst(java.lang.Object startNode, java.lang.Object endNode) Returns a new path, between the last occurence of startNode and the first occurence of endNode, inclusive.
GEDigraph	getSupergraph() Returns the supergraph.
java.lang.Object	getTail()
java.util.Set	getToNodes(java.lang.Object node) Returns the set of nodes that can be reached from this node by crossing one edge.
protected void	graftToHead(GEPath path) Adds a path to the beginning of this path.
protected void	graftToTail(GEPath path) Adds a path to the end of this path.
GEDigraph	intersectWithGEDigraph(GEDigraph digraph) Returns a new digraph that is the intersection of this with digraph.
boolean	isEdgeFree() Returns true if this GEDigraph has no edges.
boolean	isEmpty()
int	nodeCount() This method is not terribly efficient.
java.util.Iterator	nodeIterator() Implementations should explicitly state how they interpret nodeIterator()'s remove method.
int	pathEdgeCount() Returns the number of edges in the path, including repeats.
EdgeNodeIterator	pathEdgeNodeIterator() Since ListGEPath is immutable, edgeIterator()'s remove() method throws an UnsupportedOperationException.
int	pathNodeCount() Returns the number of nodes in the path, including repeates.
java.util.Iterator	pathNodeIterator() Since ListGEPath is immutable, nodeIterator()'s remove() method throws an UnsupportedOperationException.
protected GEPath	pruneHead(int index) Removes from the head to the edge at index.
GEPath	pruneHeadFromFirst(java.lang.Object node) Removes from the head to the first occurance of node.
GEPath	pruneHeadFromLast(java.lang.Object node) Removes from the head to the last occurance of node.
protected GEPath	pruneTail(int index) Removes from the edge at index to the tail.
GEPath	pruneTailFromFirst(java.lang.Object node) Removes from the first occurance of node to the tail.
GEPath	pruneTailFromLast(java.lang.Object node) Removes from the last occurance of node to the tail.
protected void	removeHead() Removes the head node from the path.
protected void	removeTail() Removes the tail node from the path.
boolean	sameGEDigraphAs(GEDigraph digraph) Returns true if digraph is the same as this, and all their contents have the same state.
boolean	sameGEPathAs(GEPath path) Returns true if path is the same path as this, on the same digraph.
boolean	sameStateAs(HasState victim) If two HasStates have the same internal state, return true.
protected GEPath	splice(GEPath path, int startNodeIndex, int endNodeIndex) Splices in path between the startNodeIndex and endNodeIndex.
protected GEPath	spliceFirst(GEPath path) Splices in path between the first occurence of path's head and the first occurence of path's tail.
protected GEPath	spliceFirstToLast(GEPath path) Splices in path between the first occurence of path's head and the last occurence of path's tail.
protected GEPath	spliceLast(GEPath path) Splices in path between the last occurence of path's head and the last occurence of path's tail.
protected GEPath	spliceLastToFirst(GEPath path) Splices in path between the last occurence of path's head and the first occurence of path's tail.
java.lang.String	toString()
GEDigraph	unionGEDigraph(GEDigraph digraph) Returns a new digraph that is the union of this with digraph.
boolean	valid() Returns true if this path is still a subgraph of its supergraph

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULTCAPACITY

private static final int DEFAULTCAPACITY

See Also:

Constant Field Values

nodes

private java.util.List nodes

modCount

private transient volatile int modCount

digraph

private GEDigraph digraph

Constructor Detail

AbstractListGEPath

protected AbstractListGEPath(GEPath path)

Create a new path that is a copy of path.

Throws:

InvalidPathException - if the path is not valid.

AbstractListGEPath

protected AbstractListGEPath(GEPath path,
                             java.util.List nodeList)

Create a new path that is a copy of path, using nodeList. This constructor clear()s the list before using it.

Throws:

InvalidPathException - if the path is not valid.

AbstractListGEPath

protected AbstractListGEPath(GEDigraph digraph,
                             java.lang.Object node)

Creates a new path on digraph that has only node in it with DEFAULTCAPACITY of 7.

Throws:

InvalidPathException - if the path is not valid (because the node isn't in the supergraph).

AbstractListGEPath

protected AbstractListGEPath(GEDigraph digraph,
                             java.lang.Object node,
                             int nodeCapacity)

Creates a new path on digraph that has only node in it, with a capacity nodeCapacity.

Throws:

InvalidPathException - if the path is not valid (because the node isn't in the supergraph).

AbstractListGEPath

protected AbstractListGEPath(GEDigraph digraph,
                             java.lang.Object node,
                             java.util.List nodeList)

Creates a new path on digraph that has only node in it, using nodeList. This constructor clear()s both lists before using them.

Throws:

InvalidPathException - if the path is not valid (because the node isn't in the supergraph).

AbstractListGEPath

protected AbstractListGEPath(GEDigraph digraph,
                             java.util.List nodeList)

Creates a new path on digraph that has only node in it, using nodeList. This constructor uses nodeList as the list of nodes.

Throws:

InvalidPathException - if the path is not valid.

Method Detail

checkValid

protected void checkValid()

Throw an InvalidPathException if anything is wrong.

nodeCount

public int nodeCount()

This method is not terribly efficient. It puts the nodes into a Set, then returns that Set's size.

Specified by:

nodeCount in interface Digraph

edgeCount

public int edgeCount()

This method is wildly inefficient. It scans the edges, and creates objects to stuff in a Set, then gets the size of the set.

Specified by:

edgeCount in interface Digraph

pathNodeCount

public int pathNodeCount()

Returns the number of nodes in the path, including repeates.

Specified by:

pathNodeCount in interface Path

pathEdgeCount

public int pathEdgeCount()

Returns the number of edges in the path, including repeats.

Specified by:

pathEdgeCount in interface Path

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Digraph

containsNode

public boolean containsNode(java.lang.Object node)

Specified by:

containsNode in interface Digraph

containsEdge

public boolean containsEdge(java.lang.Object fromNode,
                            java.lang.Object toNode)
                     throws NodeMissingException

Returns true if the digraph contains any edge from fromNode to toNode

Specified by:

containsEdge in interface Digraph

Throws:

NodeMissingException - if either node is missing from the digraph.

countInboundEdges

public int countInboundEdges(java.lang.Object node)
                      throws NodeMissingException

This implementation takes linear time. If you know the path is acyclic, override it to be constant time.

Specified by:

countInboundEdges in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

countOutboundEdges

public int countOutboundEdges(java.lang.Object node)
                       throws NodeMissingException

This implementation takes linear time. If you know the path is acyclic, override it to be constant time.

Specified by:

countOutboundEdges in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

getFromNodes

public java.util.Set getFromNodes(java.lang.Object node)
                           throws NodeMissingException

Returns the set of nodes that can reach this node by crossing one edge.

If you know this path is acyclic, override this method with one that takes constant time.

Specified by:

getFromNodes in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

getToNodes

public java.util.Set getToNodes(java.lang.Object node)
                         throws NodeMissingException

Returns the set of nodes that can be reached from this node by crossing one edge.

If you know this path is acyclic, override this method with one that takes constant time.

Specified by:

getToNodes in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

nodeIterator

public java.util.Iterator nodeIterator()

Description copied from interface: Digraph

Implementations should explicitly state how they interpret nodeIterator()'s remove method. It should either throw an UnsupportedOperationException or cause a hidden side effects of removing edges.

Specified by:

nodeIterator in interface Digraph

pathNodeIterator

public java.util.Iterator pathNodeIterator()

Since ListGEPath is immutable, nodeIterator()'s remove() method throws an UnsupportedOperationException.

Specified by:

pathNodeIterator in interface Path

pathEdgeNodeIterator

public EdgeNodeIterator pathEdgeNodeIterator()

Since ListGEPath is immutable, edgeIterator()'s remove() method throws an UnsupportedOperationException.

Specified by:

pathEdgeNodeIterator in interface Path

edgeNodeIterator

public EdgeNodeIterator edgeNodeIterator()

Description copied from interface: Digraph

Returns an iterator that iterates across pairs of nodes that make edges.

Specified by:

edgeNodeIterator in interface Digraph

getNodes

public java.util.Set getNodes()

Specified by:

getNodes in interface Digraph

isEdgeFree

public boolean isEdgeFree()

Returns true if this GEDigraph has no edges.

Specified by:

isEdgeFree in interface Digraph

containsNodes

public boolean containsNodes(java.util.Set nodes)

Specified by:

containsNodes in interface Digraph

containsGEDigraph

public boolean containsGEDigraph(GEDigraph digraph)

Returns true if digraph is a subgraph of this GEDigraph.

Specified by:

containsGEDigraph in interface GEDigraph

sameGEDigraphAs

public boolean sameGEDigraphAs(GEDigraph digraph)

Returns true if digraph is the same as this, and all their contents have the same state.

Specified by:

sameGEDigraphAs in interface GEDigraph

intersectWithGEDigraph

public GEDigraph intersectWithGEDigraph(GEDigraph digraph)

Returns a new digraph that is the intersection of this with digraph. Implementations should generally return the same implementation of GEDigraph as they have themselves.

Specified by:

intersectWithGEDigraph in interface GEDigraph

unionGEDigraph

public GEDigraph unionGEDigraph(GEDigraph digraph)

Returns a new digraph that is the union of this with digraph. Implementations should generally return the same implementation of GEDigraph as they are themselves. If the digraphs contain conflicting edges, then (unless you have a better rule) let digraph's edge win out.

Specified by:

unionGEDigraph in interface GEDigraph

getPrincipleInterface

public java.lang.Class getPrincipleInterface()

Description copied from interface: HasState

Returns the class's principle interface for state comparisons. If two objects have different principle interfaces, they never have the same state.

Specified by:

getPrincipleInterface in interface HasState

sameStateAs

public boolean sameStateAs(HasState victim)

Description copied from interface: HasState

If two HasStates have the same internal state, return true.

For objects with subobjects, Generally this method should only return true if the internal objects are equal. Implement a contentsHaveSameState() method to determine if the contents have the same state.

Specified by:

sameStateAs in interface HasState

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

valid

public boolean valid()

Returns true if this path is still a subgraph of its supergraph

Specified by:

valid in interface Path

getSupergraph

public GEDigraph getSupergraph()

Returns the supergraph. Unlike most methods, this does not copy the supergraph into an immutable object.

Specified by:

getSupergraph in interface GEPath

getHead

public java.lang.Object getHead()

Specified by:

getHead in interface Path

getTail

public java.lang.Object getTail()

Specified by:

getTail in interface Path

getNodeAtIndex

public java.lang.Object getNodeAtIndex(int index)

Specified by:

getNodeAtIndex in interface Path

getIndexOfNode

public int getIndexOfNode(java.lang.Object node)

Specified by:

getIndexOfNode in interface Path

getLastIndexOfNode

public int getLastIndexOfNode(java.lang.Object node)

Specified by:

getLastIndexOfNode in interface Path

getNodeList

public java.util.List getNodeList()

Returns an immutable list of the nodes.

Specified by:

getNodeList in interface Path

checkIndices

private void checkIndices(int startNodeIndex,
                          int endNodeIndex)
                   throws InvalidSpliceException

InvalidSpliceException

getSubpath

public GEPath getSubpath(int startNodeIndex,
                         int endNodeIndex)
                  throws InvalidSpliceException

Returns a new path, between startNodeIndex and endNodeIndex, inclusive.

Specified by:

getSubpath in interface GEPath

InvalidSpliceException

checkSubpathIndices

private void checkSubpathIndices(int startNodeIndex,
                                 int endNodeIndex,
                                 java.lang.Object startNode,
                                 java.lang.Object endNode)
                          throws NodeMissingException,
                                 InvalidSpliceException

NodeMissingException

InvalidSpliceException

getSubpathFirst

public GEPath getSubpathFirst(java.lang.Object startNode,
                              java.lang.Object endNode)
                       throws NodeMissingException,
                              InvalidSpliceException

Returns a new path, between the first occurence of startNode and the first occurence of endNode, inclusive.

Specified by:

getSubpathFirst in interface GEPath

Throws:

NodeMissingException - if the nodes are not in the path.

InvalidSpliceException - if the nodes are not in the right order.

getSubpathLast

public GEPath getSubpathLast(java.lang.Object startNode,
                             java.lang.Object endNode)
                      throws NodeMissingException,
                             InvalidSpliceException

Returns a new path, between the last occurence of startNode and the last occurence of endNode, inclusive.

Specified by:

getSubpathLast in interface GEPath

Throws:

NodeMissingException - if the nodes are not in the path.

InvalidSpliceException - if the nodes are not in the right order.

getSubpathFirstToLast

public GEPath getSubpathFirstToLast(java.lang.Object startNode,
                                    java.lang.Object endNode)
                             throws NodeMissingException,
                                    InvalidSpliceException

Returns a new path, between the first occurence of startNode and the last occurence of endNode, inclusive.

Specified by:

getSubpathFirstToLast in interface GEPath

Throws:

NodeMissingException - if the nodes are not in the path.

InvalidSpliceException - if the nodes are not in the right order.

getSubpathLastToFirst

public GEPath getSubpathLastToFirst(java.lang.Object startNode,
                                    java.lang.Object endNode)
                             throws NodeMissingException,
                                    InvalidSpliceException

Returns a new path, between the last occurence of startNode and the first occurence of endNode, inclusive.

Specified by:

getSubpathLastToFirst in interface GEPath

Throws:

NodeMissingException - if the nodes are not in the path.

InvalidSpliceException - if the nodes are not in the right order.

sameGEPathAs

public boolean sameGEPathAs(GEPath path)

Returns true if path is the same path as this, on the same digraph. So if two paths are on different supergraphs, they may be the same digraph, but not the same path.

Specified by:

sameGEPathAs in interface GEPath

addToTail

protected void addToTail(java.lang.Object node)
                  throws EdgeMissingException,
                         NodeMissingException

Adds an edge and node to the end of the path.

returns true if the operation is successful, false if the path is unchanged.

Throws:

EdgeMissingException - if the edge is not in the digraph between the tail node and node.

NodeMissingException - if the node is not in the digraph.

addToHead

protected void addToHead(java.lang.Object node)
                  throws EdgeMissingException,
                         NodeMissingException

Adds a node and edge to the beginning of the path.

returns true if the operation is successful, false if the path is unchanged.

Throws:

EdgeMissingException - if the edge is not in the digraph between the tail node and node.

NodeMissingException - if the node is not in the digraph.

graftToTail

protected void graftToTail(GEPath path)
                    throws EdgeMissingException,
                           NodeMissingException,
                           InvalidSpliceException

Adds a path to the end of this path.

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's head node is not this' tail node.

graftToHead

protected void graftToHead(GEPath path)
                    throws EdgeMissingException,
                           NodeMissingException,
                           InvalidSpliceException

Adds a path to the beginning of this path.

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's tail node is not this' head node.

removeHead

protected void removeHead()
                   throws LastNodeException

Removes the head node from the path.

LastNodeException

removeTail

protected void removeTail()
                   throws LastNodeException

Removes the tail node from the path.

LastNodeException

chopList

protected void chopList(java.util.List victim,
                        int fromIndex,
                        int toIndex)

pruneTail

protected GEPath pruneTail(int index)

Removes from the edge at index to the tail.

Returns:

the path from the node at index to the tail.

pruneHead

protected GEPath pruneHead(int index)

Removes from the head to the edge at index.

Returns:

the path from the head to the node at index.

pruneTailFromFirst

public GEPath pruneTailFromFirst(java.lang.Object node)
                          throws NodeMissingException

Removes from the first occurance of node to the tail.

Returns:

a path from the first occurance of node to the tail.

Throws:

NodeMissingException - if the node is not in the digraph.

pruneTailFromLast

public GEPath pruneTailFromLast(java.lang.Object node)
                         throws NodeMissingException

Removes from the last occurance of node to the tail.

Returns:

a path from the last occurance of node to the tail.

Throws:

NodeMissingException - if the node is not in the digraph.

pruneHeadFromFirst

public GEPath pruneHeadFromFirst(java.lang.Object node)
                          throws NodeMissingException

Removes from the head to the first occurance of node.

Returns:

a path from the head to the first occurance of node.

Throws:

NodeMissingException - if the node is not in the digraph.

pruneHeadFromLast

public GEPath pruneHeadFromLast(java.lang.Object node)
                         throws NodeMissingException

Removes from the head to the last occurance of node.

Returns:

a path from the head to the last occurance of node.

Throws:

NodeMissingException - if the node is not in the digraph.

splice

protected GEPath splice(GEPath path,
                        int startNodeIndex,
                        int endNodeIndex)
                 throws EdgeMissingException,
                        NodeMissingException,
                        InvalidSpliceException

Splices in path between the startNodeIndex and endNodeIndex.

Returns:

the orphaned path

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's head node is not the node in this at startNodeIndex, or if the path's tail node is not the node in this at endNodeIndex.

spliceFirst

protected GEPath spliceFirst(GEPath path)
                      throws EdgeMissingException,
                             NodeMissingException,
                             InvalidSpliceException

Splices in path between the first occurence of path's head and the first occurence of path's tail.

Returns:

the orphaned path

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's head node is not the node in this at startNodeIndex, or if the path's tail node is not the node in this at endNodeIndex.

spliceLast

protected GEPath spliceLast(GEPath path)
                     throws EdgeMissingException,
                            NodeMissingException,
                            InvalidSpliceException

Splices in path between the last occurence of path's head and the last occurence of path's tail.

Returns:

the orphaned path

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's head node is not the node in this at startNodeIndex, or if the path's tail node is not the node in this at endNodeIndex.

spliceFirstToLast

protected GEPath spliceFirstToLast(GEPath path)
                            throws EdgeMissingException,
                                   NodeMissingException,
                                   InvalidSpliceException

Splices in path between the first occurence of path's head and the last occurence of path's tail.

Returns:

the orphaned path

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's head node is not the node in this at startNodeIndex, or if the path's tail node is not the node in this at endNodeIndex.

spliceLastToFirst

protected GEPath spliceLastToFirst(GEPath path)
                            throws EdgeMissingException,
                                   NodeMissingException,
                                   InvalidSpliceException

Splices in path between the last occurence of path's head and the first occurence of path's tail.

Returns:

the orphaned path

Throws:

EdgeMissingException - if the any edge in path is missing from the digraph.

NodeMissingException - if any node in path not in the digraph.

InvalidSpliceException - if path's head node is not the node in this at startNodeIndex, or if the path's tail node is not the node in this at endNodeIndex.