/*
Programmer: Maxim Levin
Instructor: Professor Taylor
Section: C
Description: Program creates a hash table and has functions
*/

template <typename T>
MyStringMap<T>::MyStringMap()
{
  m_max = 0;
  m_size = 0;
  m_data = NULL;
}

template <class T>
void MyStringMap<T>::grow()
{
  int oldmax = m_max;
  if(m_max==0)
    m_max++;

  int newSize = (m_max*2);

  item* newarray = new item [newSize];

  if(oldmax == 0)
  {
    for(int k = 0; k < 2; k++)
    {
      newarray[k].key = "empty";
    }
  }
  else
  {
    for(int i = 0; i < m_max; i++)
    {
      newarray[i].key = m_data[i].key;
      newarray[i].value = m_data[i].value;  // Moves data to a temp array
    }
    for(int j = m_max; j < newSize; j++)
    {
      newarray[j].key = "empty";
    }
  }

  delete [] m_data;
  m_data = newarray;
  m_max = (newSize);
  return;
}

template <typename T>
const T& MyStringMap<T>::valueOf(const string & key) const throw (Oops)
{
    int index = -1;

    for(int i = hash(key); i < m_max; i++)
    {
      if(m_data[i].key == key)
        index = i;
    }

    if(index == -1)
    {
      for(int i = 0; i < hash(key); i++)
      {
        if(m_data[i].key == key)
          index = i;
      }
    }

    if(index == -1)
      throw Oops("Key not found!!");
    else
      return m_data[index].value;

}

template <typename T>
void MyStringMap<T>::clear()
{
  m_size = 0;
  m_max = 0;
  delete [] m_data;
  return;
}

template <typename T>
void MyStringMap<T>::remove(const string & k)
{
  int index = -1;
  for(int i = hash(k); i < m_max; i++)
  {
    if(m_data[i].key == k)
      index = i;
  }

  if(index == -1)
  {
    for(int i = 0; i < m_max; i++)
    {
      if(m_data[i].key == k)
        index = i;
    }
  }
  if(index != -1)
  {
    for(int j = index; j < m_max-1; ++j)
    {
      m_data[j].key = m_data[j+1].key;
      m_data[j].value = m_data[j+1].value;
    }
    m_size--;
  }
  return;
}

template <typename T>
void MyStringMap<T>::insert(const string& key, const T& val)
{

  if(m_size >= (m_max/2.0))
    grow();

  int index = -1;

  for(int i = hash(key); i < m_max; i++)
  {
    if(m_data[i].key == key)
      index = i;
  }

  if(index == -1)
  {
    for(int i = 0; i < hash(key); i++)
    {
      if(m_data[i].key == key)
        index = i;
    }
  }

  if(index == -1)
  {
    for(int i = hash(key); i < m_max; i++)
    {
      if(m_data[i].key == "empty")
        index = i;
    }

    if(index == -1)
    {
      for(int i = 0; i < hash(key); i++)
      {
        if(m_data[i].key == "empty")
          index = i;
      }
    }

    m_size++;
  }

  m_data[index].key = key;
  m_data[index].value = val;
  return;
}

template <typename T>
void MyStringMap<T>::print() const
{
  for(int i = 0; i < m_max; i++)
  {
    if(m_data[i].key != "empty")
      cout << "< " << m_data[i].key << ", " << m_data[i].value << " >" << endl;
  }
  return;
}

template <typename T>
int MyStringMap<T>::hash(const string & s) const
{
  int sum = 0;
  for(unsigned int i = 0; i < s.size(); i++)
    sum += s[i];
  return (sum%m_max);
}