#include "Aarray.h"

template<class Data>
ANode<Data>* Aarray<Data>::find_min(ANode<Data> *top) {
    ANode<Data> *tmp=top;
    while (tmp->left) tmp=tmp->left;
    return tmp;
};


template<class Data>
Data Aarray<Data>::remove(const char *key) {
    return remove(key, root);
};

template<class Data>
Data Aarray<Data>::remove(const char *key, ANode<Data> * & T) {
    ANode<Data> *tmp_cell;

    if (T==NULL) return NULL;       // Element not in the tree.
    else if (key < T->index) return remove(key, T->left);
         else if (T->index < key) return remove(key, T->right);
              else                  // Remove this element!
              if ((T->left != NULL)&&(T->right != NULL)) {   //Two children
                  tmp_cell=find_min(T->right);
                  T->d=tmp_cell->d;
                  T->index=tmp_cell->index;
                  remove(T->index, T->right);
              }
              else {                                        //One/Zero kids
                  tmp_cell=T;
                  if (T->left==NULL)
                    T=T->right;
                  else if (T->right==NULL)
                         T=T->left;
                  delete tmp_cell;
              };
              cerr << "What the hell??!?!!?" << endl;
              assert(1==0);
              return tmp_cell->d;
};

template<class Data>
Aarray<Data>::~Aarray() {
    delete root;
    nodes=0;
};

template<class Data>
Aarray<Data>::Aarray() : root(NULL), nodes(0) {;};

template<class Data>
Aarray<Data>::Aarray(const Aarray<Data>& other) {
    nodes=other.nodes;
    copytree(root, other.root);
};

template <class Data>
Aarray<Data>& Aarray<Data>::operator=(const Aarray<Data>& other) {
    nodes=other.nodes;
    copytree(root, other.root);
    return *this;
};

template <class Data>
void Aarray<Data>::copytree(ANode<Data>*&dest, ANode<Data> *source) {
    ANode<Data> *tmp=source;
    if (!tmp) return;
    dest=new (ANode<Data>)(*source);
    copytree(dest->right, source->right);
    copytree(dest->left, source->left);
    return;
};

template<class Data>
Aarray<Data>::Aarray(const Data& data, const char* key) {
    root=new ANode<Data>;
    root->index=new char[strlen(key)];
    strcpy(root->index, key);
    root->d=data;
    root->left=root->right=NULL;
};

template<class Data>
unsigned int Aarray<Data>::elem(const char* key) {
    ANode<Data> *tmp=root;
    while (tmp) {
        if (!strcmp(key,tmp->index)) return 1;
        if (strcmp(key, tmp->index)>0) tmp=tmp->right;
        else tmp=tmp->left;
    };
    return 0;
};

template<class Data>
Data& Aarray<Data>::operator[](char* key) {
    ANode<Data> *tmp;

    if (!elem(key)) {
        tmp=new ANode<Data>;
        tmp->index=key;
        tmp->d=NULL;
        tmp->left=tmp->right=0;
        insert(tmp);
        return tmp->d;
    };
    tmp=root;
    while (tmp) {
        if (!strcmp(key,tmp->index)) return tmp->d;
        if (strcmp(key, tmp->index)>0) tmp=tmp->right;
        else tmp=tmp->left;
    };
    cerr << "Something *BAD* happened..." << endl;
    assert(1==0);
    return (tmp->d);
};

template<class Data>
void Aarray<Data>::insert(ANode<Data>* node) {
    int flag=1;
    if (elem(node->index)) {
        cerr << "No duplicates, please!" << endl;
        assert(1==0);
    };
    nodes++;
    ANode<Data> *tmp=root;
    if (!tmp) {
        root=node;
        return;
    };
    while ((tmp)&&flag) {
        if ((strcmp(node->index, tmp->index)>0)&&(tmp->right!=NULL)) {
            tmp=tmp->right; continue;}
        if ((strcmp(node->index, tmp->index)>0)&&(tmp->right==NULL)) {
            tmp->right=node;
            flag=0;
            continue;
        }
        if ((strcmp(node->index, tmp->index)<0)&&(tmp->left!=NULL)) {
            tmp=tmp->left; continue;}
        if ((strcmp(node->index, tmp->index)<0)&&(tmp->left==NULL)) {
            tmp->left=node;
            flag=0;
            continue;
        }
        return;
    };
};

template <class Data>
ostream& operator<<(ostream& ost, const Aarray<Data>& aarray) {
    ost << (const ANode<Data>*)aarray.root;
    return ost;
};

template <class Data>
Aarray<Data> operator+(Aarray<Data>& first, const Aarray<Data>& second) {
    Aarray<Data> combo(first);
    combo.merge(second.root);
    return combo;
};

template <class Data>
Aarray<Data>& operator+=(Aarray<Data>& first, const Aarray<Data>& other) {
    first=first+other;
    return first;
};


int main() {
    Aarray<double> PB;
    PB["Ami"]=20;
    PB["Tammy"]=40;
    PB["Guy"]=30;
    cout << PB;
    Aarray<double> PB2(34, "Shlomi");
    PB2+=PB;
    cout << PB2;
    return 0;
};