#include "bintree.h"
//Function: clear()
//Use: Clears all of the nodes out of the tree and resets it to be
//     an empty tree. Memory used for all of the nodes of the tree must
//     be properly returned to the system.
//Args:
//Returns:
//Notes: calls zkill
template <class T>
void BinTree<T>::clear(void)
{
   if(this->root!=0)
   {
      zkill(this->root);
      this->root=0;
   }
}

//Function: insert(T)
//Use: Takes a value value and inserts it into the tree such that
//     the tree remains a binary search tree.
//Args: value to be inserted
//Returns: DUPLICATE if match is found, otherwise OK
//Notes:
template <class T>
int BinTree<T>::insert(T value)
{
   BinNode<T>* finger=this->root;
   if(finger==0)
   {
      finger=new BinNode<T>(value);
      this->root=finger;
      return 0;
   }
   while(1)//breakable
   {
      if(finger->value==value)
         return DUP_VAL;
      if(value<finger->value)
      {
         if(finger->left!=0)
            finger=finger->left;
         else
         {
            finger->left=new BinNode<T>(value);
            return 0;
         }
      }
      else// strictly greater than
      {
         if(finger->right!=0)
            finger=finger->right;
         else
         {
            finger->right=new BinNode<T>(value);
            return 0;
         }
      }
   }
}

//remove() removes from the binary tree the value specified in target.
//returns OK if the node is successfully killed, and NOT_FOUND if the target ditched town.
template <class T>
int BinTree<T>::remove(T target)
{
   //remove head
   if(this->root->value==target)
   {
      if(this->root->left!=NULL) //if a left child exists
      {
         BinNode<T>* killme=this->root->left;
         if(killme->right==NULL)
         {
            this->root->value=killme->value;
            this->root->left=killme->left;
            delete killme;
         }
         else
         {
            while(killme->right->right!=NULL) //move to next to last right child (highest value)
               killme=killme->right;
            this->root->value=killme->right->value; //move junk to root

            BinNode<T>* killmeinstead=killme->right; //temp holder ptr
            killme->right=killme->right->left; //pick up possible subtree
            delete killmeinstead;
         }
      }
      else//only a right child, GET ON UP GET ON UP
      {
         BinNode<T>* killme=this->root;
         this->root=this->root->right;
         delete killme;
      }
   }
   else   //remove a node in the body
   {
      BinNode<T>* sentinel=this->root;
      BinNode<T>* lastsentinel=NULL; //keeps track of sentinel<-parent
      bool lastmoveleft=true; //keeps track of which child the parent is disowning

      while(!(sentinel->value==target))
      {
         lastsentinel=sentinel; //set up trace back to sentinel<-parent

         lastmoveleft=true; //moving left, eh?
         if(sentinel->value<target)
         {
            sentinel=sentinel->right; //move higher
            lastmoveleft=false; //okay I lied, it was right
         }
         else
            sentinel=sentinel->left; //move lower

         if(sentinel==NULL)
            return -3;  //you fall into abyss, game over
      }

      //lastsentinel is the parent of sentinel, address of the node to be deleted

      if(sentinel->left==NULL && sentinel->right==NULL) //no children
      {
         if(lastmoveleft) lastsentinel->left=NULL;
         else             lastsentinel->right=NULL;
         delete sentinel;
      }
      else if(sentinel->left!=NULL && sentinel->right==NULL) //left child only
      {
         if(lastmoveleft) lastsentinel->left =lastsentinel->left ->left;
         else             lastsentinel->right=lastsentinel->right->left;
         delete sentinel;
      }
      else if(sentinel->left==NULL && sentinel->right!=NULL) //right child only
      {
         if(lastmoveleft) lastsentinel->left =lastsentinel->left ->right;
         else             lastsentinel->right=lastsentinel->right->right;
         delete sentinel;
      }
      else //sentinel has a left and a right child, you're really screwed now
      {
         BinNode<T>* nextofkin=sentinel->left;
         while(nextofkin->right!=NULL)
            nextofkin=nextofkin->right;
         nextofkin->right=sentinel->right;
         if(lastmoveleft) lastsentinel->left=sentinel->left;
         else             lastsentinel->right=sentinel->left;
         delete sentinel;
      }
   }
   return 0;
}

//recursive version of print_pre
//Notes: actual worthwhile implementation of output
template <class T>
void BinTree<T>::zrint_pre(const BinNode<T>* finger) const
{
   if(finger!=0)
   {
      //cout<<finger->value<<" ";
      zrint_pre(finger->left);
      zrint_pre(finger->right);
   }
}

//recursive version of print_in
//Notes: actual worthwhile implementation of output

template <class T>
void BinTree<T>::zrint_in(const BinNode<T>* finger) const
{
   if(finger!=0)
   {
      zrint_in(finger->left);
      cout<<finger->value.title<<" "<<finger->value.mode<<endl;
      zrint_in(finger->right);
   }
}

//recursive version of print_post
//Notes: actual worthwhile implementation of output

template <class T>
void BinTree<T>::zrint_post(const BinNode<T>* finger) const
{
   if(finger!=0)
   {
      zrint_pre(finger->left);
      zrint_pre(finger->right);
      //cout<<finger->value<<" ";
   }
}

template <class T>
int BinTree<T>::w_find(const T &target)
{
   BinNode<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?
}

//Function: ~BinTree
//Use: destructor
//Args:
//Returns:
//Notes: calls zkill, which recursively deletes all the znodes or something

template <class T>
BinTree<T>::~BinTree()
{
   if(this->root!=0)
   {
      zkill(this->root);
      this->root=0;
   }
}

//USER ADDED FUNCTIONS

//Function: zcopy
//Use: makes a clone of tree in memory
//Args: pointer to head of target tree
//Returns: pointer to head of tree
//Notes: called by copy constructor and operator=

template <class T>
BinNode<T>* BinTree<T>::zcopy(const BinNode<T>* head) const
{
   BinNode<T>* cacheP=new BinNode<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
}

//Function: zkill
//Use: deletes subtrees, followed by self
//Args: pointer to head of target tree
//Returns:
//Notes: called by destructor

template <class T>
void BinTree<T>::zkill(BinNode<T>* head)
{
   if(head->left!=0)
      zkill(head->left);
   if(head->right!=0)
      zkill(head->right);
   delete head;
}

//Function: zclimb
//Use: recursive function for counting up height of tree
//Args: pointer to head of target tree
//Returns: height of longest branch
//Notes:

template <class T>
int BinTree<T>::zclimb(const BinNode<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;
}

//Function: zsize
//Use: recursive function for counting up nodes in tree
//Args: pointer to head of target tree
//Returns: total node count from here below
//Notes:

template <class T>
int BinTree<T>::zsize(const BinNode<T>* finger) const
{
   if(finger==0)
      return 0;
   return(1+zsize(finger->left)+zsize(finger->right));
}

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

}

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

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

   return bin_iter_count;
}