#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cstdlib>

using namespace std;

struct element
{
    string data;
    element* next;
    element* prev;
};

struct queues
{
    element* head;
    element* tail;
};

struct lists
{
    element* head;
    element* tail;
    int el_num;
};

struct stacks
{
    string data;
    stacks* next;
};

void push(stacks* &st, string new_data);                                    //dodawanie elementu do stosu
void pop(stacks* &st);                                                      //usuwanie elementu ze stosu
string import(stacks* st);

lists create_empty_list();
element* create_element(string new_data);
void add_tail(string new_data, lists &ls);
void wyswietl_liste(lists ls);

queues create_queue();
void enqueue(queues &qs, string new_data);

bool search_pattern(string pattern, string text, int q,int &amount);

void import_data(string path, lists &ls);

void zadanie1(lists &ls);
void zadanie2(lists ls,queues &qs);
void zadanie3(queues qs);

int main()
{
    lists ls = create_empty_list();
    queues qs = create_queue();
    zadanie1(ls);
    zadanie2(ls,qs);
    zadanie3(qs);
    return 0;
}

bool search_pattern(string pat, string txt, int q,int &amount)
{
    int M = pat.length();
    int N = txt.length();
    bool counter=0;
    amount=0;
    int i, j;
    int d=256;
    int p = 0;
    int t = 0;
    int h = 1;

    for (i = 0; i < M - 1; i++)
        h = (h * d) % q;

    for (i = 0; i < M; i++)
    {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }


    for (i = 0; i <= N - M; i++)
    {

        if ( p == t )
        {
            for (j = 0; j < M; j++)
            {
                if (txt[i+j] != pat[j])
                    break;
            }

            if (j == M)
            {
                counter=1;
                amount++;
            }
        }

        if ( i < N-M )
        {
            t = (d*(t - txt[i]*h) + txt[i+M])%q;

            if (t < 0)
            t = (t + q);
        }
    }
    return counter;
}

lists create_empty_list()
{
    lists ls;
    ls.head = nullptr;
    ls.tail = nullptr;
    ls.el_num=0;
    return ls;
}

element* create_element(string new_data)
{
    element* temp = new element;
    temp->data=new_data;
    temp->next=nullptr;
    temp->prev=nullptr;
    return temp;
}

void import_data(string path, lists &ls)
{
    stacks* st = nullptr;
    ifstream file;
    string slowo, zdanie;
    file.open(path);
    char temp;
    while(file>>slowo)
    {
        while(1)
        {
            temp=' ';
            if(slowo[slowo.size()-1] == '?' || slowo[slowo.size()-1] == '!' || slowo[slowo.size()-1] == '.')
            {
                temp = slowo[slowo.size()-1];
                slowo.pop_back();
                push(st, slowo);
                break;
            }
            push(st,slowo);
            file>>slowo;
            if(file.eof()) break;
        }

        ostringstream ss;
        while(st!=nullptr)
        {
            ss<<import(st)<<" ";
            pop(st);
        }
        zdanie=ss.str();
        zdanie.pop_back();
        zdanie.push_back(temp);
        ss.str("");
        add_tail(zdanie,ls);
    }
    file.close();
}

void push(stacks* &st, string new_data)
{
    stacks* dodawany_element=new stacks;
    dodawany_element->data=new_data;
    dodawany_element->next=st;
    st=dodawany_element;
}

void pop(stacks* &st)
{
    stacks* temp = st;
    st=st->next;
    delete temp;
}

string import(stacks* st)
{
    string data_to_return=st->data;
    return data_to_return;
}

void add_tail(string new_data, lists &ls)
{
    element* n_e = create_element(new_data);
    if(ls.el_num==0)
        ls.head=n_e;
    else
        ls.tail->next=n_e;
    n_e->prev=ls.tail;
    ls.tail=n_e;
    ls.el_num++;
}

void wyswietl_liste(lists ls)
{
    element* temp=ls.head;
    do{
        cout<<temp->data<<endl;
        temp=temp->next;
    }while(temp!=nullptr);
}

queues create_queue()
{
    queues new_queue;
    new_queue.head=nullptr;
    new_queue.tail=nullptr;
    return new_queue;
}

void enqueue(queues &qs,string new_data)
{
    element* new_el=new element;
    new_el->data=new_data;
    new_el->next=nullptr;
    if(qs.tail!=nullptr)qs.tail->next=new_el;
    qs.tail=new_el;
    if(qs.head==nullptr)qs.head=new_el;
}

void zadanie1(lists &ls)
{
    cout<<"Zadanie 1"<<endl<<endl;
    import_data("inversed.txt",ls);
    wyswietl_liste(ls);
    cout<<"--------------------------------------------------------"<<endl;
}

void show_queue(queues qs)
{
    element* temp=qs.head;
    do
    {
        cout<<temp->data<<endl;
        temp=temp->next;
    }while(temp!=nullptr);
}
void zadanie2(lists ls,queues &qs)
{
    element* temp=ls.head;
    int q=101,z;
    cout<<endl<<"Zadanie 2"<<endl<<endl;
    do
    {
        if (((search_pattern("promotion", temp->data,q,z))==1) || ((search_pattern("discount", temp->data,q,z))==1) || ((search_pattern("sale", temp->data,q,z))==1) || ((search_pattern("offer", temp->data,q,z))==1))
        {
            enqueue(qs, temp->data);
        }
        temp=temp->next;
    }while(temp!=nullptr);

    show_queue(qs);

    cout<<"--------------------------------------------------------"<<endl;
}
void zadanie3(queues qs)
{
    element* temp=qs.head;
    int q=101;
    int z,x,c,v,y;
    cout<<endl<<"Zadanie 3"<<endl<<endl;
    do{
        if (((search_pattern("unique offer", temp->data,q,z))==1) || ((search_pattern("mega discounts", temp->data,q,x))==1) || ((search_pattern("super promotion", temp->data,q,c))==1) || ((search_pattern("low prices", temp->data,q,v))==1) || ((search_pattern("great sale", temp->data,q,y))==1))
        cout<<temp->data<<endl;
        temp=temp->next;
    }while(temp!=nullptr);
    cout<<"unique offer: "<<z<<endl;
    cout<<"mega discounts: "<<x<<endl;
    cout<<"super promotion: "<<c<<endl;
    cout<<"low prices: "<<v<<endl;
    cout<<"great sale: "<<y<<endl;
}