Package gov.nih.mipav.view.renderer.WildMagic.VOI

Class VOIManager.ActiveTree

  • Enclosing class:
    VOIManager
    public class VOIManager.ActiveTree
extends java.lang.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) VOIManager.TreeNode root
      Pointer to root of tree.

    • Constructor Summary

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

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void inOrder()
      Prints out tree in sorted order.
      private void inOrder​(VOIManager.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.
      boolean isEmpty()
      Returns a flag indicating if this tree is empty.
      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

    • Constructor Detail

      • ActiveTree

        public ActiveTree()
        Sets root node to null.

    • Method Detail

      • 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​(VOIManager.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.