#include <stdio.h>
#include<conio.h>
#include<iostream>
#include<fstream>
#include<string>
#include<windows.h>
using namespace std;

int tab[800000];

struct studenci{
    struct studenci *up, *left, *right;
    string imie, nazwisko;
    int indeks;
};

//---------------DODAWANIE-ELEMENTOW-DO-DRZEWA--------------
void add_new_student(studenci *&root, string imie, string nazwisko, int indeks){
    studenci *newone, *y=NULL, *x=root;
    newone = new studenci;
    newone->indeks = indeks;
    newone->imie = imie;
    newone->nazwisko = nazwisko;
    newone->left = newone->right = NULL;

    while(x){
        y = x;
        x = (newone->indeks < x->indeks) ? x->left : x->right;
    }
    newone->up = y;
    if(!y) root = newone;
    else if (newone->indeks < y->indeks){
        y->left = newone;
    }
    else y->right = newone;
}
//-----------------------------

//---------------PRZEGLADANIE-DRZEWA------------------------
void przejdz(studenci *&root){
    if(root)
    {
        przejdz(root->left);
        cout << root->imie << "\t" << root->nazwisko << "\t" << root->indeks << endl;
        przejdz(root->right);
    }
}
//----------------------------


studenci *search_student(studenci *root, int n){
    studenci *to_delete = root;
    while( (to_delete) && (to_delete->indeks != n)){
        to_delete = (n < to_delete->indeks) ? to_delete->left : to_delete->right;
    }
    return to_delete;
}

studenci *find_min(studenci *root, studenci *x){
    x = root;
    while(x->left) x = x->left;
    return x;
}

studenci *find_max(studenci *root, studenci *x){
    x = root;
    while(x->right) x = x->right;
    return x;
}

studenci *pred(studenci *root, studenci *x){
    if(x->left) return find_max(root, x->left);

    studenci *y;
    do{
        y = x;
        x = x->up;
    }while(x && (x->right != y));
    return x;
}

studenci *succ(studenci *root, studenci *x){
    if(x->right) return find_min(root, x->right);

    studenci *y;
    do{
        y = x;
        x = x->up;
    }while(x && (x->left != y));

    return x;
}

studenci *remove_student(studenci *root, studenci *to_delete){
    studenci *y = to_delete->up, *z;

    if((to_delete->left) && (to_delete->right)){
        z = (rand() % 2) ? remove_student(root, pred(root, to_delete)) : remove_student(root, succ(root, to_delete));
        z->left = to_delete->left; if(z->left) z->left->up = z;
        z->right = to_delete->right; if(z->right) z->right->up = z;
    }else z = (to_delete->left) ? to_delete->left : to_delete->right;

    if(z) z->up = y;
    if(!y) root = z;
    else if(y->left == to_delete) y->left = z;
    else y->right = z;
    return to_delete;
}











/*studenci *find_min(studenci *p){
    if(p) while(p->left) p=p->left;
    return p;
}

studenci *find_next(studenci *p){
    studenci *temp;

    if(p){
        if(p->right) return find_min(p->right);
        else{
            temp = p->up;
            while(temp && (p == temp->right)){
                p = temp;
                temp = temp->up;
            }
            return temp;
        }
    }
    return p;
}

//-------------USUWANIE-ELEMENTU-Z-DRZEWA-------------------
void delete_student(studenci *root, studenci *to_delete){
    studenci *y, *z;

    if(to_delete){
        y = !to_delete->left || !to_delete->right ? to_delete : find_next(to_delete);
        z = y->left ? y->left : y->right;
        if(z) z->up = y->up;

        if(!y->up) root = z;
        else if(y == y->up->left) y->up->left = z;
        else    y->up->right = z;

        if(y != to_delete) to_delete->indeks = y->indeks;
        delete y;
    }
}
//----------------------------
*/

double GetTime()
{
  long long f,t;
  QueryPerformanceFrequency((PLARGE_INTEGER)&f);
  QueryPerformanceCounter((PLARGE_INTEGER)&t);
  return (double)t/(double)f;
}

int main()
{
    string imie, nazwisko, nazwa;
    int indeks, num_elements=0, i;
    studenci *root = NULL;

//-------------------_DODAWANIE-DO-DRZEWA_---------------------
    fstream plik;
    cout << "Podaj nazwe pliku: ";
    cin >>nazwa;
    double one = GetTime();
    plik.open(nazwa.c_str(), ios::in);
    if(plik.good() == true){
        while(!plik.eof()){
            plik >> imie;
            plik >> nazwisko;
            plik >> indeks;
            tab[num_elements] = indeks;
            num_elements++;
            add_new_student(root, imie, nazwisko, indeks);
        }
        plik.close();
    }
    double two = GetTime();
    printf("DODAWANIE\t%d, czas:\t%lf\n", num_elements, (double)(two-one));

    plik.open("pomiary.txt", ios::out | ios::app);
    if(plik.good() == true){
        plik << "DODAWANIE:\t" << num_elements << ", czas:\t" << (double)(two-one) << endl;
        plik.close();
    }


//--------------------WYSZUKIWANIE_W_DRZEWIE---------------------------
    studenci *find_student;
    one = GetTime();
    for(i=0; i<num_elements; i++){
        find_student = root;
        while((find_student) && (find_student->indeks != tab[i])){
            find_student = (tab[i] < find_student->indeks) ? find_student->left : find_student->right;
        }
    }
    two = GetTime();
    printf("WYSZUKIWANIE\t%d, czas:\t%lf\n", num_elements, (double)(two-one));

    plik.open("pomiary.txt", ios::out | ios::app);
    if(plik.good() == true){
        plik << "WYSZUKIWANIE:\t" << num_elements << ", czas:\t" << (double)((two-one) / num_elements) << endl ;
        plik.close();
    }



//---------------------USUWANIE-DRZEWA---------------------------------
    studenci *to_delete;
    one = GetTime();
    for(i=0; i<num_elements; i++){
        remove_student(root, search_student(root, tab[i]));
    }
    //przejdz(root);
    getch();
    return 0;
}