#include "bugtree.h"

void bugtree::prtFile(string file)
{
   printBugs(root, file);
}

void bugtree::prtAll()
{
   printBugs(root, "");
}

void bugtree::prtBug(string name, string desc, string file)
{
   cout << name << "(" << file << "): " << desc;
}

bugtree::bugtree()
{
   root = nullptr;
   numBugs = 0;
}

bugtree::~bugtree()
{
   if (root) {
      cout << "ENTERING DESTRUCTOR ON TREE WITH ROOT " << root->name << endl;
      deallocate(root);
   }
}

bugtree::bug* bugtree::create(string name, string desc, string file)
{
   bug* b = new bug;
   b->name = name;
   b->desc = desc;
   b->file = file;
   b->left = nullptr;
   b->right = nullptr;
   return b;
}

bool bugtree::lookup(string name, string &desc, string &file)
{
   bug* b = getByName(name, root);
   if (b) {
      desc = b->desc;
      file = b->file;
      return true;
   }
   return false;
}


bugtree::bug* bugtree::getByName(string name, bug* b)
{
   // can't find anything if the tree is empty
   if (!b) {
      return nullptr;
   }

   // see if b is the one we're looking for
   else if (name == b->name) {
      return b;
   }

   // if name < b's name then what we're looking for can only be in left subtree
   else if (name < b->name) {
      return getByName(name, b->left);
   }

   // otherwise name > b's name so can only be in right subtree
   else {
      return getByName(name, b->right);
   }
}

void bugtree::deallocate(bug* &b)
{
   if (b) {
      // recursively deallocate b's subtrees then delete b itself
      if (b->left) deallocate(b->left);
      if (b->right) deallocate(b->right);
      delete b;
      b = nullptr;
   }
}

bool bugtree::insert(string name, string desc, string file, bug* &b)
{
   if (!b) {
      // b is null, we've reached the insertion point
      b = create(name, desc, file);
      numBugs++;
      return true;
   }

   // make sure the name isn't a duplicate
   else if (name == b->name) {
      return false;
   }

   // recurse on either the left or right subtree, based on the name and b's name
   else if (name < b->name) {
      return insert(name, desc, file, b->left);
   }

   else {
      return insert(name, desc, file, b->right);
   }
}

void bugtree::printBugs(bug* b, string file)
{
   if (b) {
      // print any the lesser-named bugs first
      printBugs(b->left, file);

      // print the current bug if we're printing all (file is "")
      //    or if b's file matches the specified file
      if ((file == "") || (file == b->file)) {
         prtBug(b->name, b->desc, b->file);
         cout << endl;
      }

      // print any greater-named bugs after
      printBugs(b->right, file);
   }
}

bool bugtree::insert(string name, string desc, string file)
{
   // fails if there is already a bug with that name
   bug* b = getByName(name, root);
   if (b) {
      cerr << "Error: cannot insert bugs with duplicate names," << endl;
      cerr << "   conflicts with ";
      prtBug(b->name, b->desc, b->file);
      cerr << "" << endl;
      return false;
   }

   // use the protected insert routine to do the work
   return insert(name, desc, file, root);
}

// ===== ADDED =====

// returns a pointer to the bug with the alphabetically lowest name
//    from within the subtree b (null if b is null)
bugtree::bug* bugtree::smallest(bug* b)
{
   if (!b) {
      return nullptr;
   }
   while (b->left) {
      b = b->left;
   }
   return b;
}

// returns a pointer to the bug with the alphabetically highest name
//    from within the subtree b (null if b is null)
bugtree::bug* bugtree::largest(bug* b)
{
   if (!b) {
      return nullptr;
   }
   while (b->right) {
      b = b->right;
   }
   return b;
}

// finds, removes, and deletes the bug with the provided name,
//    but still leaving the tree in a valid form
// returns true if successful, false otherwise
// (uses the protected remove method to do the actual work)
bool bugtree::remove(string name)
{
   return remove(name, root);
}

// overloaded = operator, copies content of bugtree b into current (duplicates data)
// (uses copyAllFrom to do the work)
bugtree& bugtree::operator=(const bugtree& b)
{
   // make sure we're starting from an empty tree
   if (root) deallocate(root);
   root = nullptr;

   // insert everything from the new tree, top down
   copyAllFrom(b.root);
   return *this;
}

// finds and removes the bug with the specified name from the subtree b,
//    while leaving the tree in a valid binary search tree form
// returns true if successful, false otherwise
bool bugtree::remove(string name, bug* &b)
{
   // case 1: not found
   if (!b) {
      return false;
   }

   // case 2: need to look down left
   if (name < b->name) {
       return remove(name, b->left);
   }

   // case 3: need to look down right
   else if (name > b->name) {
       return remove(name, b->right);
   }

   // case 4: found, no children
   else if (!b->left && !b->right) {
      delete b;
      b = nullptr;
      numBugs--;
      return true;
   }

   // case 5: found, only a right child, move that up to replace b
   else if (!b->left) {
      delete b;
      b = b->right;
      numBugs--;
      return true;
   }

   // case 6: found, only a left child, move that up to replace b
   else if (!b->right) {
      delete b;
      b = b->left;
      numBugs--;
      return true;
   }

   // case 7: found, two children
   else {
      // overwrite b with the name/desc/file from the smallest name on b's right
      // then recursively remove that name
      bug* small = smallest(b->right);
      if (!small) {
         cerr << "ERROR ERROR BROKEN TREE (recursive right remove)" << endl;
         return false;
      }
      b->name = small->name;
      b->desc = small->desc;
      b->file = small->file;
      return remove(small->name, b->right);
   }
}


// goes pre-order traversal of subtree b (b, then b's left, then b's right)
//    and on each b it inserts a bug with b's name/desc/file
//    into the current true (takes b's data and calls insert)
// returns a count of number of bugs successfully copied
int bugtree::copyAllFrom(bug* b)
{
   int count = 0;
   if (b) {
      if (insert(b->name, b->desc, b->file)) {
         count++;
      } else {
         cerr << "Failed to copy/insert bug: ";
         prtBug(b->name, b->desc, b->file);
         cerr << endl;
      }
      count += copyAllFrom(b->left);
      count += copyAllFrom(b->right);
   }
   return count;
}