/*
 * Name: Owen Sullivan
 * Date Submitted: 10/31/2022
 * Lab Section: 006
 * Assignment Name: Lab 8: Storing a Sequence in a Binary Search Tree
*/

#include "bstSequence.h"

using namespace std;

void fix_size(Node *T) {
  
  T->size = 1;
  if (T->left) {
    
    T->size += T->left->size;
  
  }
  if (T->right) {

    T->size += T->right->size;
  
  }

}

/*
// insert key k into tree T, returning a pointer to the resulting tree
Node *insert(Node *T, int k) {
  
  if (T == nullptr) return new Node(k);
  if (k < T->key) T->left = insert(T->left, k);
  else T->right = insert(T->right, k);
  fix_size(T);
  return T;

}
*/

// insert value v at rank r
Node *insert(Node *T, int v, int r) {
  
  // If T is empty (meaning we're at the lowest level of the tree),
  // insert a new node with key v
  if (T == nullptr) {

    return new Node(v);

  }

  int rank;

  // If the current node has no left branch, its rank is zero
  if (T->left == nullptr) {

    rank = 0;

    // If the current node has a left branch, its rank is the size
    // of its left branch
  } else {

    rank = T->left->size;

  }

  // If the rank of the node we're trying to insert is less than
  // or equal to the rank of the tree, insert to the left
  if (r <= rank) {

    T->left = insert(T->left, v, r);

    // If the rank of the node we're trying to insert is greater than
    // the rank of the tree, insert to the right
  } else {

    T->right = insert(T->right, v, (r - rank - 1));

  }

  // Fix the size of the tree since nodes are being added
  fix_size(T);

  return T;

}

// returns a vector of key values corresponding to the inorder traversal of T (i.e., the contents of T in sorted order)
vector<int> inorder_traversal(Node *T) {
  
  vector<int> inorder;
  vector<int> rhs;

  if (T == nullptr) {
    
    return inorder;
  
  }

  inorder = inorder_traversal(T->left);
  inorder.push_back(T->key);
  rhs = inorder_traversal(T->right);
  inorder.insert(inorder.end(), rhs.begin(), rhs.end());

  return inorder;

}

// return pointer to node of rank r (with r'th largest key; e.g. r=0 is the minimum)
Node *select(Node *T, int r) {
  
  assert(T != nullptr && r >= 0 && r < T->size);

  int rank_of_root = T->left ? T->left->size : 0;
  if (r == rank_of_root) return T;
  if (r < rank_of_root) return select(T->left, r);
  else return select(T->right, r - rank_of_root - 1);

}

// Split tree T on rank r into tree L (containing ranks < r) and 
// a tree R (containing ranks >= r)
void split(Node *T, int r, Node **L, Node **R) {
  
  // If T is empty, set left and right trees to nullptr to remove
  // any leftover nodes on each tree
  if (T == nullptr) {

    *L = *R = nullptr;
    return;

  }

  int rank;

  // If the current node has no left branch, its rank is zero
  if (T->left == nullptr) {

    rank = 0;

    // If the current node has a left branch, its rank is the size
    // of its left branch
  } else {

    rank = T->left->size;

  }

  // If the current node's rank is greater than or equal to the rank being used
  // as the splitting point
  if (rank >= r) {

    // Split the left branch of the current node
    split(T->left, r, L, &T->left);
    
    // Set the right tree to the current node
    *R = T;

    // If the current node's rank is less than the rank being
    // used as the splitting point
  } else {

    // Split the right branch of the current node
    split(T->right, (r - rank - 1), &T->right, R);
    
    // Set the left tree to the current node
    *L = T;

  }

  // Fix the size of T since nodes have been removed
  fix_size(T);

}

// insert value v at rank r
Node *insert_random(Node *T, int v, int r) {
  
  // If T is empty (meaning we're at the lowest level of the tree),
  // insert a new node with key v
  if (T == nullptr) {

    return new Node(v);

  }

  int rank;

  // If the current node has no left branch, its rank is zero
  if (T->left == nullptr) {

    rank = 0;

    // If the current node has a left branch, its rank is the size
    // of its left branch
  } else {

    rank = T->left->size;

  }
  
  // Generate a random integer modded by the size of the current node
  // plus 1 (since 1 is being added)
  srand(static_cast<unsigned int>(time(0)));
  int random = rand() % (T->size + 1);
  
  // If the random integer is equal to zero, create a new node with key v
  // and set the new node's left and right branches to that of the current
  // node by splitting the current node
  if (random == 0) {

    Node *newNode = new Node(v);

    split(T, r, &newNode->left, &newNode->right);

    // Fix the size since nodes were added
    fix_size(newNode);

    return newNode;

    // If the random integer is not equal to zero, compare the current node's
    // rank against the rank we're inserting
  } else {

    // If the rank of the node we're trying to insert is less than
    // or equal to the rank of the tree, insert to the left
    if (r <= rank) {

      T->left = insert_random(T->left, v, r);

      // If the rank of the node we're trying to insert is greater than
      // the rank of the tree, insert to the right
    } else {

      T->right = insert_random(T->right, v, (r - rank - 1));

    }

    // Fix the size of the tree since nodes are being added
    fix_size(T);

    return T;

  }

}

// Returns true if team x defeated team y
// Leave this function unmodified
bool did_x_beat_y(int x, int y) {
  
  assert (x != y);
  
  if (x > y) return !did_x_beat_y(y,x);
  unsigned long long lx = x;
  unsigned long long ly = y;
  return ((17 + 8321813 * lx + 1861 * ly) % 1299827) % 2 == 0;

}

// Return a BST containing a valid ordering of n teams
Node *order_n_teams(int n) {
  
  Node *T = nullptr;

  // start by inserting the first team
  T = insert_random(T, 0, 0);

  // now insert the other teams...
  for (int i = 1; i < n; i++) {
    
    // insert team i so the sequence encoded by the BST remains valid
      // can we insert at beginning?
    if (did_x_beat_y(i, select(T, 0)->key)) {

      T = insert_random(T, i, 0);

      // can we insert at end?
    } else if (did_x_beat_y(select(T, (T->size - 1))->key, i)) {
      
      T = insert_random(T, i, T->size);

      // Inserting via binary search
    } else {
	    
      int lowRank = 0;
      int midRank;
      // High rank is 1 less than the size of the tree
      int highRank = T->size - 1;

      // Loop until the tree item at highRank and lowRank are right next
      // to each other
      while (highRank - lowRank != 1) {

        midRank = (lowRank + highRank) / 2;

        // If the team at i beat the team at the tree item at midRank,
        // set highRank to midRank for next loop
        if (did_x_beat_y(i, select(T, midRank)->key)) {

          highRank = midRank;

          // If the team at i lost to the team at the tree item at midRank,
          // set lowRank to midRank for the next loop
        } else {

          lowRank = midRank;

        }

      }

      // Set midRank to the tree index right before highRank
      midRank = lowRank + 1;

      // Insert the team at i at midRank
      T = insert_random(T, i, midRank);
    
    }

  }

  return T;
  
}

void printVector(vector<int> v) {
    
    for (int i = 0; i < v.size(); i++) {
      
      cout << v[i] << endl;
    
    }

}

// int main(void) {
  
//   vector<int> inorder;
//   Node *T = nullptr;

//   // test insert at beginning
//   for (int i=0; i<5; i++) {

//     T = insert_random(T, i+1, 0);
  
//   }
//   cout << "Tree should contain 5 4 3 2 1:\n";
//   inorder = inorder_traversal(T);
//   printVector(inorder);

//   // test insert at end
//   for (int i=5; i<10; i++) {

//     T = insert_random(T, i+1, T->size);

//   }
//   cout << "Tree should contain 5 4 3 2 1 6 7 8 9 10:\n";
//   inorder = inorder_traversal(T);
//   printVector(inorder);
  
//   // test insert at middle
//   for (int i=10; i<15; i++) {

//     T = insert_random(T, i+1, T->size/2);

//   }
//   cout << "Tree should contain 5 4 3 2 1 12 14 15 13 11 6 7 8 9 10:\n";
//   inorder = inorder_traversal(T);
//   printVector(inorder);
    
//   // once insert is working, the next step is to build the
//   // insert_random function -- to test this, just change
//   // calls to insert above to insert_random.

//   int N = 100000; // this should run quickly even for very large N!
//   Node *S = order_n_teams(N);
//   if (S == nullptr || S->size != N) {

//     cout << "Size of tree returned by order_n_teams is wrong\n";

//   } else {
//     cout << "Team ordering:\n";
//     //    inorder=inorder_traversal(S);
//     //    printVector(inorder);
//     for (int i = 0; i < N - 1; i++) {
      
//       Node *x = select(S, i);
//       Node *y = select(S, i+1);
      
//       if (!did_x_beat_y(x->key, y->key)) {
        
//         cout << "Invalid sequence: team " << x->key << " (position " << i <<
// 	              ") lost to team " << y->key << " (position " << i+1 << ")\n";
      
//       }

//     }

//   }  
  
//   return 0;

// }