const _ = require("lodash");

/**
 * 使用子集构造法,将NFA转为DFA. 基于《编译原理》P97的伪代码的实现.
 * @param charset NFA所接受的字符集
 * @param Ntran NFA转换表
 */
module.exports = function subset_construct(charset, Ntran) {
    let cursor = 0; //区分Dstates中的状态集是否访问过. cursor之前的为已访问, cursor之后为未访问.

    let Dstates = []  //DFA的状态集
    let Dtran = {} //DFA的转换表
    Dstates.push(e_closure([0])) //起始状态0输入e可到达的状态集

    //遍历尚未标记的DFA状态 T
    while (cursor < Dstates.length) {
        let T = Dstates[cursor];
        cursor++;
        Dtran[T] = {}
        for (let c of charset) {
            let T_c = move(T, c)   //状态T 在输入c时可达的非空状态集 T_c
            let T_e = e_closure(T_c)    //状态集 T_c 可达的
            let U = combine(T_c, T_e)
            //判断状态集U 是否已经存在于Dstates 不存在则放入
            let exists = Dstates.find(states => states.length == U.length && _.difference(states, T).length == 0
            ) != null
            if (!exists) {
                Dstates.push(U)
            }
            /* 
            放入DFA转换表,这表示T在分别输入(charset U ε)中的每一个字符时,可达的状态集,
            */
            Dtran[T][c] = U
        }
    }

    /**
     * 返回给定状态集T输入ε可达的状态集
     * @param {*} T 状态集T
     */
    function e_closure(T) {
        let result = []
        for (let s of T) {
            result = combine(result, Ntran[s][''])
            result = combine(result, e_closure(Ntran[s][''])) //递归寻找ε
        }
        return result
    }
    /**
     * 返回给定状态集T输入c可达的状态集
     * @param {*} T 状态集T
     */
    function move(T, input) {
        let result = []
        for (let s of T) {
            result = combine(result, Ntran[s][input])
        }
        return result
    }

    return { Dstates, Dtran }
}

/* 工具性方法 */
function combine(arr1, arr2) {
    return _.sortBy(_.union(arr1, arr2))
}