SOURCE

// 根据父级节点ID获取父节点的index
var getParentIndexByChildpTag = function (nodes, p0TagName) {
    for (var i = 0; i < nodes.length; i++) {
        var cTags = nodes[i].cTag;
        for (var j = 0; cTags && j < cTags.length; j++) {
            if (cTags[j] == p0TagName) {
                return i;
            }
        }
    }
    return -1;
};

// 根据当前节点的index获取所有子节点的index
var getAllChildrenIndexByParentIndex = function (nodes, index) {
    var indexs = [];
    for (var i = 0; nodes[index].cTag && i < nodes[index].cTag.length; i++) {
        for (var j = 0; j < nodes.length; j++) {
            if (nodes[j].pTag[0] == nodes[index].cTag[i]) {
                indexs.push(j);
            }
        }
    }
    return indexs;
};

// 获取对应层的所有节点index
var getLayerIndexs = function (nodes, depth) {
    var indexs = [];
    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].depth == depth) {
            indexs.push(i);
        }
    }
    return indexs;
};

// 判断右边距是否足够
var isRightMarginEnough = function (nodes, node) {
    var parentNodeIndex = getParentIndexByChildpTag(nodes, node.pTag[0]);
    // 插入根节点
    if (parentNodeIndex < 0) {
        return true;
    }
    var brotherNodeIndexs = getAllChildrenIndexByParentIndex(nodes, parentNodeIndex);
    var layerIndexs = getLayerIndexs(nodes, node.depth);
    var leftNodeIndex = brotherNodeIndexs.length > 0 ? brotherNodeIndexs[brotherNodeIndexs.length - 1] : -1;
    var rightNodeLayerIndex = layerIndexs.length > 0 ? layerIndexs.indexOf(leftNodeIndex) + 1 : -1;

    var leftNode = leftNodeIndex >= 0 ? nodes[leftNodeIndex] : undefined;
    var rightNode = (rightNodeLayerIndex >= 0 && rightNodeLayerIndex < layerIndexs.length) ? nodes[layerIndexs[rightNodeLayerIndex]] : undefined;
    if (!rightNode) {
        return true;
    } else if (!leftNode) {
        return rightNode.xOffset - nodes[parentNodeIndex].xOffset > 270 ? true : false;
    } else {
        return rightNode.xOffset - leftNode.xOffset > 270 ? true : false;
    }
};

// 判断左边距是否足够
var isLeftMarginEnough = function (nodes, node) {
    var parentNodeIndex = getParentIndexByChildpTag(nodes, node.pTag[0]);
    // 插入根节点
    if (parentNodeIndex < 0) {
        return true;
    }
    var brotherNodeIndexs = getAllChildrenIndexByParentIndex(nodes, parentNodeIndex);
    var layerIndexs = getLayerIndexs(nodes, node.depth);
    var rightNodeIndex = brotherNodeIndexs.length > 0 ? brotherNodeIndexs[0] : -1;
    var leftNodeLayerIndex = layerIndexs.length > 0 ? layerIndexs.indexOf(rightNodeIndex) - 1 : -1;
    var leftNode = leftNodeLayerIndex >= 0 ? nodes[layerIndexs[leftNodeLayerIndex]] : undefined;
    var rightNode = rightNodeIndex >= 0 ? nodes[rightNodeIndex] : undefined;
    if (!leftNode) {
        return true;
    } else if (!rightNode) {
        return (nodes[parentNodeIndex].xOffset - leftNode.xOffset) >= 270 ? true : false;
    } else {
        return rightNode.xOffset - leftNode.xOffset > 270 ? true : false;
    }
};

// 按照行把node左侧的节点左移,included确定是否包含node及其父节点本身
var moveRowLeft = function (tmpNodes, node, distance, included) {
    var layerIndexs = getLayerIndexs(node.depth);
    var endIndex = layerIndexs.indexOf(node.index);
    endIndex = included ? endIndex + 1 : endIndex;
    for (var i = 0; i < endIndex; i++) {
        tmpNodes[layerIndexs[i]].xOffset = parseInt(tmpNodes[layerIndexs[i]].xOffset) - parseInt(distance);
    }
};

// 把nodeIndexs中的node及其子节点、子节点的子节点……全部左移
var moveAllChildrenNodesLeft = function (nodes, nodeIndexs, distance) {
    for (var i = 0; i < nodeIndexs.length; i++) {
        var node = nodes[nodeIndexs[i]];
        node.xOffset = parseInt(node.xOffset) - distance;
        if (node.cTag) {
            var childrenIndexs = getAllChildrenIndexByParentIndex(nodes, node.index);
            moveAllChildrenNodesLeft(nodes, childrenIndexs, distance);
        }
    }
};

var insertNode = function (tmpNodes, node) {
    var parentNodeIndex = getParentIndexByChildpTag(tmpNodes, node.pTag[0]);
    if (parentNodeIndex < 0) {
        node.depth = node.xOffset = node.yOffset = 0;
        tmpNodes.push(node);
        return tmpNodes;
    }
    var brotherNodeIndexs = getAllChildrenIndexByParentIndex(tmpNodes, parentNodeIndex);
    node.xOffset = parseInt(tmpNodes[parentNodeIndex].xOffset) + 135 * brotherNodeIndexs.length;
    if (isLeftMarginEnough(tmpNodes, node) && isRightMarginEnough(tmpNodes, node)) {
        console.log("左边和右边空间都够");
        // 平行子节及其子节点左移
        moveAllChildrenNodesLeft(tmpNodes, brotherNodeIndexs, 135);
    } else if (!isLeftMarginEnough(tmpNodes, node) && isRightMarginEnough(tmpNodes, node)) {
        consolog.log("左边空间不够，右边够");
        // 左侧节点左移
        var tmpNode = node;
        while (tmpNode.pTag[0] != 1) {
            moveRowLeft(tmpNodes, tmpNode, 135, false);
            var pIndex = getParentIndexByChildpTag(tmpNodes, tmpNode.pTag[0])
            tmpNode = tmpNodes[pIndex];
        }
    } else if (isLeftMarginEnough(tmpNodes, node) && !isRightMarginEnough(tmpNodes, node)) {
        console.log("左边空间够右边不够");
        // 所有节点左移（包含node及其父节点）
        var tmpNode = node;
        while (tmpNode.pTag[0] != 1) {
            moveRowLeft(tmpNodes, tmpNode, 270, true);
            var pIndex = getParentIndexByChildpTag(tmpNodes, tmpNode.pTag[0]);
            tmpNode = tmpNodes[pIndex];
        }
    } else {
        console.log("左右空间不足")
        // 所有节点左移（包含node及其父节点）
        var tmpNode = node;
        while (tmpNode.pTag[0] != 1) {
            moveRowLeft(tmpNodes, tmpNode, 270, true);
            var pIndex = getParentIndexByChildpTag(tmpNodes, tmpNode.pTag[0]);
            tmpNode = tmpNodes[pIndex];
        }
    }
};

var formatData = function (data) {
    data = data.n;
    var nodes = [];
    for (var i = 0; i < data.length; i++) {
        var tmpNode = {};
        tmpNode.index = i;
        if (data[i].c) {
            tmpNode.cTag = data[i].c;
        }
        tmpNode.pTag = [];
        tmpNode.pTag.push(data[i].p[0]);
        tmpNode.pTag.push(data[i].p[1]);
        nodes.push(tmpNode);
    }
    nodes[0].depth = nodes[0].xOffset = nodes[0].yOffset = 0;
    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].cTag) {
            var indexs = getAllChildrenIndexByParentIndex(nodes, i);
            for (var m = 0; m < indexs.length; m++) {
                // 设置depth和yOffset
                nodes[indexs[m]].depth = nodes[i].depth + 1;
                nodes[indexs[m]].yOffset = 180 * nodes[indexs[m]].depth;
                // 设置rn
                if (indexs.length > 1 && m < indexs.length - 1) {
                    nodes[indexs[m]].rn = nodes[indexs[m + 1]].pTag[0];
                }
                // 设置ln
                if (indexs.length > 1 && m > 0) {
                    nodes[indexs[m]].ln = nodes[indexs[m - 1]].pTag[0];
                }
            }
        }
    }
    return nodes;
};

var amendXoffset = function (nodes) {
    var minOffset = 135;
    for (var i = 0; i < nodes.length; i++) {
        minOffset = minOffset > nodes[i].xOffset ? nodes[i].xOffset : minOffset;
    }
    if (minOffset < 0) {
        for (var i = 0; i < nodes.length; i++) {
            nodes[i].xOffset -= minOffset;
        }
    }
};

var getResponse = function (data) {
    var nodes = formatData(data);
    var response = {};
    var tmpNodes = [];
    for (var i = 0; i < nodes.length; i++) {
        insertNode(tmpNodes, nodes[i]);
        // console.log("tmpNodes " + i + "###########");
        //tmpNodes.forEach(function(data){
        //    console.log(data);
        //})
        // console.log("End *******************");
    }
    amendXoffset(tmpNodes);
    for (var i = 0; i < tmpNodes.length; i++) {
        var tmpObject = {};
        tmpObject.p = [tmpNodes[i].xOffset, tmpNodes[i].yOffset, 250, 120];
        if (tmpNodes[i].ln) {
            tmpObject.ln = tmpNodes[i].ln;
        }
        if (tmpNodes[i].rn) {
            tmpObject.rn = tmpNodes[i].rn;
        }
        response[tmpNodes[i].pTag[0]] = tmpObject;
    }
    return response;
};