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

class Samochod{
private:
    int cena;
public:
    Samochod *left, *right, *up, *next;

    Samochod()
    {
        cena = rand() % 100 + 5;
        left = right = up = next = NULL;
        //cout << "new car. price =  " << cena << endl;
    }
Samochod* wstaw_l(Samochod *w)
{
    if(!this)
        return w;
    if(w -> cena < this -> cena)
    {
        w -> next = this;
        return w;
    }
    if(!next)
        next = w;
    else
        if(w -> cena > next -> cena)
            next -> wstaw_l(w);
        else
        {
            w -> next = next;
            this -> next = w;
        }
    return this;
}

int return_price(){return cena;}

void print_l()
{
    cout << "a car. price = " << cena << " ;)) " << endl;
    if(next)
        next -> print_l();
}

int size_l(int i = 1)
{
    if(next)
        i = next -> size_l(++i);
    return i;
}

Samochod * wstaw_d(Samochod *&w){
    if(!this)
        return w;
    if(w -> cena < this -> cena)
    {
        if(left)
            left -> wstaw_d(w);
        else
        {
            left = w;
            //w = w -> next;
           // left -> next = NULL;
        }
    }
    else
    {
        if(right)
            right -> wstaw_d(w);
        else
        {
            right = w;
            //w = w -> next;
            //right -> next = NULL;
        }
    }
    return this;
}

Samochod *l_d(Samochod *& root_l) // przenosimy tylko parzysta cene
{

    Samochod *root_d = NULL;
    if(root_l -> cena % 2 == 0)
    {
        //cout << "e h ";
        root_d = root_d -> wstaw_d(root_l);
        root_l = root_l -> next;
        root_d -> next = NULL;
        if(root_l)
        {

            while(root_l -> cena % 2 == 0)
            {

                //Samochod *pom = root_l;
                root_d = root_d -> wstaw_d(root_l);

                root_l = root_l -> next;
                //pom -> next = NULL;

                if(!root_l)
                {
                    cout << "THIS" ;
                    return this;

                }
            }
            if(root_l -> next)
            {

                Samochod * pom = root_l;
                Samochod * pom2 = root_l -> next;
                while(pom2)
                {
                    if(pom2 -> cena % 2 == 0)
                    {
                        pom -> next = pom2 -> next;
                        pom2 -> next = NULL;
                        root_d -> wstaw_d(pom2);
                        pom2 = pom -> next;
                    }
                    else
                    {
                        pom = pom2;
                        pom2 = pom2 -> next;
                    }
                }
            }
        }

    }
    else
    {
        if(root_l -> next)
        {
            Samochod *pom = root_l;
            Samochod *pom2 = root_l -> next;
            while(pom2)
            {
                //cout << "e h ";

                if(pom2 -> cena % 2 == 0)
                {
                    pom -> next = pom2 -> next;
                    pom2 -> next = NULL;
                    root_d = root_d -> wstaw_d(pom2);
                    pom2 = pom -> next;
                }
                else
                {
                    pom = pom2;

                    pom2 = pom -> next;
                }
            }
        }
    }
    //cout << " lista drzewo korzen " << root_d;

    return root_d;
}

void print_d(){
    //cout << " left - " << left << " right - " << right << endl;
    if(left)
        left -> print_d();

    cout << " drzewko || cena   =  " << cena << endl;

    if(right)
        right -> print_d();
}

int size_d(int i = 1)
{
    if(!this)
        return 0;
    if(left)
        i = left -> size_d(++i);
    if(right)
        i = right -> size_d(++i);

    return i;

}

};



int main(){

    Samochod *root = NULL;
    //cout << "root =  " << root -> return_price() << endl;

    srand(time(NULL));
    cout << endl << endl;
    for(int i = 0; i < 500; i++)
    {
           root = root -> wstaw_l(new Samochod);
    }
    cout << endl << endl;
    //cout << "root =  " << root -> return_price() << endl;
    //cout << endl << "LIST : : LENGTH: " << root -> size_l()<< endl;
    //root -> print_l();

    cout << endl << endl;
    for(int i = 0; i < 500; i++)
    {
           root = root -> wstaw_l(new Samochod);
    }

    cout << endl << endl;
    cout << endl << "LIST : : LENGTH: " << root -> size_l() << endl;
    root -> print_l();

    Samochod * root_d = NULL;
    root_d = root_d -> l_d(root);
    cout << " lista po drzewie i jej size = " << root_d -> size_d()<< endl;


    cout << endl << endl;

    root_d -> print_d();
    cout << " lista po drzewie i jej size = " << root -> size_l()<< endl;

    root -> print_l();


    return 0;
}