#include "apvector.h"
#include "apstring.h"

class Name
{
  public:
    Name();                       // constructor
    Name(const apstring & s);     // construct from string

    // accessor functions

    int length()                 const;  // returns # characters in name
    char operator [](int k)      const;  // return k-th character of name
    bool Equal(const Name & rhs) const;  // check equality
    int HashValue()              const;  // return hash value of name
    
  private:
    // declarations here
};

bool operator == (const Name & lhs, const Name & rhs)
// postcondition: returns true if lhs == rhs, otherwise returns false    
{
    return lhs.Equal(rhs);
}

template <class Type>
class HashTable
{
  public:

    HashTable(int size);                    // size of hashtable

    bool Contains(const Type & key) const;  // is key in hashtable?
    void Insert(const Type & key);          // insert key into table

    // other member functions as needed
    
  private:

    // node for linked list
    
    struct Node
    {
        Type info;    
        Node * next;
	Node(const Type & val, Node * link = 0)
	    : info(val),
	      next(link)
	{
	    
	}
    };

    apvector<Node *> myTable;   // vector linked lists
    int              mySize;    // size of myTable
};

template <class Type>
HashTable<Type>::HashTable(int size)
    : myTable(size),
      mySize(size)
{
    
}

template <class Type>
bool HashTable<Type>::Contains(const Type & key) const
{
    Node * temp = myTable[key.HashValue() % mySize];
    while (temp)
    {
	if (temp->info == key) return true;
	temp = temp->next;
    }
    return false;
}

template <class Type>
void HashTable<Type>::Insert(const Type & key)
{
    if (! Contains(key))
    {
	int index = key.HashValue() % mySize;
	myTable[index] = new Node(key,myTable[index]);
	
    }
}

template class HashTable<Name>;