// This is a stripped-down version of the BST code from the book,
// augmented with a generic traveral routine templated to support
// strategies defined by a class.

#include <iostream.h>
#include <stdlib.h>
#include <string.h>

int theCount; // Used to support the two counting traversals

// Count all nodes in tree
class CountClass {
public:
  // What to do at a leaf
  static void doleaf(int level, int val, int currVal)
    { theCount++; }
  // What to do at an internal node
  static void dointernal(int level, int val, int currVal)
    { theCount++; }
  // Decide if we should go left
  static bool doleft(int val, int currVal)
    { return true; }
  // Decide if we should go right
  static bool doright(int val, int currVal)
    { return true; }
};

// Count all leaf nodes in the tree
class LeafCountClass {
public:
  static void doleaf(int level, int val, int currVal)
    { theCount++; }
  static void dointernal(int level, int val, int currVal)
    { }
  static bool doleft(int val, int currVal)
    { return true; }
  static bool doright(int val, int currVal)
    { return true; }
};

// Print out all nodes in the tree
class PrintClass {
public:
  static void doleaf(int level, int val, int currVal) {
    for (int i=0; i<level; i++)      // Indent to level
      cout << "  ";
    cout << currVal << "\n";       // Print node value
  }
  static void dointernal(int level, int val, int currVal) {
    for (int i=0; i<level; i++)      // Indent to level
      cout << "  ";
    cout << currVal << "\n";       // Print node value
  }
  static bool doleft(int val, int currVal)
    { return true; }
  static bool doright(int val, int currVal)
    { return true; }
};

// Print out only nodes greater than some value
class PrintGtrClass {
public:
  static void doleaf(int level, int val, int currVal) {
    if (val >= currVal) return;
    for (int i=0; i<level; i++)      // Indent to level
      cout << "  ";
    cout << currVal << "\n";       // Print node value
  }
  static void dointernal(int level, int val, int currVal) {
    if (val >= currVal) return;
    for (int i=0; i<level; i++)      // Indent to level
      cout << "  ";
    cout << currVal << "\n";       // Print node value
  }
  static bool doleft(int val, int currVal) {
    if (val < currVal) return true;
    else return false;
  }
  static bool doright(int val, int currVal)
    { return true; }
};


// Binary tree node class
class BinNode {
private:
  int it;                     // The node's value
  BinNode* lc;              // Pointer to left child
  BinNode* rc;              // Pointer to right child
public:
  // Two constructors -- with and without initial values
  BinNode() { lc = rc = NULL; }
  BinNode(int e, BinNode* l =NULL,
                     BinNode* r =NULL)
    { it = e; lc = l; rc = r; }
  ~BinNode() {}             // Destructor
  int val() { return it; }
  void setVal(const int& e) { it = e; }
  inline BinNode* left() const { return lc; }
  void setLeft(BinNode* b) { lc = (BinNode*)b; }
  inline BinNode* right() const { return rc; }
  void setRight(BinNode* b) { rc = (BinNode*)b; }
  bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};


// Binary Search Tree implementation
class BST {
private:
  BinNode* root;   // Root of the BST
  int nodecount;   // Number of nodes in the BST
  // Private "helper" functions
  void clearhelp(BinNode*);
  BinNode* inserthelp(BinNode*, const int&);
  BinNode* deletemin(BinNode*, BinNode*&);
  BinNode* removehelp(BinNode*, const int&, BinNode*&);
  // Only one method is a template
  template <class CC> void traverse(BinNode*, int, int) const;
public:
  BST() { root = NULL; nodecount = 0; }  // Constructor
  bool insert(const int& e) {
    root = inserthelp(root, e);
    nodecount++;
    return true;
  }
  int size() { return nodecount; }

  // Here are the four functions supported by generic traversal
  void count() const { // Count all nodes
    theCount = 0;
    traverse<CountClass>(root, 0, 0);
    cout << "The count is: " << theCount << endl;
  }
  void leafcount() const { // Count the leaf nodes
    theCount = 0;
    traverse<LeafCountClass>(root, 0, 0);
    cout << "The count is: " << theCount << endl;
  }
  void print() const { // Print all nodes
    if (root == NULL) cout << "The BST is empty.\n";
    else traverse<PrintClass>(root, 0, 0);
  }
  void printgtr(int val) const { // Print nodes > val
    if (root == NULL) cout << "The BST is empty.\n";
    else traverse<PrintGtrClass>(root, 0, val);
  }
};

BinNode* BST::inserthelp(BinNode* subroot, const int& val) {
  if (subroot == NULL)            // Empty tree: create node
    return (new BinNode(val, NULL, NULL));
  if (val < subroot->val()) // Insert on left
    subroot->setLeft(inserthelp(subroot->left(), val));
  else subroot->setRight(inserthelp(subroot->right(), val));
  return subroot;  // Return subtree with node inserted
}


// Generic traversal function, templated with a decision-making class
// Since there are four types of traversal, the compiler makes four instances
// of source code for (only) this function
template <class CC>
void BST::traverse(BinNode* subroot, int level, int val) const {
  if (subroot == NULL) return;          // Empty tree
  if (CC::doleft(val, subroot->val()))
    traverse<CC>(subroot->left(), level+1, val);  // Do left subtree
  if (subroot->isLeaf())
    CC::doleaf(level, val, subroot->val());
  else CC::dointernal(level, val, subroot->val());
  if (CC::doright(val, subroot->val()))
    traverse<CC>(subroot->right(), level+1, val); // Do right subtree
}


// Driver
int main()
{
  BST tree;

  // Load up the tree
  tree.insert(700);
  tree.insert(350);
  tree.insert(201);
  tree.insert(170);
  tree.insert(151);
  tree.insert(190);
  tree.insert(1000);
  tree.insert(900);
  tree.insert(950);
  tree.insert(10);

  // Now lets test out our four traversals
  tree.print();
  cout << "---------------\n";
  tree.printgtr(200);
  cout << "---------------\n";
  tree.count();
  tree.leafcount();

  return(0);
}