#pragma once
#include <iostream>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;

// bugtree maintains a binary search tree of suspected programming bugs found across a variety of files.
// The tree is maintained in (pseudo)alphabetically-increasing sorted order (< on strings),
//     with each insert finding the correct position for the new bug
//     and embedding it at that spot in the tree.
class bugtree {
   protected:
      struct bug {
         string name; // one word (no spaces) identifier for bug
         string desc; // short text description of nature of bug
         string file; // name of file believed to contain source of bug

         // going from root down,
         //   left points to the node's left child,
         //        all children in the left subtree have names < current node's name
         //   left points to the node's right child,
         //        all children in the right subtree have names >= current node's name
         bug* left;
         bug* right;
      };

      // root points to the base/starting node of the tree (first node inserted)
      bug* root;

      int numBugs; // used to track current number of bugs in the tree

      // allocate, initialize, return bug
      bug* create(string name, string desc, string file);

      // find and return named bug in subtree b, null if not found
      // (must recursively search just the correct subtree based on binary search tree rules,
      //    i.e. not an exaustive search of both subtrees)
      bug* getByName(string name, bug* b);

      // deletes and nullifies each node in b's subtree, including b
      void deallocate(bug* &b);

      // if file is empty string
      //    prints all the bugs in b's subtree in (pseudo)alphabetical order,
      // otherwise prints just those bugs in the subtree related to the specified file
      //    (again, pseudo-alphabetical)
      // uses prtBug to do the individual bug displays
      void printBugs(bug* b, string file = "");

      // find the correct insertion point for the given bug within b's subtree,
      //    if valid spot found then create the bug and insert it
      // returns true if successful, false otherwise
      bool insert(string name, string desc, string file, bug* &b);

   public:
      bugtree(); // initializes an empty bugtree
     ~bugtree(); // uses deallocate on root to delete each bug in the tree

      // both prt methods must use printBugs on root to display the needed content
      void prtAll(); // display all bugs in (pseudo)alphabetical order
      void prtFile(string file); // display all bugs that are related to the named file

      // display in format name(file): desc (all one line, no newline/endl at the end)
      void prtBug(string name, string desc, string file);

      // insert and lookup each return true if successful, false otherwise

      // create/insert bug (maintaining valid binary search tree construction)
      //    insert doesn't allow two bugs with the same name,
      // uses the protected insert to actually do the tree update
      bool insert(string name, string desc, string file);

      // lookup finds the bug with the specified name (if present) and fills in the
      //    passed desc and file parameters with the values found in that bug
      //    (caller passes two string variables to be filled in by lookup)
      // must use getByName on the root to actually find the bug
      bool lookup(string name, string &desc, string &file);
};