nodelinktreelayout.java

来自「用applet实现很多应用小程序」· Java 代码 · 共 510 行 · 第 1/2 页

        determineDepths();
        
        // do second pass - assign layout positions
        secondWalk(root, null, -rp.prelim, 0);
    }

    private void firstWalk(NodeItem n, int num, int depth) {
        Params np = getParams(n);
        np.number = num;
        updateDepths(depth, n);
        
        boolean expanded = n.isExpanded();
        if ( n.getChildCount() == 0 || !expanded ) // is leaf
        { 
            NodeItem l = (NodeItem)n.getPreviousSibling();
            if ( l == null ) {
                np.prelim = 0;
            } else {
                np.prelim = getParams(l).prelim + spacing(l,n,true);
            }
        }
        else if ( expanded )
        {
            NodeItem leftMost = (NodeItem)n.getFirstChild();
            NodeItem rightMost = (NodeItem)n.getLastChild();
            NodeItem defaultAncestor = leftMost;
            NodeItem c = leftMost;
            for ( int i=0; c != null; ++i, c = (NodeItem)c.getNextSibling() )
            {
                firstWalk(c, i, depth+1);
                defaultAncestor = apportion(c, defaultAncestor);
            }
            
            executeShifts(n);
            
            double midpoint = 0.5 *
                (getParams(leftMost).prelim + getParams(rightMost).prelim);
            
            NodeItem left = (NodeItem)n.getPreviousSibling();
            if ( left != null ) {
                np.prelim = getParams(left).prelim + spacing(left, n, true);
                np.mod = np.prelim - midpoint;
            } else {
                np.prelim = midpoint;
            }
        }
    }
    
    private NodeItem apportion(NodeItem v, NodeItem a) {        
        NodeItem w = (NodeItem)v.getPreviousSibling();
        if ( w != null ) {
            NodeItem vip, vim, vop, vom;
            double   sip, sim, sop, som;
            
            vip = vop = v;
            vim = w;
            vom = (NodeItem)vip.getParent().getFirstChild();
            
            sip = getParams(vip).mod;
            sop = getParams(vop).mod;
            sim = getParams(vim).mod;
            som = getParams(vom).mod;
            
            NodeItem nr = nextRight(vim);
            NodeItem nl = nextLeft(vip);
            while ( nr != null && nl != null ) {
                vim = nr;
                vip = nl;
                vom = nextLeft(vom);
                vop = nextRight(vop);
                getParams(vop).ancestor = v;
                double shift = (getParams(vim).prelim + sim) - 
                    (getParams(vip).prelim + sip) + spacing(vim,vip,false);
                if ( shift > 0 ) {
                    moveSubtree(ancestor(vim,v,a), v, shift);
                    sip += shift;
                    sop += shift;
                }
                sim += getParams(vim).mod;
                sip += getParams(vip).mod;
                som += getParams(vom).mod;
                sop += getParams(vop).mod;
                
                nr = nextRight(vim);
                nl = nextLeft(vip);
            }
            if ( nr != null && nextRight(vop) == null ) {
                Params vopp = getParams(vop);
                vopp.thread = nr;
                vopp.mod += sim - sop;
            }
            if ( nl != null && nextLeft(vom) == null ) {
                Params vomp = getParams(vom);
                vomp.thread = nl;
                vomp.mod += sip - som;
                a = v;
            }
        }
        return a;
    }
    
    private NodeItem nextLeft(NodeItem n) {
        NodeItem c = null;
        if ( n.isExpanded() ) c = (NodeItem)n.getFirstChild();
        return ( c != null ? c : getParams(n).thread );
    }
    
    private NodeItem nextRight(NodeItem n) {
        NodeItem c = null;
        if ( n.isExpanded() ) c = (NodeItem)n.getLastChild();
        return ( c != null ? c : getParams(n).thread );
    }
    
    private void moveSubtree(NodeItem wm, NodeItem wp, double shift) {
        Params wmp = getParams(wm);
        Params wpp = getParams(wp);
        double subtrees = wpp.number - wmp.number;
        wpp.change -= shift/subtrees;
        wpp.shift += shift;
        wmp.change += shift/subtrees;
        wpp.prelim += shift;
        wpp.mod += shift;
    }
    
    private void executeShifts(NodeItem n) {
        double shift = 0, change = 0;
        for ( NodeItem c = (NodeItem)n.getLastChild();
              c != null; c = (NodeItem)c.getPreviousSibling() )
        {
            Params cp = getParams(c);
            cp.prelim += shift;
            cp.mod += shift;
            change += cp.change;
            shift += cp.shift + change;
        }
    }
    
    private NodeItem ancestor(NodeItem vim, NodeItem v, NodeItem a) {
        NodeItem p = (NodeItem)v.getParent();
        Params vimp = getParams(vim);
        if ( vimp.ancestor.getParent() == p ) {
            return vimp.ancestor;
        } else {
            return a;
        }
    }
    
    private void secondWalk(NodeItem n, NodeItem p, double m, int depth) {
        Params np = getParams(n);
        setBreadth(n, p, np.prelim + m);
        setDepth(n, p, m_depths[depth]);
        
        if ( n.isExpanded() ) {
            depth += 1;
            for ( NodeItem c = (NodeItem)n.getFirstChild();
                  c != null; c = (NodeItem)c.getNextSibling() )
            {
                secondWalk(c, n, m + np.mod, depth);
            }
        }
        
        np.clear();
    }
    
    private void setBreadth(NodeItem n, NodeItem p, double b) {
        switch ( m_orientation ) {
        case Constants.ORIENT_LEFT_RIGHT:
        case Constants.ORIENT_RIGHT_LEFT:
            setY(n, p, m_ay + b);
            break;
        case Constants.ORIENT_TOP_BOTTOM:
        case Constants.ORIENT_BOTTOM_TOP:
            setX(n, p, m_ax + b);
            break;
        default:
            throw new IllegalStateException();
        }
    }
    
    private void setDepth(NodeItem n, NodeItem p, double d) {
        switch ( m_orientation ) {
        case Constants.ORIENT_LEFT_RIGHT:
            setX(n, p, m_ax + d);
            break;
        case Constants.ORIENT_RIGHT_LEFT:
            setX(n, p, m_ax - d);
            break;
        case Constants.ORIENT_TOP_BOTTOM:
            setY(n, p, m_ay + d);
            break;
        case Constants.ORIENT_BOTTOM_TOP:
            setY(n, p, m_ay - d);
            break;
        default:
            throw new IllegalStateException();
        }
    }
    
    // ------------------------------------------------------------------------
    // Params Schema
    
    /**
     * The data field in which the parameters used by this layout are stored.
     */
    public static final String PARAMS = "_reingoldTilfordParams";
    /**
     * The schema for the parameters used by this layout.
     */
    public static final Schema PARAMS_SCHEMA = new Schema();
    static {
        PARAMS_SCHEMA.addColumn(PARAMS, Params.class);
    }
    
    protected void initSchema(TupleSet ts) {
        ts.addColumns(PARAMS_SCHEMA);
    }
    
    private Params getParams(NodeItem item) {
        Params rp = (Params)item.get(PARAMS);
        if ( rp == null ) {
            rp = new Params();
            item.set(PARAMS, rp);
        }
        if ( rp.number == -2 ) {
            rp.init(item);
        }
        return rp;
    }
    
    /**
     * Wrapper class holding parameters used for each node in this layout.
     */
    public static class Params implements Cloneable {
        double prelim;
        double mod;
        double shift;
        double change;
        int    number = -2;
        NodeItem ancestor = null;
        NodeItem thread = null;
        
        public void init(NodeItem item) {
            ancestor = item;
            number = -1;
        }
        
        public void clear() {
            number = -2;
            prelim = mod = shift = change = 0;
            ancestor = thread = null;
        }
    }
    
} // end of class NodeLinkTreeLayout