src/chart/tree/layoutHelper.ts - master - githubmirror/echarts

src/chart/tree/layoutHelper.ts
316 строк11 KB
Ovilia
fix(chord): fix lint errors
07 фев 2025, 10:09
07 фев 2025, 10:0903e2883
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/*
* A third-party license is embedded for some of the code in this file:
* The tree layoutHelper implementation was originally copied from
* "d3.js"(https://github.com/d3/d3-hierarchy) with
* some modifications made for this project.
* (see more details in the comment of the specific method below.)
* The use of the source code of this file is also subject to the terms
* and consitions of the licence of "d3.js" (BSD-3Clause, see
* </licenses/LICENSE-d3>).
*/

/**
 * @file The layout algorithm of node-link tree diagrams. Here we using Reingold-Tilford algorithm to drawing
 *       the tree.
 */

import { TreeNode } from '../../data/Tree';

interface HierNode {
    defaultAncestor: TreeLayoutNode,
    ancestor: TreeLayoutNode,
    prelim: number,
    modifier: number,
    change: number,
    shift: number,
    i: number,
    thread: TreeLayoutNode
}

export interface TreeLayoutNode extends TreeNode {
    parentNode: TreeLayoutNode
    hierNode: HierNode
    children: TreeLayoutNode[]
}
/**
 * Initialize all computational message for following algorithm.
 */
export function init(inRoot: TreeNode) {
    const root = inRoot as TreeLayoutNode;
    root.hierNode = {
        defaultAncestor: null,
        ancestor: root,
        prelim: 0,
        modifier: 0,
        change: 0,
        shift: 0,
        i: 0,
        thread: null
    };

    const nodes = [root];
    let node;
    let children;

    while (node = nodes.pop()) { // jshint ignore:line
        children = node.children;
        if (node.isExpand && children.length) {
            const n = children.length;
            for (let i = n - 1; i >= 0; i--) {
                const child = children[i];
                child.hierNode = {
                    defaultAncestor: null,
                    ancestor: child,
                    prelim: 0,
                    modifier: 0,
                    change: 0,
                    shift: 0,
                    i: i,
                    thread: null
                };
                nodes.push(child);
            }
        }
    }
}

/**
 * The implementation of this function was originally copied from "d3.js"
 * <https://github.com/d3/d3-hierarchy/blob/4c1f038f2725d6eae2e49b61d01456400694bac4/src/tree.js>
 * with some modifications made for this program.
 * See the license statement at the head of this file.
 *
 * Computes a preliminary x coordinate for node. Before that, this function is
 * applied recursively to the children of node, as well as the function
 * apportion(). After spacing out the children by calling executeShifts(), the
 * node is placed to the midpoint of its outermost children.
 */
export function firstWalk(node: TreeLayoutNode, separation: SeparationFunc) {
    const children = node.isExpand ? node.children : [];
    const siblings = node.parentNode.children;
    const subtreeW = node.hierNode.i ? siblings[node.hierNode.i - 1] : null;
    if (children.length) {
        executeShifts(node);
        const midPoint = (children[0].hierNode.prelim + children[children.length - 1].hierNode.prelim) / 2;
        if (subtreeW) {
            node.hierNode.prelim = subtreeW.hierNode.prelim + separation(node, subtreeW);
            node.hierNode.modifier = node.hierNode.prelim - midPoint;
        }
        else {
            node.hierNode.prelim = midPoint;
        }
    }
    else if (subtreeW) {
        node.hierNode.prelim = subtreeW.hierNode.prelim + separation(node, subtreeW);
    }
    node.parentNode.hierNode.defaultAncestor = apportion(
        node,
        subtreeW,
        node.parentNode.hierNode.defaultAncestor || siblings[0],
        separation
    );
}


/**
 * The implementation of this function was originally copied from "d3.js"
 * <https://github.com/d3/d3-hierarchy/blob/4c1f038f2725d6eae2e49b61d01456400694bac4/src/tree.js>
 * with some modifications made for this program.
 * See the license statement at the head of this file.
 *
 * Computes all real x-coordinates by summing up the modifiers recursively.
 */
export function secondWalk(node: TreeLayoutNode) {
    const nodeX = node.hierNode.prelim + node.parentNode.hierNode.modifier;
    node.setLayout({x: nodeX}, true);
    node.hierNode.modifier += node.parentNode.hierNode.modifier;
}


export function separation(cb?: SeparationFunc) {
    return arguments.length ? cb : defaultSeparation;
}

/**
 * Transform the common coordinate to radial coordinate.
 */
export function radialCoordinate(rad: number, r: number) {
    rad -= Math.PI / 2;
    return {
        x: r * Math.cos(rad),
        y: r * Math.sin(rad)
    };
}

/**
 * All other shifts, applied to the smaller subtrees between w- and w+, are
 * performed by this function.
 *
 * The implementation of this function was originally copied from "d3.js"
 * <https://github.com/d3/d3-hierarchy/blob/4c1f038f2725d6eae2e49b61d01456400694bac4/src/tree.js>
 * with some modifications made for this program.
 * See the license statement at the head of this file.
 */
function executeShifts(node: TreeLayoutNode) {
    const children = node.children;
    let n = children.length;
    let shift = 0;
    let change = 0;
    while (--n >= 0) {
        const child = children[n];
        child.hierNode.prelim += shift;
        child.hierNode.modifier += shift;
        change += child.hierNode.change;
        shift += child.hierNode.shift + change;
    }
}

/**
 * The implementation of this function was originally copied from "d3.js"
 * <https://github.com/d3/d3-hierarchy/blob/4c1f038f2725d6eae2e49b61d01456400694bac4/src/tree.js>
 * with some modifications made for this program.
 * See the license statement at the head of this file.
 *
 * The core of the algorithm. Here, a new subtree is combined with the
 * previous subtrees. Threads are used to traverse the inside and outside
 * contours of the left and right subtree up to the highest common level.
 * Whenever two nodes of the inside contours conflict, we compute the left
 * one of the greatest uncommon ancestors using the function nextAncestor()
 * and call moveSubtree() to shift the subtree and prepare the shifts of
 * smaller subtrees. Finally, we add a new thread (if necessary).
 */
function apportion(
    subtreeV: TreeLayoutNode,
    subtreeW: TreeLayoutNode,
    ancestor: TreeLayoutNode,
    separation: SeparationFunc
): TreeLayoutNode {

    if (subtreeW) {
        let nodeOutRight = subtreeV;
        let nodeInRight = subtreeV;
        let nodeOutLeft = nodeInRight.parentNode.children[0];
        let nodeInLeft = subtreeW;

        let sumOutRight = nodeOutRight.hierNode.modifier;
        let sumInRight = nodeInRight.hierNode.modifier;
        let sumOutLeft = nodeOutLeft.hierNode.modifier;
        let sumInLeft = nodeInLeft.hierNode.modifier;

        while (nodeInLeft = nextRight(nodeInLeft), nodeInRight = nextLeft(nodeInRight), nodeInLeft && nodeInRight) {
            nodeOutRight = nextRight(nodeOutRight);
            nodeOutLeft = nextLeft(nodeOutLeft);
            nodeOutRight.hierNode.ancestor = subtreeV;
            const shift = nodeInLeft.hierNode.prelim + sumInLeft - nodeInRight.hierNode.prelim
                    - sumInRight + separation(nodeInLeft, nodeInRight);
            if (shift > 0) {
                moveSubtree(nextAncestor(nodeInLeft, subtreeV, ancestor), subtreeV, shift);
                sumInRight += shift;
                sumOutRight += shift;
            }
            sumInLeft += nodeInLeft.hierNode.modifier;
            sumInRight += nodeInRight.hierNode.modifier;
            sumOutRight += nodeOutRight.hierNode.modifier;
            sumOutLeft += nodeOutLeft.hierNode.modifier;
        }
        if (nodeInLeft && !nextRight(nodeOutRight)) {
            nodeOutRight.hierNode.thread = nodeInLeft;
            nodeOutRight.hierNode.modifier += sumInLeft - sumOutRight;

        }
        if (nodeInRight && !nextLeft(nodeOutLeft)) {
            nodeOutLeft.hierNode.thread = nodeInRight;
            nodeOutLeft.hierNode.modifier += sumInRight - sumOutLeft;
            ancestor = subtreeV;
        }
    }
    return ancestor;
}

/**
 * This function is used to traverse the right contour of a subtree.
 * It returns the rightmost child of node or the thread of node. The function
 * returns null if and only if node is on the highest depth of its subtree.
 */
function nextRight(node: TreeLayoutNode): TreeLayoutNode {
    const children = node.children;
    return children.length && node.isExpand ? children[children.length - 1] : node.hierNode.thread;
}

/**
 * This function is used to traverse the left contour of a subtree (or a subforest).
 * It returns the leftmost child of node or the thread of node. The function
 * returns null if and only if node is on the highest depth of its subtree.
 */
function nextLeft(node: TreeLayoutNode) {
    const children = node.children;
    return children.length && node.isExpand ? children[0] : node.hierNode.thread;
}

/**
 * If nodeInLeft’s ancestor is a sibling of node, returns nodeInLeft’s ancestor.
 * Otherwise, returns the specified ancestor.
 */
function nextAncestor(
    nodeInLeft: TreeLayoutNode,
    node: TreeLayoutNode,
    ancestor: TreeLayoutNode
): TreeLayoutNode {
    return nodeInLeft.hierNode.ancestor.parentNode === node.parentNode
        ? nodeInLeft.hierNode.ancestor : ancestor;
}

/**
 * The implementation of this function was originally copied from "d3.js"
 * <https://github.com/d3/d3-hierarchy/blob/4c1f038f2725d6eae2e49b61d01456400694bac4/src/tree.js>
 * with some modifications made for this program.
 * See the license statement at the head of this file.
 *
 * Shifts the current subtree rooted at wr.
 * This is done by increasing prelim(w+) and modifier(w+) by shift.
 */
function moveSubtree(
    wl: TreeLayoutNode,
    wr: TreeLayoutNode,
    shift: number
) {
    const change = shift / (wr.hierNode.i - wl.hierNode.i);
    wr.hierNode.change -= change;
    wr.hierNode.shift += shift;
    wr.hierNode.modifier += shift;
    wr.hierNode.prelim += shift;
    wl.hierNode.change += change;
}

/**
 * The implementation of this function was originally copied from "d3.js"
 * <https://github.com/d3/d3-hierarchy/blob/4c1f038f2725d6eae2e49b61d01456400694bac4/src/tree.js>
 * with some modifications made for this program.
 * See the license statement at the head of this file.
 */
function defaultSeparation(node1: TreeLayoutNode, node2: TreeLayoutNode): number {
    return node1.parentNode === node2.parentNode ? 1 : 2;
}

interface SeparationFunc {
    (node1: TreeLayoutNode, node2: TreeLayoutNode): number
}