Hash Table with chaining

[jls36]

Im creating a Hash Table with chaining with an array of STL list(s). My getNext function works but after calling the first function then getNext it gives me the same thing. Don't know why. Also when using my retrieve function how would I get the correct one at that location since Im using chaining. Also can I resize the array even if im using #define HASHTABLE_CAPACITY. I need to re-size when the load factor gets to a certain %

MY DataType is a struct

struct Node
{
  string term, course, instructor;

};

I use term & course to get desired index then its wrapped if needed

HERE IS MY templated class HashTable.h

#include <algorithm>
#include <assert.h> // for assertions
#include <list>


#ifndef HashTable_h
#define HashTable_h

#define HASHTABLE_CAPACITY 1009


template <class DataType>
class HashTable
{
  public:
    HashTable(); // constructor
    HashTable(const list<DataType>&);
    void insert(int, const DataType&); // setter       
    void setWrappedIndex(int); // setter
    bool first(DataType& getData);
    bool getNext(DataType&);
    bool retrieve(DataType&, int);
    int getWrappedIndex() const; // getter
    int getSize() const; // getter
    double getLoadFactor() const; // getter

  private:
    list<DataType> aList[HASHTABLE_CAPACITY];
    typename list<DataType>::iterator it;
    int wrappedIndex;
    int size, current;

}; // close HashTable

template <class DataType>
HashTable<DataType>::HashTable()
  : size(0), wrappedIndex(0), current(-1)
{}

template <class DataType>
HashTable<DataType>::HashTable(const list<DataType>& a)
:  size(a.size), current(a.current)
{
  aList = a.aList;

}


template <class DataType>
void HashTable<DataType>::insert(int DI, const DataType& newData)
{
  setWrappedIndex(DI);

  it = find(aList[wrappedIndex].begin(), aList[wrappedIndex].end(), newData); 

  if (it != aList[wrappedIndex].end()) *it = newData; // replace 

  else 
  {
    aList[wrappedIndex].push_back(newData); 
    current = wrappedIndex;
    ++size;

  } // close else
  
}


template <class DataType>
void HashTable<DataType>::setWrappedIndex(int DI)
{
  if (DI > HASHTABLE_CAPACITY)
  {
    wrappedIndex = DI % HASHTABLE_CAPACITY;

    if (wrappedIndex > HASHTABLE_CAPACITY)
    {
      while (wrappedIndex > HASHTABLE_CAPACITY)
        wrappedIndex = wrappedIndex % HASHTABLE_CAPACITY;

    } // close if

  } // close if

  else if (DI < 0)
  {
    while (DI < 0 && DI < HASHTABLE_CAPACITY)
    {
      DI += HASHTABLE_CAPACITY;
    }

    wrappedIndex = DI;

  } // close else-if

  else
    wrappedIndex = DI;

} // close setWrappedIndex

template <class DataType>
bool HashTable<DataType>::first(DataType& getData)
{
  assert(current >= -1 && current < HASHTABLE_CAPACITY);

  for (current = 0; current < HASHTABLE_CAPACITY; current++)
  {
    if (!aList[current].empty())
    {
      it = aList[current].begin();
      break;
    } 
  }

  if (current == HASHTABLE_CAPACITY) current = -1;

  if (current == -1) return false;

  getData = *it;

  return true;
}


template <class DataType>
bool HashTable<DataType>::getNext(DataType& getData)
{
  assert(current >= -1 && current < HASHTABLE_CAPACITY);

  if (current == -1) return false;

  assert(!aList[current].empty());

  getData = *it++;

  if (it == aList[current].end())
  {
    for (current = current + 1; current < HASHTABLE_CAPACITY; current++)
    {
      if (!aList[current].empty())
      {
        it = aList[current].begin();
        break;
      } 
    } 
  }
  
  if (current == HASHTABLE_CAPACITY) current = -1;
  
  return current >= 0;
}


template <class DataType>
int HashTable<DataType>::getWrappedIndex() const
{
  return wrappedIndex;
}

template <class DataType>
int HashTable<DataType>::getSize() const
{
  return size;

} // close get size 


template <class DataType>
double HashTable<DataType>::getLoadFactor() const
{
  return size / HASHTABLE_CAPACITY;

}

template <class DataType>
bool HashTable<DataType>::retrieve(DataType& data, int DI)
{
  bool results = false;

  setWrappedIndex(DI);
  current = wrappedIndex;

   //   aList[current].empty()
  if (!aList[current].empty())
  {
    it = aList[current].begin();
    data = *it;
    results = true;

  }     

  return results;

}

#endif 

[jls36]

Ive tried using an STL "it" iterator but to find the exact match I had to pass the same node in to find it which kind of seems stupid. Is there a way to find the correct one by using aNode.instructor to detemine the right one I want.

Any Help would be nice Thanks.

[Peter87]

getData = *it++; is equivalent to getData = *it; it++;. Is that what you want?

I think you need to store the key together with the DataType value so that you can iterate the list to find the correct DataType in the list.

Are you doing this as an excessive? I just thought I should mention that C++ has hash tables already in case you didn't know.

[trailfrenzy]

When did the template for

std::list

include

operator[]

?

[Peter87]

trailfrenzy, aList is an array so you can use operator[] on it

[jls36]

I know about STL Hash Tables but my teacher wants us to create our own. Sorry but not sure what you mean by "excessive". I used the "it" to find the correct one. Thanks for your help. I made an array of STL list so thats why I used the [].

Thanks to all for any comments and help.