#include <iostream>
#include <stdio.h>
#include <time.h>
#include<cstdlib>
using namespace std;


int tab [1000000];
int tabx [1000000];
int tabpom [1000002]={0};
int gi=0;
//nieparzyste X
void randGenX (int n, int maks)
{
     for (int i=0;i<1000002; i++)
     {
         tabpom[i]=0;
     }
    int x;
    srand(time(NULL));
    for (int i=0; i<n; i++)
    {
        x= rand()%maks +1;
        while (tabpom [x]!=0 || x%2==0) //jesli jeden z tych warunkow nie jest spelniony-zdanie jest prawda-nastepuje ponowne losowanie-jesli oba sa prawda-nie losuje
        {
            x= rand()%maks +1;
        }

        tabx[i] = x; //poprawka - przypisanie było odwrotnie
        tabpom [x] ++; //zwiekszanie licznika wystapien danej liczby

    }

}

void ascGen (int n)
{
    for (int i=0; i<n; i++)
    {
        tab[i]=(i+1)*2;
    }
}

//int tabpom [1000002]={0};
void randGen (int n)
{
    for (int i = 0; i < 1000002; i++) {
        tabpom[i] = 0;
    }
    int x;
    srand(time(NULL));
    for (int i=0; i<n; i++)
    {
        x= rand()%1000000 +1;
        while (tabpom [x]!=0 || x%2!=0)
        {
            x= rand()%1000000 +1;
        }

        tab[i] = x; //poprawka - odwrotne przypisanie
        tabpom [x] ++;

    }

}
int tabpomm[1000000]; //tablica globalna
//polowienie binarne
void BinDiv(int left, int right)
{
    if (left<=right)
    {
        int pivot = (left+right)/2;
        tabpomm[gi]=tab[pivot];
        gi++;
        BinDiv(left, pivot-1); //lewy podprzedzial
        BinDiv(pivot+1, right); //prawy
    }
}

//funkcja przekopiowuje wynik pracy BinDiv z tablicy tabpomm do tab
void BinDivCopy(int n)
{
    for (int i = 0; i < n; i++) {
        tab[i] = tabpomm[i];
    }
}


struct Lnode
{
    Lnode *prev;
    Lnode *next;
    int n;
};


struct Tnode
{
    int n;
    Tnode *left;
    Tnode *right;
    Tnode *up;
};
Tnode *root;



void addElement(Tnode *root, int n)
{
    Tnode *current = root;
    while (true)
    {
        if (n > current->n)
        {
            if (current->right == NULL)
            {
                Tnode *newnode = new Tnode;
                newnode->n = n;
                newnode->right = NULL;
                newnode->left = NULL;
                newnode->up=current; //tutaj byl problem
                current->right = newnode;
                break;
            }
            else
            {
                current = current->right;
            }
        }
        else
        {
            if (current->left == NULL)
            {
                Tnode *newnode = new Tnode;
                newnode->n = n;
                newnode->right = NULL;
                newnode->left = NULL;
                newnode->up=current;//i tutaj tez
                current->left = newnode;
                break;
            }
            else
            {
                current = current->left;
            }
        }
    }
}


void findElement(Tnode *root, int n)
{
    Tnode *current = root;
    while (current->n != n)
    {
        if (n > current->n)
        {
            current = current -> right;
        }
        else
        {
            current = current -> left;
        }
    }
}



// Funkcja zwraca wskaznik do elementu najbardziej na lewo, na bazie eduinf.waw.pl
//Ich implementacja jest trochę klarowniejsza, uznałem że łatwiej będzie można ją wykorzystac
Tnode * FindMin(Tnode * p)
{
    if(p != NULL)
        while(p->left != NULL) p = p->left;
    return p;
}

// Funkcja znajduje następnik węzła p, na bazie eduinf.waw.pl
Tnode * FindSuccesor(Tnode * p)
{
  Tnode * r;

  if(p != NULL)
  {
    if(p->right != NULL) return FindMin(p->right);
    else
    {
      r = p->up;
      while(r != NULL && (p == r->right))
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return p;
}

// Procedura usuwa węzeł drzewa, na bazie eduinf.waw.pl
void DeleteElement(Tnode * & root, Tnode * X)
{
  Tnode * Y, * Z;

  if(X != NULL)
  {
    // Jeśli X nie ma synów lub ma tylko jednego, to Y wskazuje X
    // Inaczej Y wskazuje następnik X

    if (X->left == NULL || X->right == NULL) {
        Y = X;
    }
    else
    {
        Y = FindSuccesor(X);
    }

    // Z wskazuje syna Y lub NULL

    if (Y->left != NULL) {
        Z = Y->left;
    }
    else
    {
        Z = Y->right;
    }

    // Jeśli syn Y istnieje, to zastąpi Y w drzewie

    if(Z != NULL) Z->up = Y->up;

    // Y zostaje zastąpione przez Z w drzewie

    if (Y->up == NULL) root = Z;
    else if(Y == Y->up->left) Y->up->left  = Z;
    else                      Y->up->right = Z;

    // Jeśli Y jest następnikiem X, to kopiujemy dane

    if(Y != X) X->n = Y->n;

    delete Y;

  }
}


void DeleteElementByValue (Tnode *root, int n) {
    Tnode *current = root;
    while (current->n != n)
    {
        if (n > current->n)
        {
            current = current -> right;
        }
        else
        {
            current = current -> left;
        }
    }
    DeleteElement(root, current);
}

//usuwa drzewo dla danego korzenia
void DeleteTree (Tnode *start) {
    if (start != NULL) {
        DeleteTree(start->left);
        DeleteTree(start->right);
        delete start;
    }
}

//zwraca wysokosc drzewa, h = 0 przy wywolaniu
int getHeight (Tnode *x, int h) {
    if (x == NULL) {return h;}
    int a = getHeight(x->left, h+1);
    int b = getHeight(x->right, h+1);
    if (a>b) {
        return a;
    } return b;
}

//...........OBSLUGA LISTY....................

void AddListElement (Lnode *start, int n)
{
    Lnode *p;
    p=start;
    while (n<p->n)
    {
        p=p->next;
    }

    Lnode *mid=new Lnode;
    mid->n=n;
    Lnode *prawy=p;
    Lnode *lewy=p->prev;
    mid->prev=lewy;
    mid->next=prawy;
    lewy->next=mid;
    prawy->prev=mid;

}

//symulacja czasu znalezienia elementu
void FindListElement (Lnode *start, int n)
{
    while (start-> n != n) {
        start = start -> next;
    }
}

void RemoveListElement (Lnode *start, int n)
{
    Lnode *p;
    p=start;
    while (p->n!=n)
    {
        p=p->next;
    }
    Lnode *todelete;
    todelete=p;
    Lnode *poprzedni;
    Lnode *nastepny;
    poprzedni=p->prev;
    nastepny=p->next;

    delete todelete;
    poprzedni->next=nastepny;
    nastepny->prev=poprzedni;
}

int main()
{
    int n,x;
    clock_t t_start, t_stop; //zmiana nazw - potencjalna kolizja z start i stop listy
    double czas;
    int input;
    Lnode *start, *stop, *newlist;
    for (n=50000; n<550000; n=n+25000) {
        //cout<<"n: "<<n<<endl;
        x=n/100;
        //zestaw dla polowienia binarnego:
        gi = 0;
        ascGen(n); //Najpierw generujemy ciag rosnacy - na nim bedzie operowal BinDiv
        BinDiv(0, n-1); //Odpalamy BinDiv, dane zostaja zapisane w tabpomm
        BinDivCopy(n); //Kopiujemy dane z tabpomm do tab

        /*
        //zestaw dla rosnacego:
        //*///ascGen(n);

        //zestaw dla losowego:
        //randGen(n);

        randGenX(x,2*n); //Generujemy ciag x - w kazdym przypadku
        czas=0;
        t_start = clock(); //czas start tworzenia nowej listy
        //tworzenie nowej listy
        newlist=new Lnode;
        newlist->n=tab[0];
        newlist->prev = NULL; //konieczne przy tworzeniu listy
        newlist->next = NULL;
        start=newlist;
        stop=newlist;
        //wywolanie dla listy malejacej dodawania nowego elementu

        for (int i = 1; i < n; i++) { //i trzeba było zadeklarować przez int i
            input = tab[i]; //to potrzebne w za każdym razem - zawsze wstawiamy inny element
            if (start->n <=  input)
            { //jezeli element trzeba wstawic na poczatek listy
                Lnode *newnode=new Lnode;
                newnode->n = input;
                newnode->prev = NULL;
                newnode -> next = start;
                start->prev=newnode;
                start=newnode;
            }
            else if (stop->n >=input)
            { //jezeli element trzeba wstawic na koniec listy
                FindListElement(start, stop->n); //symulacja czasu znalezienia ostatniego elementu
                Lnode *newnode=new Lnode;
                newnode->n=input;
                newnode->prev=stop;
                newnode->next=NULL;
                stop->next=newnode;
                stop=newnode;
            }
            else
            { //jezeli element trzeba wstawic miedzy istniejace
                AddListElement (start, input);
            }
            }
            t_stop=clock();
            czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
            cout<<czas<<endl;
            czas=0;
            }
            cout<<endl;

        for (n=50000; n<550000; n=n+25000) {
        //cout<<"n: "<<n<<endl;
        x=n/100;
        //zestaw dla polowienia binarnego:
        gi = 0;
        ascGen(n); //Najpierw generujemy ciag rosnacy - na nim bedzie operowal BinDiv
        BinDiv(0, n-1); //Odpalamy BinDiv, dane zostaja zapisane w tabpomm
        BinDivCopy(n); //Kopiujemy dane z tabpomm do tab

        /*
        //zestaw dla rosnacego:
        //*/ //ascGen(n);

        //zestaw dla losowego:
        //randGen(n);

        randGenX(x,2*n); //Generujemy ciag x - w kazdym przypadku

        //tworzenie nowej listy
        newlist=new Lnode;
        newlist->n=tab[0];
        newlist->prev = NULL; //konieczne przy tworzeniu listy
        newlist->next = NULL;
        start=newlist;
        stop=newlist;
        //wywolanie dla listy malejacej dodawania nowego elementu

        for (int i = 1; i < n; i++) { //i trzeba było zadeklarować przez int i
            input = tab[i]; //to potrzebne w za każdym razem - zawsze wstawiamy inny element
            if (start->n <=  input)
            { //jezeli element trzeba wstawic na poczatek listy
                Lnode *newnode=new Lnode;
                newnode->n = input;
                newnode->prev = NULL;
                newnode -> next = start;
                start->prev=newnode;
                start=newnode;
            }
            else if (stop->n >=input)
            { //jezeli element trzeba wstawic na koniec listy
                FindListElement(start, stop->n); //symulacja czasu znalezienia ostatniego elementu
                Lnode *newnode=new Lnode;
                newnode->n=input;
                newnode->prev=stop;
                newnode->next=NULL;
                stop->next=newnode;
                stop=newnode;
            }
            else
            { //jezeli element trzeba wstawic miedzy istniejace
                AddListElement (start, input);
            }
            }



        //dane już zostały wstawione do listy, teraz dodajemy ciąg x do listy
        //cout<<"dodawanie ciagu x"<<endl;
        t_start=clock();
        for (int i = 0; i < x; i++) {
            input = tabx[i];
            if (start->n <=  input)
            { //jezeli element trzeba wstawic na poczatek listy
                Lnode *newnode=new Lnode;
                newnode->n = input;
                newnode->prev = NULL;
                newnode -> next = start;
                start->prev=newnode;
                start=newnode;
            }
            else if (stop->n >=input)
            { //jezeli element trzeba wstawic na koniec listy
                Lnode *newnode=new Lnode;
                newnode->n=input;
                newnode->prev=stop;
                newnode->next=NULL;
                stop->next=newnode;
                stop=newnode;
            }
            else
            { //jezeli element trzeba wstawic miedzy istniejace
                AddListElement (start, input);
            }
            }
            t_stop=clock();
            czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
            cout<<czas<<endl;
            czas=0;
            }
            cout<<endl;

        //następnie usuwamy ciąg x z listy
        for (n=50000; n<550000; n=n+25000) {
        //cout<<"n: "<<n<<endl;
        x=n/100;
        //zestaw dla polowienia binarnego:
        gi = 0;
        ascGen(n); //Najpierw generujemy ciag rosnacy - na nim bedzie operowal BinDiv
        BinDiv(0, n-1); //Odpalamy BinDiv, dane zostaja zapisane w tabpomm
        BinDivCopy(n); //Kopiujemy dane z tabpomm do tab

        /*
        //zestaw dla rosnacego:
        //*/ //ascGen(n);

        //zestaw dla losowego:
        //randGen(n);

        randGenX(x,2*n); //Generujemy ciag x - w kazdym przypadku

        //tworzenie nowej listy
        newlist=new Lnode;
        newlist->n=tab[0];
        newlist->prev = NULL; //konieczne przy tworzeniu listy
        newlist->next = NULL;
        start=newlist;
        stop=newlist;
        //wywolanie dla listy malejacej dodawania nowego elementu

        for (int i = 1; i < n; i++) { //i trzeba było zadeklarować przez int i
            input = tab[i]; //to potrzebne w za każdym razem - zawsze wstawiamy inny element
            if (start->n <=  input)
            { //jezeli element trzeba wstawic na poczatek listy
                Lnode *newnode=new Lnode;
                newnode->n = input;
                newnode->prev = NULL;
                newnode -> next = start;
                start->prev=newnode;
                start=newnode;
            }
            else if (stop->n >=input)
            { //jezeli element trzeba wstawic na koniec listy
                FindListElement(start, stop->n); //symulacja czasu znalezienia ostatniego elementu
                Lnode *newnode=new Lnode;
                newnode->n=input;
                newnode->prev=stop;
                newnode->next=NULL;
                stop->next=newnode;
                stop=newnode;
            }
            else
            { //jezeli element trzeba wstawic miedzy istniejace
                AddListElement (start, input);
            }
            }



        //dane już zostały wstawione do listy, teraz dodajemy ciąg x do listy
        //cout<<"dodawanie ciagu x"<<endl;
        t_start=clock();
        for (int i = 0; i < x; i++) {
            input = tabx[i];
            if (start->n <=  input)
            { //jezeli element trzeba wstawic na poczatek listy
                Lnode *newnode=new Lnode;
                newnode->n = input;
                newnode->prev = NULL;
                newnode -> next = start;
                start->prev=newnode;
                start=newnode;
            }
            else if (stop->n >=input)
            { //jezeli element trzeba wstawic na koniec listy
                Lnode *newnode=new Lnode;
                newnode->n=input;
                newnode->prev=stop;
                newnode->next=NULL;
                stop->next=newnode;
                stop=newnode;
            }
            else
            { //jezeli element trzeba wstawic miedzy istniejace
                AddListElement (start, input);
            }
            }
            t_stop=clock();
            czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
            czas=0;
            t_start=clock();
            for (int i = 0; i < x; i++) {
            input = tabx[i];
            if (start->n ==  input)
            { //jezeli usuwany element to pierwszy z listy
                Lnode *temp;
                temp=start;
                start=start->next;
                delete temp;
                start->prev=NULL;
            }

            else if (stop->n ==input)
            { //jezeli usuwany element to ostatni z listy
                FindListElement(start, stop->n); //symulacja czasu znalezienia ostatniego elementu
                Lnode *temp;
                temp=stop;
                stop=stop->prev;
                delete temp;
                stop->next=NULL;
            }

            else
            { //jezeli usuwany jest miedzy dwoma innymi
                RemoveListElement (start, input);
            }

            }
        t_stop = clock();
        czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
        cout<<czas<<endl;
        czas=0;
            }
            cout<<endl;
            for (n=50000; n<550000; n=n+25000) {
            cout<<n<<endl;
            }
/*
            //na koniec dla porządku możemy jeszcze zaimplementować usuwanie listy, pod windowsem moze to miec znaczenie
            //oczywiscie poza pomiarem czasu
            Lnode *pom;
            while (start!=NULL) {
                pom = start;
                start = start -> next;
                delete pom;
            }

            //praca na strukturze drzewa
            //dodawanie korzenia
            czas=0;
            t_start=clock();
            root = new Tnode;
            root->n = tab[0];
            root->left = NULL;
            root->right = NULL;
            root->up = NULL;
            cout<<"dodawanie elementow do drzewa"<<endl;
            //Nastepnie w petli dodajemy nowy element voidem ktory zdefiniowalismy wczesniej (AddElement)
            for (int i = 1; i < n; i++) { //i trzeba było zadeklarować przez int i
                addElement(root, tab[i]);
            }
            t_stop=clock();
            czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
            cout<<czas<<endl;
            cout<<"dodawanie elementow do drzewa z x"<<endl;
            czas=0;

            t_start=clock();
            //Dodajemy elementy z ciągu x
            for (int i = 0; i < x; i++)
                addElement(root, tabx[i]);
            t_stop=clock();
            czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
            cout<<czas<<endl;
            czas=0;

            //Usuwamy kolejne elementy z ciągu x
            t_start=clock();
            for (int i = 0; i < x; i++) {
                DeleteElementByValue(root, tabx[i]);
            }
            t_stop=clock();
            czas = double(t_stop - t_start) / CLOCKS_PER_SEC;
            cout<<czas<<endl;
*/
    }
            //wypisujemy wysokosc drzewa
            //dla drzewa idealnie zrownowazonego h = zaokraglenie w gore z log2(n)
            //for(n=200000; n<=295000; n=n+5000)
            //cout<<"h = "<<getHeight(root, 0)<<endl;
            //Usuwamy drzewo

            //DeleteTree(root);