#include <ostream>
#include <string>
#include <list>

class string_set
{
public:

  string_set(int n);
  ~string_set();

  bool insert(std::string s);
  bool remove(std::string s);
  bool member(std::string s);

  operator std::string();

private:
  typedef std::list<std::string>* ptr_to_list_of_strings;

  //array of pointers to lists of strings
  ptr_to_list_of_strings* table;

  int hash(std::string s);

  //the current number of lists in the table array
  int size;

  //the number of strings in the list
  // int current_size;
};

#include <iostream>
#include <istream>
#include <ostream>
#include <sstream>
#include <string>
#include <list>
#include <locale>

#include "string_set.hpp"

/***************************
 * CONSTRUCTOR
 * allocates a table array of size n,
 * and initializes it to contain n pointers to n empty lists.
 ***************************/
string_set::string_set(int n)
{
  size = n;

  // initialize table to new pointer
  table = new ptr_to_list_of_strings[n];

  // loop through and create a list in each array index
  for (int i(0); i < n; i++)
    {
      table[i] = new std::list<std::string>;
    }
}



/**************************
 * DESTRUCTOR
 * deletes the table array
 ***************************/
string_set::~string_set()
{
  for (int i(0); i < size; i++)
    {
      delete table[i];
    }
  delete[] table;
}



/**************************
 * INSERT
 * add the given string to the string_set if it is not already present.
 * The boolean returned should indicate whether the string_set was modified.
 ***************************/
bool string_set::insert(std::string s)
{
  // if string already exists
  if (member(s))
    {
      return false;
    }

  // otherwise string does not exist
  else
    {
      // push string onto list at hashed table index
      table[hash(s)]-> push_front(s);

      // current_size += 1;
    }

  return true;
}



/**************************
 * REMOVE
 * remove the given string from the string_set if it is present.
 * The boolean returned should indicate whether the string_set was modified.
 ***************************/
bool string_set::remove(std::string s)
{
  // if string exists
  if (member(s))
    {
      // remove the string from its hashed array index
      table[hash(s)]-> remove(s);

      return true;
    }

  return false;
}



/**************************
 * MEMBER
 * return a boolean indicating whether the given string is present in the string_set.
 ***************************/
bool string_set::member(std::string s)
{
  // store hash value in index varibale
  int index = hash(s);

  // initialize iter for looping
  std::list<std::string>::iterator iter;

  ptr_to_list_of_strings elm = table[index];

  // loop through table array
  for (iter = elm-> begin(); iter != elm-> end(); iter++)
    {
      // if equal string found
      if ((*iter) == s)
        {
          return true;
        }
    }

  return false;
}



/**************************
 * CONVERSION TO STRING
 * produce a string consisting of the strings in your string_set in no particular order
 * concatenated together, each followed by a newline. The empty set should produce just a newline.
 ***************************/
string_set::operator std::string()
{
  // initialize stringstream variable
  std::stringstream text;

  bool has_at_least_one_word = false;

  // loop through array
  for (int i(0); i < size; i++)
    {
      // else list is not empty, and contains strings
      ptr_to_list_of_strings elm = table[i];

      if (elm-> empty()==false)
        {
          // initialize iter for looping
          std::list<std::string>::iterator iter;

          // loop through table
          for (iter = elm-> begin(); iter != elm-> end(); iter++)
            {
              // load strings into stringstream
              text << *iter << 'n';
            }
          has_at_least_one_word = true;
        }
    }

  // if bool indicates we have empty set, use newline
  if (has_at_least_one_word == false)
    {
      text << 'n';
    }

  return text.str();
}



/**************************
 * HASH FUNCTION
 ***************************/
int string_set::hash(std::string s)
{
  using namespace std;

  locale loc;

  const collate<char>& coll = use_facet<collate<char> > (loc);

  unsigned long hash_num = coll.hash(s.data(), s.data() + s.length());

  return hash_num % size;
}

#include <iostream>
#include <istream>
#include <ostream>
#include <fstream>


#include "string_set.hpp"

int main()
{
  // declare a single string_set of table size 1000
  string_set S(1000);

  // then read in strings (i.e. words) from the first file
  // put them in S
  std::ifstream fin("first.txt");
  if (not fin)
    std::perror("first.txt");
  else
    {
      std::string word;
      while (fin >> word)
        S.insert(word);
      fin.close();
    }

  // then read in strings (i.e. words) from the second file and

  // take those out of S.
  std::ifstream sin("second.txt");
  if (not sin)
    std::perror("second.txt");
  else
    {
      std::string word;
      while (sin >> word)
        S.remove(word);
      sin.close();
    }

  // output the words in S to standard output (i.e. std::cout).
  std::cout << (std::string)S;
}