/*
 * Name: Owen Sullivan
 * Date Submitted: 10/31/2022
 * Lab Section: 006
 * Assignment Name: Lab 7: Binary Search Tree
*/

#include "binarySearchTree.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;

}

// 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 a pointer to the node with key k in tree T, or nullptr
// if it doesn't exist
Node *find(Node *T, int k) {
  
  // If T is nullptr, return nullptr
  if (T == nullptr) {

    return nullptr;
    
  }

  // If the current node's key is greater than the key being searched for,
  // search for the key in the current node's left branch
  if (T->key > k) {

    return find(T->left, k);

    // If the current node's key is less than the key being searched for,
    // search for the key in the current node's right branch
  } else if (T->key < k) {

    return find(T->right, k);

    // If the current node's key is equal to the key being searched for,
    // we've found the correct node
  } else {

    return T;

  }

}

// 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;

  // 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 the rank being searched for,
  // search for the rank in the current node's left branch
  if (rank > r) {

    return select(T->left, r);

    // If the current node's rank is less than the rank being searched for,
    // search for the rank in the current node's right branch
  } else if (rank < r) {

    return select(T->right, (r - rank - 1));

    // If the current node's rank is equal to the rank being searched for,
    // we've found the correct node
  } else {

    return T;

  }

}

// Join trees L and R (with L containing keys all <= the keys in R)
// Return a pointer to the joined tree.  
Node *join(Node *L, Node *R) {
  
  // If the L tree is empty, there's nothing on the left side to join
  // so return R
  if (L == nullptr) {

    return R;

    // If the R tree is empty, there's nothing on the right side to join
    // so return L
  } else if (R == nullptr) {

    return L;

  }
  
  // Use formula L/(L+R) to determine the probability of top left tree
  // becoming root tree
  double probability = L->size / (L->size + R->size);
  
  // Generate a random double for comparison against probability
  srand(static_cast<unsigned int>(time(0)));
  double random = rand() / (double)RAND_MAX;

  // If random number is less than or equal to the probability,
  // the left tree becomes the root
  if (random <= probability) {

    // Join the left branch of the right tree with the left tree,
    // setting the result to the left branch of the left tree
    L->left = join(L, R->left);

    // Fix the size because nodes are being added
    fix_size(R);

    return L;

    // If the random number is greater than the probability,
    // the right tree becomes the root
  } else {

    // Join the left branch of the right tree with the left tree,
    // setting the result to the left branch of the left tree
    R->left = join(L, R->left);

    // Fix the size because nodes are being added
    fix_size(R);

    return R;

  }

}

// Remove key k from T, returning a pointer to the resulting tree.
// It is required that k be present in T
Node *remove(Node *T, int k) {
  
  assert(T != nullptr);
  
  // If the current node's key is greater than the key being searched for,
  // search the left branch for the node to remove
  if (T->key > k) {

    T->left = remove(T->left, k);

    // Fix the size because a node is being removed
    fix_size(T);

    return T;

    // If the current node's key is less than the key being searched for,
    // search the right branch for the node to remove
  } else if (T->key < k) {

    T->right = remove(T->right, k);

    // Fix the size because a node is being removed
    fix_size(T);

    return T;

    // If the current node's key is equal to the key being searched for,
    // join the current node's left and right branches to be removed
  } else {

    // Create a new node to store the node being deleted
    Node *remove = T;
    
    // Join the left and right branches so that they are not also removed
    T = join(T->left, T->right);

    // If T is not empty, fix the size because a node is being removed
    if (T != nullptr) {

      fix_size(T);

    }

    // Free the memory for the node being removed
    delete remove;

    // Return the leftover left and right branches as a combined node
    return T;

  }

}

// Split tree T on key k into tree L (containing keys <= k) and
// a tree R (containing keys > k)
void split(Node *T, int k, 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;

  }

  // If the current node's key is greater than the key being used as the
  // splitting point
  if (T->key > k) {

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

    // If the current node's key is less than or equal to the key being
    // used as the splitting point
  } else {

    // Split the right branch of the current node
    split(T->right, k, &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 key k into the tree T, returning a pointer to the resulting tree
Node *insert_random(Node *T, int k) {
  
  // If T is empty (meaning we're at the lowest level of the tree),
  // insert a new node with key k
  if (T == nullptr) {

    return new Node(k);

  }
  
  // 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 k
  // 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(k);

    split(T, k, &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
    // key against the key we're inserting
  } else {

    // If the current node's key is greater than the key we're inserting,
    // try to insert a new node on the next level down on the left branch
    if (T->key > k) {

      T->left = insert_random(T->left, k);

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

      return T;

      // If the current node's key is less than the key we're inserting,
      // try to insert a new node on the next level down on the right branch
    } else {

      T->right = insert_random(T->right, k);

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

      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;
//   vector<int> A(10, 0);
  
//   // put 0..9 into A[0..9] in random order
//   for (int i = 0; i < 10; i++) {
    
//     A[i] = i;

//   }
//   for (int i = 9; i > 0; i--) {
    
//     swap(A[i], A[rand()%i]);

//   }
//   cout << "Contents of A (to be inserted into BST):\n";
//   printVector(A);
  
//   // insert contents of A into a BST
//   Node *T = nullptr;
//   for (int i = 0; i < 10; i++) {
    
//     T = insert(T, A[i]);

//   }
  
//   // print contents of BST (should be 0..9 in sorted order)
//   cout << "Contents of BST (should be 0..9 in sorted order):\n";
//   inorder = inorder_traversal(T);
//   printVector(inorder);

//   // test select
//   for (int i = 0; i < 10; i++) {
    
//     Node *result = select(T, i);
//     if (!result || result->key != i) {
      
//       cout << "Select test failed for select(" << i << ")!\n";

//     }
  
//   }

//   // test find: Elements 0..9 should be found; 10 should not be found
//   cout << "Elements 0..9 should be found; 10 should not be found:\n";
//   for (int i = 0; i < 11; i++) {
    
//     if (find(T, i)) {
      
//       cout << i << " found\n";

//     } else {
      
//       cout << i << " not found\n";

//     }
  
//   }

//   // test split
//   Node *L, *R;
//   split(T, 4, &L, &R);
//   cout << "Contents of left tree after split (should be 0..4):\n";
//   inorder = inorder_traversal(L);
//   printVector(inorder);
//   cout << "Left tree size " << L->size << "\n";
//   cout << "Contents of right tree after split (should be 5..9):\n";
//   inorder = inorder_traversal(R);
//   printVector(inorder);
//   cout << "Right tree size " << R->size << "\n";
    
//   // test join
//   T = join(L, R);
//   cout << "Contents of re-joined tree (should be 0..9)\n";
//   inorder = inorder_traversal(T);
//   printVector(inorder);
//   cout << "Tree size " << T->size << "\n";
  
//   // test remove
//   for (int i = 0; i < 10; i++) {
    
//     A[i] = i;

//   }
//   for (int i = 9; i > 0; i--) {
    
//     swap(A[i], A[rand()%i]);

//   }
//   for (int i = 0; i < 10; i++) {
    
//     T = remove(T, A[i]);
//     cout << "Contents of tree after removing " << A[i] << ":\n";
//     inorder = inorder_traversal(T);
//     printVector(inorder);
//     if (T != nullptr) {
      
//       cout << "Tree size " << T->size << "\n";
    
//     }
  
//   }

//   // test insert_random
//   cout << "Inserting 1 million elements in order; this should be very fast...\n";
//   for (int i = 0; i < 1000000; i++) {
    
//     T = insert_random(T, i);

//   }
//   cout << "Tree size " << T->size << "\n";
//   cout << "Done\n";
  
//   return 0;

// }