#ifndef __TABLE
#define __TABLE

#include <string>
#include "avltree.h"

// Container class 
template <class K, class T>
class __TableNode {
 public:
  K key;
  T data;
  __TableNode<K, T>* next;

  __TableNode () { next = NULL; }
  __TableNode (K k, T t) { key = k; data = t; }

  friend bool operator < 
    (const __TableNode<K, T>& t1, const __TableNode<K, T>& t2) 
    { return t1.key < t2.key; }
  friend bool operator > 
    (const __TableNode<K, T>& t1, const __TableNode<K, T>& t2) 
    { return t1.key > t2.key; }
  friend bool operator <= 
    (const __TableNode<K, T>& t1, const __TableNode<K, T>& t2) 
    { return t1.key <= t2.key; }
  friend bool operator >= 
    (const __TableNode<K, T>& t1, const __TableNode<K, T>& t2)
    { return t1.key >= t2.key; }
  friend bool operator == 
    (const __TableNode<K, T>& t1, const __TableNode<K, T>& t2)
    { return t1.key == t2.key; }
  friend ostream& operator <<
    (ostream& out, __TableNode<K, T>& t)
    { out << t.key << ":" << t.data;  return out; }
    
};

// ADT Table 
template <class T>
class Table : private BSTree< __TableNode<string, T> > {

  __TableNode<string, T> __t;
  __TableNode<string, T>& cp (string s, T& t) 
    { 
      __t.key = s; 
      __t.data = t; 
      return __t; 
    }

 public:
  
  Table () : BSTree< __TableNode<string, T> > () { }
  ~Table () { }

  virtual bool Insert (string s, T t) 
    { return BSTree< __TableNode<string, T> >::Insert (cp (s, t)); }

  virtual bool Delete (string s, T& t) 
    { 
      __t.key = s;
      bool r = BSTree< __TableNode<string, T> >::Delete (__t); 
      t = __t.data; 
      return r; 
    }
  virtual bool Retrieve (string s, T& t)
    { 
      __t.key = s;
      bool r = BSTree< __TableNode<string, T> >::Search (__t); 
      t = __t.data; 
      return r; 
    }

  friend ostream& operator << (ostream& out, Table<T>& t)
    { out << (BSTree< __TableNode<string, T> >&)t; return out; }

};

#endif // __TABLE