#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

//данные хранятся в виде массива структур из указателя и ключа

//структура элемента таблицы
typedef struct Item
{
    int key;     //ключ
    int release; //номер версии
    char* info;  //поле данных - строка
}Item;

//структура - таблица
typedef struct Table
{
    int size;  //максимальный размер таблицы
    int count; //текущий размер таблицы
    Item* val; //массив структур item
}Table;

const int SIZE = 10; //максимальны размер таблицы

//меню
int F1_End(Table*);           //функция выхода
int F2_Menu(Table*);          //меню
int F3_Print(Table*);         //вывод элементов
int F4_Generate(Table*);      //генерация рандомных значений в таблице
int F5_Input(Table*);         //ввод элемента
int F6_DeleteReleases(Table*);     //удаление элементов предыдущих версий
int F7_FindKey(Table*);       //поиск и копирование элемента
int F8_FindRelease(Table*);   //поиск версии

//функции работы с таблицей
Table* TableCreate(int size);                           //функция создания пустой таблицы
void TableDelete(Table* T);                             //удаление таблицы
void TablePrint(Table* T);                              //вывод таблицы
int TableAdd(Table* T, int key, char* info);            //добавление элемента с ключом в таблицу
int TableFindLast(Table* T, int key);                   //поиск элемнета последней версии по ключу в таблице (начинается с конца таблицы)
Table* TableFindKey(Table* T, int key);                 //поиск и получение копии элемента
char* TableFindRelease(Table* T, int key, int release); //поиск по ключу и версии
int TableDeleteRelease(Table* T);						//удаление предыдущих версий

int ItemPrint(Item*); //вывод элемента таблицы

//другие функции
int getInt(int*);   //чтение целого числа
int getStr(char**); //функция ввода строк


const char* msgs[] = { NULL, "Exit programm", "Show menu", "Print table", "Generate random table",
                       "Input item", "Delete releases", "Find key", "Find release" };  //строки меню

int main()
{
    int ex = 0;                                                 //переменые для удобного вывода меню
    int  menu = 0;                                              //далее до конца - вывод меню
    int(*fun[]) (Table*) = { NULL, F1_End, F2_Menu, F3_Print, F4_Generate,
                             F5_Input, F6_DeleteReleases,  F7_FindKey, F8_FindRelease };  //массив функций
    Table* T = TableCreate(SIZE);                                   //создание таблицы
    if (T == NULL)
    {
        puts("out of memory");
        return 0;
    }
    srand((unsigned int)time(NULL));                            //задаём зерно генератора

    F2_Menu(T);                                                 //вывод меню
    //выбор пункта меню
    while (ex != 1)
    {
        menu = 0;                           //пункт меню
        while (menu <= 0 || menu >= 9)
        {
            printf("Enter number menu (2 for enter menu): ");
            getInt(&menu);	//чтение номера пункта меню
            if (menu <= 0 || menu >= 9) {   // обнаружен неверный номер - ошибка
                printf("%s\n", "Error! Wrong symbol.");
                scanf("%*c");
            }
        }

        ex = (*fun[menu])(T);
    }
    return 0;
}

//интерфейсные функции

//завершение программы
int F1_End(Table* T)
{
    TableDelete(T); //удаление таблицы
    return 1;
}

//вывод меню
int F2_Menu(Table* T)
{
    int i;
    for (i = 1; i < 9; ++i)
        printf("%d %s\n", i, msgs[i]);//вывод пунктов меню
    return 0;
}

//вывод таблицы
int F3_Print(Table* T)
{
    puts("Table:");
    TablePrint(T); //вывод
    return 0;
}

//добавление случайных элементов
int F4_Generate(Table* T)
{
    char* str;
    int amount = 0; //количество добавляемых элементов
    int i, j;
    printf("Enter amount: ");
    getInt(&amount);
    for (i = 0; i < amount; i++)
    {  //цикл добавления
        str = (char*)calloc(5, sizeof(char));
        for (j = 0; j < 4; j++)                               //генерируем случайную строку
            str[j] = 'a' + rand() % 26;
        if (TableAdd(T, rand() % 1000, str))   //проверка на то, что таблица не переполнена
        {
            free(str);
            break;
        }
    }
    printf("Added %d keys.\n", i); //выводим сколько ключей мы смогли добавить
    return 0;
}

//добавление ключа
int F5_Input(Table* T)
{
    int key = 0;
    char* info;
    int res;
    printf("Enter key: ");
    getInt(&key);        //читаем ключ
    printf("Enter information: ");
    res = getStr(&info); //чтение информации
    if (res)  //проверка на возможность выделить память
    {
        puts("Memory is out");
        TableDelete(T); //удаляем таблицу при нехватке памяти
        return 1;
    }
    if (TableAdd(T, key, info)) //если добавление не успешно
        puts("Table is full");
    else //если успешно
        puts("Item added.");
    return 0;
}

//удаление элемента
int F6_DeleteReleases(Table* T)
{
    printf("Deleted %d items.\n", TableDeleteRelease(T)); //выводим сколько ключей мы удалили
    return 0;
}

//поиск в таблице ключа
int F7_FindKey(Table* T)
{
    int key = 0;
    Table* NewTable;
    printf("Enter key: "); //ввод ключа
    getInt(&key);
    NewTable = TableFindKey(T, key); //получаем указатель на ктаблицу с копиями ключа
    if (NewTable) //если был хотя бы один элемент с таким ключом
    {
        puts("Table:");
        TablePrint(NewTable);  //вывод
        TableDelete(NewTable); //и удаление таблицы
    }
    else
    {
        puts("Keys not found."); //или выводим сообщение об ошибке
    }
    return 0;
}

//поиск в таблице ключа и версии
int F8_FindRelease(Table* T)
{
    int key = 0;
    int release = 0;
    char* info;
    printf("Enter key: ");
    getInt(&key); //ввод ключа
    printf("Enter release: ");
    getInt(&release); //ввод версии
    info = TableFindRelease(T, key, release); //поиск информации по кючу и версии
    if (info)
        printf("Information: %s.\n", info); //вывод если нашли
    else
        puts("Key not found."); //иначе выводим сообщение об ошибке
    return 0;
}

//функци работы с таблицей

//создание таблицы, возвращаем указатель на пустую таблицу
Table* TableCreate(int size)
{
    Table* T;
    if (size <= 0)
        return NULL;
    T = (Table*)malloc(sizeof(Table)); //память под структуру таблицы
    if (T == NULL)
        return NULL;
    T->count = 0;
    T->size = size;
    T->val = (Item*)calloc(size, sizeof(Item)); //память под массив элементов
    if (T->val == NULL)
    {
        free(T);
        return NULL;
    }
    return T;
}

//удаление таблицы
void TableDelete(Table* T)
{
    int i;
    for (i = 0; i < T->count; i++)
        free(T->val[i].info); //удаление информации
    free(T->val); //чистка остальной памяти
    free(T);
}

//вывод таблицы
void TablePrint(Table* T)
{
    int i;
    printf("count = %d, size = %d.\n", T->count, T->size);
    printf("%2s %7s %7s %s\n", "i", "key", "release", "string");
    if (T->count == 0)
        puts("Empty table");
    else
    {
        for (i = 0; i < T->count; i++) {
            //проходим по массиву
            printf("%2d ", i);     //выводим очередной элемент
            ItemPrint(&T->val[i]);
        }
    }

}

//добавление ключа в таблицу
int TableAdd(Table* T, int key, char* info)
{
    int ind;
    if (T->count == T->size) //проверка на переполнение
        return 1;
    ind = TableFindLast(T, key);  //поиск индекса последней версии ключа

    //пишем новый элемент в конец таблицы
    T->val[T->count].info = info;
    T->val[T->count].key = key;

    if (ind < 0)
        T->val[T->count].release = 1;  //пишем правильную версию
    else
        T->val[T->count].release = T->val[ind].release + 1;
    ++T->count; //увеличиваем текущее количество элементов в таблице
    return 0;
}

//поиск последней версии элемента в таблице
int TableFindLast(Table* T, int key)
{
    int i;
    for (i = T->count - 1; i >= 0; i--) //идём с конца, т.к. версии элемента в силу механизма добавления расположены по возврастанию
        if (T->val[i].key == key)  //поэтому самое последнее упоминание ключа бужет с самой большой версией
            return i;
    return -1;
}

//сжатие массива
int TableZip(Table* T, int key, int release)
{
    int j = T->count; //переменная для хранения текущего размера
    int i = 0;
    while (i < j)
    {
        if (T->val[i].key == key and T->val[i].release != release) //если у текущего элемента тот же ключ, но другая версия
        {
            free(T->val[i].info); //удаляем строку
            for (int k = i; k < j - 1; k++) { //сдвигаем все элементы в массиве на один влево
                T->val[k].info = T->val[k + 1].info;
                T->val[k].key = T->val[k + 1].key;
                T->val[k].release = T->val[k + 1].release;
            }
            --j; //уменьшаем текущий размер на один
        }
        else {
            i++;
        }
    }
    int count = 0; //переменная для посчета числа удаленных элементов
    for (i = j; i < T->count; i++) {
        T->val[i].info = NULL; //удаление лишней информации
        count++;
    }
    T->count = j; //запоминаем новый размер
    return count;
}

//удаление старых весий элементов
int TableDeleteRelease(Table* T)
{
    int i = 0;
    int count = 0;
    while (i < T->count) { //проходимся по всем элемнтам
        int ver = TableFindLast(T, T->val[i].key); //получаем номер последней версии текущего элемента
        if (T->val[ver].release == T->val[i].release) { //если текущий элемент самая новая версия
            i++; //переходим к следующему элементу
        }
        else {
            count += TableZip(T, T->val[i].key, T->val[ver].release); //удаляем все старые версии
        }
    }
    return count;
}

//ищем элемент и создаём таблицу с найденными элементами
Table* TableFindKey(Table* T, int key)
{
    Table* NewTable = TableCreate(T->size);
    int i, j;
    for (i = 0; i < T->count; i++)
        if (T->val[i].key == key) //если элемент сущевстует и ключи совпали
        {
            j = NewTable->count; //пишем в конец нашей новой таблицы
            NewTable->val[j].info = (char*)calloc(strlen(T->val[i].info) + 1, sizeof(char));    //копию найденного элемента
            strcpy(NewTable->val[j].info, T->val[i].info);
            NewTable->val[j].key = key;
            NewTable->val[j].release = T->val[i].release;
            ++NewTable->count;                                   //увеличиваем размер таблицы
        }
    NewTable->size = NewTable->count;
    if (NewTable->count)
        return NewTable;
    else
        TableDelete(NewTable);
    return NULL;
}

//поиск по ключу и версии
char* TableFindRelease(Table* T, int key, int release)
{
    int i;
    char* info;
    for (i = 0; i < T->count; i++)
        if (T->val[i].key == key && T->val[i].release == release) //если совпало
        {
            info = (char*)calloc(strlen(T->val[i].info) + 1, sizeof(char));
            strcpy(info, T->val[i].info);                       //копируем инормацию
            return info;                                        //и возвращаем строку
        }
    return NULL;
}

//вывод элемента
int ItemPrint(Item* I)
{
    printf("%7d %7d %s\n", I->key, I->release, I->info);
    return 0;
}

//другие функции

//чтение целого числа
int getInt(int* a)
{
    int n = 0;
    do
    {
        n = scanf("%d", a); //считаем по адресу а - значение символа. сама функция вернёт -1, если конец файла, 0 если символ не корректный
        if (n <= 0)                                                     // обнаружен некорректный символ - ошибка
            printf("%s\n", "Error! Wrong symbol.");
        scanf("%*c");
    } while (n <= 0);
    return 1;
}

//получаем строку из входного потока
int getStr(char** s)
{
    char buf[21];                                       //считываем из входного потока строку с помощью этого буфера, кусками по 20 сиволов
    int n;                                              //сюда будет записываться результат scanf
    int len = 0;                                        //сюда длина результирующей строки
    *s = (char*)malloc(1);                             //указатель на результирующую сткроу
    **s = '\0';                                         //ноль байт, пока строка имеет только конец строки
    //scanf("%*c");
    do {
        n = scanf("%20[^\n]", buf);                     //считываем буфер
        if (n < 0)
        {                                               //если ввели конец файла (ctrl+Z), то будет -1
            free(*s);                                   //очищаем память, возвращаем пустой указатель
            return -1;
        }
        if (n > 0) {                                    //если буфер не пустой
            len += strlen(buf);                         //увеличиваем результирующую длину
            *s = (char*)realloc(*s, len + 1);          //добавляем память
            if (*s)                                     //если память выделилась
                strcat(*s, buf);                        //копируем строку из буфера в конец нашей строки
            else
            {                                           //если память не выделилась
                free(*s);                               //очищаем память
                return -2;
            }
        }
        else
            scanf("%*c");                           //если перенос строки, то очищаем входной поток
    } while (n > 0);                                    //пока во входном потоке есть хоть один символ
    return 0;
}