// sl-4-DHBW-Inf2
// avl binary search tree: insert, find, delete, fibo tree

#include <cstdlib>
#include <iostream>
#include "suchbaum.h"
#include "avlbaum.h"
#include "visualbinbaum.h"

using namespace std;

///////////////////////////////////////////////////////////////////////////////
void avl3PtrSwap(avlPtr &p1, avlPtr &p2, avlPtr &p3) {
///////////////////////////////////////////////////////////////////////////////
  avlPtr ph=p1; p1=p2; p2=p3; p3=ph;
}

///////////////////////////////////////////////////////////////////////////////
void avlRotate(avlPtr &root) {
///////////////////////////////////////////////////////////////////////////////
  // balance changed by another one, so ...
  if (root->balance==unbalancedright) { // height difference is two now
    if (root->right->balance==unbalancedright) {
      cout << "Left rotation @ " << root->value
           << "--" << root->right->value << endl;
      avl3PtrSwap(root,root->right,root->right->left);
      root->balance=balanced; root->left->balance=balanced;
      cout << "Nodes " << root->left->value << " and "
           << root->value << " are now balanced" << endl;
    } else if (root->right->balance==unbalancedleft) {
      cout << "Right+left rotation" << endl;
      cout << "Right rotation @ " << root->right->left->value
           << "--" << root->right->value << endl;
      avl3PtrSwap(root->right,root->right->left,root->right->left->right);
      cout << "Subtree after right rotation (balances will be corrected after the 2nd rotation):" << root;
      cout << "Left rotation @ " << root->value
           << "--" << root->right->value << endl;
      avl3PtrSwap(root,root->right,root->right->left);
      // new balanced depend on the former balance of the new root
      if (root->balance==unbalancedleft) {
        root->balance=balanced;
        root->left->balance=balanced;
        root->right->balance=unbalancedright;
        cout << "Nodes " << root->left->value << " and "
             << root->value << " are now balanced, node" 
             << root->right->value << " is unbalanced to the right" << endl;
      } else if (root->balance==balanced) {
        root->balance=balanced;
        root->left->balance=balanced;
        root->right->balance=balanced;
        cout << "Nodes " << root->left->value << ", " << root->value 
             << ", and " << root->right->value << " are now balanced" << endl;
      } else { // root->balance==unbalancedright
        root->balance=balanced;
        root->left->balance=unbalancedleft;
        root->right->balance=balanced;
        cout << "Node " << root->left->value << " is now unbalanced to the right, "
             << root->value << " and " << root->right->value
             << " are now balanced" << endl;
      }
    } else { // root->right->balance==balanced - can only happen during delete
      cout << "Left rotation @ " << root->value
           << "--" << root->right->value << endl;
      avl3PtrSwap(root,root->right,root->right->left);
      root->balance=unbalancedleft; root->left->balance=unbalancedright;
      cout << "Node " << root->left->value << " is now unbalanced to the right, and "
           << root->value << " is now unbalanced to the left" << endl;
    } // cases left and right+left rotation done
  } else { // root->balance==unbalancedleft // height difference is now -2
    if (root->left->balance==unbalancedleft) {
      cout << "Right rotation @ " << root->left->value
           << "--" << root->value << endl;
      avl3PtrSwap(root,root->left,root->left->right);
      root->balance=balanced; root->right->balance=balanced;
      cout << "Nodes " << root->value << " and "
           << root->right->value << " are now balanced" << endl;
    } else if (root->left->balance==unbalancedright) {
      cout << "Left+right rotation" << endl;
      cout << "Left rotation @ " << root->left->value
           << "--" << root->left->right->value << endl;
      avl3PtrSwap(root->left,root->left->right,root->left->right->left);
      cout << "Subtree after left rotation (balances will be corrected after the 2nd rotation):" << root;
      cout << "Right rotation @ " << root->left->value
           << "--" << root->value << endl;
      avl3PtrSwap(root,root->left,root->left->right);
      // new balanced depend on the former balance of the new root
      if (root->balance==unbalancedleft) {
        root->balance=balanced;
        root->left->balance=balanced;
        root->right->balance=unbalancedright;
        cout << "Nodes " << root->left->value << " and "
             << root->value << " are now balanced, node" 
             << root->right->value << " is unbalanced to the right" << endl;
      } else if (root->balance==balanced) {
        root->balance=balanced;
        root->left->balance=balanced;
        root->right->balance=balanced;
        cout << "Nodes " << root->left->value << ", " << root->value 
             << ", and " << root->right->value << " are now balanced" << endl;
      } else { // root->balance==unbalancedright
        root->balance=balanced;
        root->left->balance=unbalancedleft;
        root->right->balance=balanced;
        cout << "Node " << root->left->value << " is now unbalanced to the left, "
             << root->value << " and " << root->right->value
             << " are now balanced" << endl;
      }
    } else { // root->right->balance==balanced - can only happen during delete
      cout << "Right rotation @ " << root->left->value
           << "--" << root->value << endl;
      avl3PtrSwap(root,root->left,root->left->right);
      root->balance=unbalancedright; root->right->balance=unbalancedleft;
      cout << "Node " << root->value << " is now unbalanced to the right, and "
           << root->right->value << " is now unbalanced to the left" << endl;
    } // cases right and left+right rotation done
  }
}

///////////////////////////////////////////////////////////////////////////////
void avlInsertH(avlPtr & root, const DataType value, bool & higher) {
///////////////////////////////////////////////////////////////////////////////
  if (root==NULL) {
    root = new avlTree;
    root->value = value;
    root->left = root->right = 0;
    root->balance = balanced;
    higher=true;
  } else if (value<root->value) {
    avlInsertH(root->left,value,higher);
    if (higher) {
      if (root->balance==unbalancedleft) {
        cout << "Rotation necessary @ " << root->value << " -- subtree:" << root;
        avlRotate(root); higher=false;
        cout << "Tree is now avl again" << endl;
      } else if (root->balance==balanced) {
        root->balance=unbalancedleft; // higher is still true
        cout << "Node " << root->value << " is now unbalanced to the left" << endl;
      } else { // root->balance==unbalancedright
        root->balance=balanced; higher=false;
        cout << "Node " << root->value << " is now balanced" << endl;
      }
    }
  } else if (value>root->value) {
    avlInsertH(root->right,value,higher);
    if (higher) {
      if (root->balance==unbalancedleft) {
        root->balance=balanced; higher=false;
        cout << "Node " << root->value << " is now balanced" << endl;
      } else if (root->balance==balanced) {
        root->balance=unbalancedright; // higher is still true
        cout << "Node " << root->value << " is now unbalanced to the right" << endl;
      } else { // root->balance==unbalancedright
        cout << "Rotation necessary @ " << root->value << " -- subtree:" << root;
        avlRotate(root); higher=false;
        cout << "Tree is now avl again" << endl;
      }
    }
  } else { // it is ==
    cout << "Element " << value << " is already in the tree!" << endl;
  }
}

///////////////////////////////////////////////////////////////////////////////
void avlInsert(avlPtr & root, const DataType value) {
///////////////////////////////////////////////////////////////////////////////
  bool higher = false;
  avlInsertH(root,value,higher);
}

///////////////////////////////////////////////////////////////////////////////
bool avlFind(const avlPtr root, const DataType value) {
///////////////////////////////////////////////////////////////////////////////
  if (root==NULL) {
    return false;
  } else if (value<root->value) {
    return avlFind(root->left,value);
  } else if (value>root->value) {
    return avlFind(root->right,value);
  } else { // it is ==
    return true;
  }
}

///////////////////////////////////////////////////////////////////////////////
void avlDeleteH(avlPtr & root, const DataType value, bool & lower, bool & deleted) {
///////////////////////////////////////////////////////////////////////////////
  if (root==NULL) {
    cout << "Element " << value << " isn't in the tree!" << endl;
    lower=false;
    deleted=false; // no, the element was not in the tree
  } else if (value<root->value) {
    avlDeleteH(root->left,value,lower,deleted);
    if (lower) {
      if (root->balance==unbalancedleft) {
        root->balance=balanced;
        cout << "Node " << root->value << " is now balanced" << endl;
        // lower is still true
      } else if (root->balance==balanced) {
        root->balance=unbalancedright;
        lower=false;
        cout << "Node " << root->value << " is now unbalanced to the right" << endl;
      } else { // root->balance==unbalancedright
        if (root->right->balance==balanced) {
          lower=false;
        } // else { // lower is still true after rotation
        cout << "Rotation necessary @ " << root->value << " -- subtree:" << root;
        avlRotate(root);
      }
    }      
  } else if (value>root->value) {
    avlDeleteH(root->right,value,lower,deleted);
    if (lower) {
      if (root->balance==unbalancedleft) {
        if (root->left->balance==balanced) {
          lower=false;
        } // else { // lower is still true after rotation
        cout << "Rotation necessary @ " << root->value << " -- subtree:" << root;
        avlRotate(root);
      } else if (root->balance==balanced) {
        root->balance=unbalancedleft;
        lower=false;
        cout << "Node " << root->value << " is now unbalanced to the left" << endl;
      } else { // root->balance==unbalancedright
        root->balance=balanced;
        cout << "Node " << root->value << " is now balanced" << endl;
        // lower is still true
      }
    }      
  } else { // it is ==
    cout << "Element " << value << " is in the tree, I'll delete it!" << endl;
    if (root->left==NULL && root->right==NULL) {
      // it's a leaf => delete it
      delete root;
      root=NULL;
      lower=true; // balances will change on path to root
    } else if (root->left==NULL) {
      // right subtree must be non-empty, delete root and shift subtree up
      avlPtr tbd=root;
      root=root->right; // subtree has just one node, and it's balanced
      delete tbd;
      lower=true; // balances will change on path to root
    } else if (root->right==NULL) {
      // left subtree must be non-empty, delete root and shift subtree up
      avlPtr tbd=root;
      root=root->left; // subtree has just one node, and it's balanced
      delete tbd;
      lower=true; // balances will change on path to root
    } else { // both subtrees are non-empty => find inorder successor s,
      // copy it's value to root, and delete the value in the right subtree
      // note: recursion impossible, inorder successor has 1 child or none
      avlPtr iosucc=root->right; // is not NULL
      while (iosucc->left!=NULL) {
        iosucc=iosucc->left;
      }
      root->value=iosucc->value;
      cout << "Copy value of inorder successor " << iosucc->value 
           << " into the node " << value << ", and delete the original "
           << iosucc->value << " in the right subtree" << endl;
      avlDeleteH(root->right,iosucc->value,lower,deleted);
      // this way, subtree was traversed twice (and maybe copying the value
      // is expensive in case it's a huge struct), but traversing twice
      // isn't much difference compared to having root's value at hand during
      // recursion (and we'd have to implement another delete routine,
      // because we don't know inorder successor's value in advance)
      // only drawback: if there are other pointers to avl tree's nodes
      // those pointers will point to the wrong node (due to copying the value)
      if (lower) { // copied from above avlDeleteH(root->right,...
        if (root->balance==unbalancedleft) {
          if (root->left->balance==balanced) {
            lower=false;
          } // else { // lower is still true after rotation
          cout << "Rotation necessary @ " << root->value << " -- subtree:" << root;
          avlRotate(root);
        } else if (root->balance==balanced) {
          root->balance=unbalancedleft;
          lower=false;
          cout << "Node " << root->value << " is now unbalanced to the left" << endl;
        } else { // root->balance==unbalancedright
          root->balance=balanced;
          cout << "Node " << root->value << " is now balanced" << endl;
          // lower is still true
        }
      }
    }
    deleted=true; // yes, we deleted an element
  }
}

///////////////////////////////////////////////////////////////////////////////
bool avlDelete(avlPtr & root, const DataType value) {
///////////////////////////////////////////////////////////////////////////////
  bool lower = false; bool deleted = false;
  avlDeleteH(root,value,lower,deleted);
  return deleted;
}

///////////////////////////////////////////////////////////////////////////////
void delTree(const avlPtr root) {
///////////////////////////////////////////////////////////////////////////////
  if (root!=NULL) {
    delTree(root->left);
    delTree(root->right);
    delete root;
  }
}

///////////////////////////////////////////////////////////////////////////////
bstPtr avl2bst(const avlPtr root) {
///////////////////////////////////////////////////////////////////////////////
  if (root==NULL) {
    return NULL;
  } else {
    bstPtr cp = new bsTree(root->value,avl2bst(root->left),avl2bst(root->right));
    //    cp->value=root->value;
    //    cp->left=avl2bst(root->left);
    //    cp->right=avl2bst(root->right);
    return cp;
  }
}

///////////////////////////////////////////////////////////////////////////////
bstPtr avlbal2bst(const avlPtr root) {
///////////////////////////////////////////////////////////////////////////////
  if (root==NULL) {
    return NULL;
  } else {
    bstPtr cp = new bsTree(root->balance-1,avlbal2bst(root->left),avlbal2bst(root->right));
    //    cp->value=root->balance-1;
    //    cp->left=avlbal2bst(root->left);
    //    cp->right=avlbal2bst(root->right);
    return cp;
  }
}

///////////////////////////////////////////////////////////////////////////////
void avlInsertFiboOfHeight(avlPtr & root, const int height) {                //
// inserts elements of a fibonacci tree of <height>, <root> will be emptied  //
///////////////////////////////////////////////////////////////////////////////
  delTree(root);
  if (height>1) {
    int *fibo=new int[height+1]; fibo[0]=1; fibo[1]=1;
    // = root's value on level [.] // fibo[0]=1 only needed 10 lines below ...
    for(int i=2; i<=height; i++) { fibo[i]=fibo[i-1]+fibo[i-2]; }
    // recursive insertion isn't possible (due to induced rotations), use queue
    const int nrOfNodesInFiboTree = fibo[height]+fibo[height-1]-1;
    int *fiborder=new int[nrOfNodesInFiboTree]; // order of nodes to be inserted
    int *fibheight=new int[nrOfNodesInFiboTree]; // heights of fibo trees in above order
    int front,next; // "queue" index - this pseudo queue is good enough
    // in a fibo tree root and it's left descendants are fibo nums (1,2,3,5,..)
    // left subtree's root has value -fibnr[height-2], right +fibnr[height-2]
    // we can calculate the heights, values and insert them in parallel
    fibheight[0]=height;
    fiborder[0]=fibo[height];
    avlInsert(root,fiborder[0]);
    front=0; next=1;
    while (next<nrOfNodesInFiboTree) {
      // insert "subtrees" of height .-1 and .-2
      if (fibheight[front]>1) { // left subtree exists
        fibheight[next]=fibheight[front]-1;
        fiborder[next]=fiborder[front]-fibo[fibheight[front]-2]; // fibo[0] needed
        avlInsert(root,fiborder[next]);
        next++;
      }
      if (fibheight[front]>2) { // right subtree exists
        fibheight[next]=fibheight[front]-2;
        fiborder[next]=fiborder[front]+fibo[fibheight[next]]; // +f[h[front]-2]
        avlInsert(root,fiborder[next]);
        next++;
      }
      front++;
    }
    delete fibo; delete fiborder; delete fibheight;
  } else if (height==1) {
    root=new avlTree; root->value=1;
    root->left=root->right=NULL;
    root->balance=balanced;
  } // else height<1, root=NULL
}