javautils.graph.templates
Class TimedSearchTemplate

java.lang.Object
  |
  +--javautils.graph.templates.TimedSearchTemplate

public abstract class TimedSearchTemplate

extends java.lang.Object

An abstract Template Method [Gamma1995] for searching directed graphs in a timed fashion.

Field Summary

protected Dispenser	eventDispenser The derived class should directly push any events into this event dispenser.
protected Graph	graph The graph being searched.

Constructor Summary

protected

TimedSearchTemplate(Graph graph, java.util.Iterator roots, Dispenser eventDispenser) A new timed search template.

Method Summary

protected void	beginRoot(java.lang.Object node, IntHolder time) Called once for each root drawn from the root dispenser that has not already been done.
protected void	endRoot(java.lang.Object node, IntHolder time) Called once for root that was begun after the search has finished handling all events generated from the root.
protected abstract void	handleEdge(java.lang.Object edge, java.lang.Object target, IntHolder timeOfTarget) Called once for each edge event drawn from the event dispenser.
protected abstract void	handleNode(java.lang.Object node, IntHolder time) Called once for each node event drawn from the event dispenser.
protected IntHolder	newInitialTime() Called to create a new IntHolder-instance for each edge before the search.
protected boolean	notDone(IntHolder time) True if and only if the time indicates that associated node hasn't already been done or discovered.
protected void	prepareNode(java.lang.Object node) Called once for each node before the search.
void	search() Performs the search calling the event point methods.
protected IntHolder	timeOf(java.lang.Object node) The time associated with the node.

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected final Graph graph

The graph being searched.

eventDispenser

protected final Dispenser eventDispenser

The derived class should directly push any events into this event dispenser. The timed search template then pops events from this dispenser and calls the appropriate event handling method.

Constructor Detail

TimedSearchTemplate

protected TimedSearchTemplate(Graph graph,
                              java.util.Iterator roots,
                              Dispenser eventDispenser)

A new timed search template.

Method Detail

prepareNode

protected void prepareNode(java.lang.Object node)

Called once for each node before the search.

beginRoot

protected void beginRoot(java.lang.Object node,
                         IntHolder time)

Called once for each root drawn from the root dispenser that has not already been done.

endRoot

protected void endRoot(java.lang.Object node,
                       IntHolder time)

Called once for root that was begun after the search has finished handling all events generated from the root.

handleNode

protected abstract void handleNode(java.lang.Object node,
                                   IntHolder time)

Called once for each node event drawn from the event dispenser.

handleEdge

protected abstract void handleEdge(java.lang.Object edge,
                                   java.lang.Object target,
                                   IntHolder timeOfTarget)

Called once for each edge event drawn from the event dispenser.

search

public final void search()

Performs the search calling the event point methods.

newInitialTime

protected IntHolder newInitialTime()

Called to create a new IntHolder-instance for each edge before the search. By default the initial time is 0.

See Also:

notDone(javautils.holders.IntHolder)

notDone

protected boolean notDone(IntHolder time)

True if and only if the time indicates that associated node hasn't already been done or discovered. By default a node is considered done if the time is not 0.

See Also:

newInitialTime()

timeOf

protected final IntHolder timeOf(java.lang.Object node)

The time associated with the node.