tree.java

用applet实现很多应用小程序

package prefuse.data;

import java.util.Iterator;
import java.util.logging.Logger;

import prefuse.util.PrefuseConfig;
import prefuse.util.collections.IntIterator;

/**
 * <p>Graph subclass that models a tree structure of hierarchical
 * parent-child relationships. For each edge, the source node is considered
 * the parent, and the target node is considered the child. For the tree
 * structure to be valid, each node can have at most one parent, and hence
 * only one edge for which that node is the target. In addition to the methods
 * of the Graph class, the tree also supports methods for navigating the tree
 * structure, such as accessing parent or children nodes and next or previous
 * sibling nodes (siblings are children nodes with a shared parent). Unlike the
 * graph class, the default source and target key field names are renamed to
 * {@link #DEFAULT_SOURCE_KEY} and {@link #DEFAULT_TARGET_KEY}.
 * Like the {@link Graph} class, Trees are backed by node and edge
 * tables, and use {@link prefuse.data.Node} and
 * {@link prefuse.data.Edge} instances to provide object-oriented access
 * to nodes and edges.</p>
 * 
 * <p>The Tree class does not currently enforce that the graph structure remain
 * a valid tree. This is to allow a chain of editing operations that may break
 * the tree structure at some point before repairing it. Use the
 * {@link #isValidTree()} method to test the validity of a tree.</p>
 * 
 * <p>By default, the {@link #getSpanningTree()} method simply returns a
 * reference to this Tree instance. However, if a spanning tree is created at a
 * new root u sing the {@link #getSpanningTree(Node)} method, a new
 * {@link SpanningTree} instance is generated.</p>
 * 
 * @author <a href="http://jheer.org">jeffrey heer</a>
 */
public class Tree extends Graph {

    private static final Logger s_logger
        = Logger.getLogger(Tree.class.getName());
    
    /** Default data field used to denote the source node in an edge table */
    public static final String DEFAULT_SOURCE_KEY 
        = PrefuseConfig.get("data.tree.sourceKey");
    /** Default data field used to denote the target node in an edge table */
    public static final String DEFAULT_TARGET_KEY
        = PrefuseConfig.get("data.tree.targetKey");
    
    // implement as graph with limitations on edge settings
    // catch external modification events and throw exceptions as necessary
    
    /** The node table row number for the root node of the tree. */
    protected int m_root = -1;
    
    // ------------------------------------------------------------------------
    // Constructors
    
    /**
     * Create a new, empty Tree.
     */
    public Tree() {
        super(new Table(), false);
    }
    
    /**
     * Create a new Tree.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param edges the backing table to use for edge data.
     * Edge instances of this graph will get their data from this table.
     */
    public Tree(Table nodes, Table edges) {
        this(nodes, edges, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
    }

    /**
     * Create a new Tree.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param edges the backing table to use for edge data.
     * Edge instances of this graph will get their data from this table.
     * @param sourceKey data field used to denote the source node in an edge
     * table
     * @param targetKey data field used to denote the target node in an edge
     * table
     */
    public Tree(Table nodes, Table edges, String sourceKey, String targetKey) {
        this(nodes, edges, DEFAULT_NODE_KEY, sourceKey, targetKey);
    }
    
    /**
     * Create a new Tree.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param edges the backing table to use for edge data.
     * Edge instances of this graph will get their data from this table.
     * @param nodeKey data field used to uniquely identify a node. If this
     * field is null, the node table row numbers will be used
     * @param sourceKey data field used to denote the source node in an edge
     * table
     * @param targetKey data field used to denote the target node in an edge
     * table
     */
    public Tree(Table nodes, Table edges, String nodeKey,
            String sourceKey, String targetKey)
    {
        super(nodes, edges, false, nodeKey, sourceKey, targetKey);
        
        for ( IntIterator rows = nodes.rows(); rows.hasNext(); ) {
            int n = rows.nextInt();
            if ( getParent(n) < 0 ) {
                m_root = n;
                break;
            }
        }
    }
    
    /**
     * Internal method for setting the root node.
     * @param root the root node to set
     */
    void setRoot(Node root) {
        m_root = root.getRow();
    }
        
    /**
     * @see prefuse.data.Graph#createLinkTable()
     */
    protected Table createLinkTable() {
        Table links = super.createLinkTable();
        links.addColumns(TREE_LINKS_SCHEMA);
        return links;
    }
    
    /**
     * @see prefuse.data.Graph#updateDegrees(int, int, int, int)
     */
    protected void updateDegrees(int e, int s, int t, int incr) {
        super.updateDegrees(e, s, t, incr);
        int od = getOutDegree(s);
        if ( incr > 0 ) {
            // if added, child index is the last index in child array
            m_links.setInt(t, CHILDINDEX, od-1);
        } else if ( incr < 0 ) {
            // if removed, we renumber each child in the array
            int[] links = (int[])m_links.get(s, OUTLINKS);
            for ( int i=0; i<od; ++i ) {
                int n = getTargetNode(links[i]);
                m_links.setInt(n, CHILDINDEX, i);
            }
            m_links.setInt(t, CHILDINDEX, -1);
        }
    }
    
    // ------------------------------------------------------------------------
    // Tree Mutators
    
    /**
     * Add a new root node to an empty Tree.
     * @return the node id (node table row number) of the new root node.
     */
    public int addRootRow() {
        if ( getNodeCount() != 0 ) {
            throw new IllegalStateException(
                    "Can only add a root node to an empty tree");
        }
        return (m_root = addNodeRow());
    }
    
    /**
     * Add a new root node to an empty Tree.
     * @return the newly added root Node
     */
    public Node addRoot() {
        return getNode(addRootRow());
    }
    
    /**
     * Add a child node to the given parent node. An edge between the two
     * will also be created.
     * @param parent the parent node id (node table row number)
     * @return the added child node id
     */
    public int addChild(int parent) {
        int child = super.addNodeRow();
        addChildEdge(parent, child);
        return child;
    }
    
    /**
     * Add a child node to the given parent node. An edge between the two
     * will also be created.
     * @param parent the parent node
     * @return the added child node
     */
    public Node addChild(Node parent) {
        nodeCheck(parent, true);
        return getNode(addChild(parent.getRow()));
    }
    
    /**
     * Add a child edge between the given nodes.
     * @param parent the parent node id (node table row number)
     * @param child the child node id (node table row number)
     * @return the added child edge id
     */
    public int addChildEdge(int parent, int child) {
        return super.addEdge(parent, child);
    }

    /**
     * Add a child edge between the given nodes.
     * @param parent the parent node
     * @param child the child node
     * @return the added child edge
     */
    public Edge addChildEdge(Node parent, Node child) {
        nodeCheck(parent, true);
        nodeCheck(child, true);
        return getEdge(addChildEdge(parent.getRow(), child.getRow()));
    }
    
    /**
     * Remove a child edge from the Tree. The child node and its subtree
     * will also be removed from the Tree.
     * @param edge the edge id (edge table row number) of the edge to remove
     * @return true if the edge and attached subtree is successfully removed,
     * false otherwise
     */
    public boolean removeChildEdge(int edge) {
        return removeChild(getTargetNode(edge));
    }

    /**
     * Remove a child edge from the Tree. The child node and its subtree
     * will also be removed from the Tree.
     * @param e the edge to remove
     * @return true if the edge and attached subtree is successfully removed,
     * false otherwise
     */
    public boolean removeChildEdge(Edge e) {
        edgeCheck(e, true);
        return removeChild(getTargetNode(e.getRow()));
    }
    
    /**
     * Remove a node and its entire subtree rooted at the node from the tree.
     * @param node the node id (node table row number) to remove
     * @return true if the node and its subtree is successfully removed,
     * false otherwise
     */
    public boolean removeChild(int node) {
        while ( getChildCount(node) > 0 ) {
            removeChild(getLastChildRow(node));
        }
        return removeNode(node);
    }
    
    /**
     * Remove a node and its entire subtree rooted at the node from the tree.
     * @param n the node to remove
     * @return true if the node and its subtree is successfully removed,
     * false otherwise
     */
    public boolean removeChild(Node n) {
        nodeCheck(n, true);
        return removeChild(n.getRow());
    }
    
    // ------------------------------------------------------------------------
    // Tree Accessors
    
    /**
     * Get the root node id (node table row number).
     * @return the root node id
     */
    public int getRootRow() {
        return m_root;
    }
    
    /**
     * Get the root node.
     * @return the root Node
     */
    public Node getRoot() {
        return (Node)m_nodeTuples.getTuple(m_root);
    }

    /**
     * Get the child node id at the given index.
     * @param node the parent node id (node table row number)
     * @param idx the child index
     * @return the child node id (node table row number)
     */
    public int getChildRow(int node, int idx) {
        int cc = getChildCount(node);
        if ( idx < 0 || idx >= cc ) return -1;
        int[] links = (int[])m_links.get(node, OUTLINKS);
        return getTargetNode(links[idx]);
    }
    
    /**
     * Get the child node at the given index.
     * @param node the parent Node
     * @param idx the child index
     * @return the child Node
     */
    public Node getChild(Node node, int idx) {
        int c = getChildRow(node.getRow(), idx);
        return ( c<0 ? null : getNode(c) );
    }
    
    /**
     * Get the child index (order number of the child) for the given parent
     * node id and child node id.
     * @param parent the parent node id (node table row number)
     * @param child the child node id (node table row number)
     * @return the index of the child, or -1 if the given child node is not
     * actually a child of the given parent node, or either node is
     * invalud.
     */
    public int getChildIndex(int parent, int child) {
        if ( getParent(child) != parent )
            return -1;
        return m_links.getInt(child, CHILDINDEX);
    }
    
    /**
     * Get the child index (order number of the child) for the given parent
     * and child nodes.
     * @param p the parent Node