import hjzgg.first.First;

import java.util.LinkedHashMap;

import java.util.Map;

import java.util.Set;

import java.util.TreeMap;

import java.util.TreeSet;

public class Follow {

    private Map<String, Set<Character>> first = null;

    private Map<String, Set<Character>> follow = new TreeMap<String, Set<Character>>();

    private Map<String, String[]> mp = null;

    public Follow(Map<String, String[]> mp, Map<String, Set<Character>> first) {

        super();

        this.first = first;

        this.mp = mp;

    }

    public Map<String, Set<Character>> getFollowSet(){

        return follow;

    }

    private void getFirstSet(Set<Character> st, String node, int k){

        if(k >= node.length()) return;

        if(node.charAt(k)=='\'') --k;

        String nextNode = "" + node.charAt(k);

        if(k+1<node.length() && node.charAt(k+1)=='\''){

            nextNode += '\'';

            ++k;

        }

        if(!mp.containsKey(nextNode)){//终结点

            st.add(nextNode.charAt(0));

        } else {

            st.addAll(first.get(nextNode));

            if(first.get(nextNode).contains('$'))

                getFirstSet(st, node, k+1);

        }

    }

    private void findFollow(String curNode){

        Set<Character> st = null;

        for(String leftNode : mp.keySet()){

            String rightNodes[] = mp.get(leftNode);

            for(int i=0; i<rightNodes.length; ++i){

                int index = rightNodes[i].indexOf(curNode, 0);

                while(index != -1){

                    int nextIndex = index + 1;

                    if(curNode.length()==1 && index+1<rightNodes[i].length() && rightNodes[i].charAt(index+1)=='\''){

                        index = rightNodes[i].indexOf(curNode, nextIndex);

                        continue;

                    }

                    index = index+curNode.length();

                    if(index == rightNodes[i].length()){//末尾的非终结点, A->@B

                        if(follow.get(leftNode) == null)

                            findFollow(leftNode);

                        if(follow.get(curNode) == null){

                            st = new TreeSet<Character>();

                            st.addAll(follow.get(leftNode));

                            follow.put(curNode, st);

                        }

                        else follow.get(curNode).addAll(follow.get(leftNode));

                    } else {

                        String nextNode = ""+rightNodes[i].charAt(index);

                        if(index+1 < rightNodes[i].length() && rightNodes[i].charAt(index+1)=='\''){

                            nextNode += '\'';

                            ++index;

                        }

                        if(mp.containsKey(nextNode)){//非终结符

                            if(first.get(nextNode).contains(new Character('$'))){//A->@B&, 而 &->$

                                if(follow.get(leftNode) == null)

                                    findFollow(leftNode);

                                if(follow.get(curNode) == null){

                                    st = new TreeSet<Character>();

                                    st.addAll(follow.get(leftNode));

                                    follow.put(curNode, st);

                                }

                                else follow.get(curNode).addAll(follow.get(leftNode));

                            } 

                            //好特殊的情况啊....

                            {//A->@B&, First(&)^$ 放入follow(B)

                                Set<Character> tmpSt = new TreeSet<Character>();

                                getFirstSet(tmpSt, rightNodes[i], index);

                                tmpSt.remove('$');

                                if(follow.get(curNode) == null){

                                    st = new TreeSet<Character>();

                                    st.addAll(tmpSt);

                                    follow.put(curNode, st);

                                }

                                else follow.get(curNode).addAll(tmpSt);

                            }

                        } else {//终结符

                            if(follow.get(curNode) == null){

                                st = new TreeSet<Character>();

                                st.add(nextNode.charAt(0));

                                follow.put(curNode, st);

                            }

                            else follow.get(curNode).add(nextNode.charAt(0));

                        }

                    }

                    index = rightNodes[i].indexOf(curNode, nextIndex);

                }

            }

        }

    }

    public String followKernealCode(){

         String content = "";

         boolean flag = true;

         for(String leftNode : mp.keySet()){

             if(flag){

                 Set<Character> st = new TreeSet<Character>();

                 st.add('#');

                 follow.put(leftNode, st);

                 flag = false;

             }

             findFollow(leftNode);

         }

         //打印first集合

         System.out.println("Follow 集合如下:");

         for(Map.Entry<String, Set<Character>> entry : follow.entrySet()){

             content += entry.getKey() + "  :  " + entry.getValue() + "\n";

             System.out.println(entry.getKey() + "  :  " + entry.getValue());

         }

         return content;

    }

    public static void main(String[] args) {

        String[] rightLinearGrammar = {

            "E->TE\'",

            "E\'->+TE\'|$",

            "T->FT\'",

            "T\'->*FT\'|$",

            "F->(E)|i"

        };

//        String[] rightLinearGrammar = {

//                "S->ABc",

//                "A->a|$",

//                "B->b|$"

//        };

        Map<String, String[]> mp = new LinkedHashMap<String, String[]>();

        try{

            for(int i=0; i<rightLinearGrammar.length; ++i){

                String split1[] = rightLinearGrammar[i].split("->");

                String split2[] = split1[1].split("\\|");

                mp.put(split1[0], split2);

            }

        } catch(Exception e){

            e.printStackTrace();

            System.out.println("右线性文法错误!");

        }

        First first = new First(mp);

        first.firstKernealCode();

        new Follow(mp, first.getFirstSet()).followKernealCode();

    }

}