/**
 * Created by Mai on 2017/3/17.
 */
var idTree = {
    createNew: function (setting) {
        var _setting = {
            id: 'id',
            pid: 'pid',
            nid: 'nid',
            rootId: -1,
            autoUpdate: false
        };

        var _eventType = {
            editedData: 'editedData'
        };

        var tools = {
            findNode: function (nodes, check) {
                for (var i = 0; i < nodes.length; i++) {
                    if (check(nodes[i])) {
                        return nodes[i];
                    }
                }
                return null;
            },
            reSortNodes: function (nodes, recursive) {

                var temp = [], first;
                var findFirstNode = function (nodes) {
                    return tools.findNode(nodes, function (node) {
                        return node.preSibling === null;
                    });
                };
                var moveNode = function (node, orgArray, newArray, newIndex) {
                    var current = node, currentIndex, next;
                    // 不能递归：同级节点很多时，即使链正确也会超过浏览器调用栈。
                    while (current) {
                        currentIndex = orgArray.indexOf(current);
                        if (currentIndex < 0) {
                            break;
                        }
                        orgArray.splice(currentIndex, 1);
                        newArray.splice(newIndex, 0, current);
                        newIndex++;

                        next = current.nextSibling;
                        // next 不在当前同级数组中，说明它已处理、跨层、缺失、自指或成环。
                        // 停止当前链，剩余节点交给外层 while 继续显示。
                        if (!next || orgArray.indexOf(next) < 0) {
                            break;
                        }
                        current = next;
                    }
                };
                if (nodes.length === 0) {
                    return nodes;
                }
                if (recursive) {
                    nodes.forEach(function (node) {
                        node.children = tools.reSortNodes(node.children, recursive);
                    });
                }
                while (nodes.length > 0) {
                    first = findFirstNode(nodes);
                    first = first ? first : nodes[0];
                    moveNode(first, nodes, temp, temp.length);
                }
                nodes = null;
                tools.reSiblingNodes(temp);
                return temp;
            },
            reSiblingNodes: function (nodes) {
                var i;
                for (i = 0; i < nodes.length; i++) {
                    nodes[i].preSibling = (i === 0) ? null : nodes[i - 1];
                    nodes[i].nextSibling = (i === nodes.length - 1) ? null : nodes[i + 1];
                }
            },
            // 在nodes中，从iIndex（包括）开始全部移除
            removeNodes: function (tree, parent, iIndex, count) {
                var children = parent ? parent.children : tree.roots;
                var pre = (iIndex < 0 || iIndex >= children.length) ? null : children[iIndex].preSibling;
                var next = (pre && iIndex + count - 1 < children.length) ? children[iIndex + count] : null;
                if (pre) {
                    pre.setNextSibling(next);
                } else if (next) {
                    next.preSibling = null;
                }
                if (arguments.length === 4) {
                    children.splice(iIndex, count);
                } else {
                    children.splice(iIndex, children.length - iIndex);
                }
            },
            // 在parent.children/tree.roots中增加nodes, 位置从index开始
            addNodes: function (tree, parent, nodes, iIndex) {
                var children = parent ? parent.children : tree.roots;
                var pre, next, i;
                if (nodes.length === 0) { return; }
                if (arguments.length === 4) {
                    pre = (iIndex <= 0 || iIndex > children.length) ? null : children[iIndex - 1];
                    next = pre ? pre.nextSibling : null;
                } else if (arguments.length === 3) {
                    pre = children.length === 0 ? null : children[children.length - 1];
                    next = null;
                }
                if (pre) {
                    pre.setNextSibling(nodes[0]);
                } else {
                    nodes[0].preSibling = null;
                }
                nodes[nodes.length - 1].setNextSibling(next);
                for (i = 0; i < nodes.length; i++) {
                    if (arguments.length === 4) {
                        children.splice(iIndex + i, 0, nodes[i]);
                    } else if (arguments.length === 3) {
                        children.push(nodes[i]);
                    }
                    nodes[i].setParent(parent ? parent : null);
                }
            },
            sortTreeItems: function (tree) {
                var addItems = function (items) {
                    var i;
                    for (i = 0; i < items.length; i++) {
                        tree.items.push(items[i]);
                        addItems(items[i].children);
                    }
                };
                tree.items.splice(0, tree.items.length);
                addItems(tree.roots);
            },
            addUpdateDataForParent: function (datas, nodes, pid) {
                nodes.forEach(function (node) {
                    datas.push({ type: 'update', data: node.tree.getDataTemplate(node.getID(), pid, node.getNextSiblingID()) });
                });
            },
            addUpdateDataForNextSibling: function (datas, node, nid) {
                if (node) {
                    datas.push({ type: 'update', data: node.tree.getDataTemplate(node.getID(), node.getParentID(), nid) });
                }
            }
        };

        var Node = function (tree, data) {
            // 以下的属性，本单元外均不可直接修改
            this.tree = tree;
            this.data = data;
            this.children = [];

            this.parent = null;
            this.nextSibling = null;
            this.preSibling = null;

            this.expanded = true;
            this.visible = true;

            this.visible = true;
        };

        Node.prototype.getID = function () {
            return this.data[this.tree.setting.id];
        };
        Node.prototype.getParentID = function () {
            return this.parent ? this.parent.getID() : -1;
        };
        Node.prototype.getNextSiblingID = function () {
            return this.nextSibling ? this.nextSibling.getID() : -1;
        };

        Node.prototype.setParent = function (parent) {
            this.parent = parent;
            if (this.tree.setting.autoUpdate) {
                this.data[this.tree.setting.pid] = this.getParentID();
            }
        };
        Node.prototype.setNextSibling = function (nextSibling) {
            this.nextSibling = nextSibling;
            if (nextSibling) {
                nextSibling.preSibling = this;
            }
            if (this.tree.setting.autoUpdate) {
                this.data[this.tree.setting.nid] = this.getNextSiblingID();
            }
        }

        Node.prototype.firstChild = function () {
            return this.children.length === 0 ? null : this.children[0];
        };
        Node.prototype.lastChild = function () {
            return this.children.length === 0 ? null : this.children[this.children.length - 1];
        };

        Node.prototype.depth = function () {
            return this.parent ? this.parent.depth() + 1 : 0;
        };
        Node.prototype.isFirst = function () {
            if (this.parent) {
                return this.parent.children.indexOf(this) === 0 ? true : false;
            } else {
                return this.tree.roots.indexOf(this) === 0 ? true : false;
            }
        };
        Node.prototype.isLast = function () {
            if (this.parent) {
                return this.parent.children.indexOf(this) === this.parent.children.length - 1 ? true : false;
            } else {
                return this.tree.roots.indexOf(this) === this.tree.roots.length - 1 ? true : false;
            }
        };
        Node.prototype.siblingIndex = function () {
            return this.parent ? this.parent.children.indexOf(this) : this.tree.roots.indexOf(this);
        };
        Node.prototype.posterityCount = function () {
            var iCount = 0;
            if (this.children.length !== 0) {
                iCount += this.children.length;
                this.children.forEach(function (child) {
                    iCount += child.posterityCount();
                });
            }
            return iCount;
            /*return (node.children.length === 0) ? 0 : node.children.reduce(function (x, y) {
             return x.posterityCount() + y.posterityCount();
             }) + node.children.count;*/
        };


        Node.prototype.posterityLeafCount = function () {
            return this.getPosterity().filter(item => !item.children.length).length;
        };


        // 获取节点所有后代节点
        Node.prototype.getPosterity = function () {
            let posterity = [];
            getNodes(this.children);
            return posterity;
            function getNodes(nodes) {
                for (let node of nodes) {
                    posterity.push(node);
                    if (node.children.length > 0) {
                        getNodes(node.children);
                    }
                }
            }
        };

        // 担心链有问题，preSibling不靠谱的话，按照显示顺序算preSibling
        Node.prototype.prevNode = function () {
            const parent = this.parent || this.tree.roots;
            if (!parent) {
                return null;
            }
            const children = parent === this.tree.roots ? this.tree.roots : parent.children;
            const index = children.indexOf(this);
            return children[index - 1] || null;
        }

        Node.prototype.setExpanded = function (expanded) {
            var setNodesVisible = function (nodes, visible) {
                nodes.forEach(function (node) {
                    node.visible = visible;
                    setNodesVisible(node.children, visible && node.expanded);
                })
            };
            this.expanded = expanded;
            setNodesVisible(this.children, expanded);
        };
        /*Node.prototype.vis = function () {
         return this.parent ? this.parent.vis() && this.parent.expanded() : true;
         };*/
        Node.prototype.serialNo = function () {
            return this.tree.items.indexOf(this);
        };

        Node.prototype.addChild = function (node) {
            var preSibling = this.children.length === 0 ? null : this.children[this.children.length - 1];
            node.parent = this;
            if (preSibling) {
                preSibling.nextSibling = node;
            }
            node.preSibling = preSibling;
            this.children.push(node);
        };
        Node.prototype.removeChild = function (node) {
            var preSibling = node.preSibling, nextSibling = node.nextSibling;
            if (preSibling) {
                preSibling.nextSibling = nextSibling;
            }
            if (nextSibling) {
                nextSibling.preSibling = preSibling;
            }
            this.children.splice(node.siblingIndex, 1);
        };

        Node.prototype.canUpLevel = function () {
            return this.parent ? true : false;
        };
        Node.prototype.getUpLevelData = function () {
            var data = [];
            if (this.canUpLevel()) {
                if (!this.isLast()) {
                    tools.addUpdateDataForParent(data, this.parent.children.slice(this.siblingIndex() + 1), this.getID());
                }
                if (this.preSibling) {
                    tools.addUpdateDataForNextSibling(data, this.preSibling, this.tree.setting.rootId);
                }
                tools.addUpdateDataForNextSibling(data, this.parent, this.getID());
                data.push({ type: 'update', data: this.tree.getDataTemplate(this.getID(), this.parent.getParentID(), this.parent.getNextSiblingID()) });
            }
            return data;
        };
        Node.prototype.upLevel = function () {
            var result = { success: false, updateDatas: [] };
            var iIndex = this.parent.children.indexOf(this), orgParent = this.parent, newNextSibling = this.parent.nextSibling;
            if (this.canUpLevel) {
                // NextSiblings become child
                tools.addNodes(this.tree, this, this.parent.children.slice(iIndex + 1));
                // Orginal Parent remove node and nextSiblings
                tools.removeNodes(this.tree, this.parent, iIndex);
                // New Parent add node
                tools.addNodes(this.tree, this.parent.parent, [this], this.parent.siblingIndex() + 1);
                if (!this.expanded) {
                    this.setExpanded(true);
                }
                result.success = true;
            }
            return result;
        };

        Node.prototype.canDownLevel = function () {
            return !this.isFirst();
        };
        Node.prototype.getDownLevelData = function () {
            var data = [];
            if (this.canDownLevel()) {
                if (this.preSibling.children.length !== 0) {
                    tools.addUpdateDataForNextSibling(data, this.preSibling.lastChild(), this.getID());
                }
                tools.addUpdateDataForNextSibling(data, this.preSibling, this.getNextSiblingID());
                data.push({ type: 'update', data: this.tree.getDataTemplate(this.getID(), this.preSibling.getID(), this.tree.setting.rootId) });
            }
            return data;
        };
        Node.prototype.downLevel = function () {
            var success = false, iIndex = this.parent ? this.parent.children.indexOf(this) : this.tree.roots.indexOf(this);
            var newParent = this.preSibling;
            if (this.canDownLevel()) {
                tools.removeNodes(this.tree, this.parent, this.siblingIndex(), 1);
                tools.addNodes(this.tree, this.preSibling, [this]);
                if (!newParent.expanded) {
                    newParent.setExpanded(true);
                }
                success = true;
            }
            return success;
        };

        Node.prototype.canUpMove = function () {
            return !this.isFirst();
        };
        Node.prototype.getUpMoveData = function () {
            var data = [];
            if (this.canUpMove()) {
                if (this.preSibling.preSibling) {
                    tools.addUpdateDataForNextSibling(data, this.preSibling.preSibling, this.getID());
                }
                tools.addUpdateDataForNextSibling(data, this.preSibling, this.getNextSiblingID());
                tools.addUpdateDataForNextSibling(data, this, this.preSibling.getID());
            }
            return data;
        };
        Node.prototype.upMove = function () {
            var success = false;
            var iIndex = this.siblingIndex(), belongArray = this.parent ? this.parent.children : this.tree.roots, orgPre = this.preSibling;
            if (this.canUpMove()) {
                if (orgPre.preSibling) {
                    orgPre.preSibling.setNextSibling(this);
                } else {
                    this.preSibling = null;
                }
                orgPre.setNextSibling(this.nextSibling);
                this.setNextSibling(orgPre);
                belongArray.splice(iIndex, 1);
                belongArray.splice(iIndex - 1, 0, this);
                tools.sortTreeItems(this.tree);
                success = true;
            }
            return success;
        };

        Node.prototype.canDownMove = function () {
            return !this.isLast();
        };
        Node.prototype.getDownMoveData = function () {
            var data = [];
            if (this.canDownMove()) {
                if (this.preSibling) {
                    tools.addUpdateDataForNextSibling(data, this.preSibling, this.nextSibling.getID());
                }
                tools.addUpdateDataForNextSibling(data, this, this.nextSibling.getNextSiblingID());
                tools.addUpdateDataForNextSibling(data, this.nextSibling, this.getID());
            }
            return data;
        };
        Node.prototype.downMove = function () {
            var success = false;
            var iIndex = this.siblingIndex(), belongArray = this.parent ? this.parent.children : this.tree.roots, orgNext = this.nextSibling;
            if (this.canDownMove()) {
                if (this.preSibling) {
                    this.preSibling.setNextSibling(orgNext);
                } else if (orgNext) {
                    orgNext.preSibling = null;
                }
                this.setNextSibling(orgNext.nextSibling);
                orgNext.setNextSibling(this);
                belongArray.splice(iIndex, 1);
                belongArray.splice(iIndex + 1, 0, this);
                tools.sortTreeItems(this.tree);
                success = true;
            }
            return success;
        };

        var Tree = function (setting) {
            this.nodes = {};
            this.roots = [];
            this.items = [];
            this.setting = setting;
            this.prefix = 'id_';
            this.selected = null;

            this.event = {};
            this.eventType = _eventType;
        };

        Tree.prototype.getDataTemplate = function (id, pid, nid) {
            var data = {};
            data[this.setting.id] = id;
            data[this.setting.pid] = pid;
            data[this.setting.nid] = nid;
            return data;
        };

        Tree.prototype.maxNodeID = (function () {
            var maxID = 0;
            return function (ID) {
                if (arguments.length === 0) {
                    return maxID;
                } else {
                    maxID = Math.max(maxID, ID);
                }
            };
        })();
        Tree.prototype.rangeNodeID = (function () {
            var rangeID = -1;
            return function (ID) {
                if (arguments.length === 0) {
                    return rangeID;
                } else {
                    rangeID = Math.max(rangeID, ID);
                }
            }
        })();
        Tree.prototype.newNodeID = function () {
            if (this.rangeNodeID() == -1) {
                return this.maxNodeID() + 1;
            } else {
                if (this.maxNodeID() < this.rangeNodeID()) {
                    return this.maxNodeID() + 1;
                } else {
                    return -1;
                }
            }
            /*if (this.maxID >= this.rangeNodeID() || this.rangeNodeID === -1) {
             return -1;
             } else {
             return this.maxNodeID() + 1;
             }*/
        };

        Tree.prototype.clearNodes = function () {
            this.nodes = {};
            this.roots = [];
            this.items = [];
        };

        Tree.prototype.loadDatas = function (datas) {
            var prefix = this.prefix, i, node, parent, next, that = this;

            this.nodes = {};
            this.roots = [];
            this.items = [];

            // prepare index
            datas.forEach(function (data) {
                var node = new Node(that, data);
                that.nodes[prefix + data[that.setting.id]] = node;
                that.maxNodeID(data[that.setting.id]);
            });
            // set parent by pid, set nextSibling by nid
            datas.forEach(function (data) {
                node = that.nodes[prefix + data[that.setting.id]];
                if (data[that.setting.pid] == that.setting.rootId) {
                    that.roots.push(node);
                } else {
                    parent = that.nodes[prefix + data[that.setting.pid]];
                    if (parent) {
                        node.parent = parent;
                        parent.children.push(node);
                    }
                }
                if (data[that.setting.nid] !== that.setting.rootId) {
                    next = that.nodes[prefix + data[that.setting.nid]];
                    if (next) {
                        node.nextSibling = next;
                        next.preSibling = node;
                    }
                }
            })
            // sort by nid
            this.roots = tools.reSortNodes(this.roots, true);
            tools.sortTreeItems(this);
        };
        Tree.prototype.firstNode = function () {
            return this.roots.length === 0 ? null : this.roots[0];
        };
        Tree.prototype.findNode = function (id) {
            return this.nodes[this.prefix + id];
        };
        Tree.prototype.count = function () {
            var iCount = 0;
            if (this.roots.length !== 0) {
                iCount += this.roots.length;
                this.roots.forEach(function (node) {
                    iCount += node.posterityCount();
                });
            }
            return iCount;
        };

        Tree.prototype.insert = function (parentID, nextSiblingID) {
            var newID = this.newNodeID(), node = null, data = {};
            var parent = parentID == -1 ? null : this.nodes[this.prefix + parentID];
            var nextSibling = nextSiblingID == -1 ? null : this.nodes[this.prefix + nextSiblingID];
            if (newID !== -1) {
                data = {};
                data[this.setting.id] = newID;
                data[this.setting.pid] = parent ? parent.getID() : this.setting.rootId;
                data[this.setting.nid] = nextSibling ? nextSibling.getID() : this.setting.rootId;
                node = new Node(this, data);
                if (nextSibling) {
                    tools.addNodes(this, parent, [node], nextSibling.siblingIndex());
                } else {
                    tools.addNodes(this, parent, [node]);
                }
                this.nodes[this.prefix + newID] = node;
                tools.sortTreeItems(this);
                this.maxNodeID(newID);
            }
            return node;
        };
        Tree.prototype.m_insert = function (datas, parentID, nextSiblingID) {
            // var newID = this.newNodeID(), node = null, data = {};
            var parent = parentID == -1 ? null : this.nodes[this.prefix + parentID];
            var nextSibling = nextSiblingID == -1 ? null : this.nodes[this.prefix + nextSiblingID];
            let preInsertNode = null, nodes = [];
            for (let d of datas) {
                let node = new Node(this, d.data);
                if (preInsertNode == null) {
                    if (nextSibling) {
                        tools.addNodes(this, parent, [node], nextSibling.siblingIndex());
                    } else {
                        tools.addNodes(this, parent, [node]);
                    }
                } else {
                    tools.addNodes(this, parent, [node], preInsertNode.siblingIndex());
                }
                this.nodes[this.prefix + d.data.ID] = node;
                if (preInsertNode) node.setNextSibling(preInsertNode);
                preInsertNode = node;
                nodes.push(node);
            }
            tools.sortTreeItems(this);
            return nodes;
        };



        Tree.prototype.insertByID = function (newID, parentID, nextSiblingID) {
            var node = null, data = {};
            var parent = parentID == -1 ? null : this.nodes[this.prefix + parentID];
            var nextSibling = nextSiblingID == -1 ? null : this.nodes[this.prefix + nextSiblingID];
            if (newID) {
                data = {};
                data[this.setting.id] = newID;
                data[this.setting.pid] = parent ? parent.getID() : this.setting.rootId;
                data[this.setting.nid] = nextSibling ? nextSibling.getID() : this.setting.rootId;
                node = new Node(this, data);
                if (nextSibling) {
                    tools.addNodes(this, parent, [node], nextSibling.siblingIndex());
                } else {
                    tools.addNodes(this, parent, [node]);
                }
                this.nodes[this.prefix + newID] = node;
                tools.sortTreeItems(this);
            }
            return node;
        };
        Tree.prototype.getInsertData = function (parentID, nextSiblingID) {
            var data = [];
            var newID = this.newNodeID();
            var parent = parentID == -1 ? null : this.nodes[this.prefix + parentID];
            var nextSibling = nextSiblingID == -1 ? null : this.nodes[this.prefix + nextSiblingID];
            if (newID !== -1) {
                data.push({ type: 'new', data: this.getDataTemplate(newID, parent ? parent.getID() : this.setting.rootId, nextSibling ? nextSibling.getID() : this.setting.rootId) });

                if (nextSibling && nextSibling.preSibling) {
                    tools.addUpdateDataForNextSibling(data, nextSibling.preSibling, newID);
                } else if (parent && parent.children.length !== 0) {
                    tools.addUpdateDataForNextSibling(data, parent.lastChild(), newID);
                } else if (!parent && this.roots.length !== 0) {
                    tools.addUpdateDataForNextSibling(data, this.roots[this.roots.length - 1], newID);
                }
            }
            return data;
        };
        //插入多行
        Tree.prototype.getInsertDatas = function (rowCount, parentID, nextSiblingID) {
            let data = [], preInsertID = null, lastID;
            let parent = parentID == -1 ? null : this.nodes[this.prefix + parentID];
            let nextSibling = nextSiblingID == -1 ? null : this.nodes[this.prefix + nextSiblingID];
            for (let i = 0; i < rowCount; i++) {//先插入的在最后，后插的在最前
                let newID = this.newNodeID();
                if (newID !== -1) {
                    if (preInsertID == null) {//说明是第一个插入的
                        data.push({ type: 'new', data: this.getDataTemplate(newID, parent ? parent.getID() : this.setting.rootId, nextSibling ? nextSibling.getID() : this.setting.rootId) });
                    } else {//其它的下一节点ID取上一个插入的节点
                        data.push({ type: 'new', data: this.getDataTemplate(newID, parent ? parent.getID() : this.setting.rootId, preInsertID) });
                    }
                    this.maxNodeID(newID);
                    preInsertID = newID;
                }
            }
            if (nextSibling && nextSibling.preSibling) {
                tools.addUpdateDataForNextSibling(data, nextSibling.preSibling, preInsertID);
            } else if (parent && parent.children.length !== 0) {
                tools.addUpdateDataForNextSibling(data, parent.lastChild(), preInsertID);
            } else if (!parent && this.roots.length !== 0) {
                tools.addUpdateDataForNextSibling(data, this.roots[this.roots.length - 1], preInsertID);
            }
            return data;

        };
        Tree.prototype.insertByData = function (data, parentID, nextSiblingID) {
            var parent = parentID == -1 ? null : this.nodes[this.prefix + parentID];
            var nextSibling = nextSiblingID == -1 ? null : this.nodes[this.prefix + nextSiblingID];
            var node = this.nodes[this.prefix + data[this.setting.id]];
            if (node) {
                return node;
            } else {
                node = new Node(this, data);
                if (nextSibling) {
                    tools.addNodes(this, parent, [node], nextSibling.siblingIndex());
                } else {
                    tools.addNodes(this, parent, [node]);
                }
                this.nodes[this.prefix + data[this.setting.id]] = node;
                tools.sortTreeItems(this);
                this.maxNodeID(data[this.setting.id]);
                return node;
            }
        };
        // 插入离散节点
        Tree.prototype.insertByDatas = function (datas) {
            const nodes = [];
            datas.forEach(item => {
                const node = this.insertByData(item, item.ParentID, item.NextSiblingID);
                nodes.push(node);
            });
            return nodes;
        };
        //批量新增节点到节点后项，节点已有树结构数据
        Tree.prototype.insertDatasTo = function (preData, datas) {
            let rst = [];
            for (let data of datas) {
                this.nodes[this.prefix + data.ID] = new Node(this, data.ID);
                this.nodes[this.prefix + data.ID]['data'] = data;
                rst.push(this.nodes[this.prefix + data.ID]);
            }
            for (let data of datas) {
                let node = this.nodes[this.prefix + data.ID];
                let parent = data.ParentID == -1 ? null : this.nodes[this.prefix + data.ParentID];
                node.parent = parent;
                if (!parent) {
                    this.roots.push(node);
                }
                else {
                    parent.children.push(node);
                }
                let next = data.NextSiblingID == -1 ? null : this.nodes[this.prefix + data.NextSiblingID];
                node.nextSibling = next;
                if (next) {
                    next.preSibling = node;
                }
            }
            let preNode = this.nodes[this.prefix + preData.ID];
            if (preNode) {
                preNode.nextSibling = this.nodes[this.prefix + preData.NextSiblingID] ? this.nodes[this.prefix + preData.NextSiblingID] : null;
                if (preNode.nextSibling) {
                    preNode.nextSibling.preSibling = preNode;
                }
            }
            //resort
            this.roots = tools.reSortNodes(this.roots, true);
            tools.sortTreeItems(this);
            return rst;
        };
        Tree.prototype.delete = function (node) {
            var success = false, that = this;
            if (node) success = that.m_delete([node]);
            return success;
        };
        Tree.prototype.m_delete = function (nodes) {
            let success = false, that = this;
            let deleteIdIndex = function (nodes) {
                nodes.forEach(function (node) {
                    delete that.nodes[that.prefix + node.getID()];
                    deleteIdIndex(node.children);
                })
            };
            for (let n of nodes) {
                deleteIdIndex([n]);
                if (n.preSibling) {
                    n.preSibling.setNextSibling(n.nextSibling);
                } else if (n.nextSibling) {
                    n.nextSibling.preSibling = null;
                }
                if (n.parent) {
                    n.parent.children.splice(n.siblingIndex(), 1);
                } else {
                    this.roots.splice(n.siblingIndex(), 1);
                }
            }
            tools.sortTreeItems(this);
            success = true;
            return success;
        };

        Tree.prototype.m_upLevel = function (nodes) {//原先的父节点变成前一个节点，原先的兄弟节点变成子节点
            let o_parent = nodes[0].parent;//原来的父节点
            let o_next = o_parent.nextSibling;//父节点的下一节点
            let o_pre = nodes[0].preSibling;
            let o_children = o_parent.children;//旧的所有兄弟节点
            let children = o_parent.parent ? o_parent.parent.children : this.roots;//新的兄弟节点
            let last;
            let lastNext;//最后一个选中节点后面的所有兄弟节点变成最后一个节点的子节点
            for (let i = 0; i < nodes.length; i++) {
                let index = children.indexOf(o_parent) + 1;
                children.splice(index + i, 0, nodes[i]);//往新的父节点的子节点插入节点
                o_children.splice(nodes[i].siblingIndex(), 1);//旧的数组删除节点
                if (i == 0) {//第一个节点变成原来父节点的下一节点
                    o_parent.setNextSibling(nodes[i]);
                    if (o_pre) o_pre.setNextSibling(null); //第一个选中节点的前一节点的下一节点设置为空
                }
                nodes[i].setParent(o_parent.parent);
                last = nodes[i];
                lastNext = last.nextSibling;
            }
            last.setNextSibling(o_next);//最后一个选中的节点的下一个节点设置为原父节点的下一节点
            if (lastNext) {
                let t_index = o_children.indexOf(lastNext);
                for (let j = t_index; j < o_children.length; j++) {//剩下的添加为最后一个选中节点的子节点
                    last.addChild(o_children[j]);
                }
                if (o_children.length > t_index) o_children.splice(t_index, o_children.length - t_index);//从原先的children中移除
            }
            if (o_parent.parent && !o_parent.parent.expanded) o_parent.parent.setExpanded(true);
            tools.sortTreeItems(this);
            return true;
        };
        Tree.prototype.getUpLevelDatas = function (nodes) {
            //getParentID
            let o_parentID = nodes[0].getParentID();
            let o_children = nodes[0].parent.children;//旧的所有兄弟节点
            let o_pre = nodes[0].preSibling;
            let new_parentID = nodes[0].parent.getParentID();
            let o_nextID = nodes[0].parent.getNextSiblingID();
            let dataMap = {}, updateDatas = [], lastID, lastNext;
            for (let i = 0; i < nodes.length; i++) {
                if (i == 0) {
                    dataMap[o_parentID] = { "ID": o_parentID, "NextSiblingID": nodes[i].getID() };
                    if (o_pre) dataMap[o_pre.getID()] = { "ID": o_pre.getID(), "NextSiblingID": -1 }; //nodes[i].preSibling.setNextSibling(null);
                }
                dataMap[nodes[i].getID()] = { "ID": nodes[i].getID(), "ParentID": new_parentID };
                lastID = nodes[i].getID();
                lastNext = nodes[i].nextSibling;
            }
            if (dataMap[lastID] !== undefined) {
                dataMap[lastID].NextSiblingID = o_nextID;
            }
            if (lastNext) {
                let t_index = o_children.indexOf(lastNext);
                for (let j = t_index; j < o_children.length; j++) {//剩下的添加为最后一个选中节点的子节点
                    dataMap[o_children[j].getID()] = { "ID": o_children[j].getID(), "ParentID": lastID };
                }
            }
            for (let key in dataMap) {
                updateDatas.push({ type: 'update', data: dataMap[key] });
            }
            return updateDatas;
        };
        Tree.prototype.m_downLevel = function (nodes) {
            let pre = nodes[0].preSibling; //第一个节点的前一节点，即会成为新的父节点
            let next;//最后一个节点的后一节点，会成为pre 的下一个节点
            let last;//选中的最后一个节点，nextSibling要设置为0
            for (let n of nodes) {
                next = n.nextSibling;
                last = n;
                let children = n.parent ? n.parent.children : this.roots;
                children.splice(n.siblingIndex(), 1);
                pre.addChild(n);
            }
            if (!pre.expanded) pre.setExpanded(true);
            pre.setNextSibling(next);
            last.nextSibling = null;
            tools.sortTreeItems(this);
            return true;
        };

        Tree.prototype.getDownLevelDatas = function (nodes) {
            let dataMap = {}, updateDatas = [], nextID, last;//注释同m_downLevel 方法
            let newParent = nodes[0].preSibling;//{"type":"update","data":{"ID":3,"ParentID":-1,"NextSiblingID":5}}
            let newPre = newParent.children && newParent.children.length > 0 ? newParent.children[newParent.children.length - 1] : null;
            if (newPre) { //如果新的父节点有子节点，则把新的父节点的最后一个子节点的下一节点的值改成第一个选中节点的ID
                dataMap[newPre.getID()] = { "ID": newPre.getID(), "NextSiblingID": nodes[0].getID() }
            }
            for (let n of nodes) {
                nextID = n.getNextSiblingID();
                last = n;
                dataMap[n.getID()] = { "ID": n.getID(), "ParentID": newParent.getID() }//修改父ID;
            }
            dataMap[newParent.getID()] = { "ID": newParent.getID(), "NextSiblingID": nextID }//设置新的父节点的下一个节点ID;
            if (dataMap[last.getID()] !== undefined) {//把最后一个节点的下一个节点ID变成-1
                dataMap[last.getID()].NextSiblingID = -1
            } else {
                dataMap[last.getID()] = { "ID": last.getID(), "NextSiblingID": -1 };
            }
            for (let key in dataMap) {
                updateDatas.push({ type: 'update', data: dataMap[key] });
            }
            return updateDatas;
        };

        Tree.prototype.getDeleteData = function (node) {
            var data = [];
            var addUpdateDataForDelete = function (datas, nodes) {
                nodes.forEach(function (node) {
                    var delData = {};
                    delData[node.tree.setting.id] = node.getID();
                    datas.push({ type: 'delete', data: delData });
                    addUpdateDataForDelete(datas, node.children);
                })
            };
            if (node) {
                addUpdateDataForDelete(data, [node]);
                if (node.preSibling) {
                    tools.addUpdateDataForNextSibling(data, node.preSibling, node.getNextSiblingID());
                }
            }
            return data;
        };
        Tree.prototype.getDeleteDatas = function (deleteMap, deleteNodes) {//批量删除
            let datas = [];
            addDeleteDatas(datas, deleteNodes);
            for (let d of deleteNodes) {
                addPreUpdateData(datas, deleteMap, d.preSibling, d.nextSibling);
            }
            function addPreUpdateData(updateDatas, map, preSibling, nextSibling) {
                if (preSibling && (map[preSibling.getID()] == undefined || map[preSibling.getID()] == null)) {
                    if (nextSibling) {
                        if (map[nextSibling.getID()]) {//如果下一个节点也是要删除的，则再往下顺延
                            addPreUpdateData(updateDatas, map, preSibling, nextSibling.nextSibling);
                        } else {
                            updateDatas.push({ type: 'update', data: preSibling.tree.getDataTemplate(preSibling.getID(), preSibling.getParentID(), nextSibling.getID()) });
                        }
                    } else {
                        updateDatas.push({ type: 'update', data: preSibling.tree.getDataTemplate(preSibling.getID(), preSibling.getParentID(), -1) });
                    }
                }
            }

            function addDeleteDatas(dataArray, nodes) {
                for (let n of nodes) {
                    let delData = {};
                    delData[n.tree.setting.id] = n.getID();
                    dataArray.push({ type: 'delete', data: delData });
                    addDeleteDatas(dataArray, n.children);
                }
            }
            return datas;
        };


        /*Tree.prototype.editedData = function (field, id, newText) {
         var node = this.findNode(id), result = {allow: false, nodes: []};
         if (this.event[this.eventType.editedData]) {
         return this.event[this.eventType.editedData](field, node.data);
         } else {
         node.data[field] = newText;
         result.allow = true;
         return result;
         }
         };*/

        Tree.prototype.bind = function (eventName, eventFun) {
            this.event[eventName] = eventFun;
        };

        Tree.prototype.resetID = function (items, IDFunc) {
            const IDMap = {};
            items.forEach(item => {
                IDMap[item.ID] = IDFunc();
            });
            items.forEach(item => {
                if (IDMap[item.ID]) {
                    item.ID = IDMap[item.ID];
                }
                if (IDMap[item.ParentID]) {
                    item.ParentID = IDMap[item.ParentID];
                }
                if (IDMap[item.NextSiblingID]) {
                    item.NextSiblingID = IDMap[item.NextSiblingID];
                }
            });
        };

        /**
         * 检查原始树数据，并给出可用于修复数据的 updateDatas。
         * 最好在 loadDatas 前调用 newCheck(datas)，避免错误的关系影响树的构建。
         * 不传 datas 时检查当前树中保存的原始 data；本方法不会修改原数据。
         */
        Tree.prototype.newCheck = function (datas) {
            var that = this;
            var idField = this.setting.id;
            var pidField = this.setting.pid;
            var nidField = this.setting.nid;
            var rootId = this.setting.rootId;
            var source = Array.isArray(datas) ? datas : Object.keys(this.nodes).map(function (key) {
                return that.nodes[key].data;
            });
            var problems = [];
            var updateMap = Object.create(null);
            var nodeMap = Object.create(null);
            var duplicateMap = Object.create(null);
            var duplicates = [];
            var stackRisks = [];
            var records = [];

            var valueKey = function (value) {
                return String(value);
            };
            var sameValue = function (left, right) {
                return left == right;
            };
            var addProblem = function (type, record, field, currentValue, suggestedValue, message) {
                problems.push({
                    type: type,
                    id: record ? record.id : undefined,
                    dataIndex: record ? record.index : undefined,
                    rowNumber: record ? record.index + 1 : undefined,
                    // 保留对象引用供控制台展开，不能 JSON.stringify：Node 包含 tree 循环引用。
                    nodeData: record ? record.data : null,
                    field: field || '',
                    currentValue: currentValue,
                    suggestedValue: suggestedValue,
                    message: message
                });
            };
            var suggestUpdate = function (record, field, value) {
                var key = valueKey(record.id);
                if (!updateMap[key]) {
                    updateMap[key] = {};
                    updateMap[key][idField] = record.id;
                }
                updateMap[key][field] = value;
            };

            source.forEach(function (data, index) {
                // 兼容 newCheck(rawDatas) 和 newCheck(tree.items) 两种调用方式。
                // Tree Node 中包含 node.tree.nodes -> node 的循环关系，只检查其原始 data。
                var rawData = data && typeof data.getID === 'function' && data.data ? data.data : data;
                var record = {
                    data: rawData,
                    id: rawData[idField],
                    pid: rawData[pidField],
                    nid: rawData[nidField],
                    index: index
                };
                var key = valueKey(record.id);
                if (nodeMap[key]) {
                    var firstRecord = nodeMap[key];
                    duplicateMap[key] = true;
                    duplicates.push({
                        id: record.id,
                        first: {
                            dataIndex: firstRecord.index,
                            rowNumber: firstRecord.index + 1,
                            data: firstRecord.data
                        },
                        duplicate: {
                            dataIndex: record.index,
                            rowNumber: record.index + 1,
                            data: record.data
                        }
                    });
                    addProblem('duplicate-id', record, idField, record.id, undefined,
                        'ID ' + record.id + ' 重复：datas[' + firstRecord.index + ']（第 ' +
                        (firstRecord.index + 1) + ' 条）和 datas[' + record.index + ']（第 ' +
                        (record.index + 1) + ' 条）是两个不同节点，请修改其中一个节点的 ID');
                    return;
                }
                nodeMap[key] = record;
                records.push(record);
            });

            // 先修正无效父节点，再检查父子关系是否成环。
            records.forEach(function (record) {
                var parent = nodeMap[valueKey(record.pid)];
                record.fixedPid = record.pid;
                if (sameValue(record.pid, rootId)) {
                    return;
                }
                if (sameValue(record.pid, record.id) || !parent) {
                    record.fixedPid = rootId;
                    suggestUpdate(record, pidField, rootId);
                    addProblem(sameValue(record.pid, record.id) ? 'parent-self' : 'parent-missing',
                        record, pidField, record.pid, rootId,
                        sameValue(record.pid, record.id) ? '父节点指向自身，应改为根节点' : '父节点不存在，应改为根节点');
                }
            });

            records.forEach(function (record) {
                var current = record;
                var path = [];
                var pathIndex = Object.create(null);
                while (current && !sameValue(current.fixedPid, rootId)) {
                    var currentKey = valueKey(current.id);
                    if (pathIndex[currentKey] !== undefined) {
                        var breaker = path[path.length - 1];
                        var cycle = path.slice(pathIndex[currentKey]).map(function (item) {
                            return item.id;
                        });
                        breaker.fixedPid = rootId;
                        suggestUpdate(breaker, pidField, rootId);
                        addProblem('parent-cycle', breaker, pidField, breaker.pid, rootId,
                            '父节点形成环：' + cycle.join(' -> ') + '，建议断开此节点并改为根节点');
                        break;
                    }
                    pathIndex[currentKey] = path.length;
                    path.push(current);
                    current = nodeMap[valueKey(current.fixedPid)];
                }
            });

            // 按修正后的父节点分组，在每组内恢复为一条完整、无环、无分叉的兄弟链。
            var groups = Object.create(null);
            records.forEach(function (record) {
                var groupKey = valueKey(record.fixedPid);
                if (!groups[groupKey]) {
                    groups[groupKey] = [];
                }
                groups[groupKey].push(record);
            });

            Object.keys(groups).forEach(function (groupKey) {
                var siblings = groups[groupKey];
                var siblingMap = Object.create(null);
                var nextMap = Object.create(null);
                var incoming = Object.create(null);
                var visited = Object.create(null);
                var ordered = [];
                var stackRiskLimit = 1000;

                siblings.forEach(function (record) {
                    siblingMap[valueKey(record.id)] = record;
                    incoming[valueKey(record.id)] = 0;
                });
                siblings.forEach(function (record) {
                    var next = sameValue(record.nid, rootId) ? null : nodeMap[valueKey(record.nid)];
                    if (next && siblingMap[valueKey(next.id)] && !sameValue(next.id, record.id)) {
                        nextMap[valueKey(record.id)] = next;
                        incoming[valueKey(next.id)]++;
                    } else {
                        nextMap[valueKey(record.id)] = null;
                        if (!sameValue(record.nid, rootId)) {
                            addProblem(next && sameValue(next.id, record.id) ? 'next-self' : 'next-invalid',
                                record, nidField, record.nid, undefined,
                                next ? 'NextSiblingID 指向不同父节点下的节点或自身' : 'NextSiblingID 指向不存在的节点');
                        }
                    }
                });

                Object.keys(incoming).forEach(function (key) {
                    if (incoming[key] > 1) {
                        var target = siblingMap[key];
                        addProblem('next-branch', target, nidField, target.id, undefined,
                            '有 ' + incoming[key] + ' 个节点同时指向该节点，兄弟链产生分叉');
                    }
                });

                var appendChain = function (start) {
                    var current = start;
                    var chain = [];
                    var chainIndex = Object.create(null);
                    while (current && !visited[valueKey(current.id)]) {
                        chainIndex[valueKey(current.id)] = chain.length;
                        chain.push(current);
                        visited[valueKey(current.id)] = true;
                        ordered.push(current);
                        current = nextMap[valueKey(current.id)];
                    }
                    if (current && chainIndex[valueKey(current.id)] !== undefined) {
                        var cycleStart = chainIndex[valueKey(current.id)];
                        var cycleRecords = chain.slice(cycleStart);
                        var cycleEnd = cycleRecords[cycleRecords.length - 1];
                        addProblem('next-cycle', cycleEnd, nidField, cycleEnd.nid, undefined,
                            '兄弟节点的 NextSiblingID 形成环：' + cycleRecords.map(function (item) {
                                return item.id;
                            }).concat([current.id]).join(' -> ') + '，请按 updateDatas 修复');
                    }
                    if (chain.length > stackRiskLimit) {
                        stackRisks.push({
                            parentId: start.fixedPid,
                            chainLength: chain.length,
                            firstNodeId: chain[0].id,
                            lastNodeId: chain[chain.length - 1].id,
                            message: '同一父节点下连续兄弟链有 ' + chain.length +
                                ' 个节点，旧版 moveNode 逐节点递归会导致 Maximum call stack size exceeded；请使用迭代版 moveNode'
                        });
                    }
                };
                siblings.forEach(function (record) {
                    if (incoming[valueKey(record.id)] === 0) {
                        appendChain(record);
                    }
                });
                // 剩余节点属于环，或处于已合并链的未访问部分；按原数据顺序接到末尾。
                siblings.forEach(function (record) {
                    appendChain(record);
                });

                ordered.forEach(function (record, index) {
                    var expectedNid = index === ordered.length - 1 ? rootId : ordered[index + 1].id;
                    if (!sameValue(record.nid, expectedNid)) {
                        suggestUpdate(record, nidField, expectedNid);
                        addProblem('next-order', record, nidField, record.nid, expectedNid,
                            '兄弟链不连续，按可恢复顺序修改 NextSiblingID');
                    }
                });
            });

            var updateDatas = Object.keys(updateMap).map(function (key) {
                return { type: 'update', data: updateMap[key] };
            });
            var result = {
                valid: problems.length === 0,
                canAutoFix: Object.keys(duplicateMap).length === 0,
                problems: problems,
                duplicates: duplicates,
                stackRisks: stackRisks,
                updateDatas: updateDatas
            };

            if (typeof console !== 'undefined') {
                if (result.valid) {
                    console.log('树结构检查通过，共 ' + records.length + ' 个节点');
                } else {
                    console.group('树结构检查：发现 ' + problems.length + ' 个问题');
                    console.table(problems);
                    duplicates.forEach(function (item, index) {
                        console.group('重复 ID 问题 ' + (index + 1) + '：ID = ' + item.id);
                        console.error('以下两个节点的 ID 相同，必须修改其中一个：');
                        console.log('节点 A：datas[' + item.first.dataIndex + ']，第 ' +
                            item.first.rowNumber + ' 条原始数据', item.first.data);
                        console.log('节点 B：datas[' + item.duplicate.dataIndex + ']，第 ' +
                            item.duplicate.rowNumber + ' 条原始数据', item.duplicate.data);
                        console.groupEnd();
                    });
                    console.log('建议修改数据（newCheck 只生成建议，不会自动修改）：');
                    console.table(updateDatas.map(function (item) { return item.data; }));
                    if (!result.canAutoFix) {
                        console.warn('存在重复 ID，必须先人工分配新 ID，其他修改建议才可安全应用');
                    }
                    console.groupEnd();
                }
                if (stackRisks.length) {
                    console.group('树排序递归栈风险：发现 ' + stackRisks.length + ' 条过长兄弟链');
                    console.table(stackRisks);
                    console.warn('这不一定是数据错误；旧版递归 moveNode 会因此堆栈溢出，改为迭代实现即可正常显示');
                    console.groupEnd();
                }
            }
            return result;
        };

        //检查树结构数据有没问题
        Tree.prototype.check = function (roots) {
            return isValid(roots);
            function isValid(nodes) {
                for (let node of nodes) {
                    if (node.data.ParentID != -1 &&
                        (!node.parent || node.parent.data.ID !== node.data.ParentID)) {
                        console.log(`${node.serialNo() + 1}:${node.data.name} parent对应错误`);
                        return false;
                    }
                    if (node.data.ParentID == -1 && node.parent) {
                        console.log(`${node.serialNo() + 1}:${node.data.name} 不应有parent`);
                        return false;
                    }
                    if (node.data.NextSiblingID != -1 &&
                        (!node.nextSibling || node.nextSibling.data.ID !== node.data.NextSiblingID)) {
                        console.log(`${node.serialNo() + 1}:${node.data.name} next对应错误`);
                        return false;
                    }
                    if (node.data.NextSiblingID == -1 && node.nextSibling) {
                        console.log(`${node.serialNo() + 1}:${node.data.name} 不应有next`);
                        return false;
                    }
                    let sameDepthNodes = node.parent ? node.parent.children : roots,
                        nodeIdx = sameDepthNodes.indexOf(node),
                        nextIdx = sameDepthNodes.indexOf(node.nextSibling);
                    if (nodeIdx != -1 && nextIdx != -1 && nodeIdx > nextIdx) {
                        console.log(`${node.serialNo() + 1}:${node.data.name} node索引大于next索引`);
                        return false;
                    }
                    // nextSibling跟parent children的下一节点对应不上
                    if (nodeIdx != -1 &&
                        (nodeIdx === sameDepthNodes.length - 1 && nextIdx != -1) ||
                        (nodeIdx !== sameDepthNodes.length - 1 && nodeIdx + 1 !== nextIdx)) {
                        console.log(`${node.serialNo() + 1}:${node.data.name} nextSibling与树显示的下一节点对应不上`);
                        return false;
                    }
                    if (node.children.length) {
                        let v = isValid(node.children);
                        if (!v) {
                            return false;
                        }
                    }
                }
                return true;
            }
        };

        return new Tree(setting);
    },
    updateType: { update: 'update', new: 'new', delete: 'delete' }
};