// sl-4-DHBW-inf2
// visualize binary search trees and avl binary search trees

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

using namespace std;

//////////////////////////////////////////////////////////////////////////////
struct extBsTree; // Binbaum mit Zusatzinfos
typedef extBsTree * extBstPtr;
struct extBsTree {
  DataType value;        // Kopie
  extBstPtr left, right; // "Kopie"
  int inordernr;         // Position in sortierter Rhf
  bool isleft;           // Flag, ob es ein linkes Kind ist
};
//////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////
extBstPtr cpBsTree(const bstPtr root, const bool isleft, int & inordernr) {
//////////////////////////////////////////////////////////////////////////////
  // Kopiert den Baum und berechnet Abstand vom linken Rand
  extBstPtr cproot, cpleft;
  if (root==NULL) {
    return NULL;
  } else {
    cpleft=cpBsTree(root->left,true,inordernr);
    inordernr++;
    cproot= new extBsTree;
    cproot->value=root->value;
    cproot->left=cpleft;
    cproot->inordernr = inordernr;
    cproot->isleft=isleft;
    cproot->right=cpBsTree(root->right,false,inordernr);
    return cproot;
  }
}

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

///////////////////////////////////////////////////////////////////////////////
DataType MaxExtBsTree(const extBstPtr root) {
///////////////////////////////////////////////////////////////////////////////
  // root mustn't be NULL
  if (root->right==NULL) {
    return root->value;
  } else {
    return MaxExtBsTree(root->right);
  }
}

///////////////////////////////////////////////////////////////////////////////
struct extBstList; // will be used as mixed list and ring list
typedef extBstList * extBstLPtr;
struct extBstList { // für Levelorderausgabe
  extBstPtr node;
  extBstLPtr next;
};
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
void removeFirst (extBstLPtr & l, extBstPtr & node) {
///////////////////////////////////////////////////////////////////////////////
  // l mustn't be empty
  extBstLPtr tbd = l;
  node = l->node;
  l = l->next;
  delete tbd;
}

///////////////////////////////////////////////////////////////////////////////
void getListOfSuccessors(const extBstLPtr oldlist, extBstLPtr & newlist) {
///////////////////////////////////////////////////////////////////////////////
  // recursion! at the end newlist must point to the first new item in that list
  // if no new item was added, newlist must be used unchanged in the next call
  if (oldlist!=NULL) {
    if (oldlist->node->left!=NULL) {
      newlist = new extBstList;
      newlist->node = oldlist->node->left;
      newlist->next = NULL;
      if (oldlist->node->right!=NULL) {
        newlist->next = new extBstList;
        newlist->next->node = oldlist->node->right;
        newlist->next->next = NULL;
        getListOfSuccessors(oldlist->next,newlist->next->next);
      } else {
        getListOfSuccessors(oldlist->next,newlist->next);
      }
    } else {
      if (oldlist->node->right!=NULL) {
        newlist = new extBstList;
        newlist->node = oldlist->node->right;
        newlist->next = NULL;
        getListOfSuccessors(oldlist->next,newlist->next);
      } else {
        getListOfSuccessors(oldlist->next,newlist);
      }
    }
  } // else { // no more elements in oldlist
}

///////////////////////////////////////////////////////////////////////////////
void mput(ostream& os, char bst, int times) {
///////////////////////////////////////////////////////////////////////////////
  for(int i=0;i<times;i++) os << bst;
}


///////////////////////////////////////////////////////////////////////////////
ostream& operator << (ostream& os, const bstPtr root) {
///////////////////////////////////////////////////////////////////////////////
  // to be used for "cout << tree;" or "cerr << tree;"
  if (root==NULL) { os << "tree is empty!" << endl; return os; }

  extBstLPtr thisLevelList = NULL; // root of list
  extBstLPtr nextLevelList = NULL;  
  extBstLPtr nextLevelNode = NULL; // current ptr to list
  extBstPtr thisNode = NULL;
  extBstPtr nextNode = NULL;

  int lastOffset = 0;
  int nrOfElements = 0;

  os << endl;

  // initialize List with (copied) root as the only top level node
  thisLevelList = new extBstList;
  thisLevelList->node = cpBsTree(root,false,nrOfElements);
  extBstPtr tbd=thisLevelList->node; // zur Speicherfreigabe am Ende
  thisLevelList->next = NULL;

  while (thisLevelList!=NULL) { // es gibt noch ein Level zum Ausgeben
    // nächstes Level bestimmen
    getListOfSuccessors(thisLevelList,nextLevelList);
    // unter Berücksichtigung des nächsten Levels das aktuelle ausgeben
    lastOffset=0; nextLevelNode=nextLevelList;
    while (thisLevelList!=NULL) {
      removeFirst(thisLevelList,thisNode);
      if (thisNode->left!=NULL) {
        nextNode=nextLevelNode->node; nextLevelNode=nextLevelNode->next;
        mput(os,' ',4*(nextNode->inordernr-lastOffset-1)+3);
        mput(os,'_',1+4*(thisNode->inordernr-nextNode->inordernr-1));
      } else {
        mput(os,' ',4*(thisNode->inordernr-lastOffset-1));
      }
      os << '('; if (thisNode->value<10 && thisNode->value>=0) { os << ' '; }
      os << thisNode->value << ')';
      lastOffset=thisNode->inordernr;
      if (thisNode->right!=NULL) {
        nextNode=nextLevelNode->node; nextLevelNode=nextLevelNode->next;
        mput(os,'_',4*(nextNode->inordernr-lastOffset-1)+1);
        mput(os,' ',3); lastOffset=nextNode->inordernr;
      }
    }
    os << endl;
    lastOffset=0; nextLevelNode=nextLevelList;
    while (nextLevelNode) {
      nextNode=nextLevelNode->node; nextLevelNode=nextLevelNode->next;
      if (nextNode) {
        mput(os,' ',4*(nextNode->inordernr-lastOffset-1));
        if (nextNode->isleft) os << "  / "; else os << " \\  ";
      }
      lastOffset=nextNode->inordernr;
    }
    os << endl;
    thisLevelList=nextLevelList; nextLevelList=NULL;
  }
  delTree(tbd); // Speicher der erweiterten Baumkopie freigeben
  return os;
}

///////////////////////////////////////////////////////////////////////////////
ostream& operator << (ostream& os, const avlPtr root) {
///////////////////////////////////////////////////////////////////////////////
  // to be used for "cout << tree;" or "cerr << tree;"
  bstPtr cp=avl2bst(root);
  os << cp;
  delTree(cp);
  cp=avlbal2bst(root);
  os << cp;
  delTree(cp);
  return os;
}