#include "binarni-strom.h"

PrvekStromu::PrvekStromu( const int _data )
{
   data = _data;
   levy = NULL;
   pravy = NULL;
}

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

void Strom::VlozPrvek( const int data )
{
   if (koren==NULL)
   {
      koren = new PrvekStromu( data );
      return;
   }
   PrvekStromu *predchudce = NULL;
   PrvekStromu *soucasny = koren;
   if( NajdiVeStromu(data, &soucasny, &predchudce ) == true )
   {
      std::cout << "Prvek uz je ve stromu," << std::endl;
      return;
   }
   assert(predchudce != NULL);
   assert(predchudce->data != data);
   
   if(predchudce->data < data)
   {
      predchudce->pravy = new PrvekStromu( data );
   }
   else predchudce->levy = new PrvekStromu( data );
}

bool Strom::NajdiPrvek( const int data )
{
    PrvekStromu *soucasny = koren;
    PrvekStromu *predchudce = NULL;
    return NajdiVeStromu(data, &soucasny, &predchudce);
}


bool Strom::NajdiVeStromu( const int data,
                           PrvekStromu **soucasny,
                           PrvekStromu **predchudce)
{
   if (*soucasny==NULL)
   {
      return false;
   }
   if ( (*soucasny)->data == data)
   {
      return true;
   }
   if ((*soucasny)->data > data)
   {
      *predchudce = *soucasny;
      *soucasny = (*soucasny)->levy;
      NajdiVeStromu(data, soucasny, predchudce );         
   }
   else
   {
      *predchudce = *soucasny;
      *soucasny = (*soucasny)->pravy;
      NajdiVeStromu(data, soucasny, predchudce );
   }
}

void Strom::SmazList( PrvekStromu* predchudce, PrvekStromu* soucasny )
{
    if( predchudce == NULL )
    {
        koren = NULL;
        delete soucasny;
        return;
    }
    assert ((predchudce->pravy==soucasny)||(predchudce->levy==soucasny));
    if (predchudce->pravy==soucasny)
    {
        predchudce->pravy=NULL;
    }  else {
        predchudce->levy=NULL;
    }
    delete soucasny;
}

void Strom::SmazVeVetvi( PrvekStromu* predchudce, PrvekStromu* soucasny )
{
    PrvekStromu *nasledovnik = soucasny -> levy;
    if (nasledovnik == NULL)
    {
        nasledovnik = soucasny -> pravy;
    }
    
    if( predchudce == NULL )
    {
        koren = nasledovnik;
        delete soucasny;
        return;
    }
    assert ((predchudce->pravy==soucasny)||(predchudce->levy==soucasny));
    if (predchudce->pravy==soucasny)
    {
        predchudce->pravy=nasledovnik;
    }  else {
        predchudce->levy=nasledovnik;
    }
    delete soucasny;     
}

void Strom::SmazVeStromu( PrvekStromu* prvek )
{
    /****
     * Najdi nejmensi prvek v pravem podstromu
     */
    PrvekStromy* soucasny = prvek;
    PrvekStromu* predchudce = soucasny;
    soucasny = soucasny->pravy;
    while( soucasny->levy != NULL )
    {
        predchudce = soucasny;
        soucasny = soucasny->levy;
    }
    prvek->data = soucasny->data;
    
    /****
     * Smaz nejmensi prvek v pravem podstromu
     */
    if( soucasny->pravy==NULL && soucasny->levy==NULL )
        return SmazList( predchudce, soucasny );
    
    if( soucasny->levy==NULL || soucasny->pravy == NULL )
        return SmazVeVetvi( predchudce, soucasny );    
    
}

void Strom::SmazPrvek( const int data )
{
    PrvekStromu *soucasny = koren;
    PrvekStromu *predchudce = NULL;
    if (NajdiVeStromu(data, &soucasny, &predchudce)==false)
    {
        return;
    };
    assert (soucasny!=NULL);

    if( soucasny->pravy==NULL && soucasny->levy==NULL )
        return SmazList( predchudce, soucasny );
    
    if( soucasny->levy==NULL || soucasny->pravy == NULL )
        return SmazVeVetvi( predchudce, soucasny );
    
    return SmazVeStromu( soucasny );
}