/*
 avl.cpp

 Support for AVL tree manipulation.
 Currently implemented are AVLInsert and various support
 routines, such as printTreeShape, which does a pretty-print
 of a binary search tree.

 Not implemented: AVLDelete (exercise for students).

  Oct 30, 1999.

 S. Tanimoto
*/

#include <stdio.h>
#include "avl.h"

#define INDENT 5
#define TELL(msg) if(debug == 1) {printf(#msg "\n"); }
#define debug 0


// Here are the implementations of the accessor functions,
// which retrieve or set member variables of an AVLNode instance.

int AVLNode::getBalance() {
  return balance;
}

void AVLNode::setBalance(int theBalance) {
  balance = theBalance;
}

int AVLNode::getKey() {
  return key;
}

void AVLNode::setKey(int theKey) {
  key = theKey;
}

char *AVLNode::getInfo() {
  return info;
}

void AVLNode::setInfo(char *theInfo) {
  info = theInfo;
}

// Here are some useful printing routines.

void AVLNode::printInOrder() {
  // Do an inOrder traversal and print out the info at
  // each node.
  if (LC != NULL) { LC->printInOrder(); }
  printf(" %d -- %s\n", key, info);
  if (RC != NULL) { RC->printInOrder(); }
}

void AVLNode::printTreeShape1(int depth) {
  // Pretty-print the tree with indentation according to depth.
  if (RC != NULL) { RC->printTreeShape1(depth + 1); }
  for (int i=0; i< INDENT * depth; i++) { printf(" "); }
  printf("%2d (%d)\n", key, balance);
  if (LC != NULL) { LC->printTreeShape1(depth + 1); }
}

void AVLNode::printTreeShape() {
  // Print the tree starting at depth 0.
  printTreeShape1(0);
}

AVLNode *AVLNode::find(int theKey) {
  // Traditional FIND operation, returning a pointer
  // to the node where the key is found, or NULL if
  // the key is not found in the tree.
  if (theKey == key) { printf("Found it.\n"); return this;}
  if (theKey < key) {
    if (LC == NULL) { return NULL;} else { return LC->find(theKey); }
  }
  if (theKey > key) {
    if (RC == NULL) { return NULL;} else { return RC->find(theKey); }
  }
  return NULL;
}

// Here is a variation of FIND, which solves the "locative" problem.
// It requires that we pass in another arg -- myParent, which is
// the parent of the node we are calling with.
// Before it returns a pointer to the node where the key is found,
// it writes a pointer to the found node's parent at the location
// specified by foundParent.

AVLNode *AVLNode::findNodeAndParent(int theKey, AVLNode *myParent, AVLNode **foundParent) {
  TELL(Entering findNodeAndParent)
  *foundParent = myParent;
  if (theKey == key) { 
    TELL(Found it)
    return this;
  }
  if (theKey < key) {
    if (LC == NULL) {
      *foundParent = this;
      return NULL;
    }
    else {
      return LC->findNodeAndParent(theKey, this, foundParent);
    }
  }
  if (theKey > key) {
    if (RC == NULL) {
      *foundParent = this;
      return NULL;
    }
    else {
      return RC->findNodeAndParent(theKey, this, foundParent);
    }
  }
  return NULL;
}

void AVLNode::BSTInsert(int theKey, char *theInfo) {
  // Inserts a new node into a Binary Search Tree.
  // This version does no rebalancing, and is not really
  // an essential part of the AVL tree implementation.
  // It's here for comparison purposes.
  TELL(Entering BSTInsert)
  AVLNode *P;
  AVLNode *L = findNodeAndParent(theKey, this, &P);
  if (L != NULL)  printf("L's value is %d and its parent has value %d.\n",
    L->getKey(), P->getKey());
  //AVLNode *L = find(theKey);
  if (L != NULL) return;
  AVLNode *N = new AVLNode(theKey, theInfo);
  if (theKey < P->getKey()) P->LC = N;
  if (theKey > P->getKey()) P->RC = N;
  TELL(Leaving BSTInsert)
}

int AVLNode::AVLInsert(int theKey, char *theInfo, AVLNode **parentsChildPointer) {
  // This is the AVL tree insertion method.
  // Returns 1 if the height increases, 0 otherwise.
  // It performs any rebalancing that is necessary.

  // First, find the location for the (new?) key
  // in a manner similar to that of find.
  TELL(Entering AVLInsert)
  if (theKey == key) { printf("Key is already in the tree.\n"); return 0;}
  int deltah; // represents amount of height change to subtree.
  if (theKey < key) {
    if (LC == NULL) {
      /* Insert node here, adjust balance, and return 1 if height changed*/
      LC = new AVLNode(theKey, theInfo);
      if (balance == 0) { balance = -1; return 1; } // was leaf, now left-heavy
      else { balance = 0; return 0; } // was right-heavy, now balanced.
    }
    else {
      deltah = LC->AVLInsert(theKey, theInfo, &LC);
      // check balance and do possible rebalancing with right-rotate here.
      if (deltah == 0) return 0;
      if (balance == -1) {
        rotateRight(parentsChildPointer);
        balance = 0;
        return 0;
       }
      if (balance == 0) {
        balance = -1; 
        return 1;
      }
      if (balance == 1) {
        balance = 0;
        return 0;
      }
    }
  }
  if (theKey > key) {
    if (RC == NULL) {
      /* Insert node here, adjust balance, and return 1 if height changed*/
      RC = new AVLNode(theKey, theInfo);
      if (balance == 0) { balance = 1; return 1; } // was leaf, now right-heavy
      else { balance = 0; return 0; } // was left-heavy, now balanced.
    }
    else {
      deltah = RC->AVLInsert(theKey, theInfo, &RC);
      // check balance and do possible rebalancing with left-rotate here.
      if (deltah == 0) return 0;
      if (balance == -1) {
        balance = 0;
        return 0;
       }
      if (balance == 0) {
        balance = 1; 
        return 1;
      }
      if (balance == 1) {
        rotateLeft(parentsChildPointer);
        balance = 0;
        return 0;
      }
    }
  }
  return 0;
}

// Not yet implemented...
void AVLNode::AVLDelete(int theKey) {
  int i = 1;
}

AVLNode *AVLNode::inOrderSuccessorForAVLDelete(AVLNode **foundParent) {
  // Finds the in-order successor of a node in a BST, but makes
  // the assumption that this node in fact has a right child.
  // This function handles the locative
  // problem for use in implementing AVLDelete.
  AVLNode *Q = RC; // Move to right child.
  *foundParent = this;
  while (Q->LC != NULL) { // keep moving to left child
    *foundParent = Q;  // parent will be needed to link assignment.
    Q = Q->LC;
  }
  return Q;
}

void AVLNode::rotateLeft(AVLNode **parentsChildPointer) {
  // Figures out what kind of left rotation is necessary,
  // then performs it.
  // If right child is left-heavy, then perform a
  // RightLeft double rotation.
  if (RC!= NULL & RC->getBalance() == -1) {
    doubleRotateRightLeft(parentsChildPointer);
  }
  else {
    singleRotateLeft(parentsChildPointer);
  }
}

void AVLNode::rotateRight(AVLNode **parentsChildPointer) {
  // Figures out what kind of right rotation is necessary,
  // and then performs it.
  // If left child is right-heavy, then perform a
  // LeftRight double rotation.
  if (LC != NULL & LC->getBalance() == 1) {
    doubleRotateLeftRight(parentsChildPointer);
  }
  else {
    singleRotateRight(parentsChildPointer);
  }
}

void AVLNode::singleRotateLeft(AVLNode **parentsChildPointer) {
  TELL(Entering SingleRotateLeft)
  AVLNode *B = RC;
  //  AVLNode *X = LC;
  AVLNode *Y = B->LC;
  //  AVLNode *Z = B->RC;
  //  LC = X;
  RC = Y;
  B->LC = this;
  //  B->RC = Z;
  balance = 0;
  B->setBalance(0);
  *parentsChildPointer = B;
  TELL(Leaving SingleRotateLeft)
}

void AVLNode::singleRotateRight(AVLNode **parentsChildPointer) {
  TELL(Entering SingleRotateRight)
  AVLNode *A = LC;
  //  AVLNode *X = A->LC;
  AVLNode *Y = A->RC;
  //  AVLNode *Z = RC;
  //  A->LC = X;
  LC = Y;
  A->RC = this;
  balance = 0;
  A->setBalance(0);
  *parentsChildPointer = A;
  TELL(Leaving SingleRotateRight)
}

void AVLNode::doubleRotateLeftRight(AVLNode **parentsChildPointer) {
  TELL(Entering doubleRotateLeftRight)
  LC->singleRotateLeft(&LC);
  singleRotateRight(parentsChildPointer);
  TELL(Leaving doubleRotateLeftRight)
}

void AVLNode::doubleRotateRightLeft(AVLNode **parentsChildPointer) {
  TELL(Entering doubleRotateRightLeft)
  RC->singleRotateRight(&RC);
  singleRotateLeft(parentsChildPointer);
  TELL(Leaving doubleRotateRightLeft)
}

int main() {
  printf("Beginning AVL Tree test.\n");

  AVLNode *T = new AVLNode(35, "The root, right?");
  T->printTreeShape();

#define N 10

  for (int i = 0; i < N; i++) {
    T->AVLInsert(i, "a node", &T);
    printf("Here's the tree after inserting %d:\n", i);
    T->printTreeShape();
  }

  /*
  printf("At checkpoint 1.\n");
  T->AVLInsert(10, "ten", &T);
  T->printTreeShape();
  printf("At checkpoint 2.\n");
  T->AVLInsert(50, "fifty", &T);
  T->printTreeShape();
  printf("At checkpoint 3.\n");
  T->AVLInsert(13, "thirteen", &T);
  T->printTreeShape();
  printf("At checkpoint 4.\n");
  T->AVLInsert(11, "thirteen", &T);
  T->printTreeShape();
  printf("At checkpoint 5.\n");
  */
  return 0;
}