od_do

#include <iostream>
#include <stdexcept>
#include <vector>


using namespace std;

template <typename Tip1, typename Tip2>
class Cvor
{
public:
    Cvor()
    {
        lijevo=desno=roditelj=0;
    }
    Cvor (const Tip1& klj, const Tip2 &el, Cvor* l, Cvor *r, Cvor* parent)
    {
        kljuc=klj;
        element=el;
        lijevo=l;
        desno=r;
        roditelj=parent;
    }
    Tip1 kljuc;
    Tip2 element;
    Cvor* lijevo, *desno, *roditelj;
};

template <typename Tip1, typename Tip2>
class BinStabloMapa
{
    int brojEL;
    Cvor<Tip1, Tip2>* Korijen;

    Cvor<Tip1, Tip2> * Trazi(Cvor<Tip1, Tip2> *r, const Tip1 &x)const
    {
        if(r==0 || r->kljuc==x )
            return r;
        else if (x < r->kljuc)
            return Trazi(r->lijevo, x);
        else
            return Trazi(r->desno, x);
    }


    Cvor<Tip1, Tip2> * TraziPot(Cvor<Tip1, Tip2> *r, const Tip1 &x)const
    {
        if(r->lijevo && x < r->kljuc)
            return TraziPot(r->lijevo, x);
        else if(r->desno && x> r->kljuc)
            return TraziPot(r->desno, x);
        else return r;
    }

    Cvor<Tip1, Tip2>* pomocnaAlociraj(Cvor<Tip1, Tip2> * C)
    {
        if (C==0)
            return 0;
        Cvor<Tip1, Tip2> *novi=new Cvor<Tip1, Tip2>();
        novi->kljuc=C->kljuc;
        novi->element=C->element;
        return novi;
    }

    void pomocnaKonstruktor(Cvor<Tip1, Tip2> * C1, Cvor<Tip1, Tip2> * C2)
    {
        if (C1==0) return;
        C2->desno = pomocnaAlociraj(C1->desno);
        C2->lijevo = pomocnaAlociraj(C1->lijevo);
        if (C2->desno)
            C2->desno->roditelj = C2;
        if (C2->lijevo)
            C2->lijevo->roditelj = C2;
        pomocnaKonstruktor(C1->desno, C2->desno);
        pomocnaKonstruktor(C1->lijevo, C2->lijevo);

    }
    void Brisi(Cvor<Tip1, Tip2>* Temp)
    {
        if(Temp)
        {
            Brisi(Temp->lijevo);
            Brisi(Temp->desno);

            delete Temp;
        }

    }

    Cvor<Tip1, Tip2>* pomocnaKonstruktor1(const Tip1 *nizKljuceva, const Tip2 *nizVrijednosti,  int prva, int druga,  bool grana=true)
    {
        if(prva==druga)
        {
            Cvor<Tip1, Tip2>* novi= new Cvor<Tip1, Tip2>();
            novi->kljuc=nizKljuceva[prva];
            novi->element=nizVrijednosti[prva];
            return novi;
        }
        else if(prva+1==druga)
        {
            Cvor<Tip1, Tip2> *novi1= new Cvor<Tip1, Tip2>();
            Cvor<Tip1, Tip2> *novi2= new Cvor<Tip1, Tip2>();
            novi1->kljuc=nizKljuceva[prva];
            novi1->element=nizVrijednosti[prva];
            novi2->kljuc=nizKljuceva[druga];
            novi2->element=nizKljuceva[druga];
            if(grana)
            {
                novi2->lijevo=novi1;
                novi1->roditelj=novi2;
                return novi2;
            }
            else
            {
                novi1->desno=novi2;
                novi2->roditelj=novi1;
                return novi1;
            }

        }

        if(prva+1<druga)
        {
            int sredina=(prva+druga)/2;
            int druga2=sredina-1;
            int prva2=sredina+1;
            Cvor<Tip1,Tip2>* glavni=new Cvor<Tip1, Tip2>();
            Cvor<Tip1,Tip2>* lijevi=new Cvor<Tip1, Tip2>();
            Cvor<Tip1,Tip2>* desni=new Cvor<Tip1, Tip2>();
            glavni->kljuc=nizKljuceva[sredina];
            glavni->element=nizVrijednosti[sredina];

            lijevi=pomocnaKonstruktor1(nizKljuceva,nizVrijednosti, prva, druga2, true);
            desni=pomocnaKonstruktor1(nizKljuceva,nizVrijednosti, prva2, druga, false);
            lijevi->roditelj=glavni;
            desni->roditelj=glavni;
            glavni->lijevo=lijevi;
            glavni->desno=desni;
            return glavni;

        }
        else
            return 0;

    }

    Cvor<Tip1, Tip2>* Minimum(Cvor<Tip1, Tip2>* c )
    {
        Cvor<Tip1, Tip2>* Temp=c;

        while(Temp->lijevo)
        {
            Temp=Temp->lijevo;
        }

        return Temp;
    }

    Cvor<Tip1, Tip2>* Maksimum(Cvor<Tip1, Tip2>* c)
    {
        Cvor<Tip1, Tip2>* Temp=c;

        while(Temp->desno)
        {
            Temp=Temp->desno;
        }

        return Temp;
    }
public:
    BinStabloMapa()
    {
        Korijen= 0;
        brojEL=0;
    }

    ~BinStabloMapa()
    {
        if(brojEL!=0)
            Brisi(Korijen);

    }


    Tip2& operator[](Tip1 kljuc)
    {
        Cvor<Tip1, Tip2> *Temp, *Novi;
        if (brojEL == 0)
        {
            Novi= new Cvor<Tip1, Tip2>();
            Novi->kljuc=kljuc;
            Korijen = Novi;
            brojEL++;
        }
        else
        {
            Temp = Trazi(Korijen, kljuc);

            if (Temp)
                return Temp->element;
            Cvor<Tip1, Tip2> *Roditelj;
            bool zadnjeLijevo = false;
            Temp = Korijen;
            while(Temp!=0)
            {
                Roditelj = Temp;

                if(Temp->kljuc > kljuc)
                {
                    Temp=Temp->lijevo;
                    zadnjeLijevo = true;
                }
                else
                {
                    Temp=Temp->desno;
                    zadnjeLijevo = false;
                }
            }

            Novi= new Cvor<Tip1, Tip2>();
            Novi->kljuc=kljuc;
            Novi->roditelj = Roditelj;

            if (zadnjeLijevo)
                Roditelj->lijevo = Novi;
            else
                Roditelj->desno = Novi;

            brojEL++;
        }
        Novi->element = Tip2();

        return Novi->element;

    }
    Tip2 operator[](Tip1  kljuc)const
    {
        Cvor<Tip1, Tip2>* Temp=Trazi(Korijen,kljuc);
        if(!Temp) return Tip2();
        return Temp->element;
    }

    int brojElemenata()const
    {
        return brojEL;
    }

    void obrisi()
    {
        Brisi(Korijen);
        Korijen = 0;
        brojEL=0;
    }

    void obrisi(const Tip1& kljuc)
    {
        Cvor<Tip1, Tip2>* Temp = Trazi(Korijen, kljuc);
        Cvor<Tip1, Tip2>* it=Temp;

        if(it->roditelj==0)
        {
            if (it->desno && it->lijevo)
            {
                it = it->desno;

                while (it->lijevo)
                    it=it->lijevo;

                if (it->desno)
                {
                    it->desno->roditelj = it->roditelj;
                    it->roditelj->lijevo = it->desno;
                    it->desno = 0;
                }

                it->roditelj = 0;
            }
            else if (it->desno)
            {
                it = it->desno;
                it->roditelj = 0;
                Korijen = it;

                delete Temp;
                brojEL--;
                return;
            }
            else if (it->lijevo)
            {
                it = it->lijevo;
                it->roditelj = 0;
                Korijen = it;

                delete Temp;
                brojEL--;
                return;
            }
            else
            {
                Brisi(Korijen);
                brojEL = 0;
                return;
            }

            Temp->kljuc = it->kljuc;
            Temp->element = it->element;

            brojEL --;
            return;
        }
        else
        {
            if (it->desno && it->lijevo)
            {
                it = it->desno;

                while (it->lijevo)
                    it=it->lijevo;

                if (it->desno)
                {
                    it->desno->roditelj = it->roditelj;
                    it->roditelj->lijevo = it->desno;
                    it->desno = 0;
                }

                it->roditelj = 0;

                Temp->kljuc = it->kljuc;
                Temp->element = it->element;

                brojEL --;
                return;
            }
            else if (it->desno)
            {
                it = it->desno;
                it->roditelj=Temp->roditelj;
            }
            else if (it->lijevo)
            {
                it = it->lijevo;
                it->roditelj= Temp->roditelj;
            }
            else
            {
                if(Temp->roditelj->lijevo == Temp)
                    Temp->roditelj->lijevo=0;
                else
                    Temp->roditelj->desno=0;

                delete Temp;
                brojEL --;
                return;
            }

            if(Temp->roditelj->lijevo == Temp)
                Temp->roditelj->lijevo=it;
            else
                Temp->roditelj->desno=it;

            delete Temp;
            brojEL--;
        }


    }

    BinStabloMapa(const BinStabloMapa &B)
    {
        Korijen=pomocnaAlociraj(B.Korijen);
        pomocnaKonstruktor(B.Korijen, Korijen);
        brojEL=B.brojEL;
    }
    BinStabloMapa &operator =(const BinStabloMapa &B)
    {
        if(&B != this)
        {
            if (brojEL)
                Brisi(Korijen);
            Korijen=pomocnaAlociraj(B.Korijen);
            pomocnaKonstruktor(B.Korijen, Korijen);

            brojEL=B.brojEL;
        }
        return *this;
    }




    bool operator<(const BinStabloMapa<Tip1, Tip2> b2)
    {

        Cvor<Tip1, Tip2>* Temp1=Maksimum(Korijen);
        Cvor<Tip1, Tip2>* Temp2=Minimum(b2.Korijen);
        if(Temp1->kljuc < Temp2->kljuc)
            return true;

        return false;
    }

    bool operator>(const BinStabloMapa<Tip1, Tip2> b2)
    {

        Cvor<Tip1, Tip2>* Temp1=Minimum(Korijen);
        Cvor<Tip1, Tip2>* Temp2=Maksimum(b2.Korijen);
        if(Temp1->kljuc > Temp2->kljuc)
            return true;

        return false;
    }


    BinStabloMapa (const Tip1 *nizKljuceva, const Tip2 *nizVrijednosti,  int vel)
    {
        Korijen=pomocnaKonstruktor1(nizKljuceva, nizVrijednosti, 0, vel-1);
        this->brojEL=vel;

    }

    Tip2 prviManji(Tip1 kljuc)
    {
       if(kljuc <= Minimum(Korijen)->kljuc) throw "nema finte";
       Cvor<Tip1, Tip2> * nadjeni;
       nadjeni=Trazi(Korijen,kljuc);//ispravljena funkciaj upotpunosti jer niej nikako radila dobro
       if(!nadjeni)
       {
           nadjeni=TraziPot(Korijen, kljuc);
             if(!nadjeni)
            throw "dfsgh";
       }
       else
       {
           if(nadjeni->lijevo) // ovo se uopste nije provjeravalo, odnosno jest, ali ako je nadjeni->Lijevo nullptr bacala sam izuzetak
            return Maksimum(nadjeni->lijevo)->element;
           else
           {
               while(nadjeni->roditelj->kljuc > kljuc)
                nadjeni=nadjeni->roditelj;
                 nadjeni= nadjeni->roditelj;    // a treba ovaj dodatni kod uraditi, jer stablo nije balansirano
                if(nadjeni==0) throw "nadfi";
           }

       }
       return nadjeni->element;
    }

    void pomocna(Tip1 a, Tip1 b, vector<Tip1> &v, Cvor<Tip1,Tip2> *c)
    {
        if(!c) return;
        if(c->kljuc < b) pomocna(a,b,v,c->desno);
        if(c->kljuc < b && c->kljuc > a) v.push_back(c->kljuc);
        if(c->kljuc > a) pomocna(a,b,v,c->lijevo);
    }
    vector <Tip1> od_doo(Tip1 a, Tip1 b)
    {
        vector<Tip1> v;
        Cvor<Tip1,Tip2>* c=Korijen;
        pomocna(a,b,v, c);
        return v;

    }

    template <typename Tip>
    friend void bin_stablo_sort(Tip*, int );
};
template <typename Tip1>
void inorder(int &i, Tip1* niz, Cvor<Tip1, int>* C)
{
    if(C)
    {
        inorder(i, niz, C->lijevo);
        niz[i++]=C->kljuc;
        inorder(i, niz, C->desno);
    }

}

template <typename Tip>
void bin_stablo_sort(Tip* niz, int vel)
{
    BinStabloMapa<Tip,int> b;
    for(int i=0; i<vel; i++)
    {
        b[niz[i]]=0;
    }
    int i=0;
    inorder(i,niz, b.Korijen);
}


int main()
{
    BinStabloMapa<int,int> b;
    b[15]=15;
    b[17]=17;
    b[13]=13;
    b[18]=18;
    b[10]=10;
    b[8]=8;

    vector<int> v=b.od_doo(8,17);
    for(int i = 0; i < v.size(); i ++)
        cout << v[i] << " ";
    return 0;
}