// sl-4-DHBW-Inf2
#include <cstdlib>
#include "suchbaum.h"
#include <iostream>
using namespace std;

void bstInsert(bstPtr & root, const DataType value) {
  // inserts <value> into a binary search tree rooted at <root>
  // won't insert it again if it's already in the tree
  if (root==NULL) {
    root = new bsTree(value); // children become NULL by default
  } else if (value<root->value) {
    bstInsert(root->left,value);
  } else if (value>root->value) {
    bstInsert(root->right,value);
  } else { // it is ==
    cout << "Element " << value << " is already in the tree!" << endl;
  }
}

bool bstFind(const bstPtr root, const DataType value) {
  // tries to find <value> in a binary search tree rooted at <root>
  if (root==NULL) {
    return false;
  } else if (value<root->value) {
    return bstFind(root->left,value);
  } else if (value>root->value) {
    return bstFind(root->right,value);
  } else { // it is ==
    return true;
  }
}

bool bstDelete(bstPtr & root, const DataType value) {
  // tries to delete <value> in a binary search tree rooted at <root>
  // returns true if <value> was deleted, false if it isn't in the tree
  if (root==NULL) {
    cout << "Element " << value << " isn't in the tree!" << endl;
    return false; // no, the element was not in the tree
  } else if (value<root->value) {
    return bstDelete(root->left,value);
  } else if (value>root->value) {
    return bstDelete(root->right,value);
  } 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;
    } else if (root->left==NULL) {
      // right subtree must be non-empty, delete root and shift subtree up
      bstPtr tbd=root;
      root=root->right;
      delete tbd;
    } else if (root->right==NULL) {
      // left subtree must be non-empty, delete root and shift subtree up
      bstPtr tbd=root;
      root=root->left;
      delete tbd;
    } else { // both subtrees are non-empty => find inorder successor s,
      // put s to the actual position, shift right subtree of s up
      bstPtr iosucc=root->right; // root is not NULL
      bstPtr iosparent=root;
      while (iosucc->left!=NULL) {
        iosparent=iosucc;
        iosucc=iosucc->left;
      } // now iosucc is the inorder successor of root
      if (iosparent!=root) { // iosucc is not right child of root
        iosparent->left=iosucc->right; // may be NULL, doesn't matter
        iosucc->right=root->right;
      }
      iosucc->left=root->left;
      bstPtr tbd=root;
      root=iosucc; // root parent's child ptr will be corrected by the &
      delete tbd;
    }
    return true; // yes, we deleted an element
  }
}

void preorder(const bstPtr root) {
  if (root!=NULL) {
    cout << root->value << ' ';
    preorder(root->left);
    preorder(root->right);
  }
}

void inorder(const bstPtr root) {
  if (root!=NULL) {
    inorder(root->left);
    cout << root->value << ' ';
    inorder(root->right);
  }
}

void postorder(const bstPtr root) {
  if (root!=NULL) {
    postorder(root->left);
    postorder(root->right);
    cout << root->value << ' ';
  }
}

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

#define CreateDyn2DArray(typ,name,size) typ **name=new typ*[size]; \
                    for(int i=0;i<size;i++) name[i]=new typ[size];
#define DeleteDyn2DArray(name,size) for(int i=0;i<size;i++) delete name[i]; \
                   delete name;

bstPtr optBST(int elems[], double probs[], const int size) {
  CreateDyn2DArray(int,w,size); //int **w=new int*[size]; for (int i=0;i<size;i++) w[i]=new int[size];
  CreateDyn2DArray(double,s,size); //double s[size][size]; // s[x][y]=mittlere Suchdauer für T. mit I. x bix y
  CreateDyn2DArray(double,g,size); //double g[size][size]; // g[x][y]=Summe der Wahrscheinlichkeiten...x bis y
  int i,j,groesse,links,rechts,auswahl;
  double bmsd,vmsd; // bisher kleinste und zu vergleichende mittlere Suchdauer
  for(i=0;i<size;i++) {
    s[i][i]=probs[i];
    w[i][i]=i;
    g[i][i]=probs[i];
    for(j=i+1;j<size;j++) {
      g[i][j]=g[i][j-1]+probs[j];
    }
  }
  for(groesse=2;groesse<=size;groesse++) {
    for(links=0;links+groesse<=size;links++) {
      rechts=links+groesse-1;
      // Minimumsuche mit einem der Fälle "leerer Unterbaum" initialisieren
      bmsd=s[links+1][rechts]; vmsd=s[links][rechts-1];
      if(vmsd<bmsd) {
        bmsd=vmsd; w[links][rechts]=rechts;
      } else {
        w[links][rechts]=links;
      }
      for(auswahl=links+1;auswahl<=rechts-1;auswahl++) {
        vmsd=s[links][auswahl-1]+s[auswahl+1][rechts];
        if(vmsd<bmsd) {
          bmsd=vmsd; w[links][rechts]=auswahl;
        }
      }
      s[links][rechts]=bmsd+g[links][rechts];
    }
  }
  bstPtr erg=genBST(elems,w,size,0,size-1);
  DeleteDyn2DArray(w,size); //for(int i=0;i<size;i++) delete w[i]; delete w;
  DeleteDyn2DArray(s,size);
  DeleteDyn2DArray(g,size);
  return erg;
}

bstPtr genBST(int elems[], int ** roots, const int size, const int l, const int r) {
  if (l>r) {
    return NULL;
  } else {
    int rootidx=roots[l][r];
    bstPtr root=new bsTree(elems[rootidx]);
    root->left=genBST(elems,roots,size,l,rootidx-1);
    root->right=genBST(elems,roots,size,rootidx+1,r);
    return root;
  }
}