treelayoutpanel.java

一个决策树的Applet（转载

    // First, we resize the panel.
    int treeWidth  = (int)
      Math.round( (LEFT_EXTENT + RIGHT_EXTENT + 1) * SCALING_FACTOR );
    int treeHeight = (int)
      Math.round( TREE_HEIGHT * SCALING_FACTOR );

    int panelWidth  = 0;
    int panelHeight = 0;
    int viewWidth   = 0;
    int viewHeight  = 0;

    // Now, shift the entire tree for optimal viewing.
    if( m_viewport == null ) {
      // Center the whole tree in the middle of the panel.
      ROOT_OFFSET = treeWidth/2;

      panelWidth  = treeWidth +  2 * BORDER_SIZE;
      panelHeight = treeHeight + 2 * BORDER_SIZE;
    }
    else {
      // We have a viewport.  If the view window
      // is large enough to accomodate the scaled
      // tree, then we center the tree in the window.
      // Otherwise, we push the tree as far to the
      // left as possible, and then center the view
      // on the supplied coordinates.

      viewWidth  = m_viewport.getExtentSize().width;
      viewHeight = m_viewport.getExtentSize().height;

      // Panel height is largest of tree height and
      // view height.
      panelHeight = treeHeight + 2 * BORDER_SIZE >
        viewHeight ? treeHeight + 2 * BORDER_SIZE : viewHeight;

      int scaledLeftExtent  = (int)
        Math.round( LEFT_EXTENT * SCALING_FACTOR );
      int scaledRightExtent = treeWidth - scaledLeftExtent;

      // Case 1: The tree is skinny enough that the root
      // can be centered in the current viewport.
      if( scaledLeftExtent  + BORDER_SIZE <= viewWidth/2 &&
          scaledRightExtent + BORDER_SIZE <= viewWidth/2 ) {
        ROOT_OFFSET = viewWidth/2;
        panelWidth  = viewWidth;
      }

      // Case 2: The tree is skinny, but can't be centered
      // in the current viewport - so push it as far to
      // left as possible.
      else if( treeWidth + 2 * BORDER_SIZE <= viewWidth ) {
        ROOT_OFFSET = scaledLeftExtent + BORDER_SIZE;
        panelWidth  = viewWidth;
      }

      // Case 3: The tree is too wide to fit in the
      // viewport, so we push it as far to the left
      // as possible and expand the panel size.
      else {
        ROOT_OFFSET = scaledLeftExtent + BORDER_SIZE;
        panelWidth  = treeWidth + 2 * BORDER_SIZE;
      }
    }

    // Resize the panel.
    setPreferredSize( new Dimension( panelWidth, panelHeight ) );

    // If necessary, we can now adjust the viewport view
    // so that it is centered over the active area of the
    // tree (i.e. the area where the last node was added
    // or removed).
    if( m_viewport != null && newNode != null ) {
      int scaledUlcX   = (int)(ROOT_OFFSET +
        Math.round( (newNode.getXCoord() - newNode.getWidth()/2)
          * SCALING_FACTOR ));
      int scaledUlcY   = (int)(BORDER_SIZE + Math.round( newNode.getYCoord()
          * SCALING_FACTOR ));
      int scaledWidth  = (int)Math.round( newNode.getWidth() );
      int scaledHeight = (int)Math.round( newNode.getHeight() );

      m_viewport.scrollRectToVisible(
        new Rectangle( scaledUlcX, scaledUlcY, scaledWidth, scaledHeight ) );
    }

    revalidate();
  }

  // Private methods

  /**
   * Builds and arranges the various GUI components
   * for this panel.
   */
  private void buildPanel()
  {
    // Make the panel opaque - this helps speed up the drawing process.
    setOpaque( true );

    // White background - easy to see.
    setBackground( Color.white );

    // Font setup - 9 pt. version of the current panel font.
    setFont( getFont().deriveFont( Font.PLAIN, 9 ) );
  }

  //-------------------------------------------------------

  // Node-positioning algorithm implementation

  /**
   * Properly positions all nodes in the tree.  This
   * requires two recursive passes through all the nodes.
   */
  private void positionTree()
  {
    // First, we grab a reference to the root node
    // of the tree.  If the tree is empty, we don't
    // do anything.
    if( m_nodes.size() == 0 ) return;

    AbstractTreeNode root = (AbstractTreeNode)m_nodes.elementAt( 0 );

    // Initialize the list of previous nodes at each level.
    initPreviousNodeList();

    // Perform the first walk through the tree,
    // setting the preliminary positions for all the nodes.
    firstWalk( root, 0 );

    // Figure out how to adjust node positions
    // with respect to the root of the tree.
    m_xTopAdjustment = root.getXCoord() - root.getPrelim();
    m_yTopAdjustment = root.getYCoord();

    // Perform the second walk through the tree,
    // setting the absolute positions of each node.
    secondWalk( root, 0, 0 );

    // All finished!
  }

  /**
   * Initializes the list of previous nodes at each
   * level in the tree.
   */
  private void initPreviousNodeList()
  {
    // Simply set all the current positions
    // in the list to null.
    for( int i = 0; i < m_previousNodeList.size(); i++ )
      m_previousNodeList.setElementAt( null, i );
  }

  /**
   * Returns the previous node at a certain level.
   *
   * @param level The level to retrieve the previous
   *        node from.  The identity of the previous
   *        node depends on the position of the
   *        algorithm within the tree.
   *
   * @return The previous node at the current level.
   */
  private AbstractTreeNode getPrevNodeAtLevel( int level )
  {
    if( level >= m_previousNodeList.size() )
      return null;  // No node at the specified level

    return (AbstractTreeNode)m_previousNodeList.elementAt( level );
  }

  /**
   * Set the 'current' previous node for a level.
   *
   * @param level The level to set the previous node at.
   *
   * @param node The 'new' previous node.
   */
  private void setPrevNodeAtLevel( int level, AbstractTreeNode node )
  {
    if( level < m_previousNodeList.size() )
      m_previousNodeList.setElementAt( node, level );
    else
      m_previousNodeList.add( node );
  }

  /**
   * Perform a post-order walk through the tree, setting
   * the preliminary x-coordinate and adjusting the modifier
   * value for each node.
   *
   * @param node The node to begin the post-order walk at.
   *
   * @param level The current level.
   */
  private void firstWalk( AbstractTreeNode node, int level )
  {
    // Setup the reference to the previous node at this level.
    node.setLeftNeighbor( getPrevNodeAtLevel( level ) );
    setPrevNodeAtLevel( level, node );

    node.setModifier( 0 );  // Set default modifier

    if( node.isLeaf() ) {
      // Preliminary x-coord is based on the
      // x-coord of the left sibling, if available.
      // (This accounts for the variable node sizes,
      //  and required separation between siblings).
      if( node.getLeftSibling() != null ) {
        AbstractTreeNode leftSibling = node.getLeftSibling();
        node.setPrelim(
          leftSibling.getPrelim() + SIBLING_SEPARATION +
          meanNodeSize( leftSibling, node ) );
      }
      else {
        // No siblings to the left.
        node.setPrelim( 0 );
      }
    }
    else {
      // The node is not a leaf, so we have to
      // recurively descend to all of its offspring.
      AbstractTreeNode leftmost  = null;
      AbstractTreeNode rightmost = null;

      // Get the leftmost child and recursively descend.
      leftmost = rightmost = node.getChild( 0 );
      firstWalk( leftmost, level + 1 );

      while( rightmost.getRightSibling() != null ) {
        rightmost = rightmost.getRightSibling();
        firstWalk( rightmost, level + 1 );
      }

      // Find the midpoint between the leftmost
      // and rightmost children - this will become
      // the position of the parent.
      int midpoint = ( leftmost.getPrelim() + rightmost.getPrelim() )/2;

      if( node.getLeftSibling() != null ) {
        AbstractTreeNode leftSibling = node.getLeftSibling();
        node.setPrelim(
          leftSibling.getPrelim() + SIBLING_SEPARATION +
          meanNodeSize( leftSibling, node ) );
        node.setModifier( node.getPrelim() - midpoint );

        // Shift the node (and any intermediate nodes
        // to avoid collisions).
        apportion( node, level );
      }
      else {
        // No siblings to the left.
        node.setPrelim( midpoint );
      }
    }
  }

  /**
   * Shifts subtrees beneath a node to ensure that
   * there are no collisions.
   *
   * @param node The node whose subtrees are examined
   *        and shifted.
   *
   * @param level The current level.
   */
  private void apportion( AbstractTreeNode node, int level )
  {
    AbstractTreeNode leftmost     = node.getChild( 0 );
    AbstractTreeNode leftNeighbor = leftmost.getLeftNeighbor();
    int compareDepth = 1;

    while( leftmost != null && leftNeighbor != null ) {
      // Figure out where leftmost should be
      // with respect to it's neighbor.
      int leftModSum  = 0;
      int rightModSum = 0;

      AbstractTreeNode ancestorLeftmost = leftmost;
      AbstractTreeNode ancestorNeighbor = leftNeighbor;

      for( int i = 0; i < compareDepth; i++ ) {
        // We're moving back up the tree,
        // figuring out how far we're going to
        // have to move things.
        ancestorLeftmost = ancestorLeftmost.getParent();
        ancestorNeighbor = ancestorNeighbor.getParent();

        rightModSum += ancestorLeftmost.getModifier();
        leftModSum  += ancestorNeighbor.getModifier();
      }

      // Compute the actual move distance, and
      // adjust smaller internal subtrees so that
      // everything is still balanced.
      int moveDistance = (leftNeighbor.getPrelim() + leftModSum +
        SUBTREE_SEPARATION + meanNodeSize( leftmost, leftNeighbor )) -
        (leftmost.getPrelim() + rightModSum);

      if( moveDistance > 0 ) {
        // Check for and count any interior
        // subtrees that need to be repositioned.
        AbstractTreeNode tempNode = node;
        int leftSiblingCount = 0;

        while( tempNode != null && tempNode != ancestorNeighbor ) {
          leftSiblingCount++;
          tempNode = tempNode.getLeftSibling();
        }

        // If we encountered subtrees that need
        // to be shifted, shift them.
        if( tempNode != null ) {
          int portion = (int)Math.round(
            ((double)moveDistance)/leftSiblingCount );
          tempNode = node;

          while( tempNode != ancestorNeighbor ) {
            tempNode.setPrelim( tempNode.getPrelim() + moveDistance );
            tempNode.setModifier( tempNode.getModifier() + moveDistance );

            moveDistance -= portion;
            tempNode = tempNode.getLeftSibling();
          }
        }
        else {
          // We don't need to move anything.
          return;
        }
      }

      // Find the leftmost descendent of 'node'
      // at the next lower level, and compare
      // it's position against that of it's
      // neighbor (checking for a collision).
      compareDepth++;

      if( leftmost.isLeaf() )
        leftmost = getLeftmost( node, 0, compareDepth );
      else
        leftmost = leftmost.getChild( 0 );

      if( leftmost != null )
        leftNeighbor = leftmost.getLeftNeighbor();
    }
  }

  /**
   * Returns the leftmost descendant of a node at a given
   * depth.
   *
   * @param node The node to recursively search under.
   *
   * @param level The current <i>relative</i> level,
   *        in relation to the level we were at when
   *        the method was first called.
   *
   * @param depth Maximum number of levels to descend.
   *
   * @return The leftmost node at the requested depth,
   *         or null if the supplied node is a leaf node.
   */
  private AbstractTreeNode getLeftmost( AbstractTreeNode node,
                                        int level, int depth )
  {
    // Base cases.
    if( level >= depth )
      return node;
    else if( node.isLeaf() )
      return null;
    else {
      // Recursive case.
      AbstractTreeNode rightmost = node.getChild( 0 );
      AbstractTreeNode leftmost  =
        getLeftmost( rightmost, level + 1, depth );

      // Post-order walk through the subtree below node.
      while( leftmost == null && rightmost.getRightSibling() != null ) {
        rightmost = rightmost.getRightSibling();
        leftmost  = getLeftmost( rightmost, level + 1, depth );
      }

      return leftmost;
    }
  }

  /**
   * Performs a pre-order walk through the tree, setting
   * the final x and y coordinates for all nodes.
   *
   * <p>
   * Final x-coordinate values are determined by summing
   * a node's preliminary placement value and the
   * modifiers of all the node's ancestors.
   *
   * @param node The node at which to start the
   *        recursive traversal.
   *
   * @param level The level for the supplied node.
   *
   * @param modSum The current modifier sum.
   */
  private void secondWalk( AbstractTreeNode node, int level, int modSum )
  {
    node.setXCoord( m_xTopAdjustment + node.getPrelim() + modSum );
    node.setYCoord( m_yTopAdjustment + level*LEVEL_SEPARATION );

    if( !node.isLeaf() )
      secondWalk( node.getChild( 0 ), level + 1, modSum + node.getModifier() );

    if( node.getRightSibling() != null )
      secondWalk( node.getRightSibling(), level, modSum );

    // An addition to the original algorithm -
    // If this is the leftmost node in the tree thus
    // far, we adjust LEFT_EXTENT.  If this is the
    // rightmost node in the tree thus far, we adjust
    // RIGHT_EXTENT.
    if( node.getXCoord() - node.getWidth()/2 < (- LEFT_EXTENT) )
      LEFT_EXTENT  = - node.getXCoord() + node.getWidth()/2;
    else if( node.getXCoord() + node.getWidth()/2 > RIGHT_EXTENT )
      RIGHT_EXTENT = node.getXCoord() + node.getWidth()/2;

    // If this node is the lowest node in the tree, we
    // adjust the overall height of the tree.
    if( node.getYCoord() + node.getHeight() - 1 > TREE_HEIGHT )
      TREE_HEIGHT = node.getYCoord() + node.getHeight() - 1;
  }

  /**
   * Returns the mean width of the two supplied nodes.
   *
   * @return The mean width of the two supplied nodes.
   *         If one of the nodes is null, the method
   *         returns the width of the non-null node
   *         divided by 2.  If both nodes are null, the
   *         method returns 0.
   */
  private int meanNodeSize( AbstractTreeNode leftNode,
                            AbstractTreeNode rightNode )
  {
    int widthSum =
      (leftNode  != null ? leftNode.getWidth()  : 0) +
      (rightNode != null ? rightNode.getWidth() : 0);

      return widthSum/2;
  }
}