tree.java

用applet实现很多应用小程序

     * @param c the child Node
     * @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(Node p, Node c) {
        return getChildIndex(p.getRow(), c.getRow());
    }
    
    /**
     * Get the node id of the first child of the given parent node id.
     * @param node the parent node id (node table row number)
     * @return the node id of the first child
     */
    public int getFirstChildRow(int node) {
        return getChildRow(node, 0);
    }

    /**
     * Get the first child node of the given parent node.
     * @param node the parent Node
     * @return the first child Node
     */
    public Node getFirstChild(Node node) {
        return getChild(node, 0);
    }
    
    /**
     * Get the node id of the last child of the given parent node id.
     * @param node the parent node id (node table row number)
     * @return the node id of the last child
     */
    public int getLastChildRow(int node) {
        return getChildRow(node, getChildCount(node)-1);
    }
    
    /**
     * Get the last child node of the given parent node.
     * @param node the parent Node
     * @return the last child Node
     */
    public Node getLastChild(Node node) {
        return getChild(node, node.getChildCount()-1);
    }
    
    /**
     * Get the node id of the previous sibling of the given node id.
     * @param node a node id (node table row number)
     * @return the node id of the previous sibling, or -1 if there
     * is no previous sibling.
     */
    public int getPreviousSiblingRow(int node) {
        int p = getParent(node);
        if ( p < 0 )
            return -1;
        int[] links = (int[])m_links.get(p, OUTLINKS);
        int idx = m_links.getInt(node, CHILDINDEX);
        return ( idx<=0 ? -1 : getTargetNode(links[idx-1]));
    }
    
    /**
     * Get the previous sibling of the given node.
     * @param node a node
     * @return the previous sibling, or null if there is no previous sibling
     */
    public Node getPreviousSibling(Node node) {
        int n = getPreviousSiblingRow(node.getRow());
        return ( n<0 ? null : getNode(n) );
    }
    
    /**
     * Get the node id of the next sibling of the given node id.
     * @param node a node id (node table row number)
     * @return the node id of the next sibling, or -1 if there
     * is no next sibling.
     */
    public int getNextSiblingRow(int node) {
        int p = getParent(node);
        if ( p < 0 )
            return -1;
        int[] links = (int[])m_links.get(p, OUTLINKS);
        int idx = m_links.getInt(node, CHILDINDEX);
        int max = getChildCount(p)-1;
        return ( idx<0 || idx>=max ? -1 : getTargetNode(links[idx+1]));
    }
    
    /**
     * Get the next sibling of the given node.
     * @param node a node
     * @return the next sibling, or null if there is no next sibling
     */
    public Node getNextSibling(Node node) {
        int n = getNextSiblingRow(node.getRow());
        return ( n<0 ? null : getNode(n) );
    }
    
    /**
     * Get the depth of the given node id in the tree.
     * @param node a node id (node table row number)
     * @return the depth of the node in tree. The root node
     * is at a depth level of 0, with each child at a greater
     * depth level. -1 is returned if the input node id is not
     * in the tree.
     */
    public int getDepth(int node) {
        if ( !getNodeTable().isValidRow(node) )
            return -1;
        
        int depth = 0;
        if ( node!=m_root && getParent(node) < 0 ) return -1;
        for ( int i=node; i!=m_root && i>=0; ++depth, i=getParent(i) );
        return depth;
    }
    
    /**
     * Get the number of children of the given node id.
     * @param node a node id (node table row number)
     * @return the number of child nodes for the given node
     */
    public int getChildCount(int node) {
        return getOutDegree(node);
    }
    
    /**
     * Get the edge id of the edge to the given node's parent.
     * @param node the node id (node table row number)
     * @return the edge id (edge table row number) of the parent edge
     */
    public int getParentEdge(int node) {
        if ( getInDegree(node) > 0 ) {
            int[] inlinks = (int[])m_links.get(node, INLINKS);
            return inlinks[0];
        } else {
            return -1;
        }
    }
    
    /**
     * Get the edge to the given node's parent.
     * @param n a Node instance
     * @return the parent Edge connecting the given node to its parent
     */
    public Edge getParentEdge(Node n) {
        nodeCheck(n, true);
        int pe = getParentEdge(n.getRow());
        return ( pe < 0 ? null : getEdge(pe) );
    }
    
    /**
     * Get a node's parent node id
     * @param node the child node id (node table row number)
     * @return the parent node id, or -1 if there is no parent
     */
    public int getParent(int node) {
        int pe = getParentEdge(node);
        return ( pe < 0 ? -1 : getSourceNode(pe) );
    }

    /**
     * Get a node's parent node
     * @param n the child node
     * @return the parent node, or null if there is no parent
     */
    public Node getParent(Node n) {
        int p = getParent(n.getRow());
        return ( p < 0 ? null : getNode(p) );
    }
    
    // ------------------------------------------------------------------------
    // Iterators
    
    /**
     * Get an iterator over the edge ids for edges connecting child nodes to
     * a given parent
     * @param node the parent node id (node table row number)
     * @return an iterator over the edge ids for edges conencting child nodes
     * to a given parent
     */
    public IntIterator childEdgeRows(int node) {
        return super.outEdgeRows(node);
    }
    
    /**
     * Get an iterator over the edges connecting child nodes to a given parent 
     * @param n the parent node
     * @return an iterator over the edges connecting child nodes to a given
     * parent
     */
    public Iterator childEdges(Node n) {
        return super.outEdges(n);
    }
    
    /**
     * Get an iterator over the child nodes of a parent node.
     * @param n the parent node
     * @return an iterator over the child nodes of a parent node
     */
    public Iterator children(Node n) {
        return super.outNeighbors(n);
    }
    
    // ------------------------------------------------------------------------
    // Sanity Test
    
    /**
     * Check that the underlying graph structure forms a valid tree.
     * @return true if this is a valid tree, false otherwise
     */
    public boolean isValidTree() {
        // TODO: write a visitor interface and use that instead?
        int nnodes = getNodeCount();
        int nedges = getEdgeCount();
        
        // first make sure there are n nodes and n-1 edges
        if ( nnodes != nedges+1 ) {
            s_logger.warning("Node/edge counts incorrect.");
            return false;
        }
        
        // iterate through nodes, make sure each one has the right
        // number of parents
        int root = getRootRow();
        IntIterator nodes = getNodeTable().rows();
        while ( nodes.hasNext() ) {
            int n = nodes.nextInt();
            int id = getInDegree(n);
            if ( n==root && id > 0 ) {
                s_logger.warning("Root node has a parent.");
                return false;
            } else if ( id > 1 ) {
                s_logger.warning("Node "+n+" has multiple parents.");
                return false;
            }
        }
        
        // now do a traversal and make sure we visit everything
        int[] counts = new int[] { 0, nedges };
        isValidHelper(getRootRow(), counts);
        if ( counts[0] > nedges ) {
            s_logger.warning("The tree has non-tree edges in it.");
            return false;
        }
        if ( counts[0] < nedges ) {
            s_logger.warning("Not all of the tree was visited. " +
                "Only "+counts[0]+"/"+nedges+" edges encountered");
            return false;
        }
        return true;
    }
    
    /**
     * isValidTree's recursive helper method.
     */
    private void isValidHelper(int node, int[] counts) {
        IntIterator edges = childEdgeRows(node);
        int ncount = 0;
        while ( edges.hasNext() ) {
            // get next edge, increment count
            int edge = edges.nextInt();
            ++ncount; ++counts[0];
            // visit the next edge
            int c = getAdjacentNode(edge, node);
            isValidHelper(c, counts);
            // check the counts
            if ( counts[0] > counts[1] )
                return;
        }
    }

    // ------------------------------------------------------------------------
    // Spanning Tree Methods
    
    /**
     * Returns a spanning tree over this tree. If no spanning tree
     * has been constructed at an alternative root, this method simply returns
     * a pointer to this Tree instance. If a spanning tree rooted at an
     * alternative node has been created, that tree is returned.
     * 
     * @return a spanning tree over this tree
     * @see #getSpanningTree(Node)
     * @see Graph#clearSpanningTree()
     */
    public Tree getSpanningTree() {
        return m_spanning==null ? this : m_spanning;
    }
    
    /**
     * Returns a spanning tree over this tree, rooted at the given root. If
     * the given root is not the same as that of this Tree, a new spanning
     * tree instance will be constructed, made the current spanning tree
     * for this Tree instance, and returned.
     * 
     * To clear out any generated spanning trees use the clearSpanningTree()
     * method of the Graph class. After calling clearSpanningTree(), the
     * getSpanningTree() method (with no arguments) will return a pointer
     * to this Tree instance instead of any generated spanning trees.
     * 
     * @param root the node at which to root the spanning tree.
     * @return a spanning tree over this tree, rooted at the given root
     * @see #getSpanningTree()
     * @see Graph#clearSpanningTree()
     */
    public Tree getSpanningTree(Node root) {
        nodeCheck(root, true);
        if ( m_spanning == null ) {
            if ( m_root == root.getRow() ) {
                return this;
            } else {
                m_spanning = new SpanningTree(this, root);
            }
        } else if ( m_spanning.getRoot() != root ) {
            m_spanning.buildSpanningTree(root);
        }
        return m_spanning;
    }
    
    // ------------------------------------------------------------------------
    // Tree Linkage Schema (appended to the Graph Linkage Schema)
    
    /** Links table data field storing the index number of a child node */
    protected static final String CHILDINDEX = "_childIndex";
    /** Schema addition to be added onto {@link Graph#LINKS_SCHEMA}. */
    protected static final Schema TREE_LINKS_SCHEMA = new Schema();
    static {
        TREE_LINKS_SCHEMA.addColumn(CHILDINDEX, int.class, new Integer(-1));
        TREE_LINKS_SCHEMA.lockSchema();
    }
    
} // end of class Tree