main.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <array>
#include <vector>
#include <boost/random.hpp>
#include <afxres.h>
#include <random>
#include <chrono>
#include <iomanip>
#include <conio.h>
#include "tree.hh"

//G({0,1,2,3,4,5,6,7,8,9,-,+},{S,T,F}, P, S)
//P:
//  S->T|+T|-T
//  T->F|TF
//  F->0|1|2|3|4|5|6|7|8|9


//G({0,1,2,3,4,5,6,7,8,9,-,+},{S,T,F}, {S->T|+T|-T, T->F|TF, F->0|1|2|3|4|5|6|7|8|9}, S)

using namespace std;

int Rand(size_t max){
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine generator (seed);
    std::uniform_int_distribution<int> distribution(0, max - 1);
    return distribution(generator);
}

int _min = 6;
int _max = 8;
int realSize = 0;
vector <string> Out;
array <int, 260> compactedRulesIndex {{0}};
array <int, 260> compactedRulesIndexLen {{0}};
string permanent_start_point;

template <typename T>
void printVector(T s)
{
    cout << "##########DEBUG VECTOR" << endl;
    int z = 0;
    for (auto i = s.begin(); i != s.end(); ++i)
    {
        if(z > 4){
            cout << endl;
            z = 0;
        }
        cout << *i << "->";
        z++;
    }
    cout << endl << "##########DEBUG VECTOR" << endl;
};

template void printVector<vector <int>> (vector <int>);
template void printVector<vector <string>> (vector <string>);

void printVectorAndExit(vector<string> s)
{
    sort( s.begin(), s.end() );
    s.erase( unique( s.begin(), s.end() ), s.end() );
    for (auto i = s.begin(); i != s.end(); ++i)
        cout << *i << "->";
    cout << endl <<  "program ended, press enter to exit" << endl;
    getch();
    exit(0);
}

bool strInAlphabet(const string &source_alphabet, const string &tick)
{
    bool ex = false;
    if (source_alphabet.find(tick)!=std::string::npos)ex = true;
    return ex;
}

string vecToString(vector<string> v)
{
    string out;
    return accumulate(begin(v), end(v), out);
}

vector <string> merge(vector <string> v, string s)
{
    vector <string> o;
    for(int i=0;i<s.length();i++)
        o.push_back(string (1, s[i]));
    for (auto it = v.begin() ; it != v.end(); ++it)
        o.push_back(*it);
    return o;
}

int main() {
    string grammar = "0,1,2,3,4,5,6,7,8,9;"
            "A,B,C,D,E;"
            "A->BC,B->2|DE,C->4|5,D->6|7,E->8|9;"
            "A";

    std::istringstream ss(grammar);
    std::string token;

    array <string, 4> G;

    int i=0;
    while(std::getline(ss, token, ';')) {
        G[i] = token;
        i++;
    }

    string source_alphabet = G[0];
    string termination_symbols = G[1];
    string rules = G[2];
    string start_symbol = G[3];

    cout << "source alphabet:       " << source_alphabet      << endl;
    cout << "termination symbols:   " << termination_symbols  << endl;
    cout << "rules:                 " << rules                << endl;
    cout << "start symbol:          " << start_symbol         << endl;

    //calculate rules length
    std::istringstream ss_rules(rules);
    int rules_len = 0;
    i=0;
    vector <string> Rules;

    while(std::getline(ss_rules, token, ',')) {
        Rules.push_back(token);
        i++;
    }

    vector <char> TerminationSymbols;
    std::istringstream ss_termination(termination_symbols);
    while(std::getline(ss_termination, token, ',')) {
        TerminationSymbols.push_back(token[0]);
    }

    bool match = false;
    for(int z=0;z<TerminationSymbols.size();z++)
    {
        if(start_symbol[0] == TerminationSymbols[z])match = true;
    }

    if(!match)
    {
        cout << "Start symbol not listed in termination symbols" << endl;
        exit(1);
    }


    rules_len = i;
    ::realSize = i;
    cout << endl;
    string pattern = "->";
    char token_delimeter = '|';
    array <vector <string>, 260> compactedRules;

    for(int z=0;z<rules_len;z++)
    {
        std::istringstream rule(Rules[z].substr(Rules[z].find(pattern)+pattern.length()));
        while(std::getline(rule, token, token_delimeter))
        {
            int idx = Rules[z][0];
            compactedRules[idx].push_back(token);
            compactedRulesIndexLen[idx]++;
        }
    }

    for(int z=0;z<rules_len;z++)
    {
        cout << Rules[z][0] << pattern;
        for (auto x = compactedRules[(int)Rules[z][0]].begin(); x != compactedRules[(int)Rules[z][0]].end(); ++x)
            std::cout << *x << token_delimeter;
        cout << endl;
    }

    if(compactedRules[(int)start_symbol[0]].empty())
        cout << "exit, empty array based on address " << (int)start_symbol[0] << " (this is " << start_symbol[0] << " symbol)" << endl;

    tree<string> tr;
    tree<string>::iterator root;
    root=tr.begin();

    permanent_start_point = start_symbol;
    tr.insert(root, permanent_start_point);

    string tick = permanent_start_point;
    int tick_int = (int)tick[0];

    bool fuck = true;
    vector <string> treePath;
    treePath.push_back(tick);

    vector<string> outTree;
    int max_stack_size = 50;
    int current_stack_size = 0;

    vector <string> complicated[10];
    bool proc = false;
    bool comp = false;
    vector <int> cindex {{0}};
    int ccindex = 0;
    string blocks;
    vector <string> vblocks;


    //save old index table
    array <int, 260> t1 {{0}};
    array <int, 260> t2 {{0}};

    vector <string> tempHead;

    bool firstrun = false;
    while(fuck)
    {
        cout << "STACK SIZE: " << current_stack_size << endl;
        cout << "cindex: " << endl;
        printVector(cindex);
        cout << "blocks: " << blocks << endl;
        cout << "blocks length: " << blocks.length() << endl;

        if(current_stack_size > max_stack_size)
        {
            cout << "maximum stack size exceeded" << endl;
            cout << "please fix grammar and try again" << endl;
            getch();
            break;
        }

        if(proc)
        {
            ccindex = cindex.back();
            cindex.pop_back();
            if(ccindex == blocks.length())
            {
                proc = false;
                comp = false;
                cout << "VBLOCKS: " << endl;
                printVector(vblocks);

                if(!vblocks.empty())
                {
                    vblocks.pop_back();
                    continue;
                }
                printVectorAndExit(outTree);
            }
            cout << "TICK: " << tick << endl;
            string cc (1, blocks[ccindex++]);
            tick = cc;
            cout << "TICK: " << tick << endl;
            proc = false;
            comp = true;
            t1 = compactedRulesIndex;
            t2 = compactedRulesIndexLen;

            cout << "TREE PATH: " << vecToString(treePath) << endl;
        }else {
            tick = compactedRules[tick_int][compactedRulesIndex[tick_int]];
            cout << "CURRENT TICK IS: " << tick << endl;
        }

        if(tick.length() > 1)
        {
            tempHead = treePath;
            vblocks.push_back(tick);
            blocks = tick;
            proc = true;
            cout << "TREE PATH: " << endl;
            printVector(treePath);
            continue;
        }else
        {
            if(treePath[0][0] != start_symbol[0])
            {
                treePath = merge(treePath, vecToString(tempHead));
            }

            treePath.push_back(tick);
        }

        cout << "OUT TREE: " << endl;
        printVector(outTree);

        printVector(treePath);

        if (strInAlphabet(source_alphabet, tick))
        {
            int start_pos = 2;
            do{
                int pos = treePath.size()-start_pos++;
                cout << "POS: " << pos << endl;
                if(pos < 0){
                    if(comp == true)
                    {
                        proc = true;
                        compactedRulesIndex = t1;
                        compactedRulesIndexLen = t2;
                        break;
                    }
                    outTree.push_back(vecToString(treePath));
                    printVectorAndExit(outTree);
                }
                tick = treePath[pos];
                cout << "possible new tick is: " << tick << endl;
                tick_int = (int)tick[0];
                compactedRulesIndex[tick_int]++;
            } while(compactedRulesIndex[tick_int] == compactedRulesIndexLen[tick_int]);

            cout << "TREE PATH: " << vecToString(treePath) << endl;
            outTree.push_back(vecToString(treePath));
            for (int z = start_pos; z > 2; z--)
                treePath.pop_back();
            cout << "TREE PATH: " << vecToString(treePath) << endl;
            current_stack_size = 0;
        }

        tick_int = (int)tick[0];
        cout << "OUT VECTOR" << endl;
        printVector(outTree);
        current_stack_size++;
    }
    return 0;
}