Author Separate Chaining

[khal]

Hi, I downloaded the author code online but it does not compile and I don't understand why its not compiling?

#ifndef SEPARATE_CHAINING_H
#define SEPARATE_CHAINING_H

#include <vector>
#include <list>
#include <string>
#include <algorithm>
using namespace std;


int nextPrime( int n );

// SeparateChaining Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x )       --> Insert x
// bool remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// void makeEmpty( )      --> Remove all items
// int hash( string str ) --> Global method to hash strings

template <typename HashedObj>
class HashTable
{
  public:
    explicit HashTable( int size = 101 )
      : currentSize( 0 )
      { theLists.resize( 101 ); }

    bool contains( const HashedObj & x ) const
    {
        const list<HashedObj> & whichList = theLists[ myhash( x ) ];
        return find( whichList.begin( ), whichList.end( ), x ) != whichList.end( );
    }

    void makeEmpty( )
    {
        for( int i = 0; i < theLists.size( ); i++ )
            theLists[ i ].clear( );
    }

    bool insert( const HashedObj & x )
    {
        list<HashedObj> & whichList = theLists[ myhash( x ) ];
        if( find( whichList.begin( ), whichList.end( ), x ) != whichList.end( ) )
            return false;
        whichList.push_back( x );

            // Rehash; see Section 5.5
        if( ++currentSize > theLists.size( ) )
            rehash( );

        return true;
    }

    bool remove( const HashedObj & x )
    {
        list<HashedObj> & whichList = theLists[ myhash( x ) ];
        list<HashedObj>::iterator itr = find( whichList.begin( ), whichList.end( ), x );

        if( itr == whichList.end( ) )
            return false;

        whichList.erase( itr );
        --currentSize;
        return true;
    }

  private:
    vector<list<HashedObj> > theLists;   // The array of Lists
    int  currentSize;

    void rehash( )
    {
        vector<list<HashedObj> > oldLists = theLists;

            // Create new double-sized, empty table
        theLists.resize( nextPrime( 2 * theLists.size( ) ) );
        for( int j = 0; j < theLists.size( ); j++ )
            theLists[ j ].clear( );

            // Copy table over
        currentSize = 0;
        for( int i = 0; i < oldLists.size( ); i++ )
        {
            list<HashedObj>::iterator itr = oldLists[ i ].begin( );
            while( itr != oldLists[ i ].end( ) )
                insert( *itr++ );
        }
    }

    int myhash( const HashedObj & x ) const
    {
        int hashVal = hash( x );

        hashVal %= theLists.size( );
        if( hashVal < 0 )
            hashVal += theLists.size( );

        return hashVal;
    }
};

int hash( const string & key );
int hash( int key );

#endif

#include "SeparateChaining.h"
#include <iostream>
using namespace std;


/**
 * Internal method to test if a positive number is prime.
 * Not an efficient algorithm.
 */
bool isPrime( int n )
{
    if( n == 2 || n == 3 )
        return true;

    if( n == 1 || n % 2 == 0 )
        return false;

    for( int i = 3; i * i <= n; i += 2 )
        if( n % i == 0 )
            return false;

    return true;
}

/**
 * Internal method to return a prime number at least as large as n.
 * Assumes n > 0.
 */
int nextPrime( int n )
{
    if( n % 2 == 0 )
        n++;

    for( ; !isPrime( n ); n += 2 )
        ;

    return n;
}

/**
 * A hash routine for string objects.
 */
int hash( const string & key )
{
    int hashVal = 0;

    for( int i = 0; i < key.length( ); i++ )
        hashVal = 37 * hashVal + key[ i ];

    return hashVal;
}

/**
 * A hash routine for ints.
 */
int hash( int key )
{
    return key;
}

#include <iostream>
#include "SeparateChaining.h"
using namespace std;

    // Simple main
int main( )
{
    HashTable<int> H;

    const int NUMS = 4000;
    const int GAP  =   37;
    int i;

    cout << "Checking... (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        H.insert( i );
    for( i = 1; i < NUMS; i += 2 )
        H.remove( i );

    for( i = 2; i < NUMS; i += 2 )
        if( !H.contains( i ) )
            cout << "Contains fails " << i << endl;

    for( i = 1; i < NUMS; i += 2 )
    {
        if( H.contains( i ) )
            cout << "OOPS!!! " <<  i << endl;
    }

    return 0;
}

[devonrevenge]

do you know how to compile the headers first then run the source code with your linker all set against it?

[khal]

I am not sure I understand what you mean but the way I compile my code is g++ main.cpp SeparateChaining.cpp. I know thats correct.

[devonrevenge]

the whole linker thing does my head in but what i mean is you got your linker including the .Os?

[cire]

Hi, I downloaded the author code online but it does not compile and I don't understand why its not compiling?

Neither do we since you didn't include anything that might help us. Do you get an error message?

[Chervil]

What are the error messages that you get?

[Moschops]

This looks like some code that an old version of VC++ let by, when it shouldn't have.

I think it needs typename at the start of lines 61 and 88 in SeparateChaining.h, and in that same header file is an attempt on line 96 to use a function that has the prototype after that line. I also think there are some issues with const to non-const going on.

[khal]

Sorry I didnt include the error message. I assumed you guy would probably compile it but any ways here it is.

SeparateChaining.h: In member function `bool HashTable<HashedObj>::remove(const HashedObj&)':
SeparateChaining.h:61: error: expected `;' before "itr"
SeparateChaining.h:63: error: `itr' undeclared (first use this function)
SeparateChaining.h:63: error: (Each undeclared identifier is reported only once for each function it appears in.)
SeparateChaining.h: In member function `void HashTable<HashedObj>::rehash()':
SeparateChaining.h:88: error: expected `;' before "itr"
SeparateChaining.h:89: error: `itr' undeclared (first use this function)
SeparateChaining.h: In member function `bool HashTable<HashedObj>::remove(const HashedObj&) [with HashedObj = int]':
TestSeparateChaining.cpp:19:   instantiated from here
SeparateChaining.h:61: error: dependent-name ` std::list<HashedObj,std::allocator<_CharT> >::iterator' is parsed as a non-type, but instantiation yields a type
SeparateChaining.h:61: note: say `typename  std::list<HashedObj,std::allocator<_CharT> >::iterator' if a type is meant
SeparateChaining.h: In member function `void HashTable<HashedObj>::rehash() [with HashedObj = int]':
SeparateChaining.h:53:   instantiated from `bool HashTable<HashedObj>::insert(const HashedObj&) [with HashedObj = int]'
TestSeparateChaining.cpp:17:   instantiated from here
SeparateChaining.h:88: error: dependent-name ` std::list<HashedObj,std::allocator<_CharT> >::iterator' is parsed as a non-type, but instantiation yields a type
SeparateChaining.h:88: note: say `typename  std::list<HashedObj,std::allocator<_CharT> >::iterator' if a type is meant

 

[khal]

@devonrevenge I used Microsoft visual studio 2010 and got the same errors so I do not believe its my compiler.

[Moschops]

I used Microsoft visual studio 2010 and got the same errors so I do not believe its my compiler.

Older MS compiler were much less.... formal when dealing with this sort of thing. They would let all sorts of wrong things through, particularly in the field of iterators. As I said above, stick typename at the start of line 61 and 88, and many of those errors will vanish.

[khal]

@Moschops Thanks the typename did the trick run perfectly