#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <Windows.h>

using namespace std;
int s_count = 0;
const int M = 256;
const int page_size = 20;
int C[M][M];
int codblock = 0;
int simvB = 0;
float leng = 0;
int sumA = 0;
int sumL = 0;

struct code
{
    char a;
    float p;
    float q;
    int l;
}
A[M], B[166];

struct record1 {
    char a[30];
    short int b;
    char c[22];
    char d[10];
};

struct vertex {
    record1* data;
    vertex* left;
    vertex* right;
    vertex* next;
    int Bal;
};

struct tLE {
    record1 data;
    int digit[4];
    tLE* next;
};

struct queue {
    tLE* head = nullptr;
    tLE* tail = nullptr;

    void enqueue(tLE* r) {
        tLE* newNode = new tLE();
        *newNode = *r;
        newNode->next = nullptr;
        if (tail) {
            tail->next = newNode;
        }
        tail = newNode;
        if (!head) {
            head = newNode;
        }
    }

    tLE* dequeue() {
        if (!head) return nullptr;
        tLE* temp = head;
        head = head->next;
        if (!head) {
            tail = nullptr;
        }
        return temp;
    }

    bool isEmpty() {
        return head == nullptr;
    }
};

vertex* LL(vertex*& p) {
    vertex* q = p->left;
    p->Bal = 0;
    q->Bal = 0;
    p->left = q->right;
    q->right = p;
    return q;
}

vertex* RR(vertex*& p) {
    vertex* q = p->right;
    p->Bal = 0;
    q->Bal = 0;
    p->right = q->left;
    q->left = p;
    return q;
}

vertex* LR(vertex*& p) {
    vertex* q = p->left;
    vertex* r = q->right;

    if (r->Bal < 0) p->Bal = 1;
    else p->Bal = 0;

    if (r->Bal > 0) q->Bal = -1;
    else q->Bal = 0;

    r->Bal = 0;

    q->right = r->left;
    p->left = r->right;
    r->left = q;
    r->right = p;

    return r;
}

vertex* RL(vertex*& p) {
    vertex* q = p->right;
    vertex* r = q->left;

    if (r->Bal > 0) p->Bal = -1;
    else p->Bal = 0;

    if (r->Bal < 0) q->Bal = 1;
    else q->Bal = 0;

    r->Bal = 0;

    q->left = r->right;
    p->right = r->left;
    r->right = q;
    r->left = p;

    return r;
}

bool AVL(record1* D, vertex*& p, bool& Rost) {
    if (p == NULL) {
        p = new vertex;
        p->data = D;
        p->left = NULL;
        p->right = NULL;
        p->next = NULL;
        p->Bal = 0;
        Rost = true;
    } else {
        int cmp = strcmp(D->a, p->data->a);
        if (cmp == 0) {
            AVL(D, p->next, Rost);
            Rost = false;
        }
        else if (cmp < 0) {
            AVL(D, p->left, Rost);
            if (Rost) {
                if (p->Bal > 0) {
                    p->Bal = 0;
                    Rost = false;
                } else if (p->Bal == 0) {
                    p->Bal = -1;
                    Rost = true;
                } else {
                    if (p->left->Bal < 0) {
                        p = LL(p);
                    } else {
                        p = LR(p);
                    }
                    Rost = false;
                }
            }
        }
        else if (cmp > 0) {
            AVL(D, p->right, Rost);
            if (Rost) {
                if (p->Bal < 0) {
                    p->Bal = 0;
                    Rost = false;
                } else if (p->Bal == 0) {
                    p->Bal = 1;
                    Rost = true;
                } else {
                    if (p->right->Bal > 0) {
                        p = RR(p);
                    } else {
                        p = RL(p);
                    }
                    Rost = false;
                }
            }
        }
    }
    return true;
}


vertex* tree_search(vertex *p, char x[], int size) {
    while (p != nullptr) {
        if (strncmp(x, p->data->a, size) < 0) {
            p = p->left;
        } else if (strncmp(x, p->data->a, size) > 0) {
            p = p->right;
        } else {
            break;
        }
    }
    return p;
}

int size_tree = 0;
void obhod_left(vertex *p) {
    if (p != NULL) {
        obhod_left(p->left);

        vertex *o = p;
        while (o != NULL) {
            cout << p->data->a << "\t"
                 << p->data->c << "\t"
                 << p->data->b << "\t"
                 << p->data->d << "\t" << endl;
            size_tree++;
            o = o->next;
        }

        obhod_left(p->right);
    }
}


void convertDateToDigits(tLE* node) {
    int year = (node->data.d[6] - '0') * 10 + (node->data.d[7] - '0');
    int month = (node->data.d[3] - '0') * 10 + (node->data.d[4] - '0');
    int day = (node->data.d[0] - '0') * 10 + (node->data.d[1] - '0');

    year += 1900;
    int dateNum = year * 10000 + month * 100 + day;

    node->digit[0] = (dateNum >> 24) & 0xFF;
    node->digit[1] = (dateNum >> 16) & 0xFF;
    node->digit[2] = (dateNum >> 8) & 0xFF;
    node->digit[3] = dateNum & 0xFF;
}

void DigitalSort(tLE** head) {
    int d, i, j;
    tLE* p;
    queue q[256];

    for (j = 3; j >= 0; j--) {
        for (i = 0; i < 256; i++) {
            q[i].head = nullptr;
            q[i].tail = nullptr;
        }

        p = *head;
        while (p != nullptr) {
            d = p->digit[j];
            tLE* nextNode = p->next;
            p->next = nullptr;
            if (q[d].tail == nullptr) {
                q[d].head = p;
            } else {
                q[d].tail->next = p;
            }
            q[d].tail = p;
            p = nextNode;
        }

        p = nullptr;

        for (i = 0; i < 256; i++) {
            if (q[i].head != nullptr) {
                if (p == nullptr) {
                    *head = q[i].head;
                } else {
                    p->next = q[i].head;
                }
                p = q[i].tail;
            }
        }

        if (p != nullptr) {
            p->next = nullptr;
        }
    }
}

void displayRecords(tLE* head, int start, int count) {
    tLE* current = head;
    int i = 0;
    while (current != nullptr && i < start) {
        current = current->next;
        i++;
    }
    i = 0;
    while (current != nullptr && i < count) {
        cout << current->data.a << "\t" << current->data.b << "\t"
             << current->data.c << "\t" << current->data.d << endl;
        current = current->next;
        i++;
    }
}

int getTotalRecords(tLE* head) {
    tLE* temp = head;
    int totalRecords = 0;
    while (temp != nullptr) {
        totalRecords++;
        temp = temp->next;
    }
    return totalRecords;
}

queue BinarySearchByYear(tLE* head, const char* targetYear) {
    int totalRecords = getTotalRecords(head);
    tLE* nodes[totalRecords];
    tLE* temp = head;

    for (int i = 0; i < totalRecords; i++) {
        nodes[i] = temp;
        temp = temp->next;
    }

    int L = 0, R = totalRecords - 1, flag = -1, m;

    while (L < R) {
        m = (L + R) / 2;
        if (strncmp(nodes[m]->data.d + 6, targetYear, 2) < 0) {
            L = m + 1;
        } else {
            R = m;
        }
    }

    if (strncmp(nodes[R]->data.d + 6, targetYear, 2) == 0) {
        flag = R;
    }

    queue recordQueue;

    if (flag == -1) {
        cout << "No records found for year: " << (1900 + atoi(targetYear)) << endl;
        return recordQueue;
    }

    int i = flag;
    cout << "Records found for year " << (1900 + atoi(targetYear)) << ":\n";

    int foundCount = 0;

    while (i < totalRecords && strncmp(nodes[i]->data.d + 6, targetYear, 2) == 0) {
        cout << nodes[i]->data.a << "\t" << nodes[i]->data.b << "\t"
             << nodes[i]->data.c << "\t" << nodes[i]->data.d << endl;

        recordQueue.enqueue(nodes[i]);
        foundCount++;
        i++;
    }

    cout << "Total records found: " << foundCount << endl;

    return recordQueue;
}


vertex* buildAVLFromQueue(queue& q) {
    vertex* root = nullptr;
    bool Rost;

    while (!q.isEmpty()) {
        tLE* node = q.dequeue();
        AVL(&(node->data), root, Rost);
    }

    return root;
}

int sum = 0;
float entropy = 0;

void ToNull()
{
    for(int i = 0; i < M; i++)
    {
        A[i].a = char(i-128);
        A[i].p = 0;
        A[i].q = 0;
        A[i].l = 0;
    }
    sum = 0;
    entropy = 0;
    codblock = 0;
    simvB = 0;
    leng = 0;
    sumA = 0;
    sumL = 0;

}

void CreateP()
{
    for(int i = 0; i < M; i++)
    {
        A[i].p /= sum;
        if(A[i].p > 0)
        {
            simvB += 1;
            entropy += A[i].p * abs(log2(A[i].p));
        }
    }
}
void CreateB()
{
    int j = 0;
    for(int i = 0; i < M; i++)
    {
        if(A[i].p > 0)
        {
            B[j] = A[i];
            j++;
        }
    }
}

void MoorCode()
{
    float pr = 0;
    for(int i = 0; i < simvB; i++)
    {
        B[i].q = pr + B[i].p/2;
        pr += B[i].p;
        B[i].l = ceil(-log2(B[i].p)) + 1;
    }
    for(int i = 0; i < simvB; i++)
    {
        for(int j = 0; j < B[i].l; j++)
        {
            B[i].q *= 2;
            C[i][j] = floor(B[i].q);
            if(B[i].q > 1)
            {
                B[i].q -= 1;
            }
        }
    }
}

void CodePrepar()
{
    FILE* fp;
    fp = fopen("testBase2.dat", "rb");
    ToNull();

    while (!feof(fp))
    {
        char c;
        fscanf(fp, "%c", &c);

        A[c + 128].p++;
        sum++;
    }
    CreateP();
    CreateB();
    MoorCode();
    fclose(fp);
}

void codeOutput()
{
    int mode = 0;
    while(mode != 1)
    {
        leng = 0;
        cout << "Gilbert-Moore code" << endl;
        cout << endl;
        cout << "num" << "  " << "Symbol " << " " << "Probability" << " " << "Code word" << "   " << "Code word length" << endl;
        float q = 0;
        for (int i = 0; i < simvB; i++)
        {
            leng += B[i].p * B[i].l;
            q += B[i].p;
            cout << i+1 << "    " << B[i].a << "    "; printf("%.5f", B[i].p);
            cout << "       ";
            for(int j = 0; j < B[i].l; j++)
            {
                cout << C[i][j];
            }
            if(B[i].l >= 8)
            {
                cout << "\t\t";
            }
            else
            {
                cout << "\t\t\t";
            }
            cout << B[i].l;
            cout << endl;
        }
        cout << "\t" << "Sum frequencies = " << q << endl;
        cout << endl;
        cout << "Entropy:" << " " << "Average length:" << endl;
        cout << entropy << "\t\t"; printf("%.5f", leng);
        cout << endl;
        cout << endl;
        cout << "data compression ratio: " << (sumL / 8) * 100 / sumA << endl;
        cout << endl;
        cout << "Input command number: ";
        cin >> mode;
    }
}

void codeDB()
{
    FILE *fp, *fc;
    fp = fopen("testBase2.dat", "rb");
    fc = fopen("codedBase2.dat", "wb");

    char c;
    while(!feof(fp))
    {
        fscanf(fp, "%c", &c);
        sumA++;
        for(int i = 0; i < simvB; i++)
        {
            if(c == B[i].a)
            {
                sumL += B[i].l;
                for(int j = 0; j < B[i].l; j++)
                {
                    putc(C[i][j], fc);
                }
            }
        }
    }

    fclose(fp);
    fclose(fc);
}

int main() {
    system("chcp 866 > nul");
    FILE* fp = fopen("testBase2.dat", "rb");

    if (!fp) {
        cout << "Error opening file!" << endl;
        return 1;
    }

    record1 records[4000] = { 0 };
    tLE* head = nullptr;
    tLE* tail = nullptr;

    vertex* searchAVLRoot = nullptr;
    bool Rost;

    int count = fread(records, sizeof(record1), 4000, fp);
    fclose(fp);

    for (int i = 0; i < count; i++) {
        tLE* node = new tLE();
        node->data = records[i];
        node->next = nullptr;
        convertDateToDigits(node);

        if (head == nullptr) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }

    DigitalSort(&head);

    int start = 0;
    const int linesPerPage = 20;
    int totalRecords = getTotalRecords(head);
    char command;

    while (true) {
        system("cls");
        displayRecords(head, start, linesPerPage);

        cout << "\nCommands: (N)ext page, (P)revious page, (L)ast page, (B)inary search by birth date, ";
        cout << "(S)earch by FIO (AVL), (O)bhod LR, (C)ode, (E)xit\n";
        cout << "Enter command: ";
        cin >> command;

        if (command == 'N' || command == 'n') {
            start += linesPerPage;
            if (start >= totalRecords) start = totalRecords - linesPerPage;
        } else if (command == 'P' || command == 'p') {
            start -= linesPerPage;
            if (start < 0) start = 0;
        } else if (command == 'L' || command == 'l') {
            start = totalRecords - linesPerPage;
            if (start < 0) start = 0;
        } else if (command == 'B' || command == 'b') {
            cout << "Enter birth year (yy): ";
            string year;
            cin >> year;

            queue searchResultQueue = BinarySearchByYear(head, year.c_str());

            if (!searchResultQueue.isEmpty()) {
                searchAVLRoot = buildAVLFromQueue(searchResultQueue);
            }

            cout << "\nPress any key to return to the main menu...";
            cin.ignore();
            cin.get();
        } else if (command == 'S' || command == 's') {
            cout << "Enter FIO for search: ";
            char fullname[32];
            string fio;
            cin.ignore();
            getline(cin, fio);
            for (int i = 0; i < fio.length(); i++){
                fullname[i] = fio[i];
            }
            fullname[fio.length()] = '\0';
            vertex* result = NULL;
            result = tree_search(searchAVLRoot, fullname, fio.length());
            if (result) {
                cout << "Found: " << endl;
                int i = 0;
                while (result != NULL){
                    cout << i + 1 << "\t" << result->data->a << "\t" << result->data->b << "\t"
                     << result->data->c << "\t" << result->data->d << endl;
                    result = result->next;
                    i++;
                }
            } else {
                cout << "FIO not found.\n";
            }

            cout << "\nPress any key to return to the main menu...";
            cin.ignore();
            cin.get();
        } else if (command == 'O' || command == 'o') {
            size_tree = 0;
            if (searchAVLRoot) {
                cout << "\nLR Obhod:\n";
                obhod_left(searchAVLRoot);
                cout << "Total records displayed: " << size_tree << endl;
            } else {
                cout << "No search result tree available. Perform a binary search first.\n";
            }
            cout << "\nPress any key to return to the main menu...";
            cin.ignore();
            cin.get();
        } else if (command == 'C' || command == 'c'){
            SetConsoleCP(866);
                if(codblock == 0)
                {
                    CodePrepar();
                    codeDB();
                    codblock = 1;
                }
                codeOutput();
        }else if (command == 'E' || command == 'e') {
            break;
        } else {
            cout << "Invalid command!" << endl;
        }
    }

    tLE* current = head;
    while (current != nullptr) {
        tLE* next = current->next;
        delete current;
        current = next;
    }

    return 0;
}