Perfect Hash Table Iteration
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Perfect Hash Table Iteration

  1. #1
    Join Date
    Mar 2007
    Posts
    42

    Perfect Hash Table Iteration

    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
    Code:
    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
    }

  2. #2
    Join Date
    Oct 2002
    Location
    Timisoara, Romania
    Posts
    14,360

    Re: Perfect Hash Table Iteration

    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?
    Marius Bancila
    Home Page
    My CodeGuru articles

    I do not offer technical support via PM or e-mail. Please use vbBulletin codes.

  3. #3
    Join Date
    Mar 2007
    Posts
    42

    Re: Perfect Hash Table Iteration

    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
    Code:
    #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
    Attached Images Attached Images  
    Last edited by kenny.kor; December 12th, 2008 at 04:43 PM. Reason: updated code, fixed and working

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center