// ConsoleApplication13.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include "pch.h"
#include <iostream>
#include <cstdlib>

using namespace std;

class kulka
{
public:
	int wartosc;
	int numer;
	kulka *next = NULL;
	kulka *right = NULL;
	kulka *left = NULL;

	kulka(int nr)
	{
		wartosc = rand() % 100;
		numer = nr;
	}

	void lista(kulka *nowa)
	{
		if (next)
		{
			if (nowa->wartosc > next->wartosc)
			{
				nowa->next = next;
				next = nowa;
			}
			else
				next->lista(nowa);
		}

		else
			next = nowa;
	}

	void show_lista()
	{
		cout << "numer: " << numer << "  " << wartosc << endl;
		if (next)
			next->show_lista();
	}

	void show_lista_rosnaco()
	{
		if (next)
			next->show_lista_rosnaco();
		cout << "numer: " << numer << " " << wartosc << endl;
	}


	void drzewo(kulka *nowa)
	{
		if (nowa->wartosc < wartosc)
		{
			if (left)
				left->drzewo(nowa);
			else
				left = nowa;
		}
		else
		{
			if (right)
				right->drzewo(nowa);
			else
				right = nowa;
		}
	}

	void show_drzewo()
	{
		if (left)
			left->show_drzewo();
		cout << "numer:  " << numer << " " << wartosc << endl;
		if (right)
			right->show_drzewo();
	}
	int P(int &p)
	{
		if(wartosc % 3 == 0)
		p = p + 1;
		if (next)
			next->P(p);

		return p;
	}
	int NP(int &p)
	{
		if (wartosc % 3 != 0)
			p = p + 1;
		if (next)
			next->NP(p);

		return p;
	}
	int lel(int &i)
	{
		i = i + 1;
		if (next)
			next->lel(i);

		return i;
	}
};
int main()
{
	kulka *root_p = NULL;
	kulka *root_np = NULL;
	kulka *root = NULL;

	for (int i = 0; i < 20; i++)
	{
		kulka *nowa = new kulka(i);

		if (root == NULL)
			root = nowa;

		else
		{
			if (nowa->wartosc > root->wartosc)
			{
				nowa->next = root;
				root = nowa;
			}
			else
				root->lista(nowa);
		}
	}


	cout << "cala lista malejaco" << endl;
	root->show_lista();

	cout << endl;

	cout << "cala lista rosnaco" << endl;
	root->show_lista_rosnaco();

	cout << endl;
	int p = 0;
	int np = 0;
	root->P(p);
	root->NP(np);
	cout << "Licza elementow podzielnych przez 3: " << p  << endl;
	cout << "Licza elementow niepodzielnych przez 3: " << np << endl << endl;

	//dodawanie elementow do list: parzystej i nieparzystej

	kulka *pom = root;

	while (root->next)
	{
		pom = root;
		root = root->next;
		pom->next = NULL;
		if (pom->wartosc % 2 == 0)
		{
			if (root_p == NULL)
				root_p = pom;
			else
				root_p->lista(pom);
		}
		else
		{
			if (root_np == NULL)
				root_np = pom;
			else
				root_np->lista(pom);
		}

	}

	if (root->wartosc % 2 == 0)
		root_p->lista(root);
	else
		root_np->lista(root);

	int P = 1;
	int NP = 1;
	root_p->lel(P);
	root_p->lel(NP);

	//drzewo z listy parzystej

	kulka *pom_drzewo1 = NULL;
	kulka *root_drzewo = NULL;

	while (root_p->next)
	{
		pom_drzewo1 = root_p;
		root_p = root_p->next;
		pom_drzewo1->next = NULL;
		if (root_drzewo == NULL)
			root_drzewo = pom_drzewo1;
		else
			root_drzewo->drzewo(pom_drzewo1);
	}

	if (root_p)
		root_drzewo->drzewo(root_p);

	cout << "Drzewo parzyste" << endl;
	root_drzewo->show_drzewo();

	cout << endl;

	//drzewo z listy parzystej

	kulka *pom_drzewo2 = NULL;
	kulka *root_drzewo2 = NULL;

	while (root_np->next)
	{
		pom_drzewo2 = root_np;
		root_np = root_np->next;
		pom_drzewo2->next = NULL;
		if (root_drzewo2 == NULL)
			root_drzewo2 = pom_drzewo2;
		else
			root_drzewo2->drzewo(pom_drzewo2);
	}

	if (root_np)
		root_drzewo->drzewo(root_np);

	cout << "Drzewo nieparzyste" << endl;
	root_drzewo2->show_drzewo();

	cout << endl;

	cout << "Liczba elementów w drzewie parzystym : " << P << endl;
	cout << "Liczba elementów w drzewie nieparzystym : " << NP << endl;



	return 0;
}