#include "Strom.h" 
#include <iostream>
#include <assert.h>  //preklad s -DNDEBUG

using namespace std;

Strom::Strom()
{
	koren = nullptr;
}

bool Strom::Vloz(int data )
{ 
	Prvek *predchudce=nullptr;
	Prvek *hledany = nullptr;
	if( Najdi( data, koren, &predchudce, &hledany) )
	{
		return false;
	}
	else
	{
		Prvek * tmp = new Prvek;
		tmp->data = data;
		tmp->levy = nullptr;
		tmp->pravy = nullptr;
		if( koren == nullptr )
		{
			koren = tmp;
			return true;
		}
		else
		{
			if( predchudce->data < data )
				predchudce->pravy = tmp;				
			else
				predchudce->levy = tmp;
			return true;
		}
	}

}

bool Strom::Smaz( int data )
{
	Prvek *predchudce=nullptr;
	Prvek *hledany = nullptr;
	if(!Najdi(data, koren, &predchudce, &hledany)) return false;
	if(hledany->pravy == nullptr && hledany->levy== nullptr){
		smazList(hledany, predchudce);
		return true;
	}
	if(hledany->pravy == nullptr || hledany->levy== nullptr){
		smazVeVetvi(hledany, predchudce);
		return true;
	}
	smazVeStromu(hledany);
	return true;
}

bool Strom::Najdi(int data )
{
	Prvek *predchudce=nullptr;
	Prvek *hledany = nullptr;
	return Najdi( data, koren, &predchudce, &hledany);
}

bool Strom::Najdi(int data, Prvek *podstrom, Prvek **predchudce, Prvek **hledany)
{
	if( podstrom != nullptr )
	{
		if (podstrom->data == data )
		{
			(*hledany) = podstrom;
			return true;
		}
		(*predchudce) = podstrom;
		if( data < podstrom->data)
			return Najdi( data, podstrom->levy, predchudce, hledany );
		else
			return Najdi( data, podstrom->pravy, predchudce, hledany );

	}
	*hledany = nullptr;
	return false;
}

void Strom::smazList( Prvek* mazany, Prvek* predchudce )
{
   assert( predchudce->levy==mazany || predchudce->pravy==mazany );
   assert( mazany->levy == nullptr && mazany->pravy == nullptr );
   
   if( predchudce->levy==mazany )
	   predchudce->levy=nullptr;
   else predchudce->pravy=nullptr;
   delete mazany;
}
	
void Strom::smazVeVetvi( Prvek* mazany, Prvek* predchudce )
{
   assert( predchudce->levy==mazany || predchudce->pravy==mazany );
   assert( ( mazany->levy == nullptr || mazany->pravy == nullptr ) &&
         	!( mazany->levy == nullptr && mazany->pravy == nullptr) );
   
   Prvek* nasledovnik;
   if( mazany->levy)
      nasledovnik = mazany->levy;
   else
     nasledovnik= mazany->pravy;
   
   if( predchudce->levy==mazany )
      predchudce->levy=nasledovnik;
   else
      predchudce->pravy=nasledovnik;
   delete mazany;
}
	
void Strom::smazVeStromu( Prvek* mazany )
{
   assert(mazany->levy!=nullptr && mazany->pravy!=nullptr);
   Prvek* pomocny = mazany->levy;
   Prvek* predchudce = mazany;
   while(pomocny->pravy!=nullptr){
	   predchudce = pomocny;
	   pomocny = pomocny->pravy;
   }
   mazany->data=pomocny->data;   
   if( pomocny->levy==nullptr)
       smazList(pomocny, predchudce);
   else
       smazVeVetvi(pomocny,predchudce);
}

Strom::~Strom()
{
   if( koren != nullptr )
      smazPodstrom( koren );
}

void Strom::smazPodstrom( Prvek* podstrom )
{
   if( podstrom->levy != nullptr )	
	   smazPodstrom( podstrom->levy );
   if( podstrom->pravy != nullptr )	
	   smazPodstrom( podstrom->pravy );
   delete podstrom;  
}