org.graffiti.plugins.algorithms.mst.animation
Class PrimsAlgorithmStep

java.lang.Object
  extended by org.graffiti.plugins.algorithms.mst.animation.PrimsAlgorithmStep
All Implemented Interfaces:
Step

public class PrimsAlgorithmStep
extends Object
implements Step

One step of Prim's algorithm; selects the next edge of a minimum spanning tree.

Version:
$Revision$ $Date$
Author:
Harald

Constructor Summary
PrimsAlgorithmStep(org.graffiti.plugins.algorithms.mst.adapters.HeapAdapter h, boolean isSingleton)
          Creates a new step for Prim's algorithm with the specified heap proxy.
 
Method Summary
 boolean hasNext()
          Returns true if this step has a successor.
 Step next()
          Performs this step and returns its successor.
 void redo()
          Redoes the effects of this step after it has been undone.
 void undo()
          Undoes the effects of this step after it has been performed or redone.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

PrimsAlgorithmStep

public PrimsAlgorithmStep(org.graffiti.plugins.algorithms.mst.adapters.HeapAdapter h,
                          boolean isSingleton)
Creates a new step for Prim's algorithm with the specified heap proxy. If isSingleton is true this instance will return itself upon a call to next instead of creating a new instance of PrimsAlgorithmStep.

Parameters:
h - the HeapProxy to use by this step of Prim's algorithm.
isSingleton - true if this instance is a singleton step.
See Also:
HeapAdapter
Method Detail

hasNext

public boolean hasNext()
Returns true if this step has a successor.

This implementation returns true if the heap it uses is not empty.

Specified by:
hasNext in interface Step
Returns:
true if this step has a successor.

next

public Step next()
Performs this step and returns its successor.

This implementation first checks whether this step has a successor. If not it throws IllegalStateException. Otherwise it processes the peek node in this step's heap as specified by Prim's algorithm and selects the edge from the peek node to its parent. Finally if this step is a singleton step, it returns itself; otherwise it creates a new instance of PrimsAlgorithmStep with identical parameters and returns it.

Specified by:
next in interface Step
Returns:
the successor of this step.
Throws:
IllegalStateException - if this step has no successor.
See Also:
HeapAdapter.removePeek(), NodeAdapter, NodeAdapter.edgeTo(NodeAdapter), NodeAdapter.getParent(), EdgeAdapter.select()

redo

public void redo()
Redoes the effects of this step after it has been undone.

This implementation first checks whether this step is a singleton step or the last edge

Specified by:
redo in interface Step
Throws:
IllegalStateException - if this step has not been undone.
UnsupportedOperationException - if this step is a singleton step.

undo

public void undo()
Undoes the effects of this step after it has been performed or redone.

Specified by:
undo in interface Step
Throws:
IllegalStateException - if this step has not been performed or redone yet.
UnsupportedOperationException - if this step is a singleton step.


Generated at 2012-05-30 11:01:25 PM CEST