#include "avltree.h"
template <class T>
int avlnode<T>::zheight(avlnode<T>* limb)
{
   if(limb==NULL)
      return 0;
   int leftside=1+zheight(limb->left);
   int rightside=1+zheight(limb->right);
   if(leftside>rightside)
      return leftside;
   return rightside;
}

template <class T>
int avltree<T>::avlinsert(avlnode<T>* &p, const T &x, avlnode<T>** parent)
{
   if(p==NULL)                                  //only applies when p is passed
   {                                            //NULL to begin with. other
      p=new avlnode<T>(x);                      //statements catch successive nulls
      this->root=p;
      return OK;
   }
   if(p->value==x)                              //duplicate value found
      return DUP_VAL;
   if(p->value>x)                               //move LOW
   {
      if(p->left==NULL)                         //LOW is free space
      {
         p->left=new avlnode<T>(x);             //conquer it and return to homeland
         return OK;                             //since its balance will be 0
      }                                         //and parent's cannot be +/-2
      else
      {
         int ret=avlinsert(p->left,x,&(p->left));        //otherwise, simply make child do work

         int bias=p->right->height()-p->left->height();      //this recursion ensures that balance is
         if(bias==0-2) //left-heavy                      //maintained back on up the tree
         {
            int subbias=p->left->right->height()-p->left->left->height();
            if(subbias==0-1) rotateleftsingle(p,parent);
            if(subbias==0+1) rotateleftdouble(p,parent);
         }
         return ret;
      }
   }
   if(p->value<x)                               //move HIGH
   {
      if(p->right==NULL)                        //HIGH is free space
      {
         p->right=new avlnode<T>(x);            //conquer it and return to homeland
         return OK;                             //since its balance will be 0
      }                                         //and parent's cannot be +/-2
      else
      {
         int ret=avlinsert(p->right,x,&(p->right));      //otherwise, simple make child do work

         int bias=p->right->height()-p->left->height();      //this recursion ensudes that balance is
         if(bias==0+2) //right-heavy                     //maintained back on up the tree
         {
            int subbias=p->right->right->height()-p->right->left->height();
            if(subbias==0+1) rotaterightsingle(p,parent);
            if(subbias==0-1) rotaterightdouble(p,parent);
         }
         return ret;
      }
   }
   return 573;                                  //UUDDLRLRBAS -- program should never get here
}

//assertions: w contains the address of the pointer that points to p.
// p -> [INSTANCE.OF.BSNODE]
// p == mp
// w ---[-----------> mp --]---->[SAME.INSTANCE]

template <class T>
void avltree<T>::rotateleftsingle(avlnode<T>* &p, avlnode<T>** &w)
{
   avlnode<T>* A=p;                                 //storage for swapping
   avlnode<T>* B=p->left;
   avlnode<T>* C=p->left->right;
   *w=B;                                        //now adjust links
   A->left=C;
   B->right=A;
}
template <class T>
void avltree<T>::rotaterightsingle(avlnode<T>* &p, avlnode<T>** &w)
{
   avlnode<T>* A=p;                                 //storage for swapping
   avlnode<T>* B=p->right;
   avlnode<T>* C=p->right->left;
   *w=B;                                        //now adjust links
   A->right=C;
   B->left=A;
}
template <class T>
void avltree<T>::rotateleftdouble(avlnode<T>* &p, avlnode<T>** &w)
{
   avlnode<T>* A=p;                                 //sweet jesus
   avlnode<T>* B=p->left;
   avlnode<T>* C=p->left->right;
   avlnode<T>* D=p->left->right->right;
   avlnode<T>* E=p->left->right->left;
   *w=C;                                        //adjust links
   A->left=D;
   B->right=E;
   C->right=A;
   C->left=B;
}
template <class T>
void avltree<T>::rotaterightdouble(avlnode<T>* &p, avlnode<T>** &w)
{
   avlnode<T>* A=p;                                 //sweet jesus
   avlnode<T>* B=p->right;
   avlnode<T>* C=p->right->left;
   avlnode<T>* D=p->right->left->left;
   avlnode<T>* E=p->right->left->right;
   *w=C;                                        //adjust links
   A->right=D;
   B->left=E;
   C->left=A;
   C->right=B;
}

template <class T>
int avltree<T>::w_find(const T &target)
{
   avlnode<T>* sentinel=root;

   if(root==NULL)                               //prevent against segfault
      return 0;

   int compare_count=1;                         //if you hit root, return as 1
   while(1-(sentinel->value==target))           //otherwise traverse down and then increment
   {
      if(sentinel->value<target)
         sentinel=sentinel->right;
      else
         sentinel=sentinel->left;

      if(sentinel==NULL)                        //protect against idiocy
      {
         cout<<"can't find target "<<target.title<<" "<<target.mode<<" "<<target.djname<<endl;
         break;
      }

      compare_count++;                          //increment and check again
   }
   //now *sentinel==target

   return compare_count;                        //how long did it take to find?
}

template <class T>
avlnode<T>* avltree<T>::zcopy(const avlnode<T>* head) const
{
   avlnode<T>* cacheP=new avlnode<T>(head->value);//make new corresponding node

   if(head->left!=0)
      cacheP->left=zcopy(head->left);
   if(head->right!=0)
      cacheP->right=zcopy(head->right);

   return cacheP;//return passed value, unchanged
}

template <class T>
int avltree<T>::zclimb(const avlnode<T>* limb) const
{
   if(limb==0)
      return 0;
   int leftside=1+zclimb(limb->left);
   int rightside=1+zclimb(limb->right);
   if(leftside>rightside)
      return leftside;
   return rightside;
}

template <class T>
int avltree<T>::zsize(const avlnode<T>* here) const
{
   if(here==NULL)
      return 0;
   return 1+zsize(here->left)+zsize(here->right);
}

template <class T>
void avltree<T>::build(const usermaster &allusers)
{
   for(entry* here=allusers.userlist[0].head; here!=NULL; here=here->nextsong_full)
      insert(*here);
}

template <class T>
int avltree<T>::itercount(const usermaster &allusers)
{
   int avl_iter_count=0;

   for(entry* here=allusers.userlist[0].head; here!=NULL; here=here->nextsong_full)
      avl_iter_count+=w_find(*here);

   return avl_iter_count;
}