treelayoutpanel.java

一个决策树的Applet（转载

package ai.decision.gui;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;
import ai.decision.algorithm.*;
import ai.common.*;

/**
 * A panel that formats and displays a tree decision tree.
 * This class uses a node-positioning algorithm described in
 * "A Node-Positioning Algorithm for General Trees"
 * by John Q. Walker II, in <i>Software - Practise and
 * Experience</i>, Vol. 20(7), 685-705 (July 1990).
 *
 * <p>
 * A TreeLayoutPanel is only responsible for computing and
 * rendering a graphical representation of a decision tree.
 * Mouse events (i.e. clicks, drag operations) should be
 * handled by a subclass.
 *
 * <p>
 * <b>Change History:</b>
 *
 * <p><pre>
 * Name:            Date:            Change:
 * =============================================================
 * J. Kelly         Nov-15-2000      Created.
 * </pre>
 *
 * Copyright 2000 University of Alberta.
 *
 * <!--
 * This file is part of the Decision Tree Applet.
 *
 * The Decision Tree Applet is free software; you can redistribute it
 * and/or modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Foobar is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with the Decision Tree Applet; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * -->
 */
public class TreeLayoutPanel
  extends JPanel
  implements TreeChangeListener
{
  // Class data members

  /**
   * The distance between adjacent levels in the tree.
   * (this is fixed).
   */
  public static final int LEVEL_SEPARATION = 60;

  /**
   * The minimum distance between adjacent siblings
   * in a subtree.
   */
  public static final int SIBLING_SEPARATION = 50;

  /**
   * The minimum distance between adjacent subtrees.
   */
  public static final int SUBTREE_SEPARATION = 50;

  /**
   * Size (in pixels) of the current border -
   * there is a least this much whitespace between
   * any tree node and the edge of the panel.
   */
  public static int BORDER_SIZE = 15;

  /**
   * The <i>scaled</i> left offset of the center of the
   * root node of the tree.  All nodes adjust their
   * x-coordinate by this value prior to rendering.
   */
  public static int ROOT_OFFSET = 0;

  /**
   * The left extent of the tree from the center of
   * the root node.  This value is used to adjust
   * the size of the panel dynamically, so it's always
   * just large enought to display the tree.
   */
  public static int LEFT_EXTENT = 0;

  /**
   * The right extent of the tree from the center of
   * the root node.  This value is used to adjust the
   * size of the panel dynamically, so it's always
   * just large enough to display the tree.
   */
  public static int RIGHT_EXTENT = 0;

  /**
   * The total height of the tree, from the top of
   * the root node to the bottom of the deepest leaf.
   * This value is used to adjust the size of the
   * panel dynamically, so it's always just large
   * enough to display the tree.
   */
  public static int TREE_HEIGHT = 0;

  /**
   * The current scaling factor.  Nodes automatically
   * check this value when they draw themselves.
   */
  public static double SCALING_FACTOR = 1.0;

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

  // Instance data members

  /*
   * A list containing the previous node at each level
   * (i.e. adjacent neighbor to the left).
   */
  Vector m_previousNodeList;

  /**
   * Value used to determine the absolute x-cooridinate
   * of a node with respect to the apex node of the tree.
   */
  int m_xTopAdjustment = 0;

  /**
   * Value used to determine the absolute y-coordinate
   * of a node with respect to the apex node of the tree.
   */
  int m_yTopAdjustment = 0;

  Vector      m_nodes;     // List of visual tree nodes.
  Font        m_font;      // Font used to render all text labels.

  JViewport   m_viewport;  // Viewport that displays the tree.

  ComponentManager m_manager;

  // Constructors

  /**
   * Builds a new TreeLayoutPanel.  The panel has a white
   * background by default.
   *
   * @param manager The global component manager.
   *
   * @throws NullPointerException If the supplied
   *         ComponentManager is null.
   */
  public TreeLayoutPanel( ComponentManager manager )
  {
    if( manager == null )
      throw new
        NullPointerException( "Component manager is null." );

    m_manager          = manager;
    m_nodes            = new Vector();
    m_previousNodeList = new Vector();

    // Now, build the panel structure.
    buildPanel();
  }

  // Public methods

  /**
   * Informs that panel that it's being tracked by
   * a viewport.  The panel will automatically adjust
   * the viewport window so that it displays the
   * active (most recently modified) portion of the
   * tree.
   *
   * <p>
   * The panel also uses the viewport width to compute
   * the centering coordinates for the decision tree.
   */
  public void setViewport( JViewport viewport )
  {
    m_viewport = viewport;
  }

  /**
   * Notifies the panel that a new tree has been
   * created.  The panel will clear itself in response.
   */
  public void notifyNewTree()
  {
    // Remove all current nodes.
    m_nodes.clear();
    m_previousNodeList.clear();

    // Reset the width and height of the panel.
    setMinimumSize(   new Dimension( 0, 0 ) );
    setPreferredSize( new Dimension( 0, 0 ) );
    revalidate();

    // Repaint the panel.
    repaint();
  }

  /**
   * Notifies the panel that a node has been added to
   * the tree.  The panel recomputes the optimal display
   * configuration for the tree with the new node attached
   * and then repaints the display.
   *
   * @param node The most recently added node.
   */
  public void notifyNodeAdded( DecisionTreeNode node )
  {
    if( node == null )
      throw new NullPointerException( "Node is null." );

    // First, clear any selected rows in the dataset table.
    if( m_manager.getDatasetPanel() != null )
      m_manager.getDatasetPanel().clearSelectedRows();

    // Determine if a visual representation of the
    // node's parent already exists - this gives us
    // a place to attach the node.
    VisualTreeNode visParent = null;
    int arcNum = 0;

    for( int i = 0; i < m_nodes.size(); i++ ) {
      VisualTreeNode currNode = (VisualTreeNode)m_nodes.elementAt(i);

      if( node.getParent() == currNode.getDecisionTreeNode() ) {
        visParent = currNode;
        arcNum = node.getParent().getChildPosition( node );
        break;
      }
    }

    // Add the node to our internal node list.
    VisualTreeNode newNode =
      new VisualTreeNode( visParent, arcNum,
                          node, this.getFont(), getGraphics() );

    m_nodes.add( newNode );

    // Reset the root position.  If there's a viewport
    // available, then we position the root at the
    // horizontal center position.
    VisualTreeNode root = (VisualTreeNode)m_nodes.elementAt( 0 );
    root.setXCoord( 0 );
    root.setYCoord( 0 );

    // Reset the tree size, as it may have changed.
    LEFT_EXTENT  = 0;
    RIGHT_EXTENT = 0;
    TREE_HEIGHT  = 0;

    // Reposition all nodes in the tree - this may take
    // a moment or two.
    positionTree();

    // The call to positionTree() might have changed
    // the required panel size - we also have to take
    // into account the current scaling factor.
    handlePanelAdjust( newNode );

    // We can't modify the training/testing datasets (by moving
    // examples around) while there are nodes in the tree.
    m_manager.getDatasetMenu().setMoveExamplesEnabled( false );

    // We've recalculated, now repaint.
    repaint();
  }

  /**
   * Notifies the panel that a node had been removed
   * from the tree.  The panel recomputes the optimal
   * display configuration for the tree with the
   * node removed and then repaints the display.
   *
   * <p>
   * This method can be used to remove <i>any</i> visual
   * node within the tree - the structure of the entire
   * tree is rebuilt before any painting occurs.
   *
   * @param node The most recently removed node.
   */
  public void notifyNodeRemoved( DecisionTreeNode node )
  {
    if( node == null )
      throw new NullPointerException( "Node is null." );

    // First, clear any selected rows in the dataset table.
    if( m_manager.getDatasetPanel() != null )
      m_manager.getDatasetPanel().clearSelectedRows();

    // Find the visual representation of the
    // node to remove. We have to tell the parent to
    // replace the deleted node with a 'vacant' node.
    VisualTreeNode visParent = null;
    int nodeNum = 0;

    for( int i = 0; i < m_nodes.size(); i++ ) {
      VisualTreeNode currNode = (VisualTreeNode)m_nodes.elementAt(i);

      if( node == currNode.getDecisionTreeNode() ) {
        if( currNode.getParent() != null )
        visParent = (VisualTreeNode)currNode.getParent();

        nodeNum = i;
        break;
      }
    }

    // Remove the node from the node list.
    pruneSubtree( nodeNum );

    // Reset the root position.  If there's a viewport
    // available, then we position the root at the
    // horizontal center position.
    if( m_nodes.size() != 0 ) {
      VisualTreeNode root = (VisualTreeNode)m_nodes.elementAt( 0 );
      root.setXCoord( 0 );
      root.setYCoord( 0 );
    }

    // Reset the tree size, as it may have changed.
    LEFT_EXTENT  = 0;
    RIGHT_EXTENT = 0;
    TREE_HEIGHT  = 0;

    // Reposition all nodes in the tree - this may take
    // a moment or two.
    positionTree();

    // The call to positionTree() might have changed
    // the required panel size - we also have to take
    // into account the current scaling factor.
    handlePanelAdjust( visParent );

    // We can't modify the training/testing datasets (by moving
    // examples around) while there are nodes in the tree.
    if( m_manager.getAlgorithm().getTree().isEmpty() )
      m_manager.getDatasetMenu().setMoveExamplesEnabled( true );

    // We've recalculated, now repaint.
    repaint();
  }

  /**
   * Notifies the panel that a node had been modified.
   *
   * @param node The most recently modified node.
   */
  public void notifyNodeModified( DecisionTreeNode node )
  {
    // All we have to do is repaint the display,
    // VisualTreeNodes already know how to handle
    // flagged / modified nodes.
    repaint();
  }

  /**
   * Paints a visual representation of the current tree.
   */
  public void paintComponent( Graphics g )
  {
    super.paintComponent( g );

    // Paint each node.
    for( int i = 0; i < m_nodes.size(); i++ )
      ((VisualTreeNode)m_nodes.elementAt(i)).paintNode(g);
  }

  // Protected methods

  /**
   * Prunes off the subtree whose root is at position
   * <code>pos</code> in the internal visual node list.
   * The node and any nodes below it are removed from
   * the tree.
   *
   * @param pos The position of the node to remove
   *        in the internal visual node list.
   */
  protected void pruneSubtree( int pos )
  {
    // Grab the node.
    VisualTreeNode pruneRoot =
      (VisualTreeNode)m_nodes.elementAt( pos );

    pruneSubtree( pruneRoot );
  }

  /**
   * Prunes off the subtree whose rooted at <code>pruneRoot</code>.
   * The node and any nodes below it are removed from the tree.
   *
   * @param pruneRoot The root of the subtree to prune.
   */
  protected void pruneSubtree( VisualTreeNode pruneRoot )
  {
    // If the node has a visual parent, tell
    // the parent to replace the link to the node
    // with a link to a new 'vacant' node.
    if( pruneRoot.getParent() != null )
      ((VisualTreeNode)pruneRoot.getParent()).removeChild( pruneRoot );

      // Now, tell the vector to remove all the node's children.
      recursiveRemoveSubtree( pruneRoot );
  }

  /**
   * Recursively descends through the tree, removing
   * the supplied visual node and any descendants from
   * the internal visual node list.
   *
   * @param node The root node of the subtree to remove.
   */
  protected void recursiveRemoveSubtree( VisualTreeNode node )
  {
    // Remove this node from the vector.
    m_nodes.remove( node );

    // Recursively remove all it's children.
    if( node.isLeaf() ) return;

    for( int i = 0; i < node.getMaxNumChildren(); i++ )
      if( node.getChild( i ) instanceof VisualTreeNode )
      this.recursiveRemoveSubtree( (VisualTreeNode)node.getChild( i ) );
  }

  /**
   * Handles panel size adjustment and tree positioning.
   * This method adjusts the ROOT_OFFSET value used when
   * drawing the tree, based on the current LEFT_EXTENT,
   * RIGHT_EXTENT and SCALING_FACTOR values.
   *
   * @param newNode The most recently added node.  If
   *        this parameter is non-null, the node is
   *        positioned in the view window.
   */
  protected void handlePanelAdjust( VisualTreeNode newNode )
  {