package toolgood.words.internals;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

public class BaseMatch {
    protected TrieNode3[] _first;
    protected int[] _keywordLength;
    protected int[] _keywordIndex;
    protected String[] _matchKeywords;

    protected List<TrieNode> BuildFirstLayerTrieNode(List<String> keywords) {
        TrieNode root = new TrieNode();

        Map<Integer, List<TrieNode>> allNodeLayers = new Hashtable<Integer, List<TrieNode>>();
        // 第一次关键字
        for (int i = 0; i < keywords.size(); i++) {
            String p = keywords.get(i);
            TrieNode nd = root;
            int start = 0;
            while (p.charAt(start) == 0) { // 0 为 通配符
                start++;
            }
            for (int j = start; j < p.length(); j++) {
                nd = nd.Add(p.charAt(j));
                if (nd.Layer == 0) {
                    nd.Layer = j + 1 - start;
                    if (allNodeLayers.containsKey(nd.Layer) == false) {
                        List<TrieNode> nodes = new ArrayList<TrieNode>();
                        nodes.add(nd);
                        allNodeLayers.put(nd.Layer, nodes);
                    } else {
                        allNodeLayers.get(nd.Layer).add(nd);
                    }
                }
            }
            nd.SetResults(i);
        }
        Character z = 0;
        // 第二次关键字 通配符
        for (int i = 0; i < keywords.size(); i++) {
            String p = keywords.get(i);
            if (p.contains(z.toString()) == false) {
                continue;
            }
            int start = 0;
            while (p.charAt(start) == 0) { // 0 为 通配符
                start++;
            }
            List<TrieNode> trieNodes = new ArrayList<TrieNode>();
            trieNodes.add(root);

            for (int j = start; j < p.length(); j++) {
                List<TrieNode> newTrieNodes = new ArrayList<TrieNode>();
                Character c = p.charAt(j);
                if (c == 0) {
                    for (TrieNode nd : trieNodes) {
                        for (Character key : nd.m_values.keySet()) {
                            newTrieNodes.add(nd.m_values.get(key));
                        }
                    }
                } else {
                    for (TrieNode nd : trieNodes) {
                        TrieNode nd2 = nd.Add(c);
                        if (nd2.Layer == 0) {
                            nd2.Layer = j + 1 - start;
                            if (allNodeLayers.containsKey(nd2.Layer) == false) {
                                List<TrieNode> nodes = new ArrayList<TrieNode>();
                                nodes.add(nd2);
                                allNodeLayers.put(nd2.Layer, nodes);
                            } else {
                                allNodeLayers.get(nd2.Layer).add(nd2);
                            }
                            // List<TrieNode> tnodes;
                            // if (allNodeLayers.TryGetValue(nd2.Layer, tnodes) == false) {
                            // tnodes = new ArrayList<TrieNode>();
                            // allNodeLayers[nd.Layer] = tnodes;
                            // }
                            // tnodes.add(nd2);
                        }
                        newTrieNodes.add(nd2);
                    }
                }
                trieNodes = newTrieNodes;
            }
            for (TrieNode nd : trieNodes) {
                nd.SetResults(i);
            }
        }

        // 添加到 allNode
        List<TrieNode> allNode = new ArrayList<TrieNode>();
        allNode.add(root);
        for (int i = 0; i < allNodeLayers.size(); i++) { // 注意 这里不能用 keySet()
            List<TrieNode> nodes = allNodeLayers.get(i + 1);
            for (int j = 0; j < nodes.size(); j++) {
                allNode.add(nodes.get(j));
            }
        }
        allNodeLayers.clear();
        allNodeLayers = null;

        // 第一次 Set Failure
        for (int i = 1; i < allNode.size(); i++) {
            TrieNode nd = allNode.get(i);
            nd.Index = i;
            TrieNode r = nd.Parent.Failure;
            char c = nd.Char;
            while (r != null &&(r.m_values==null || !r.m_values.containsKey(c)))
                r = r.Failure;
            if (r == null)
                nd.Failure = root;
            else {
                nd.Failure = r.m_values.get(c);
                if (nd.Failure.Results!=null){
                    for (Integer result : nd.Failure.Results)
                        nd.SetResults(result);
                }
            }
        }

        // 第二次 Set Failure
        Character zore = 0;
        for (int i = 1; i < allNode.size(); i++) {
            TrieNode nd = allNode.get(i);
            if (nd.Layer == 1) {
                continue;
            }
            if(nd.m_values!=null){
                if (nd.m_values.containsKey(zore)) {
                    nd.HasWildcard = true;
                }
            }
            if (nd.Failure.HasWildcard) {
                nd.HasWildcard = true;
            }
            if (nd.Char == 0) {
                nd.IsWildcard = true;
                continue;
            } else if (nd.Parent.IsWildcard) {
                nd.IsWildcard = true;
                nd.WildcardLayer = nd.Parent.WildcardLayer + 1;
                if (nd.Failure != root) {
                    if (nd.Failure.Layer <= nd.WildcardLayer) {
                        nd.Failure = root;
                    }
                }
                continue;
            }
        }
        root.Failure = root;

        return allNode;
    }

    protected boolean HasMatch(String keyword) {
        for (int i = 0; i < keyword.length(); i++) {
            Character c = keyword.charAt(i);
            if (c == '.' || c == '?' || c == '\\' || c == '[' || c == '(') {
                return true;
            }
        }
        return false;
    }

    protected List<String> MatchKeywordBuild(String keyword) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();
        Map<Integer, List<String>> parameterDict = new Hashtable<Integer, List<String>>();
        SeparateParameters(keyword, stringBuilder, parameterDict);

        if (parameterDict.size() == 0) {
            List<String> al = new ArrayList<String>();
            al.add(stringBuilder.toString());
            return al;
        }
        List<String> parameters = new ArrayList<String>();
        KeywordBuild(parameterDict, 0, parameterDict.keySet().size() - 1, "", parameters);
        String keywordFmt = stringBuilder.toString();
        List<String> list = new ArrayList<String>();

        String z = ((Character) (char) 0).toString();
        for (int i = 0; i < parameters.size(); i++) {
            String item = parameters.get(i);
            String[] items = item.split(z);
            Object[] ls = new Object[items.length];
            for (int j = 0; j < ls.length; j++) {
                ls[j] = items[j];
            }
            String t = String.format(keywordFmt, ls);
            if (list.contains(t) == false) {
                list.add(t);
            }
        }
        return list;
    }

    private void SeparateParameters(String keyword, StringBuilder stringBuilder,
            Map<Integer, List<String>> parameterDict) throws Exception {
        int index = 0;
        int parameterIndex = 0;
        Character zore = 0;

        while (index < keyword.length()) {
            Character c = keyword.charAt(index);
            if (c == '.') {
                if (index + 1 < keyword.length() && keyword.charAt(index + 1) == '?') {
                    List<String> lt = new ArrayList<String>();
                    lt.add("");
                    lt.add(zore.toString());
                    parameterDict.put(parameterIndex, lt);
                    stringBuilder.append("%" + (parameterIndex+1)  + "$s");
                    parameterIndex++;
                    index += 2;

                } else {
                    stringBuilder.append(((char) 0));
                    index++;
                }
            } else if (c == '\\') {
                if (index + 2 < keyword.length() && keyword.charAt(index + 2) == '?') {
                    List<String> lt = new ArrayList<String>();
                    lt.add("");
                    lt.add(((Character) keyword.charAt(index + 1)).toString());
                    parameterDict.put(parameterIndex, lt);
                    stringBuilder.append("%" + (parameterIndex+1)  + "$s");
                    parameterIndex++;
                    index += 3;
                } else if (index + 1 < keyword.length()) {
                    stringBuilder.append(keyword.charAt(index + 1));
                    index += 2;
                } else {
                    throw new Exception("【{keyword}】出错了，最后一位为\\");
                }
            } else if (c == '[') {
                index++;
                List<String> ps = new ArrayList<String>();
                while (index < keyword.length()) {
                    c = keyword.charAt(index);
                    if (c == ']') {
                        break;
                    } else if (c == '\\') {
                        if (index + 1 < keyword.length()) {
                            ps.add(((Character) keyword.charAt(index + 1)).toString());
                            index += 2;
                        }
                    } else {
                        ps.add(c.toString());
                        index++;
                    }
                }
                if (c != ']') {
                    throw new Exception("【{keyword}】出错了，最后一位不为]");
                }
                if (index + 1 < keyword.length() && keyword.charAt(index + 1) == '?') {
                    ps.add("");
                    parameterDict.put(parameterIndex, ps);
                    stringBuilder.append("%" + (parameterIndex+1)  + "$s");
                    parameterIndex++;
                    index += 2;
                } else {
                    parameterDict.put(parameterIndex, ps);
                    stringBuilder.append("%" + (parameterIndex+1)  + "$s");
                    parameterIndex++;
                    index++;
                }
            } else if (c == '(') {
                index++;
                List<String> ps = new ArrayList<String>();
                String words = "";
                while (index < keyword.length()) {
                    c = keyword.charAt(index);
                    if (c == ')') {
                        break;
                    } else if (c == '|') {
                        ps.add(words);
                        words = "";
                        index++;
                    } else if (c == '\\') {
                        if (index + 1 < keyword.length()) {
                            words += keyword.charAt(index + 1);
                            index += 2;
                        }
                    } else {
                        words += c;
                        index++;
                    }
                }
                ps.add(words);
                if (c != ')') {
                    throw new Exception("【{keyword}】出错了，最后一位不为)");
                }
                if (index + 1 < keyword.length() && keyword.charAt(index + 1) == '?') {
                    ps.add("");
                    parameterDict.put(parameterIndex, ps);
                    stringBuilder.append("%" + (parameterIndex+1)  + "$s");
                    parameterIndex++;
                    index += 2;
                } else {
                    parameterDict.put(parameterIndex, ps);
                    stringBuilder.append("%" + (parameterIndex+1)  + "$s");
                    parameterIndex++;
                    index++;
                }
            } else {
                if (index + 1 < keyword.length() && keyword.charAt(index + 1) == '?') {
                    List<String> lt = new ArrayList<String>();
                    lt.add("");
                    lt.add(c.toString());
                    parameterDict.put(parameterIndex, lt);
                    stringBuilder.append("%" + (parameterIndex+1) + "$s");
                    parameterIndex++;
                    index += 2;
                } else {
                    if (c == '{') {
                        stringBuilder.append("{{");
                    } else if (c == '}') {
                        stringBuilder.append("}}");
                    } else {
                        stringBuilder.append(c);
                    }
                    index++;
                }
            }
        }

    }

    private static void KeywordBuild(Map<Integer, List<String>> parameterDict, int index, int end, String keyword,
            List<String> result) {
        Character span = (char) 1;
        List<String> list = parameterDict.get(index);
        if (index == end) {
            for (int i = 0; i < list.size(); i++) {
                String item = list.get(i);
                result.add((keyword + span + item).substring(1));
            }
        } else {
            for (int i = 0; i < list.size(); i++) {
                String item = list.get(i);
                KeywordBuild(parameterDict, index + 1, end, keyword + span + item, result);
            }
        }
    }

    /**
     * 设置关键字
     * 
     * @param keywords 关键字列表
     * @throws Exception
     */
    public void SetKeywords(List<String> keywords) throws Exception {
        _matchKeywords = keywords.toArray(new String[0]);
        List<String> newKeyword = new ArrayList<String>();
        List<Integer> newKeywordLength = new ArrayList<Integer>();
        List<Integer> newKeywordIndex = new ArrayList<Integer>();
        Integer index = 0;
        for (String keyword : keywords) {
            if (HasMatch(keyword) == false) {
                newKeyword.add(keyword);
                newKeywordLength.add(keyword.length());
                newKeywordIndex.add(index);
            } else {
                List<String> list = MatchKeywordBuild(keyword);
                for (String item : list) {
                    newKeyword.add(item);
                    newKeywordLength.add(item.length());
                    newKeywordIndex.add(index);
                }
            }
            index++;
        }
        _keywordLength = new int[newKeywordLength.size()];
        for (int i = 0; i < _keywordLength.length; i++) {
            _keywordLength[i] = newKeywordLength.get(i);
        }
        _keywordIndex = new int[newKeywordIndex.size()];
        for (int j = 0; j < _keywordIndex.length; j++) {
            _keywordIndex[j] = newKeywordIndex.get(j);
        }

        SetKeywords2(newKeyword);
    }

    protected void SetKeywords2(List<String> keywords) {
        List<TrieNode> allNode = BuildFirstLayerTrieNode(keywords);
        TrieNode root = allNode.get(0);

        List<TrieNode3> allNode2 = new ArrayList<TrieNode3>();
        for (int i = 0; i < allNode.size(); i++) {
            allNode2.add(new TrieNode3());
        }
        for (int i = allNode2.size()-1; i >= 0; i--) {
            TrieNode oldNode = allNode.get(i);
            TrieNode3 newNode = allNode2.get(i);

            if(oldNode.m_values!=null){
                for (Character key : oldNode.m_values.keySet()) {
                    int index = oldNode.m_values.get(key).Index;
                    if (key == 0) {
                        newNode.HasWildcard = true;
                        newNode.WildcardNode = allNode2.get(index);
                        continue;
                    }
                    newNode.Add(key, allNode2.get(index));
                }
            }
            if(oldNode.Results!=null){
                for (Integer item : oldNode.Results) {
                    if (oldNode.IsWildcard) {
                        if (keywords.get(item).length() > oldNode.WildcardLayer) {
                            newNode.SetResults(item);
                        }
                    } else {
                        newNode.SetResults(item);
                    }
                }
            }
            TrieNode failure = oldNode.Failure;
            while (failure != root) {
                if (oldNode.IsWildcard && failure.Layer <= oldNode.WildcardLayer) {
                    break;
                }
                if  (failure.m_values!=null){
                    for (Character key : failure.m_values.keySet()) {
                        int index = failure.m_values.get(key).Index;
                        if (key == 0) {
                            newNode.HasWildcard = true;
                            if (newNode.WildcardNode == null) {
                                newNode.WildcardNode = allNode2.get(index);
                            }
                            continue;
                        }
                        if (newNode.HasKey(key) == false) {
                            newNode.Add(key, allNode2.get(index));
                        }
                    }
                }
                if(failure.Results!=null){
                    for (Integer item : failure.Results) {
                        if (oldNode.IsWildcard) {
                            if (keywords.get(item).length() > oldNode.WildcardLayer) {
                                newNode.SetResults(item);
                            }
                        } else {
                            newNode.SetResults(item);
                        }
                    }
                }
                failure = failure.Failure;
            }
            allNode.get(i).Dispose();
        }
        allNode.clear();
        allNode = null;
        root = null;

        // var root2 = allNode2[0];
        TrieNode3[] first = new TrieNode3[Character.MAX_VALUE + 1];
        for (Character key : allNode2.get(0).m_values.keySet()) {
            first[key] = allNode2.get(0).m_values.get(key);
        }
        _first = first;
    }

}