// DEMO: Binary search trees in C++, with parametric data definition

#include <cassert>
#include <cstdlib>
#include <cstring>
using namespace std;

/* DATA DEFINITION
      A (bst X) is one of:
        - a pointer to
          Node<X>::Node(left, key, value, right)
            where key is a C-string (const char *)
                  value is an X
                  left and right are (bst X)
        - NULL
*/

template <class X> class Node { // definition by parts, parametric in X
public:
  const char *key;
  X *value;
  Node <X> *left;
  Node <X> *right;
public: // a constructor function associated with this class
  Node (Node <X>*, const char *, X*, Node <X>*);
};


// in C++ we have to provide our own constructor function
// which initializes the parts
template <class X>
Node <X>::Node (Node <X> *left, const char *key, X *value, Node <X> *right) {
  this->left = left;
  this->key  = key;
  this->value = value;
  this->right = right;
}

template <class X>
X *lookup(const char *key, Node <X> *tree) {
  if (tree == NULL)
    return NULL;
  else {
    int n = strcmp(key, tree->key);
    if (n < 0)
      return lookup(key, tree->left);
    else if (n == 0)
      return tree->value;
    else if (n > 0)
      return lookup(key, tree->right);
    else
      assert(false);
  }
}
    
template <class X>
Node <X> *insert(const char *key, X *value, Node <X> *tree) {
  if (tree == NULL)
    return new Node<X>(NULL, key, value, NULL);
  else {
    int n = strcmp(key, tree->key);
    if (n < 0)
      return new Node <X>(insert(key, value, tree->left),
                          tree->key, tree->value,
                          tree->right);
    else if (n == 0)
      return new Node <X>(tree->left, key, value, tree->right);
    else if (n > 0)
      return new Node <X>(tree->left,
                          tree->key, tree->value,
                          insert(key, value, tree->right));
    else
      assert(false);
  }
}
    

/////////////////////////////////////////////////////////////

// testing

// see http://cppunit.sourceforge.net/doc/lastest/cppunit_cookbook.html

#include <cppunit/TestCase.h>
#include <cppunit/TestFixture.h>
#include <cppunit/TestCaller.h>
#include <cppunit/ui/text/TestRunner.h>

class TestInt {
public:
  int n;
  TestInt (int m);
};

TestInt::TestInt (int m) {
  this->n = m;
}

typedef Node <TestInt> INode;

class BSTTest : public CppUnit::TestFixture { 
private:
  INode *et, *t1, *t2;
public: 
  void setUp() {
    et = NULL;
    t1 = new INode (new INode (et, "Guyer", new TestInt (5), et),
                    "Hescott", new TestInt (7),
                    new INode (et, "Ramsey", new TestInt (8), et));
    t2 = NULL;
  }

  void tearDown() {
    delete t1;
  }
  

  void testLookup() {
    
    CPPUNIT_ASSERT( lookup("Ramsey", et) == NULL );
    CPPUNIT_ASSERT( lookup("Ramsey", t1) != NULL );
    CPPUNIT_ASSERT( lookup("Ramsey", t1) != NULL
                    && lookup("Ramsey", t1)->n == 8);
  }

  void testInsert() {
    
    CPPUNIT_ASSERT( insert("Ramsey", new TestInt (99), et)->value->n == 99 );
  }

public: 
  static CppUnit::Test *suite()
  {
    CppUnit::TestSuite *suiteOfTests = new CppUnit::TestSuite( "BSTTest" );
    suiteOfTests->addTest( new CppUnit::TestCaller<BSTTest>( 
                                   "testLookup", 
                                   &BSTTest::testLookup ) );
    suiteOfTests->addTest( new CppUnit::TestCaller<BSTTest>( 
                                   "testInsert", 
                                   &BSTTest::testInsert ) );
    return suiteOfTests;
  }

};


int main( int argc, char **argv)
{
  CppUnit::TextUi::TestRunner runner;
  runner.addTest(BSTTest::suite());
  runner.run();
  return 0;
}