govno3

using namespace std;
#include <iostream>
#include <Windows.h>
#include <conio.h>
class GameObject
{
protected:
    bool printed;
public:

    virtual int GetUniqueIdentifier() = 0;


    virtual void UniqueIdentifier(int u) = 0;
      void Print() {
          printed = true;
        cout <<"Уникальный идентификатор " << GetUniqueIdentifier() << endl;

    };
};
struct RBTree { RBTree* Left, * Right, * Parent; int Data; bool red; GameObject* obj; };
void ClassDefinition(GameObject* obj);
//создание красно-черного дерева
/*void Make_RBTree(RBTree** Node, int n) {
    GameObject* Data;
    while (n > 0) {
        cout << "Введите значение ";
        cin >> Data;
        Insert_Node(Node, Data);
        n--;
    }
}*/
RBTree* NIL = new RBTree();

void Insert_Fixup(RBTree** Node, RBTree* New_Node);
void Rotate_Left(RBTree** Node, RBTree* Current);
void Rotate_Right(RBTree** Node, RBTree* Current);
//добавление узла в красно-черное дерево
void Insert_Node(RBTree** Node, GameObject* Data) {
    RBTree** Curent, * Parent, * New_Node;
    Curent = Node;
    Parent = NIL; //узел, под который мы будем вставлять
    // Поиск местоположения
    while (*Curent != NIL) {
        Parent = (*Curent);
        Curent = Data->GetUniqueIdentifier() < (*Curent)->Data ? &((*Curent)->Left) : &((*Curent)->Right);
    }
    // Создание нового узла
    New_Node = new RBTree();
    New_Node->Data = Data->GetUniqueIdentifier();
    New_Node->obj = Data;
    New_Node->Parent = Parent;
    New_Node->Left = NIL;
    New_Node->Right = NIL;
    New_Node->red = true;
    // Вставка элемента в дерево
    if (Parent != NIL) {
        if (Data->GetUniqueIdentifier() < Parent->Data) Parent->Left = New_Node;
        else Parent->Right = New_Node;
    }
    else (*Curent) = New_Node;
    Insert_Fixup(Node, New_Node);
}

// Поддержка баланса дерева после вставки нового элемента
void Insert_Fixup(RBTree** Node, RBTree* New_Node) {
    RBTree* Current = New_Node;
    // Проверка свойств дерева
    while (Current != *(Node) && Current->Parent->red == true) {
        // если есть нарушение
        if (Current->Parent == Current->Parent->Parent->Left) {
            RBTree* ptr = Current->Parent->Parent->Right;
            if (ptr->red == true) {
                Current->Parent->red = false;

                ptr->red = false;
                Current->Parent->Parent->red = true;
                Current = Current->Parent->Parent;
            }
            else {
                if (Current == Current->Parent->Right) {
                    // сделать Current левым потомком
                    Current = Current->Parent;
                    Rotate_Left(Node, Current);
                }
                // перекрасить и повернуть
                Current->Parent->red = false;
                Current->Parent->Parent->red = true;
                Rotate_Right(Node, Current->Parent->Parent);
            }
        }
        else {
            RBTree* ptr = Current->Parent->Parent->Left;

                if (ptr->red == true ) {
                    Current->Parent->red = false;

                    ptr->red = false;
                    Current->Parent->Parent->red = true;
                    Current = Current->Parent->Parent;
                }

            else {
                if (Current == Current->Parent->Left) {
                    Current = Current->Parent;
                    Rotate_Right(Node, Current);
                }
                Current->Parent->red = false;
                Current->Parent->Parent->red = true;
                Rotate_Left(Node, Current->Parent->Parent);
            }
        }
    }
    (*Node)->red = false;
}

//поворот узла Current влево
void Rotate_Left(RBTree** Node, RBTree* Current) {
    RBTree* ptr = Current->Right;
    Current->Right = ptr->Left;
    if (ptr->Left != NIL) ptr->Left->Parent = Current;
    if (ptr != NIL) ptr->Parent = Current->Parent;
    if (Current->Parent != NIL) {
        if (Current == Current->Parent->Left)
            Current->Parent->Left = ptr;
        else
            Current->Parent->Right = ptr;
    }
    else {
        (*Node) = ptr;
    }
    ptr->Left = Current;
    if (Current != NIL) Current->Parent = ptr;
}

//поворот узла Current вправо
void Rotate_Right(RBTree** Node, RBTree* Current) {
    RBTree* ptr = Current->Left;
    Current->Left = ptr->Right;
    if (ptr->Right != NIL) ptr->Right->Parent = Current;
    if (ptr != NIL) ptr->Parent = Current->Parent;
    if (Current->Parent != NIL) {
        if (Current == Current->Parent->Right)
            Current->Parent->Right = ptr;
        else
            Current->Parent->Left = ptr;
    }
    else {
        (*Node) = ptr;
    }
    ptr->Right = Current;
    if (Current != NIL) Current->Parent = ptr;
}




//прямой обход красно-черного дерева
void PreOrder_RBTree(RBTree* Node) {
    if (Node != NIL) {
        ClassDefinition(Node->obj);
        PreOrder_RBTree(Node->Left);
        PreOrder_RBTree(Node->Right);
    }
}

//обратный обход красно-черного дерева
void PostOrder_RBTree(RBTree* Node) {
    if (Node != NIL) {
        PostOrder_RBTree(Node->Left);
        PostOrder_RBTree(Node->Right);
        cout << Node->Data << " ";
    }
}

//симметричный обход красно-черного дерева
void SymmetricOrder_RBTree(RBTree* Node) {
    if (Node != NIL) {
        PostOrder_RBTree(Node->Left);
      cout <<  Node->Data << " ";
        PostOrder_RBTree(Node->Right);
    }
}

//проверка пустоты красно-черного дерева
bool Empty_RBTree(RBTree* Node) {
    return (Node == NIL ? true : false);
}

//освобождение памяти, выделенной под красно-черное дерево
void Delete_RBTree(RBTree* Node) {
    if (Node != NIL) {
        Delete_RBTree(Node->Left);
        Delete_RBTree(Node->Right);
        delete(Node);
    }
}
RBTree* FindItem(int  data, RBTree* Tree)
{
    RBTree* ret = Tree;
    while (ret!=NIL)
    {
        if (data < ret->Data)
        {
            ret = ret->Left;
        }
        else if (data > ret->Data)
        {
            ret = ret->Right;
        }
        else
        {
            break;
        }
    }
    return ret;
}
void PrintTree1(RBTree* Tree)
{
    if (Tree != NIL)
    {
        cout << Tree->Data;
        cout << "-" << Tree->red;
        cout << " (";
        PrintTree1(Tree->Left);
        cout << ") ";
        cout << " (";
        PrintTree1(Tree->Right);
        cout << ") ";
    }
    else cout << "null";
}


class PhysicalObject : public virtual GameObject
{

public:
    virtual int GetWeight() = 0;
    virtual void Weight(int w) = 0;
    virtual void  Print() {
        if (!printed){

            cout << "Вес " << GetWeight() << endl;
            GameObject::Print();
        }

        else

        cout << "Вес " << GetWeight() << endl;

    }
};
class GraphicObject : public virtual GameObject
{
public:
    virtual string GetTexture() = 0;
    virtual void Texture(string t) = 0;
    virtual void Print(){
        if (!printed) {

            cout << "Текстура " << GetTexture() << endl;
            GameObject::Print();

        }

        else


        cout << "Текстура " << GetTexture() << endl;

    }
};
class Projectile : public virtual PhysicalObject
{
private:
    int weight;
    string caliber;
    int uniqueIdentifier;
public:

    void Caliber(string c) {
        caliber = c;
    }
    void Weight(int w) override {
        weight = w;
    }
    void UniqueIdentifier(int u) override {
        uniqueIdentifier = u;

    }
    int GetUniqueIdentifier() override {
        return uniqueIdentifier;
    }
    int GetWeight() override {
        return weight;
    }
    string GetCaliber() {
        return caliber;
    }
    void  Print()    {

        cout << "Снаряд" << endl;
        cout << "Калибр: " << GetCaliber() << endl;

        PhysicalObject::Print();

    }

};
class TransportVehicle : public virtual PhysicalObject
{
private:
    int weight;
    int uniqueIdentifier;
    int enginePower;
public:

    void EnginePower(int e) {
        enginePower = e;
    }
    void Weight(int w) override {
        weight = w;
    }
    void UniqueIdentifier(int u) override {
        uniqueIdentifier = u;

    }
    int GetUniqueIdentifier() override{
        return uniqueIdentifier;
    }
    int GetWeight() override {
        return weight;
    }
    int GetEnginePower() {
        return enginePower;
    }
    void Print()  {

        cout << "Транспортное средство" << endl;
        cout << "Мощность двигателя: " << GetEnginePower() << endl;

        PhysicalObject::Print();

    }
};
class Tank : public virtual TransportVehicle, public virtual GraphicObject
{
private:
    string texture;
    int uniqueIdentifier;
    int armorThickness;
public:

    void ArmorThickness(int a) {
        armorThickness = a;
    }
    void UniqueIdentifier(int u) override {
        uniqueIdentifier = u;

    }
    void Texture(string t) override {
        texture = t;
    }
    int GetUniqueIdentifier() override {
        return uniqueIdentifier;
    }
    string GetTexture() override {
        return texture;
    }
    int GetArmorThickness() {
        return armorThickness;
    }
    void Print()  {
        printed = false;
        cout << "Танк" << endl;
        cout << "Толщина брони " << GetArmorThickness() << endl;
        TransportVehicle::Print();
        GraphicObject::Print();

    }

};
class Airplane : public virtual TransportVehicle, public virtual GraphicObject
{
private:
    string texture;
    int uniqueIdentifier;
    int loadCapacity;
public:

    void LoadCapacity(int l) {
        loadCapacity = l;
    }
    void UniqueIdentifier(int u) override {
        uniqueIdentifier = u;

    }
    string GetTexture() override {
        return texture;
    }
    int GetLoadCapacity() {
        return loadCapacity;
    }
    void Texture(string t) override {
        texture = t;
    }
    int GetUniqueIdentifier() override {
        return uniqueIdentifier;
    }
    void Print()  {
        printed = false;
        cout << "Самолёт" << endl;
        cout << "Грузоподъёмность " << GetLoadCapacity() << endl;
        TransportVehicle::Print();
        GraphicObject::Print();

    }
};
void ClassDefinition(GameObject* obj) {
    string name = typeid(*obj).name();
    if (name == "class Projectile") {
        Projectile* p = dynamic_cast<Projectile*> (obj);
        p->Print();
    }
    else if (name == "class TransportVehicle") {
        TransportVehicle* t = dynamic_cast<TransportVehicle*> (obj);
        t->Print();
    }
    else if (name == "class Tank") {
        Tank* tn = dynamic_cast<Tank*> (obj);
        tn->Print();
    }
    else if (name == "class Airplane") {
        Airplane* a = dynamic_cast<Airplane*> (obj);
        a->Print();
    }
}
void DeleteFixup(RBTree* x, RBTree* root, RBTree** Tree) {



    while (x != root && x->red == false) {
        if (x == x->Parent->Left) {
            RBTree* w = x->Parent->Right;
            if (w->red == true) {
                w->red = false;
                x->Parent->red =true;
                Rotate_Left(Tree, x->Parent);
                w = x->Parent->Right;
            }
            if (w->Left->red == false && w->Right->red ==false) {
                w->red = true;
                x = x->Parent;
            }
            else {
                if (w->Right->red == false) {
                    w->Left->red = false;
                    w->red = true;
                    Rotate_Right(Tree,w);
                    w = x->Parent->Right;
                }
                w->red = x->Parent->red;
                x->Parent->red = false;
                w->Right->red = false;
                Rotate_Left(Tree, x->Parent);
                x = root;
            }
        }
        else {
            RBTree* w = x->Parent->Left;
            if (w->red == true) {
                w->red = false;
                x->Parent->red = true;
                Rotate_Right(Tree, x->Parent);
                w = x->Parent->Left;
            }
            if (w->Right->red == false && w->Left->red == false) {
                w->red = true;
                x = x->Parent;
            }
            else {
                if (w->Left->red == false) {
                    w->Right->red = false;
                    w->red = true;
                    Rotate_Left(Tree,w);
                    w = x->Parent->Left;
                }
                w->red = x->Parent->red;
                x->Parent->red = false;
                w->Left->red = false;
                Rotate_Right(Tree, x->Parent);
                x = root;
            }
        }
    }
    x->red = false;
}
RBTree* Successor(RBTree* p)
{
    RBTree* y = NIL;
    if (p->Left != NIL)
    {
        y = p->Left;
        while (y->Right != NIL)
            y = y->Right;
    }
    else
    {
        y = p->Right;
        while (y->Left != NIL)
            y = y->Left;
    }
    return y;
}
void Delfix(RBTree* p, RBTree** Tree);
    void DeleteNode(int Data, RBTree** Tree)
    {
        if (*Tree == NIL)
        {
            cout << "Дерево пустое" << endl;
            return;
        }

        RBTree* p;
        p = *Tree;
        RBTree* y = NIL;
        RBTree* q = NIL;
        int found = 0;
        while (p != NIL && found == 0)
        {
            if (p->Data == Data)
                found = 1;
            if (found == 0)
            {
                if (p->Data < Data)
                    p = p->Right;
                else
                    p = p->Left;
            }
        }
        if (found == 0)
        {
            cout << "Элемент с данным идентификатором не найден" << endl;;
            return;
        }
        else
        {



            if (p->Left == NIL || p->Right == NIL)
                y = p;
            else
                y = Successor(p);
            if (y->Left != NIL)
                q = y->Left;
            else
            {
                if (y->Right != NIL)
                    q = y->Right;
                else
                    q = NIL;
            }
            if (q != NIL)
                q->Parent = y->Parent;
            if (y->Parent == NIL)
                *Tree = q;
            else
            {
                if (y == y->Parent->Left) {
                    y->Parent->Left = q;
                    q->Parent = y->Parent;
                }
                else {
                    y->Parent->Right = q;
                    q->Parent = y->Parent;
                }
            }
            if (y != p)
            {

                p->Data = y->Data;
            }
            if (y->red == false)
                DeleteFixup(q, *Tree, Tree);
        }
        (*Tree)->red = false;
        delete(y);
    }

    void Delfix(RBTree* p, RBTree **Tree)
    {
        RBTree* s;
        while (p != *Tree && p->red == false)
        {
            if (p->Parent->Left == p)
            {
                s = p->Parent->Right;
                if (s->red == true)
                {
                    s->red = false;
                    p->Parent->red = true;
                    Rotate_Left( Tree,p->Parent);
                    s = p->Parent->Right;
                }
                if (s->Right->red == false && s->Left->red == false)
                {
                    s->red = true;
                    p = p->Parent;
                }
                else
                {
                    if (s->Right->red == false)
                    {
                        s->Left->red = false;
                        s->red = true;
                        Rotate_Right(Tree,s);
                        s = p->Parent->Right;
                    }
                    s->red = p->Parent->red;
                    p->Parent->red = false;
                    s->Right->red = false;
                    Rotate_Left(Tree,p->Parent);
                    p = *Tree;
                }
            }
            else
            {
                s = p->Parent->Left;
                if (s->red == true)
                {
                    s->red = false;
                    p->Parent->red = true;
                    Rotate_Right(Tree,p->Parent);
                    s = p->Parent->Left;
                }
                if (s->Left->red == false && s->Right->red ==false)
                {
                    s->red = true;
                    p = p->Parent;
                }
                else
                {
                    if (s->Left->red == false)
                    {
                        s->Right->red = false;
                        s->red = true;
                        Rotate_Left(Tree,s);
                        s = p->Parent->Left;
                    }
                    s->red = p->Parent->red;
                    p->Parent->red = false;
                    s->Left->red = false;
                    Rotate_Right(Tree,p->Parent);
                    p = *Tree;
                }
            }
            p->red = false;
            (*Tree)->red = false;
        }
    }





int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    /* int N, k;
     cin >> N;
     PNode root = NULL;
     for (int i = 1; i <= N; i++)
     {
         cin >> k;
         AddToTree(root, k);
     }
     PrintTree1(root);*/
    GameObject* obj=NULL ;
    NIL->Left = nullptr;
    NIL->Right = nullptr;
    NIL->obj = nullptr;
    NIL->red = false;
    //RBTree** Tree= NULL;
    RBTree* New_Node = new RBTree();
    New_Node = NIL;


    int action = -1;
    while (action != 0) {
        cout << "1.Добавить элемент\n2.Удалить элемент\n3.Вывести элементы\n0.Выход" << endl;
        int action;
        cin >> action;
        switch (action)
        {
        case 1: {
            cout << "Введите тип игрового объекта: 1- снаряд, 2- транспортное средство, 3- танк, 4- самолёт" << endl;
            int type;int ident=0;
            cin >> type;
            cout << "Введите идентификатор" << endl;;

            cin >> ident;
            RBTree *result = FindItem(ident, New_Node);
            while (result!=NIL) {
                cout << "Элемент с таким идентификатором уже существует" << endl;
                GameObject* obj = result->obj;
                ClassDefinition(obj);
                cout << "Введите идентификатор" << endl;

                cin >> ident;
                result = FindItem(ident, New_Node);
            }

            if (type == 1) {
                Projectile* p = new Projectile();
                p->UniqueIdentifier(ident);
                cout << "Укажите калибр" << endl;
                string caliber;
                cin >> caliber;
                cout << "Укажите вес" << endl;
                int weight;
                cin >> weight;
                p->Caliber(caliber);
                p->Weight(weight);
                 obj = p;


            }
            else if (type == 2) {
                TransportVehicle* t = new  TransportVehicle();
                t->UniqueIdentifier(ident);
                cout << "Укажите мощность двигателя" << endl;
                int enginePower;
                cin >> enginePower;
                cout << "Укажите вес" << endl;
                int weight;
                cin >> weight;
                t->EnginePower(enginePower);
                t->Weight(weight);
                obj = t;
            }
            else if (type == 3) {
                Tank*tn =new Tank();

                cout << "Укажите толщину брони" << endl;
                int armorThickness;
                cin >> armorThickness;
                cout << "Укажите текстуру" << endl;
                string texture;
                cin >> texture;
                cout << "Укажите мощность двигателя" << endl;
                int enginePower;
                cin >> enginePower;
                cout << "Укажите вес" << endl;
                int weight;
                cin >> weight;
                tn->EnginePower(enginePower);
                tn->Weight(weight);
                tn->ArmorThickness(armorThickness);
                tn->Texture(texture);
                tn->UniqueIdentifier(ident);
                obj = tn;
            }
            else {
                Airplane* a = new Airplane();
                a->UniqueIdentifier(ident);

                cout << "Грузоподъёмность" << endl;
                int loadCapacity;
                cin >> loadCapacity;
                cout << "Укажите текстуру" << endl;
                string texture;
                cin >> texture;
                cout << "Укажите мощность двигателя" << endl;
                int enginePower;
                cin >> enginePower;
                cout << "Укажите вес" << endl;
                int weight;
                cin >> weight;
                a->EnginePower(enginePower);
                a->Weight(weight);
                a->LoadCapacity(loadCapacity);
                a->Texture(texture);
                obj = a;
            }

            //int s = *d;
            Insert_Node(&New_Node, obj);
            break;

        }
        case 2: {
            cout << "Введите идентификатор" << endl;
            int ident;
            cin >> ident;


                DeleteNode(ident, &New_Node);

            break;
        }
        case 3: {
            cout << "1- прямой обход, 2- обратный обход, 3- симметричный обход" << endl;
            int bypass;
            cin >> bypass;

            if (bypass == 1) {
                PreOrder_RBTree(New_Node);
                cout << endl;
            }
            else if (bypass == 2) {
                PostOrder_RBTree(New_Node);
                cout << endl;
            }
            else SymmetricOrder_RBTree(New_Node); {
                cout << endl; }
            PrintTree1(New_Node);
            cout << endl;
            break;
        }
        case 0: {
            delete (obj);
            Delete_RBTree(New_Node);
            return 0;
        }
        default:
            break;
        }
    }
}