#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;

// hash a string to an unsigned int
//   by adding up all the ASCII values
//   of the string
unsigned int hash( string key )
{
  unsigned int hash_value = 0;

  for ( int i = 0 ; i < key.size() ; i++ )
  {
    hash_value += (unsigned int)key[i];
  }

  cout << "HASHED " << key << " TO " << hash_value << endl;
  return hash_value;
}

// also add find() and erase()




// the string "name" serves as both key and as the data
//   stored (or associated) with the key
void
insert_into_hash_table( vector< list<string> >& hash_table,
                        int size, string name )
{
  // first see if the key is already in the hash table
  int hash_value = hash( name );
  int index = hash_value % size;

  // if the key is in the hash table, it will be in the
  //   linked list at the given index of the vector
  list<string>::iterator i;
  i = hash_table[index].begin();
  while ( i != hash_table[index].end() )
  {
    if ( *i == name ) {
      cout << name << " is already in the list...." << endl;
      return;   // !!!!!!!!
    }
    i++;
  }
  // if the above loop ends, the name is not in the list....

  // add key to hash table
  hash_table[index].push_front( name );
  cout << "Added " << name << " to the hash table at index "
       << index << endl;
}

int main()
{
  int size = 37;

  // create hash table as a vector of size "size"
  vector< list<string> > hash_table( size );

  string name = "A. B. Smith";
  insert_into_hash_table( hash_table, size, name );
//  int h = hash( name );
//  int index = h % size;
//  cout << "index is " << index << endl;
//  hash_table[index].push_front( name );

//  name = "B. A. Smith";
//  name = "Goldschmidt";
  name = "A. B. Smith";
  insert_into_hash_table( hash_table, size, name );
//  h = hash( name );
//  index = h % size;
//  cout << "index for " << name << " is " << index << endl;
//  hash_table[index].push_front( name );

  return 0;
}