3AA

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

typedef int KeyType1;
typedef char KeyType2;
typedef int IndexType1;
typedef int IndexType2;
typedef short int BusyType1;
typedef short int BusyType2;
typedef short int RelType1;

typedef struct InfoType {
    int a;
    int b;
    char* string;
} InfoType;

typedef struct Item {
    InfoType* info;
    KeyType1 key1;
    KeyType2* key2;

} Item;

typedef struct KeySpace1 {
    BusyType1 busy;
    KeyType1 key;
    RelType1 release;
    Item* info;
} KeySpace1;

typedef struct KeySpace2 {
    BusyType2 busy;
    KeyType2* key;
    Item* info;
} KeySpace2;

typedef struct Table {
    KeySpace1* ks1;
    KeySpace2* ks2;

    IndexType1 	msize1;
    IndexType2 msize2;

    IndexType1 	size1;
    IndexType2 size2;
} Table;


Table* table_new(int msize1, int msize2) {
    Table* t = (Table*)malloc(sizeof(Table));
    t->msize1 = msize1;
    t->size1 = 0;
    t->ks1 = (KeySpace1*)malloc(msize1 * sizeof(KeySpace1));
    for (int i = 0; i < msize1; i++) {
        t->ks1[i].info = NULL;
        t->ks1[i].busy = 0;
        t->ks1[i].key = 0;
        t->ks1[i].release = 0;
    }

    t->msize2 = msize2;
    t->size2 = 0;
    t->ks2 = (KeySpace2*)malloc(msize2 * sizeof(KeySpace2));
    for (int i = 0; i < msize2; i++) {
        t->ks2[i].info = NULL;
        t->ks2[i].busy = 0;
        t->ks2[i].key = NULL;
    }

    return t;
}

int dialog(const char* msgs[], int n) {
    char* error = (char*)"";
    int choice;
    do {
        puts(error);
        error = (char*)"You're wrong. Try again!";
        for (int i = 0; i < n; ++i) {
            puts(msgs[i]);
        }
        puts("Make your choice: ");
        choice = get_int();
        while (getchar() != '\n') {}
    } while (choice < 0 || choice >= n);
    return choice;
}

int get_int() {
    int n = 0;
    int res;
    do {
        n = scanf("%d", &res);
        if (n < 0) {
            exit(-1);
            return -1;
        }
        else if (n == 0) {
            while (getchar() != '\n');
            printf("Please enter integer:");
        }
    } while (n == 0);
    return res;
}

char* get_str() {
    char buf[81] = { 0 };
    char* res = NULL;
    int len = 0;
    int n = 0;
    do {
        n = scanf("%s", buf);

        if (n < 0) {
            if (!res) {
                return NULL;
            }
        }
        else if (n > 0) {
            int chunk_len = strlen(buf);
            int str_len = len + chunk_len;
            res = (char*)realloc(res, str_len + 1);
            memcpy(res + len, buf, chunk_len);
            len = str_len;
        }
        else {
            scanf("%*c");
        }
    } while (n == 0);

    if (len > 0) {
        res[len] = '\0';
    }
    else {
        res = (char*)calloc(1, sizeof(char));
    }

    return res;
}

void include_element(Table* t) {
    InfoType info;
    printf("Input INFO:\n\ta: ");
    info.a = get_int();
    printf("\tb: ");
    info.b = get_int();
    printf("\tstr: ");
    info.string = get_str();

    printf("Input Key 1: ");
    KeyType1 key1 = get_int();

    printf("Input Key 2: ");
    KeyType2* key2 = (KeyType2*)calloc(100, sizeof(KeyType2));
    scanf("%s", key2);

    int res = table_include(t, info, key1, key2);

    if (res == 1)
        printf("Success!\n");
    else if (res == -1)
        printf("Error: Table is full!\n");
    else if (res == 0)
        printf("Error: key is already exists\n");
}

void correct_versions(KeySpace1* ks,KeyType1 key1,int size) {
    int i = 0;
    int version = 0;
    for (i = 0; i < size; i++) {
        if (ks[i].key == key1 && ks[i].busy == 1) {
            ks[i].release = version;
            version += 1;
        }
    }
}

Item* keyspace1_find_key(KeySpace1* ks, KeyType1 key, int size) {
    int i = 0;
    int ind = size;

    for (i = 0; i < ind; i++) {
        if (ks[i].key == key && ks[i].busy == 1) {
            return ks[i].info;
        }
    }
    return 0;
}

Item* keyspace1_find_key_versions(KeySpace1* ks, KeyType1 key, int size, int version) {
    int i = 0, m = 0;
    int ind = size;
    int s = version;

    for (i = 0; i < ind; i++) {
        if (ks[i].key == key && ks[i].busy == 1) {
            if (ks[i].release == version) {
                return ks[i].info;
            }

        }
    }
    return 0;
}

int keyspace2_hash(KeyType2* key, int msize) {
    int lkey, skey = 0;
    lkey = strlen(key);
    for (int i = 0; i < lkey; i++) {
        skey += (int)key[i];
    }

    return skey % msize;
}

Item* keyspace2_find_key(KeySpace2* ks, KeyType2* key, int msize) {
    int ind = abs(keyspace2_hash(key, msize));
    if (ks[ind].busy == 1 && strcmp(ks[ind].key, key) == 0)
        return ks[ind].info;

    for (int i = ind + 1; i != ind; i = (i + 1) % msize) {
        if (ks[i].busy == 1 && strcmp(ks[i].key, key) == 0)
            return ks[i].info;
    }

    return 0;
}

void keyspace1_include(KeySpace1* ks, Item* info, KeyType1 key, int size) {
    int i = 0, j = 0;
    int ind = size;

    for (i = 0; i < ind; i++) {
        if (ks[i].key == info->key1 && ks[i].busy == 1) {
            j += 1;
        }
    }


    ks[ind].key = key;
    ks[ind].info = info;
    ks[ind].busy = 1;
    ks[ind].release = j;
    return;
}

void keyspace2_include(KeySpace2* ks, Item* info, KeyType2* key, int msize) {
    int ind = abs(keyspace2_hash(key, msize));
    if (ks[ind].busy == 0 && ks[ind].key != key) {
        ks[ind].busy = 1;
        ks[ind].info = info;
        ks[ind].key = key;
        return;
    }

    for (int i = ind + 1; i != ind; i = (i + 1) % msize) {
        if (ks[i].busy == 0 && ks->key != key) {
            ks[i].busy = 1;
            ks[i].info = info;
            ks[i].key = key;
            return;
        }
    }

    return;
}

Item* item_new(InfoType info, KeyType1 key1, KeyType2* key2) {
    Item* item = (Item*)malloc(sizeof(Item));
    item->info = (InfoType*)malloc(sizeof(InfoType));
    (*item->info) = info;
    item->key1 = key1;
    item->key2 = key2;

    return item;
}

int table_include(Table* t, InfoType info, KeyType1 key1, KeyType2* key2) {
    if (t->msize1 == t->size1 || t->msize2 == t->size2)
        return -1;

    if (keyspace2_find_key(t->ks2, key2, t->msize2))
        return 0;

    Item* item = item_new(info, key1, key2);


    keyspace1_include(t->ks1, item, key1, t->size1);
    keyspace2_include(t->ks2, item, key2, t->msize2);

    t->size1++;
    t->size2++;

    return 1;
}

void print_table(Table* t) {
    printf("1: \n");
    for (int i = 0; i < t->msize1; i++) {
        if (t->ks1[i].info)
            printf(" Busy: %d Key1: %d      Int A:%d Int B:%d String:'%s' Version: %d\n", t->ks1[i].busy, t->ks1[i].key, t->ks1[i].info->info->a, t->ks1[i].info->info->b, t->ks1[i].info->info->string, t->ks1[i].release);
        else
            printf("-\n");
    }
    printf("2:\n");
    for (int i = 0; i < t->msize2; i++) {
        if (t->ks2[i].info)
            printf(" Busy: %d Key2: %s      Int A:%d Int B:%d String:'%s'\n", t->ks2[i].busy, t->ks2[i].key, t->ks2[i].info->info->a, t->ks2[i].info->info->b, t->ks2[i].info->info->string);
        else
            printf("-\n");
    }
}

void find_element_with_key(Table* t) {
    printf("From key space 1 or key space 2? (1/2): ");
    int space = get_int();
    while (space < 1 || space > 2) {
        printf("Please choose between 1 and 2\n");
        printf("From key space 1 or key space 2? (1/2): ");
        space = get_int();
    }

    Item* res = 0;
    if (space == 1) {
        printf("Input Key 1: ");
        KeyType1 key1 = get_int();
        printf("Input Version: ");
        int version = get_int();
        res = keyspace1_find_key_versions(t->ks1, key1, t->size1, version);
    }
    else {
        printf("Input Key 2: ");
        KeyType2* key2 = (KeyType2*)calloc(100, sizeof(KeyType2));
        scanf("%s", key2);
        res = keyspace2_find_key(t->ks2, key2, t->msize2);
    }

    if (res != NULL)
        printf("Success: %d %s %d %d %s\n", res->key1, res->key2, res->info->a, res->info->b, res->info->string);
    else
        printf("Error: Not Exist!\n");
}

Item* table_find_composite(Table* t, KeyType1 key1, KeyType2* key2) {
    int i = 0, j = 0;
    for (i = 0; (i < t->size1) || (i < t->msize2); i++) {
        if ((t->ks1[i].key == key1) && (t->ks1[i].busy == 1)) {
            if ((strcmp(t->ks1[i].info->key2, key2) == 0)) {
                return t->ks1[i].info;
            }
        }
    }
    return 0;
}

void find_element_with_composite(Table* t) {
    printf("Input Key 1: ");
    KeyType1 key1 = get_int();
    printf("Input Key 2: ");
    KeyType2* key2 = (KeyType2*)calloc(100, sizeof(KeyType2));
    scanf("%s", key2);

    Item* res = table_find_composite(t, key1, key2);
    if (res)
        printf("Success: %d %s      %d %d %s\n", res->key1, res->key2, res->info->a, res->info->b, res->info->string);
    else
        printf("Error: Not Exist!\n");
}


void table_delete_item1(Table* t, Item* item) {
    int i = 0, j = 0;
    for (i = 0; i < t->size1; i++) {
        if (t->ks1[i].info == item && t->ks1[i].busy == 1) {
            t->ks1[i].busy = 0;
            for (j = 0; j < t->msize2 - 1; j++) {
                if (t->ks2[j].info == item && t->ks2[j].busy == 1) {
                    t->ks2[j].busy = 0;
                    t->size2 -= 1;
                    correct_versions(t->ks1, t->ks1[i].key, t->size1);
                }
            }
        }
    }
}

void table_delete_item123(Table* t, Item* item) {
    int i = 0, j = 0;
    for (i = 0; i < t->size1; i++) {
        if (t->ks1[i].key == item->key1 && t->ks1[i].busy == 1) {
            t->ks1[i].busy = 0;
            for (j = 0; j < t->msize2 - 1; j++) {
                if (t->ks2[j].info == t->ks1[i].info && t->ks2[j].busy == 1) {
                    t->ks2[j].busy = 0;
                    t->size2 -= 1;
                    correct_versions(t->ks1, t->ks1[i].key, t->size1);
                }
            }
        }
    }
}

void table_delete_item12(Table* t, Item* item, int version) {
    int i = 0, j = 0;
    for (i = 0; i < t->size1; i++) {
        if (t->ks1[i].info == item && t->ks1[i].busy == 1 && t->ks1[i].release == version) {
            t->ks1[i].busy = 0;
            for (j = 0; j < t->msize2; j++) {
                if (t->ks1[i].info == t->ks2[j].info && t->ks2[j].busy == 1) {
                    t->ks2[j].busy = 0;
                    t->size2 -= 1;
                    correct_versions(t->ks1, t->ks1[i].key, t->size1);
                }
            }
        }
    }
}

void table_delete_item2(Table* t, Item* item) {
    int i = 0, j = 0;
    for (i = 0; i < t->msize2 - 1; i++) {
        if (t->ks2[i].info == item && t->ks2[i].busy == 1) {
            t->ks2[i].busy = 0;
            for (j = 0; j < t->size1; j++) {
                if (t->ks1[i].info == t->ks2[j].info && t->ks1[j].busy == 1) {
                    t->ks1[j].busy = 0;
                    t->size2 -= 1;
                    correct_versions(t->ks1, t->ks1[i].key, t->size1);
                }
            }
        }
    }
}

void table_delete_item_version(Table* t, Item* item, int version) {
    int i = 0, j = 0;
    for (i = 0; i < t->size1; i++) {
        if (t->ks1[i].info == item && t->ks1[i].release == version) {
            t->ks1[i].busy = 0;
            for (j = 0; j < t->msize2; j++) {
                if (t->ks1[i].info == t->ks2[j].info) {
                    t->ks2[j].busy = 0;
                    t->size2 -= 1;
                    correct_versions(t->ks1, t->ks1[i].key, t->size1);
                }
            }
        }
    }
}

// 1 - deleted , -1 - not found
int table_delete_composite(Table* t, KeyType1 key1, KeyType2* key2) {
    Item* item = table_find_composite(t, key1, key2);
    if (item) {
        table_delete_item1(t, item);
        return 1;
    }
    return -1;
}

void delete_element_with_composite(Table* t) {
    printf("Input Key 1: ");
    KeyType1 key1 = get_int();
    printf("Input Key 2: ");
    KeyType2* key2 = (KeyType2*)calloc(100, sizeof(KeyType2));
    scanf("%s", key2);
    int res = table_delete_composite(t, key1, key2);
    if (res == 1)
        printf("Success!");
    else
        printf("Error: Not Exist!\n");
}

void delete_element_with_key(Table* t) {
    printf("From key space 1 or key space 2? (1/2): ");
    int space = get_int();
    while (space < 1 || space > 2) {
        printf("Please choose between 1 and 2\n");
        printf("From key space 1 or key space 2? (1/2): ");
        space = get_int();
    }

    Item* res;
    if (space == 1) {
        printf("Input Key 1: ");
        KeyType1 key1 = get_int();
        printf("Input Version: ");
        int version = get_int();
        res = keyspace1_find_key_versions(t->ks1, key1, t->size1, version);
        if (res) {
            table_delete_item12(t, res, version);
            printf("Success!");
        }
        else {
            printf("Error: Not Exist!\n");
        }
    }
    else {
        printf("Input Key 2: ");
        KeyType2* key2 = (KeyType2*)calloc(100, sizeof(KeyType2));
        scanf("%s", key2);
        res = keyspace2_find_key(t->ks2, key2, t->msize2);
        if (res) {
            table_delete_item2(t, res);
            printf("Success!");
        }
        else {
            printf("Error: Not Exist!\n");
        }
    }
}

void reorganize_first_key(Table* t) {
    KeySpace1 tmp1;
    int zero_num = 0;
    int i = 0, j = 0;
    for (i = 0; i < t->msize1; i++) {
        if (t->ks1[i].busy == 0) {
            zero_num += 1;
        }
        else {
            if (zero_num > 0) {
                tmp1 = t->ks1[i];
                t->ks1[i] = t->ks1[i - zero_num];
                t->ks1[i - zero_num] = tmp1;
                t->size1 -= 1;
            }
        }

    }
}

void work_with_versions(Table* t) {
    printf("Delete every versions (1) or one version (2)?: ");
    int space = get_int();
    while (space < 1 || space > 2) {
        printf("Please choose between 1 and 2\n");
        printf("Delete every versions (1) or one version (2)?: ");
        space = get_int();
    }

    Item* res;

    if (space == 1) {
        printf("Input Key 1: ");
        KeyType1 key1 = get_int();
        res = keyspace1_find_key(t->ks1, key1, t->size1);
        if (res) {
            table_delete_item123(t, res);
            printf("Success!");
        }
        else {
            printf("Error: Not Exist!\n");
        }
    }
    else {
        printf("Input Key 1: ");
        KeyType1 key1 = get_int();;
        printf("Input Version: ");
        int version = get_int();
        res = keyspace1_find_key_versions(t->ks1, key1, t->size1, version);
        if (res) {
            table_delete_item_version(t, res, version);
            printf("Success!");
        }
        else {
            printf("Error: Not Exist!\n");
        }
    }
}

int main() {
    const char* MSGS[] = { "0. Quit", "1. Including new element", "2. Finding element with composite key", "3. Deleting element with composite key", "4. Finding element with one key", "5. Deleting element with one key", "6. Print table", "7. Reorganize First Keys", "8. Work with versions" };
    const int MSGS_SIZE = sizeof(MSGS) / sizeof(MSGS[0]);
    int c = 0;
    printf("Enter msize1: ");
    int msize1 = get_int();
    printf("Enter msize2: ");
    int msize2 = get_int();
    Table* t = table_new(msize1, msize2);
    do {
        c = dialog(MSGS, MSGS_SIZE);
        switch (c) {
        case 0: {
            free(t);
            break;
        } case 1: {
            include_element(t);
            break;
        } case 2: {
            find_element_with_composite(t);
            break;
        } case 3: {
            delete_element_with_composite(t);
            break;
        } case 4: {
            find_element_with_key(t);
            break;
        } case 5: {
            delete_element_with_key(t);
            break;
        } case 6: {
            print_table(t);
            break;
        } case 7: {
            reorganize_first_key(t);
            break;
        } case 8: {
            work_with_versions(t);
            break;
        }
        }
    } while (c != 0);
    return 0;
}