package Syntax;

import BreakMyFuckingSky.Lexi;
import BreakMyFuckingSky.Token;
import sun.nio.cs.Surrogate;

import java.io.*;
import java.util.*;

public class Earley {

    private ArrayList<TreeSet<State>> states =new ArrayList<>();//TODO создать I списков

    private ArrayList<Token> tokens = new ArrayList<Token>();


    class State implements Comparable<State>{
        String left;
        ArrayList<String> rule = new ArrayList<>();
        int pointer;
        int ind;
        TreeSet<State> parents = new TreeSet<>();

        public State(String l, ArrayList<String> r, int p, int i, State parent) {
            left = l;
            rule.addAll(r);
            pointer = p;
            ind = i;
            if(parent!=null)
                parents.add(parent);
        }

        public State(State s) {
            left = s.left;
            rule.addAll(s.rule);
            pointer = s.pointer;
            ind = s.ind;
            parents.addAll(s.parents);
        }


        @Override
        public int compareTo(State s) {
            int res;
            if(left.equals(s.left)) res =0;
            else if(left.length()<=s.left.length()) res=-1;
            else res = 1;
            if(res!=0) return res;
            if(rule.size()==s.rule.size()) {
                for (int i = 0; i < rule.size(); ++i) {
                    if (!rule.get(i).equals(s.rule.get(i))) {
                        res =-1;
                        break;
                    }
                }
                res =0;
            }
            else if(rule.size()<s.rule.size()) res = -1;
            else res=1;
            if(res!=0) return res;
            res = Integer.compare(pointer,s.pointer);
            if(res!=0) return res;
            res = Integer.compare(ind,s.ind);
            if(res!=0) return res;
            return res;
        }
    }

    private HashMap<String, ArrayList<ArrayList<String>>> rules = new HashMap<>();

    /**
     * Считывает грамматику из файла
     * @param grammar файл с грамматикой
     */
    private void readGrammar(File grammar) {
        try (BufferedReader rd = new BufferedReader(new FileReader(grammar))) {
            String key;
            String line;
            while ((line = rd.readLine()) != null) {
                key = line.substring(0, (line.indexOf("::=")));
                line = line.substring(line.indexOf('=') + 1);
                StringTokenizer ExtenderRules = new StringTokenizer(line.trim(), "|");
                ArrayList<ArrayList<String>> arr = new ArrayList<>();
                while (ExtenderRules.hasMoreTokens()) {
                    String token = ExtenderRules.nextToken();
                    ArrayList<String> Rule = new ArrayList<>();
                    StringTokenizer ExtenderWords = new StringTokenizer(token, " ");
                    while (ExtenderWords.hasMoreTokens()) {
                        Rule.add(ExtenderWords.nextToken());
                    }
                    arr.add(Rule);
                }
                rules.put(key, arr);
            }
        } catch (IOException exc) {
            System.out.println("Error");
        }
    }

    /**
     * Алгоритм Эрли. Запускает считыватель, предсказатель или завершатель по мере необходимости в зависимости
     * от того, где находится указатель
     * @return true - если грамматика порождает строку, false - если нет
     */
    private boolean earley() {

        ArrayList<String> startRule = new ArrayList<>();
        startRule.add("S");

        for (int i = 0; i <= tokens.size(); i++) states.add(new TreeSet<State>());

        State BEGINING_STATE = new State("S'", startRule, 0, 0, null);
        State ENDING_STATE = new State("S'", startRule, 1, 0, null);

        states.get(0).add(BEGINING_STATE);
        for (int i = 0; i < tokens.size(); ++i) {
            ArrayDeque<State> que = new ArrayDeque<>(states.get(i));
            while (!que.isEmpty()) {
                State viewedState = que.pollFirst();
                int pointer = viewedState.pointer;
                if (pointer == viewedState.rule.size()) complete(viewedState, i, que);
                else {
                    String elem = viewedState.rule.get(pointer);
                    // проверка на то, что элемент либо тэг (класс Tag), либо класс токена
                    if (elem.matches("\\p{Digit}+")) scan(viewedState, i);
                    else predict(viewedState, i, que);
                }
            }
        }
        int end = tokens.size();
        ArrayDeque<State> que = new ArrayDeque<>(states.get(end));
        while (!que.isEmpty() && !states.get(end).contains(ENDING_STATE)) {
            State viewedState = que.pollFirst();
            lastComplete(viewedState, end, que);
        }
        return states.get(end).contains(ENDING_STATE);
    }

    /**
     * Функция считыватель для Эрли. Если i символ входной строки совпадает с i символом в i множестве событий,
     * то указатель сдвигается и новое правило добавляется в следуещее множнество
     * @param viewedState правило, где указатель перед терминалом
     * @param i индекс нужного множество
     */
    private void scan(State viewedState, int i) {
        //выбирается терминал перед которым стоит точка
        int pointed = new Integer(viewedState.rule.get(viewedState.pointer));
        if(tokens.get(i).getTag() == pointed){
            State newState = new State(viewedState);
            newState.pointer++;
            states.get(i+1).add(newState);
        }
        // TODO Синтаксическая ошибка
        //else
    }

    /**
     * Завершатель для Эрли. Берет индекс входного State (поле ind) и по нему выбирает множество M.
     * Далее выбираются из М все State у которых индекс совпадает с ранее выбранным индексом и указатель на символ стоит
     * в начале (поле pointed)
     * @param viewedState правило, где указатель в конце
     * @param i индекс множества, в котором содержится viewedState
     */
    private void complete(State viewedState, int i, ArrayDeque<State> que) {
        int ind = viewedState.ind;
        TreeSet<State> M = states.get(ind);
        for(State state: M){
            if(state.pointer==0 && state.ind==ind) {
                for (State parent : state.parents) {
                    State newState = new State(parent);
                    newState.pointer++;
                    if(!states.get(i).contains(newState)) {
                        states.get(i).add(newState);
                        que.addLast(newState);
                    }
                    else
                        // TODO опасная зона на неправильный возврат значений
                        states.get(i).ceiling(newState).parents.add(viewedState);
                }
            }
        }
    }


    private void lastComplete(State viewedState, int i, ArrayDeque<State> que) {
        int ind = viewedState.ind;
        TreeSet<State> M = states.get(ind);
        for(State state: M){
            if(state.pointer==0 && state.ind==ind) {
                for (State parent : state.parents) {
                    State newState = new State(parent);
                    if(++newState.pointer==newState.rule.size()) {
                        states.get(i).add(newState);
                        que.addLast(newState);
                    }
                }
            }
        }
    }
    /**
     * Предикт для Эрли. Добавляет все порождения входного правила
     * @param viewedState правило, где указатель перед нетерминалом
     * @param i индекс нужного множество
     */
    private void predict(State viewedState, int i, ArrayDeque<State> que) {
        //выбирается нетерминал перед которым стоит точка
        String pointed = viewedState.rule.get(viewedState.pointer);
        // Можно ли упростить? тут проверка на существование этого нетерминала в грамматике(Кстати, тут можно выдать
        // синтаксическую ошибку)
        if (rules.containsKey(pointed)) {
            //добавление порождений
            for (ArrayList<String> r : rules.get(pointed)) {
                State newState=new State(pointed, r, 0, i, viewedState);
                if(!states.get(i).contains(newState)) {
                    states.get(i).add(newState);
                    que.addLast(newState);
                }
                else
                // TODO опасная зона на неправильный возврат значений
                    states.get(i).ceiling(newState).parents.add(viewedState);
            }
        }
    }



    public Earley(ArrayList<Token> tokens, File grammFile) {
        this.tokens = tokens;
        readGrammar(grammFile);
    }

    public static void main(String[] args) {
        Lexi lexi=null;
        try {
            lexi = new Lexi(new File("src\\main\\resources\\PROG1.txt"));
        } catch (Exception e) {
            System.out.println("Файл не найден");
        }
        Earley solution = new Earley(lexi.tokens, new File("src\\main\\resources\\test.txt"));
        System.out.println(solution.earley());
        //Surrogate.Generator generator = new Surrogate.Generator(lexi.tokens, "src\\outputCode.asm");
       // generator.generate();
    }
}