Perfect Hash Table Iteration

[kenny.kor]

For a class assignment, I need to make a perfect hash table but I don't think my iterator works properly.

I tried a google search to look for some sample code or an explained implementation but didn't find much useful.

Does anyone know a website that might have some methods?

I don't think my code is wrong but it's not iterating properly, it might be just as useful if someone could look over the logic.


iterator object

template <class T>
class MyHashTablePIterator{
  const MyHashTableP<T>* host;  
  int i;

public:
  MyHashTablePIterator(){};
  MyHashTablePIterator(const MyHashTableP<T>& host);
  bool hasNext();
  T next();
};
// constructor

template <class T>
MyHashTablePIterator<T>::MyHashTablePIterator(const MyHashTableP<T>& host){
  MyHashTablePIterator::host = &host;

  for (i = 0; i < host.cap; i++)//finds first value
    if (host.status[i] == 0) break; //status array is bool, makes sure matching entry[i] has a value
}

template <class T>
T MyHashTablePIterator<T>::next(){
  const T& item = host->entry[i++]; //gets next value;

  for (; i < host->size(); i++)
    if (host->status[i] == 0) break;

  return item;
}

template <class T>
bool MyHashTablePIterator<T>::hasNext(){
  return i < host->cap; //finds end of array
}

[cilu]

You should remove the default constructor. It doesn't make sense.

You're checking the current index against host.cap and host.size(). Are they the same?

You haven't show us the hash table implementation. What is status?

Also, what is going wrong? Can you give us an example with what you expect and what you actually get?

[kenny.kor]

cap is capacity
size is N amount of values stored in the array
status is a int array (flag) that checks if the index in entry for a value.

I keep getting values returned with 90 as the last two digits of an id, one 50 at the end, and the rest are irrelevant values.

I made a very small mistake. I was only iterating N (number of values) values at the capacity number of times resulting in errors.

Code is fixed and fully working, thanks everyone for looking

full class implementation

#pragma once

#ifndef MYHASHTABLEP_H
#define MYHASHTABLEP_H

template <class T>
class MyHashTablePIterator;

template <class T>
class MyHashTableP{
  T *entry;
  int *status;
  int cap;
  int n;

  friend class MyHashTablePIterator<T>;
  int wrappedIndex(const T& target)const;
public:
  MyHashTableP(){cap = 101; n = 0; entry = new T[cap]; status = new int[cap]; for (int i = 0; i < cap; i++) status[i] = 1;}
  MyHashTableP(const MyHashTableP& a);
  ~MyHashTableP();
  int size()const;
  bool empty()const;
  bool retrieve(T& value)const;
  bool insert(const T& value);
  bool replace(const T& value);
  bool remove(T& value);
  void clear();
  void operator = (const MyHashTableP<T>& a);
};

template <class T>
MyHashTableP<T>::MyHashTableP(const MyHashTableP& a){
  cap = a.cap;
  n = a.n;
  entry = new T[cap];
  status = new bool[cap];

  for(MyHashTablePIterator<T> it(a); it.hasNext();)
    insert(it.next());
}

template <class T>
MyHashTableP<T>::~MyHashTableP(){
  delete[] status;
  delete[] entry;
}

template <class T>
int MyHashTableP<T>::size()const{
  return n;
}

template <class T>
bool MyHashTableP<T>::insert(const T& value){
  int wi = wrappedIndex(value);
  if(wi >= cap) 
    return false;
  else if(status[wi] == 0) 
    return false;

  entry[wi] = value;
  status[wi] = 0;
  n++;
  return true;
}

template <class T>
bool MyHashTableP<T>::remove(T& value){
  int wi = wrappedIndex(value);
  if(status[wi] == 1) return false;

  status[wi] = 1;//set to unused -- replaces value on next wrapped index insert;
  n--;
  return true;
}

template <class T>
bool MyHashTableP<T>::replace(const T& value){
  int wi = wrappedIndex(value);
  if(status[wi] == 1) return false;

  entry[wi] = value;
  return true;
}

template <class T>
bool MyHashTableP<T>::retrieve(T& value)const{
  int wi = wrappedIndex(value);
  if(status[wi] == 1) return false;
  else if(entry[wi] == value){
    value = entry[wi];
    return true;
  }
  return false;
}

template <class T>
bool MyHashTableP<T>::empty()const{
  return n != 0;
}

template <class T>
void MyHashTableP<T>::clear(){
  delete[] entry;
  for(int i = 0; i < cap; i++) status[i] = 1;
  entry = new T[cap];
}

template <class T>
int MyHashTableP<T>::wrappedIndex(const T &target)const{
  int value = target.hashCode();
  value = value &#37; cap;
  if(value < 0) return value += cap;
  return value;
}

template <class T>
void MyHashTableP<T>::operator = (const MyHashTableP<T>& a){
  delete[] status;
  delete[] entry;

  cap = a.cap;
  n = a.n;
  entry = new T[cap];
  status = new int[cap];

  for(MyHashTablePIterator<T> it(a); it.hasNext();)
    insert(it.next());
}

template <class T>
class MyHashTablePIterator{
  const MyHashTableP<T>* host;  
  int i;

public:
  MyHashTablePIterator(){};
  MyHashTablePIterator(const MyHashTableP<T>& host);
  bool hasNext();
  T next();
};
// constructor

template <class T>
MyHashTablePIterator<T>::MyHashTablePIterator(const MyHashTableP<T>& host){
  MyHashTablePIterator::host = &host;

  for (i = 0; i < host.cap; i++)
    if (host.status[i] == 0) break;
}

template <class T>
T MyHashTablePIterator<T>::next(){
  const T& item = host->entry[i++];

  for (; i < host->cap; i++)
    if (host->status[i] == 0) break;

  return item;
}

template <class T>
bool MyHashTablePIterator<T>::hasNext(){
  return i < host->cap;
}
#endif