Package gov.nih.mipav.view

Class RubberbandLivewire.ActiveTree

java.lang.Object
gov.nih.mipav.view.RubberbandLivewire.ActiveTree
Enclosing class:
RubberbandLivewire
public class RubberbandLivewire.ActiveTree extends Object
Binary search tree, modified so it will work with elements that have the same cost. In theory this should not be a problem because we have a unique identifier in the parameter position. New nodes of the same cost as an existing node are inserted to the left of the first existing node of the same cost. The children of the first existing node are transferred to the left of the new node. The new node is not put all the way to the left of a chain of nodes of the same cost so as to save tree traversal time. This convention must be followed in the remove and pop or else some nodes get lost and others are never removed.

The main reason for using a Binary Search Tree is that the cost of a "find" (required for remove, pop, and insert) is log n if the tree is reasonably balanced. To insure balance we could have used a red-black tree, but test runs indicate that this tree stays fairly balanced on its own due to the nature of the insertions and deletions.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) RubberbandLivewire.TreeNode
    root
    Pointer to root of tree.

  • Constructor Summary

    Constructors
    Constructor
    Description
    ActiveTree()
    Sets root node to null.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    inOrder()
    Prints out tree in sorted order.
    private void
    inOrder(RubberbandLivewire.TreeNode node, int level)
    Prints out tree in sorted order.
    void
    insert(int position, float cost)
    Inserts node with given position and cost at the appropriate location in the tree.
    final boolean
    isEmpty()
    Returns a flag indicating if this tree is empty.
    final int
    pop()
    Pops off minimum cost in tree.
    void
    remove(int position, float cost)
    Removes node of given position and cost.
    void
    reset()
    Sets root to null.

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

    • ActiveTree

      public ActiveTree()
      Sets root node to null.

  • Method Details

    • inOrder

      public void inOrder()
      Prints out tree in sorted order. Level allows user to see the structure of the tree.

    • insert

      public void insert(int position, float cost)
      Inserts node with given position and cost at the appropriate location in the tree. If the cost is the same as one previously in the tree, inserts the node on the left of the original.
      Parameters:
      position - Position in image array.
      cost - Cost at this position.

    • isEmpty

      public final boolean isEmpty()
      Returns a flag indicating if this tree is empty.
      Returns:
      true if tree is empty.

    • pop

      public final int pop()
      Pops off minimum cost in tree. Returns position of minimum cost and also removes that node from the tree.
      Returns:
      Position of minimum cost.

    • remove

      public void remove(int position, float cost)
      Removes node of given position and cost. cost is used to find where the node is; position is used to uniquely identify the node.
      Parameters:
      position - Position in image array of node to remove.
      cost - Cost of function at position.

    • reset

      public void reset()
      Sets root to null.

    • inOrder

      private void inOrder(RubberbandLivewire.TreeNode node, int level)
      Prints out tree in sorted order. Level allows user to see the structure of the tree. Will print out tree from given node on down.
      Parameters:
      node - Root of tree to print.
      level - Level of tree to print.