#ifndef __TREEMAP_H__
#define __TREEMAP_H__

#include <string>

class TreeMap
{
public:
  typedef string ItemType;
  typedef double ValueType;

  TreeMap();
  ~TreeMap();

  int getSize() const;
  ValueType getValue(const ItemType& i) const;
  bool contains(const ItemType& i) const;
  
  void makeEmpty();
  void addItem(const ItemType&, const ValueType& val);
  
private:
  // prohibit copying until we feel like writing deep copy methods
  TreeMap(const TreeMap&);
  TreeMap& operator = (const TreeMap&);

  struct Node
  {
    ItemType info;
    ValueType value;
    Node *left, *right;
  };

  static ValueType getValue(const Node *tree, const ItemType& i);
  static void makeEmpty(Node*& tree);
  static void addItem(Node*& tree, const ItemType& toAdd, const ValueType& val);
  static bool contains(const Node *tree, const ItemType& it);

  Node *root;
  int numItems;
};

#endif