import { Laya } from "Laya";
import { Sprite } from "laya/display/Sprite";
import { WebGL } from "laya/webgl/WebGL";
import { Text } from "laya/display/Text";
import { Tween } from "laya/utils/Tween";
import { Ease } from "laya/utils/Ease";
import { Handler } from "laya/utils/Handler";
import { InferTypeNode } from "../../../node_modules/typescript/lib/typescript";


export interface IMyPoint { // 单元格坐标或屏幕像素位置
    x: number;
    y: number;
}

export interface IMyRect { // 单元格坐标或屏幕像素位置
    width: number;
    height: number;
}

/**
 * 节点，为叶子节点及内节点的父类
 */
export interface IItem {
    id: number;  // 唯一编号 ，用于绘图 
    frequency: number; // 频度
    // parentNode?: INode; // 父节点 ，用于绘图 
    isLeftChild: boolean; // 是否为父类左子节点
    width: number; // 图形总的宽度；如果有子节点，则包含子节点的宽度单位,否则为1;叶子节点width全部为1，只是为了好计算;height全部为1，暂时不用写；x,y 需要实时计算
}

/**
 * 叶子节点
 */
export interface ILeaf extends IItem {
    content: string; // 字符的内容
}

/**
 * 内节点
 */
export interface INode extends IItem {
    left: INode | ILeaf; // 左节点 
    right: INode | ILeaf; // 右节点

}

/**
 * 算法导论第二版＝》贪心算法＝》赫夫曼编码
 */
export class C163Huffman {

    private init_data: { [content: string]: number } = { "f": 5, "e": 9, "c": 12, "b": 13, "d": 16, "a": 45 };

    private static maxId: number = 1;// 当前最大编号，用于各结点生成id

    private arr_res: (ILeaf | INode)[] = []; // 存储按频度排序的数据结果，

    private map_text_graphics: { [id: number]: Text } = {}; // 存储绘制的文本
    private map_circle_graphics: { [id: number]: Text } = {}; // 存储绘制的圆圈
    private map_line_graphics: { [id: number]: Sprite } = {}; // 存储绘制的连接线

    private static unitXPx: number = 75; // 一个x坐标位置对应着75像素,可随意更改
    private static unitYPx: number = 150; // 一个y坐标位置对应着150像素,可随意更改

    constructor() {

        Laya.init(2000, 1000, WebGL);

        this.initTextGraphics(); // 初使化图形

        setTimeout(() => { this.huffman(); }, 2000); // 延迟动画时间

        // console.info(this.result);

        // this.drawResult(); // 绘制结果

    }

    huffman() {

        if (!this.arr_res || !this.arr_res.length || this.arr_res.length < 2) { // 只有一个结点，则结束运行
            console.info(this.arr_res);
            return;
        }

        let leftNode = this.arr_res.shift(); // 获取并删除第一个节点 ，作为左节点
        let rightNode = this.arr_res.shift();  // 获取并删除第一个节点 ，作为右节点
        console.info('after shift: ', this.arr_res);

        // 开始更新数据；
        // 合并最低频度的两个节点成一个新的节点
        let curId = C163Huffman.maxId++;
        let newNode: INode = {
            id: curId++,
            frequency: leftNode.frequency + rightNode.frequency,
            left: leftNode,
            right: rightNode,
            width: leftNode.width + rightNode.width + 1,
            isLeftChild: false,
        }
        leftNode.isLeftChild = true;
        // leftNode.parentNode = newNode;
        // rightNode.parentNode = newNode;

        // 插入新的节点到结果中
        let flag_insert: boolean = false; // 新节点插入是否成功
        for (let i = 0, cnt = this.arr_res.length; i < cnt; i++) {
            if (this.arr_res[i].frequency > newNode.frequency) { // 找到第一个频度大于新节点的位置，就是要插入的位置 
                this.arr_res.splice(i, 0, newNode);
                console.info('after insert position ' + i + ' element:', this.arr_res);
                flag_insert = true;
                break;
            }
        }
        if (!flag_insert) { // 如果生成的新的结点是最大频度导致没有插入(或者结果数组为空)，则插入结果数组末尾
            this.arr_res[this.arr_res.length] = newNode;
            console.info('after insert last element:', this.arr_res);
        }


        // 开始更新图形
        let txtPos: IMyPoint = this.getRealXY(-1, -1); // 隐藏新结点，放置的单元格坐标位置（－1，－1）位于屏幕外

        // 绘制左子节点连接线
        let txtLineLeft: Sprite = new Sprite();
        Laya.stage.addChild(txtLineLeft);

        let rectUnitLineLeft: IMyRect = { width: 1, height: 1 };// 对应着矩形宽高; 默认为叶子结点， 叶子结点就是一个坐标位置
        if (this.isNode(newNode.left)) { //如果是内结点
            rectUnitLineLeft.width = (newNode.left.right.width + 1); //左子结点自身加上＋左子结点的右边宽度，就是连接线的长度
        }
        let rectLineLeft = this.getRect(rectUnitLineLeft);
        txtLineLeft.width = rectLineLeft.width;
        txtLineLeft.height = rectLineLeft.height;
        txtLineLeft.pos(-1 * txtLineLeft.width, -1 * txtLineLeft.height); // 隐藏连接线
        txtLineLeft.graphics.drawLine(0, txtLineLeft.height, txtLineLeft.width, 0, "#ff0000", 3);
        this.map_line_graphics[newNode.left.id] = txtLineLeft;

        // 绘制右子节点连接线
        let txtLineRight: Sprite = new Sprite();
        Laya.stage.addChild(txtLineRight);
        let rectUnitLineRight: IMyRect = { width: 1, height: 1 };// 对应着矩形宽高; 默认为叶子结点， 叶子结点就是一个坐标位置
        if (this.isNode(newNode.right)) { // 子结点为内结点
            rectUnitLineRight.width = (newNode.right.left.width + 1); // 右子结点连接线的长度= 父类结点宽度 ＋左子结点宽度
        }
        let rectLineRight = this.getRect(rectUnitLineRight);
        txtLineRight.width = rectLineRight.width;
        txtLineRight.height = rectLineRight.height;
        txtLineRight.pos(-1 * txtLineRight.width, -1 * txtLineRight.height);  // 隐藏连接线
        txtLineRight.graphics.drawLine(0, 0, txtLineRight.width, txtLineRight.height, "#ff0000", 3);
        this.map_line_graphics[newNode.right.id] = txtLineRight;

        // 绘制文字背景圆圈
        let txtCircle: Text = new Text();
        txtCircle.text = '🔴';
        txtCircle.color = "#ff0000";
        txtCircle.fontSize = 36;
        txtCircle.pos(txtPos.x - 12, txtPos.y - 12);
        Laya.stage.addChild(txtCircle);
        this.map_circle_graphics[newNode.id] = txtCircle;

        // 将新的节点添加图形中
        let txt: Text = new Text();
        //给文本的text属性赋值
        txt.text = `${newNode.frequency}`;
        txt.color = "#ffffff";
        txt.fontSize = 18;
        txt.pos(txtPos.x, txtPos.y);
        Laya.stage.addChild(txt);
        this.map_text_graphics[newNode.id] = txt;



        // 更新坐标
        let startPos: IMyPoint = { x: 1, y: 1 }; //起始x坐标位置
        for (let i = 0, cnt = this.arr_res.length; i < cnt; i++) {
            let curNode = this.arr_res[i];
            this.drawTree(curNode, startPos); // 绘制子节点树；

            startPos.x = startPos.x + curNode.width; // 更新绘制下一个图形的起始位置

        }

        setTimeout(() => { this.huffman(); }, 2000); // 延迟动画时间

    }

    /**
     *  绘制子节点树；
     * @param item 子节点 
     * @param startPos 起始位置，左上角坐标
     */
    drawTree(curNode: INode | ILeaf, startPos: IMyPoint) {
        if (!this.isNode(curNode)) { // 如果是叶子节点
            let txtPos = this.getRealXY(startPos.x, startPos.y);
            Tween.to(this.map_text_graphics[curNode.id], { x: txtPos.x, y: txtPos.y }, 200, Ease.elasticOut, null, 2000); // 移动文字位置 
            Tween.to(this.map_circle_graphics[curNode.id], { x: txtPos.x - 12, y: txtPos.y - 12 }, 200, Ease.elasticOut, null, 2000); // 移动圆圈位置
            if (this.map_line_graphics[curNode.id] != undefined) { // 如果该节点的连接线存在

                let lineCoord: IMyPoint = curNode.isLeftChild ? { x: startPos.x, y: startPos.y - 1 } : { x: startPos.x - 1, y: startPos.y - 1 }; // 连接线坐标位置
                let linePos = this.getRealXY(lineCoord.x, lineCoord.y); // 连接线实际像素位置
                Tween.to(this.map_line_graphics[curNode.id], { x: linePos.x + 18, y: linePos.y + 18 }, 200, Ease.elasticOut, null, 2000); // 移动连接线位置
            }

        } else if (this.isNode(curNode)) {// 如果为内节点

            let txtPos = this.getRealXY(startPos.x + curNode.left.width, startPos.y); //  起始位置位于左子节点的末尾

            Tween.to(this.map_text_graphics[curNode.id], { x: txtPos.x, y: txtPos.y }, 200, Ease.elasticOut, null, 2000);
            Tween.to(this.map_circle_graphics[curNode.id], { x: txtPos.x - 12, y: txtPos.y - 12 }, 200, Ease.elasticOut, null, 2000);

            if (this.map_line_graphics[curNode.id] != undefined) {
                let lineCoord: IMyPoint = curNode.isLeftChild ? { x: startPos.x + curNode.left.width, y: startPos.y - 1 } : { x: startPos.x - 1, y: startPos.y - 1 };
                let linePos = this.getRealXY(lineCoord.x, lineCoord.y);

                Tween.to(this.map_line_graphics[curNode.id], { x: linePos.x + 18, y: linePos.y + 18 }, 200, Ease.elasticOut, null, 2000);
            }

            this.drawTree(curNode.left, { x: startPos.x, y: startPos.y + 1 }); // 移动左子结点位置
            this.drawTree(curNode.right, { x: startPos.x + curNode.left.width + 1, y: startPos.y + 1 }); // 移动右子结点位置
        }
    }

    initTextGraphics() { // 初使化图形
        // 初使化叶子节点 
        for (let key in this.init_data) {
            let curId = C163Huffman.maxId++;
            this.arr_res.push({
                id: curId,
                frequency: this.init_data[key],
                content: key,
                width: 1,
                isLeftChild: false,
            });


            let txtPos: IMyPoint = this.getRealXY(curId, 1); // 文字的位置

            // 绘制文字背景矩形
            let txtCircle: Text = new Text();
            txtCircle.text = '🟥';
            txtCircle.color = "#ff0000";
            txtCircle.fontSize = 45;
            txtCircle.pos(txtPos.x - 12, txtPos.y - 12);
            Laya.stage.addChild(txtCircle);
            this.map_circle_graphics[curId] = txtCircle;

            // 绘制文字
            let txt: Text = new Text();
            txt.text = `${key}:${this.init_data[key]}`;
            txt.color = "#ffffff";
            txt.fontSize = 18;
            txt.pos(txtPos.x, txtPos.y);
            Laya.stage.addChild(txt);
            this.map_text_graphics[curId] = txt;



        }
    }

    getRealXY(i: number, j: number): IMyPoint { // 根据位置 i,j得到位置的真实像素坐标
        return { x: (i + 1) * C163Huffman.unitXPx, y: j * C163Huffman.unitYPx };
    }

    getRect(unit: IMyRect): IMyRect { // 根据单元格坐标的宽高得到实际像素宽高
        return { width: unit.width * C163Huffman.unitXPx, height: unit.height * C163Huffman.unitYPx }
    }

    isNode(item: ILeaf | INode): item is INode { // 判断当前结点是否为内结点（父结点)
        return (item as INode).left !== undefined;
    }
}