/*1) Stworzyć 100 kulek o wartościach od 100-999, każda kulka ma wartość,

wskaźnik na następną, oraz licznik którą jest z kolei
2) Włożyć kulki na listę jednokierunkową w taki sposób, że nowa kulka jest

wstawiana bezpośrednio za roota
3) Wyświetlić listę, podać wartość ostatniej kulki i podać licznik ostatniej

(obie rzeczy na funkcjach w klasie)
4) Z listy wyjąć wszystkie wartości parzyste i z nich utworzyć drugą listę,

która zawsze będzie posortowana rosnąco
5) Po każdorazowym dodaniu nowej kulki do drugiej listy, wyświetlać drugą

listę
6) Wyświetlić obie gotowe listy, zrobić funkcję liczącą ile jest kulek w

każdej liście
7) Z obu list wyjąć liczby podzielne przez 3 i wstawić je do drzewa
8) Przygotować funkcje do drzewa, która będzie zwracała ile jest poziomów w

drzewie, oraz ile jest elementów na drzewie (? od tego momentu już nie

pamiętam dokładnie)
9) Destruktor do usuwania kulek

*/

#include <iostream>
#include <cstdlib>
using namespace std;


class Kulka{
public:
        int val,nr;
        Kulka *next;

        Kulka(int);
        Kulka(int,int);
        void add(Kulka *);
        void display();
        void last();
        void addv2(Kulka *);
        int ile();
};
class Drzewo{
public:
    int val;
    Drzewo *prawy,*lewy;
    Drzewo(int);
    void add(Drzewo *);
    void display();
    int ile();
};

Drzewo::Drzewo(int value){
    val=value;
    prawy=NULL;
    lewy=NULL;
}
Kulka::Kulka(int number){
    nr=number;
    val=(rand()%900)+100;
    next=NULL;
}
Kulka::Kulka(int number,int wart){
    nr=number;
    val=wart;
    next=NULL;
}
void Kulka::add(Kulka *wsk){
    if(!next){
        next=wsk;
    }
    else{
        wsk->next=next;
        next=wsk;
    }
}
void Kulka::addv2(Kulka *wsk){
    wsk->next=NULL;
    if(!next){
        next=wsk;
    }
    else if(next->val>wsk->val){
        wsk->next=next;
        next=wsk;
    }
    else{
        next->addv2(wsk);
    }
}
void Kulka::display(){
    cout << val <<" ";
    if(next)next->display();
    else{cout << endl;}
}
void Kulka::last(){
   if(next)next->last();
    else{
        cout << endl << "Ostatnia wartosc: " << val << " Numer: " << nr <<endl;
;    }
}
int Kulka::ile(){
    if(next)return 1+next->ile();
    return 1;

}
void Drzewo::add(Drzewo *wsk){
    if(val>wsk->val){
        if(lewy){
            lewy->add(wsk);
        }
        else{
            lewy=wsk;
        }
    }
    else{
        if(prawy){
            prawy->add(wsk);
        }
        else{
            prawy=wsk;
        }
    }
}
void Drzewo::display(){
    if(lewy){lewy->display();}
    cout << val << "\t";
    if(prawy){prawy->display();}
}
int Drzewo::ile(){
    if(lewy && prawy){return 2+lewy->ile()+prawy->ile();}
    else if(prawy){return 1+prawy->ile();}
    else if(lewy){return 1+lewy->ile();}
    return 0;
}


int main(){

    Kulka *first=new Kulka(0);

    for(int i=1;i<20;i++){
        first->add(new Kulka(i));
    }


    first->display();
    first->last();

    Kulka *second=NULL;

    Kulka *t=first;
    Kulka *h=NULL;

    while(t){
        if(t->val%2==0){
            if(t==first){
                first=first->next;
                if(second==NULL){
                    second=t;
                    second->next=NULL;
                    t=t->next;
                    second->display();
                }
                else{
                    second->addv2(t);
                    second->display();
                }
            }
            else{
                if(second==NULL){
                    second=t;
                    h->next=t->next;
                    second->next=NULL;
                    t=h->next;
                    second->display();
                }
                else{
                    h->next=t->next;
                    second->addv2(t);
                    second->display();
                    t=h->next;
                }
            }

        }
        else{
            h=t;
            t=t->next;
        }
    }

    cout << endl;
    first->display();
    cout << endl;
    second->display();
    cout << endl << "Liczba elem w pierwszej liscie: " << first->ile() <<endl;
    cout << endl << "Liczba elem w drugiej liscie: " << second->ile() <<endl;
    cout << endl;
    t=first;
    h=NULL;
    Drzewo *root=NULL;

    while(t){
        if(t->val%3==0){
            if(t==first){
                if(root==NULL){
                    first=t->next;
                    root=new Drzewo(t->val);
                    t=t->next;
                }
                else{
                    first=t->next;
                    root->add(new Drzewo(t->val));
                    t=t->next;
                }
            }
            else{
                if(root==NULL){
                    root=new Drzewo(t->val);
                    h->next=t->next;
                    t=t->next;
                }
                else{
                    root->add(new Drzewo(t->val));
                    h->next=t->next;
                    t=t->next;
                }

            }
        }
        else{
            h=t;
            t=t->next;
        }
    }

    root->display();
    cout << endl << "Liczba elem w drzewie: " << root->ile()+1 <<endl;
    h=NULL;
    t=second;
    cout <<endl;

    while(t){
        if(t->val%3==0){
            if(t==second){
                if(root==NULL){
                    second=t->next;
                    root=new Drzewo(t->val);
                    t=t->next;
                }
                else{
                    second=t->next;
                    root->add(new Drzewo(t->val));
                    t=t->next;
                }
            }
            else{
                if(root==NULL){
                    root=new Drzewo(t->val);
                    h->next=t->next;
                    t=t->next;
                }
                else{
                    root->add(new Drzewo(t->val));
                    h->next=t->next;
                    t=t->next;
                }

            }
        }
        else{
            h=t;
            t=t->next;
        }
    }

    root->display();
    cout << endl << "Liczba elem w drzewie: " << root->ile()+1 <<endl;
}