Кодик

#include <iostream>
#include <ctime>
#include <fstream>
#include <cstring>
#include <list>

using namespace std;

struct BTNode {
    long long key = 0;
    int offset = 0;
    BTNode* leftChild = nullptr;
    BTNode* rightChild = nullptr;
};

class BSTree {
private:
    BTNode* root = nullptr;
    int countOfAdd = 0;
public:
    BSTree() = default;

    void print(BTNode* node, int level) {
        if (node) {
            print(node->rightChild, level + 1);
            for (int i = 0; i < level; i++) {
                cout << "\t";
            }
            cout << node->key << endl;
            print(node->leftChild, level + 1);
        }
    }

    BTNode* insert(BTNode* node, long long key, int offset) {
        if (!node) {
            node = new BTNode;
            node->key = key;
            node->offset = offset;
        }
        if (key < node->key) {
            node->leftChild = insert(node->leftChild, key, offset);
        }
        else if (key > node->key) {
            node->rightChild = insert(node->rightChild, key, offset);
        }
        return node;
    }

    BTNode* find(BTNode* node, long long key, int* compares) {
        (*compares)++;
        if (!node) {
            return 0;
        }
        if (node->key == key) {
            return node;
        }
        if (key < node->key) {
            return find(node->leftChild, key, compares);
        }
        else {
            return find(node->rightChild, key, compares);
        }
    }

    BTNode* getNodeWithMinValue(BTNode* node) {
        BTNode* current = node;
        while (current && current->leftChild) {
            current = current->leftChild;
        }
        return current;
    }

    BTNode* remove(BTNode* node, long long key) {
        if (!node) {
            return node;
        }
        if (key < node->key) {
            node->leftChild = remove(node->leftChild, key);
        }
        else if (key > node->key) {
            node->rightChild = remove(node->rightChild, key);
        }
        else {
            if (!node->leftChild && !node->rightChild) {
                return nullptr;
            }
            else if (!node->leftChild) {
                BTNode* ret = node->rightChild;
                delete node;
                return ret;
            }
            else if (!node->rightChild) {
                BTNode* ret = node->leftChild;
                delete node;
                return ret;
            }

            BTNode* tmp = getNodeWithMinValue(node->rightChild);
            node->key = tmp->key;
            node->offset = tmp->offset;
            node->rightChild = remove(node->rightChild, tmp->key);
        }
        return node;
    }

    void insert(long long key, int offset) {
        root = insert(root, key, offset);
        countOfAdd++;
    }

    BTNode* find(long long key, int* compares) {
        return find(root, key, compares);
    }

    void remove(long long key) {
        root = remove(root, key);
    }

    void print() {
        print(root, 0);
    }

    int getCountOfAdd() {
        return countOfAdd;
    }

    long long getMemory() {
        return (sizeof(BTNode) * countOfAdd) / 1024;
    }

    void removeAll(BTNode* current) {
        if (!current) {
            return;
        }
        if (current->leftChild) {
            removeAll(current->leftChild);
        }
        if (current->rightChild) {
            removeAll(current->rightChild);
        }
        delete current;
    }

    ~BSTree() {
        removeAll(root);
    }
};

struct RTNode {
    long long key = 0;
    int offset = 0;
    int size = 1;
    RTNode* leftChild = nullptr;
    RTNode* rightChild = nullptr;
    int getSize(RTNode* node) {
        if (!node) {
            return 0;
        }
        return node->size;
    }
    void setSize(RTNode* node) {
        node->size = getSize(node->leftChild) + getSize(node->rightChild) + 1;
    }
};

class RTree {
private:
    RTNode* root = nullptr;
    int countOfAdd = 0;
    int countOfRotate = 0;
public:
    RTree() = default;

    void print(RTNode* node, int level) {
        if (node) {
            print(node->rightChild, level + 1);
            for (int i = 0; i < level; i++) {
                cout << "\t";
            }
            cout << node->key << endl;
            print(node->leftChild, level + 1);
        }
    }

    RTNode* rotateRight(RTNode* node) {
        countOfRotate++;
        RTNode* temp = node->leftChild;
        if (!temp) {
            return node;
        }
        node->leftChild = temp->rightChild;
        temp->rightChild = node;
        temp->size = node->size;
        node->setSize(node);
        return temp;
    }

    RTNode* rotateLeft(RTNode* node) {
        countOfRotate++;
        RTNode* temp = node->rightChild;
        if (!temp) {
            return node;
        }
        node->rightChild = temp->leftChild;
        temp->leftChild = node;
        temp->size = node->size;
        node->setSize(node);
        return temp;
    }

    RTNode* insertRoot(RTNode* node, long long key, int offset) {
        if (!node) {
            node = new RTNode;
            node->key = key;
            node->offset = offset;
        }
        if (key < node->key) {
            node->leftChild = insertRoot(node->leftChild, key, offset);
            return rotateRight(node);
        }
        else if (key > node->key) {
            node->rightChild = insertRoot(node->rightChild, key, offset);
            return rotateLeft(node);
        }
        return node;
    }

    RTNode* insert(RTNode* node, long long key, int offset) {
        if (!node) {
            node = new RTNode;
            node->key = key;
            node->offset = offset;
        }
        if (rand() % (node->size + 1) == 0) {
            return insertRoot(node, key, offset);
        }
        if (key < node->key) {
            node->leftChild = insert(node->leftChild, key, offset);
        }
        else if (key > node->key) {
            node->rightChild = insert(node->rightChild, key, offset);
        }
        node->setSize(node);
        return node;
    }

    RTNode* find(RTNode* node, long long key, int* compares) {
        (*compares)++;
        if (!node) {
            return 0;
        }
        if (node->key == key) {
            return node;
        }
        if (key < node->key) {
            return find(node->leftChild, key, compares);
        }
        else {
            return find(node->rightChild, key, compares);
        }
    }

    RTNode* join(RTNode* node, RTNode* temp)
    {
        if (!node) {
            return temp;
        }
        if (!temp) {
            return node;
        }
        if (rand() % (node->size + temp->size) < node->size)
        {
            node->rightChild = join(node->rightChild, temp);
            node->setSize(node);
            return node;
        }
        else {
            temp->leftChild = join(node, temp->leftChild);
            temp->setSize(temp);
            return temp;
        }
    }

    RTNode* remove(RTNode* node, int key) {
        if (!node) {
            return node;
        }
        if (node->key == key)
        {
            RTNode* temp = join(node->leftChild, node->rightChild);
            delete node;
            return temp;
        }
        else if (key < node->key) {
            node->leftChild = remove(node->leftChild, key);
        }
        else if (key > node->key) {
            node->rightChild = remove(node->rightChild, key);
        }
        return node;
    }

    void insert(long long key, int offset) {
        root = insert(root, key, offset);
        countOfAdd++;
    }

    RTNode* find(long long key, int* compares) {
        return find(root, key, compares);
    }

    void remove(long long key) {
        root = remove(root, key);
    }

    void print() {
        print(root, 0);
    }

    int getCountOfAdd() {
        return countOfAdd;
    }

    int getAverageCountOfRotate() {
        return countOfRotate / countOfAdd;
    }

    long long getMemory() {
        return (sizeof(RTNode) * countOfAdd) / 1024;
    }

    void removeAll(RTNode* current) {
        if (!current) {
            return;
        }
        if (current->leftChild) {
            removeAll(current->leftChild);
        }
        if (current->rightChild) {
            removeAll(current->rightChild);
        }
        delete current;
    }

    ~RTree() {
        removeAll(root);
    }
};

struct HashNode {
    long long key = 0;
    int offset = 0;
};

class HashTable
{
public:
    int size;
    int countOfNotes = 0;
    int countOfAdd = 0;
    list<HashNode>* table;

    HashTable(int size)
    {
        this->size = size;
        table = new list<HashNode>[size];
    }

    int getCountOfNotes() {
        return countOfNotes;
    }

    void insert(long long key, int offset)
    {
        HashNode node;
        node.key = key;
        node.offset = offset;
        int index = hashFunction(key);
        table[index].push_back(node);

        countOfNotes++;
        countOfAdd++;

        if (countOfNotes / size > 0.75) {
            rehash();
        }
    }

    HashNode* find(long long key, int* compares)
    {
        int index = hashFunction(key);

        list<HashNode>::iterator i;
        for (i = table[index].begin(); i != table[index].end(); i++) {
            (*compares)++;
            if (i->key == key) {
                HashNode* node = new HashNode;
                node->key = i->key;
                node->offset = i->offset;
                return node;
            }
        }
    }

    void remove(long long key)
    {
        int index = hashFunction(key);

        list<HashNode>::iterator i;
        for (i = table[index].begin(); i != table[index].end(); i++) {
            if (i->key == key)
                break;
        }

        if (i != table[index].end())
            table[index].erase(i);

        countOfNotes--;
    }

    int hashFunction(int key)
    {
        return key % size;
    }

    void rehash() {
        HashTable newHT(size * 2);
        for (int i = 0; i < size; i++) {
            for (HashNode node : table[i]) {
                newHT.insert(node.key, node.offset);
            }
        }
        size = size * 2;
        table = newHT.table;
    }

    void displayHash() {
        cout << "HashTable now:" << endl;
        for (int i = 0; i < size; i++) {
            cout << i;
            for (HashNode node : table[i])
                cout << " --> " << node.key;
            cout << endl;
        }
        cout << endl;
    }

    int getCountOfAdd() {
        return countOfAdd;
    }

    long long getMemory() {
        return (sizeof(HashNode) * countOfAdd) / 1024;
    }

    void removeAll() {
        delete[] table;
    }

    ~HashTable() {
        removeAll();
    }
};


struct Car {
    long long num;
    char brand[5];
    char ownerName[5];

    void print() {
        cout << "==========================" << endl;
        cout << "Car's num: " << num << endl;
        cout << "Brand: " << brand << endl;
        cout << "Owner's name: " << ownerName << endl;
        cout << "==========================" << endl;
    }
};

class File {
private:
    string fileName;
    int fileSize;

public:
    File(string& fn, int fz) {
        fileName = fn;
        fileSize = fz;
    }

    void generateFile() {
        int brandLen = 4, ownerNameLen = 4, numLen = 4;
        char symbol;

        ofstream file(fileName, ios::binary | ios::trunc);

        for (int i = 0; i < fileSize; i++) {
            Car car;

            car.num = 0;
            char tmp[4];
            for (int j = 0; j < numLen; j++) {
                tmp[j] = (char)('1' + rand() % 9);
            }
            for (int j = numLen - 1; j >= 0; j--) {
                car.num += (long long)((tmp[j] - '0') * pow(10, numLen - j - 1));
            }

            if (i == 0) {
                cout << "First generated key: " << car.num << endl;
            }
            else if (i == fileSize / 2) {
                cout << "Middle generated key: " << car.num << endl;
            }
            else if (i == fileSize - 1) {
                cout << "Last generated key: " << car.num << endl;
            }


            for (int j = 0; j < brandLen; j++) {
                symbol = (char)('a' + rand() % 26);
                car.brand[j] = symbol;
            }
            car.brand[brandLen] = '\0';

            for (int j = 0; j < ownerNameLen; j++) {
                symbol = (char)('a' + rand() % 26);
                car.ownerName[j] = symbol;
            }
            car.ownerName[ownerNameLen] = '\0';

            file.write((char*)&car, sizeof(Car));
        }

        file.close();
    }

    template<typename T>
    bool insertFromFile(T& container) {
        ifstream file(fileName, ios::binary);
        if (file) {
            for (size_t i = 0; i < fileSize; i++) {
                Car car;
                file.read((char*)&car, sizeof(Car));
                container.insert(car.num, i);
            }
        }
        else {
            return false;
        }
        file.close();
        return true;
    }

    template<typename T>
    bool insertInFile(T& container, long long num, char brand[], char ownerName[]) {
        ofstream file(fileName, ios::binary | ios::app | ios::ate);
        if (file) {
            Car car;
            car.num = num;
            strcpy_s(car.brand, brand);
            strcpy_s(car.ownerName, ownerName);
            file.write((char*)&car, sizeof(Car));
            container.insert(num, container.getCountOfAdd());
            file.close();
            return true;
        }
        file.close();
        return false;
    }

    template<typename T, typename N>
    Car* findInFile(T& container, long long num, int* compares) {
        N* value = container.find(num, compares);
        if (value) {
            int offset = value->offset;
            ifstream file(fileName, ios::binary);
            if (file) {
                Car* car = new Car;
                file.seekg(offset * sizeof(Car), ios::beg);
                file.read((char*)car, sizeof(Car));
                file.close();
                return car;
            }
            file.close();
        }
        return nullptr;
    }

    template<typename T, typename N>
    void testFind(T& container, long long num) {
        int compares_count = 0;
        long long start = clock();
        findInFile<T, N>(container, num, &compares_count);
        long long end = clock();

        long long time = end - start;
        cout << "Number of compares: " << compares_count << endl;
        cout << "Time: " << time << "us" << endl;
        cout << "==========================" << endl;
    }

    template<typename T, typename N>
    bool removeFromFile(T& container, long long num) {
        int plug = 0;
        N* value = container.find(num, &plug);
        if (value) {
            int offset = value->offset;
            fstream file(fileName, ios::binary | ios::out | ios::in);
            if (file) {
                file.seekp(sizeof(Car) * offset, ios::beg);
                Car blank;
                string blankBrand, blankOwnerName;
                blankBrand.append(4, '-');
                blankOwnerName.append(4, '-');
                blank.num = 1000;
                strcpy_s(blank.brand, blankBrand.c_str());
                strcpy_s(blank.ownerName, blankOwnerName.c_str());
                file.write((char*)&blank, sizeof(Car));
            }
            file.close();
            container.remove(num);
            return true;
        }
        return false;
    }
};

void mainMenu() {
    cout << "Menu" << endl;
    cout << "1. Task1" << endl;
    cout << "2. Task2" << endl;
    cout << "3. Task3" << endl;
    cout << "0. Exit" << endl;
    cout << endl;
}

void firstTaskMenu() {
    cout << endl;
    cout << "Task1" << endl;
    cout << "1. Insert in file and BinarySearchTree" << endl;
    cout << "2. Find in file using BinarySearchTree" << endl;
    cout << "3. Remove from file and BinarySearchTree" << endl;
    cout << "4. Print BinarySearchTree" << endl;
    cout << "0. Exit" << endl;
    cout << endl;
}

void secondTaskMenu() {
    cout << endl;
    cout << "Task2" << endl;
    cout << "1. Insert in file and RandomTree" << endl;
    cout << "2. Find in file using RandomTree" << endl;
    cout << "3. Remove from file and RandomTree" << endl;
    cout << "4. Print RandomTree" << endl;
    cout << "5. Get average count of rotations" << endl;
    cout << "0. Exit" << endl;
    cout << endl;
}

void thirdTaskMenu() {
    cout << endl;
    cout << "Task3" << endl;
    cout << "1. Find data using 3 containers" << endl;
    cout << "2. Get used memory for 3 containers" << endl;
    cout << "3. Print HashTable" << endl;
    cout << "0. Exit" << endl;
    cout << endl;
}

int main()
{
    srand(time(0));
    string fileName = "file.bin";
    int fileSize = 0;
    cout << "Enter file size:" << endl;
    cin >> fileSize;

    File file(fileName, fileSize);
    file.generateFile();

    long long key = 0;
    string tempBrand, tempOwnerName;
    char brand[5], ownerName[5];

    int plug = 0;

    int mainOptions = -1;
    while (mainOptions != 0) {
        mainMenu();
        cin >> mainOptions;
        if (mainOptions == 1) {
            int firstTaskOptions = -1;
            BSTree bst;
            file.insertFromFile(bst);

            while (firstTaskOptions != 0) {
                firstTaskMenu();
                cin >> firstTaskOptions;
                if (firstTaskOptions == 1) {
                    cout << "Enter car's num, brand and owner's name :" << endl;
                    cin >> key >> tempBrand >> tempOwnerName;
                    strcpy_s(brand, tempBrand.c_str());
                    strcpy_s(ownerName, tempOwnerName.c_str());
                    if (file.insertInFile(bst, key, brand, ownerName)) {
                        cout << "Successful insert" << endl;
                    }
                    else {
                        cout << "Unsuccessful insert" << endl;
                    }
                }
                else if (firstTaskOptions == 2) {
                    cout << "Enter num:" << endl;
                    cin >> key;
                    Car* res = file.findInFile<BSTree, BTNode>(bst, key, &plug);
                    if (res) {
                        res->print();
                    }
                    else {
                        cout << "Not found" << endl;
                    }
                }
                else if (firstTaskOptions == 3) {
                    cout << "Enter num:" << endl;
                    cin >> key;
                    if (file.removeFromFile<BSTree, BTNode>(bst, key)) {
                        cout << "Successful remove" << endl;
                    }
                    else {
                        cout << "Unsuccessful remove" << endl;
                    }
                }
                else if (firstTaskOptions == 4) {
                    bst.print();
                }
            }
        }
        else if (mainOptions == 2) {
            int secondTaskOptions = -1;
            RTree rt;
            file.insertFromFile(rt);

            while (secondTaskOptions != 0) {
                secondTaskMenu();
                cin >> secondTaskOptions;
                if (secondTaskOptions == 1) {
                    cout << "Enter car's num, brand and owner's name:" << endl;
                    cin >> key >> tempBrand >> tempOwnerName;
                    strcpy_s(brand, tempBrand.c_str());
                    strcpy_s(ownerName, tempOwnerName.c_str());
                    if (file.insertInFile(rt, key, brand, ownerName)) {
                        cout << "Successful insert" << endl;
                    }
                    else {
                        cout << "Unsuccessful insert" << endl;
                    }
                }
                else if (secondTaskOptions == 2) {
                    cout << "Enter num:" << endl;
                    cin >> key;
                    Car* res = file.findInFile<RTree, RTNode>(rt, key, &plug);
                    if (res) {
                        res->print();
                    }
                    else {
                        cout << "Not found" << endl;
                    }
                }
                else if (secondTaskOptions == 3) {
                    cout << "Enter num:" << endl;
                    cin >> key;
                    if (file.removeFromFile<RTree, RTNode>(rt, key)) {
                        cout << "Successful remove" << endl;
                    }
                    else {
                        cout << "Unsuccessful remove" << endl;
                    }
                }
                else if (secondTaskOptions == 4) {
                    rt.print();
                }
                else if (secondTaskOptions == 5) {
                    cout << "Average rotations: " << rt.getAverageCountOfRotate() << endl;
                }
            }
        }
        else if (mainOptions == 3) {
            int thirdTaskOptions = -1;
            BSTree bst;
            RTree rt;
            HashTable ht(fileSize*2);
            file.insertFromFile(bst);
            file.insertFromFile(rt);
            file.insertFromFile(ht);

            while (thirdTaskOptions != 0) {
                thirdTaskMenu();
                cin >> thirdTaskOptions;
                if (thirdTaskOptions == 1) {
                    cout << "Enter num:" << endl;
                    cin >> key;
                    cout << "BinarySearchTree results:" << endl;
                    file.testFind<BSTree, BTNode>(bst, key);
                    cout << "RandomTree results:" << endl;
                    file.testFind<RTree, RTNode>(rt, key);
                    cout << "HashTable results:" << endl;
                    file.testFind<HashTable, HashNode>(ht, key);
                }
                else if (thirdTaskOptions == 2) {
                    cout << "BinarySearchTree used memory: " << bst.getMemory() << "kB" << endl;
                    cout << "RandomTree used memory: " << rt.getMemory() << "kB" << endl;
                    cout << "HashTable used memory: " << ht.getMemory() << "kB" << endl;
                }
                else if (thirdTaskOptions == 3) {
                    ht.displayHash();
                    cout << endl;
                }
            }
        }
    }
}