Solved: hashing and database | Experts Exchange

ASKER

I got ten files like this with ten restaurants(at least) each:

Name: Dario's Gourmet
Address: Route 156, km. 8
Phone number: 890-6143
Specialty: Continental

Name: Dos Amigos
Address: Route 107, km. 2.1
Phone number: 882-8000
Specialty: Puerto Rican

Name: Golden Crown
Address: Route 110, km. 9.2
Phone number: 890-2016
Specialty: Chinese

Name: Molina's Restaurant
Address: Route 2, km. 124.5
Phone number: 891-1487
Specialty: Sea Food

Name: Cathy's Chinese Restaurant
Address: Route 459, km. 2.9, Bo. Esteves
Phone number: 891-1720
Specialty: Chinese

Name: Bohio
Address: Route 102, km. 13.9
Phone number: 851-2755
Specialty: Sea Food

Name: Cascada
Address: Parador Boquemar
Phone number: 851-2158
Specialty: Sea Food

..
..
..

The file name are the towns where the restaurants are located.

milalik

ASKER

The classes for the hashtable that I am using are:

#ifndef __AbsHash
#define __AbsHash
// HashTable abstract class interface
//
// Etype: must have zero-parameter constructor and
// operator==; implementation may require operator!=;
//implementation will require either
// operator= or copy constructor, perhaps both
// unsigned int Hash( const Etype & Element, int TableSize )
// must be defined
// CONSTRUCTION: with (a) no initializer;
// copy constructor of HahsTable objects is DISALLOWED
//
// ******************PUBLIC OPERATIONS*********************
// All of the following are pure virtual functions
// int Insert( Etype X ) --> Insert X
// int Remove( Etype X ) --> Remove X
// Etype Find( Etype X ) --> Return item that matches X
// int WasFound( ) --> Return 1 if last Find succeeded
// int IsFound( Etype X ) --> Return 1 if X would be found
// int IsEmpty( ) --> Return 1 if empty; else return 0
// int IsFull( ) --> Return 1 if full; else return 0
// void MakeEmpty( ) --> Remove all items

template <class Etype>
class AbsHTable
{
public:
AbsHTable( ) { }
virtual ~AbsHTable( ) { }

virtual int Insert( const Etype & X ) = 0;
virtual int Remove( const Etype & X ) = 0;
virtual const Etype & Find( const Etype & X ) = 0;
virtual int WasFound( ) const = 0;
virtual int IsFound( const Etype & X ) const = 0;
virtual int IsEmpty( ) const = 0;
virtual int IsFull( ) const = 0;
virtual void MakeEmpty( ) = 0;

private:
// Disable copy constructor
AbsHTable( const AbsHTable & ) { }
};
#endif

milalik

ASKER

// HashTable class interface
//
// Etype: must have zero-parameter and copy constructor,
// operator= and operator!=
// unsigned int Hash( const Etype & Element, int TableSize )
// must be defined
// CONSTRUCTION: with (a) no initializer;
// Copy constructon of HashTable objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS*********************
// int Insert( Etype X ) --> Insert X
// int Remove( Etype X ) --> Remove X
// Etype Find( Etype X ) --> Return item that matches X
// int WasFound( ) --> Return 1 if last Find succeeded
// int IsFound( Etype X ) --> Return 1 if X would be found
// int IsEmpty( ) --> Return 1 if empty; else return 0
// int IsFull( ) --> Return 1 if full; else return 0
// void MakeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Predefined exception is propogated if new fails

#ifndef __HashTable
#define __HashTable

#include "AbsHash.h"

template <class Etype>
class HashTable : public AbsHTable<Etype>
{
public:
enum KindOfEntry { Active, Empty, Deleted };

HashTable( );
~HashTable( ) { delete [ ] Array; }

const HashTable & operator=( const HashTable & Rhs );

int Insert( const Etype & X );
int Remove( const Etype & X ); // Return 1 if found, 0 if not
const Etype & Find( const Etype & X ); // Return item in table
int IsFound( const Etype & X ) const; // Return 1 if found
int WasFound( ) const; // Return 1 if last find ok
int IsEmpty( ) const;
int IsFull( ) const { return 0; } // Return 1 if full
void MakeEmpty( );
private:
struct HashEntry
{
Etype Element; // The item
KindOfEntry Info; // Active, empty, or deleted

HashEntry( ) : Info( HashTable<Etype>::Empty ) { }
HashEntry( const Etype & E, KindOfEntry i = Empty ) :
Element( E ), Info( i ) { }
};

enum { DefaultSize = 11 };

int ArraySize; // The size of this array
int CurrentSize; // The number of non-empty items
int LastFindOK; // True of last search was successful
HashEntry *Array; // The array of elements

// Some internal routines
void AllocateArray( );
unsigned int FindPos( const Etype & X ) const;
};
#endif

#include "Hash.h"

// Find next prime > N; assume N >= 5

int NextPrime( int N )
{
if( N % 2 == 0 )
N++;

for( ; ; N += 2 )
{
int i;

for( i = 3; i * i <= N; i += 2 )
if( N % i == 0 )
break;
if( i * i > N )
return N;
}
}

// Allocate the hash table array

template <class Etype>
void
HashTable<Etype>::AllocateArray( )
{
Array = new HashEntry[ ArraySize ];
}

// HashTable constructor

template <class Etype>
HashTable<Etype>::HashTable( ) : ArraySize ( DefaultSize )
{
AllocateArray( );
CurrentSize = 0;
}

// Clear the hash table

template <class Etype>
void
HashTable<Etype>::MakeEmpty( )
{
CurrentSize = 0;
for( int i = 0; i < ArraySize; i++ )
Array[ i ].Info = Empty;
}

// Return item in hash table that matches X
// Success can be tested by WasFound

template <class Etype>
const Etype &
HashTable<Etype>::Find( const Etype & X )
{
unsigned int CurrentPos = FindPos( X );
LastFindOK = Array[ CurrentPos ].Info == Active;
return Array[ CurrentPos ].Element;
}

// Routine to resolve collisions and locate
// cell that must contain X if X is found

template <class Etype>
unsigned int
HashTable<Etype>::FindPos( const Etype & X ) const
{
unsigned int i = 0; // The number of failed probes
unsigned int CurrentPos = Hash( X, ArraySize );

while( Array[ CurrentPos ].Info != Empty &&
Array[ CurrentPos ].Element != X )
{
CurrentPos += 2 * ++i - 1; // Compute ith probe
if( CurrentPos >= ArraySize ) // Implement the mod
CurrentPos -= ArraySize;
}

return CurrentPos;
}

// Test if X is in the hash table

template <class Etype>
int
HashTable<Etype>::IsFound( const Etype & X ) const
{
unsigned int CurrentPos = FindPos( X );
return Array[ CurrentPos ].Info == Active;
}

// Return true if last Find operation was successful

template <class Etype>
int
HashTable<Etype>::WasFound( ) const
{
return LastFindOK;
}

// Remove X from hash table
// Return true if X was removed; false otherwise

template <class Etype>
int
HashTable<Etype>::Remove( const Etype & X )
{
unsigned int CurrentPos = FindPos( X );

if( Array[ CurrentPos ].Info != Active )
return 0;

Array[ CurrentPos ].Info = Deleted;
return 1;
}

// Insert X into hash table
// Return false if Xis a duplicate; true otherwise
// Rehash automatically as needed

template <class Etype>
int
HashTable<Etype>::Insert( const Etype & X )
{
unsigned int CurrentPos = FindPos( X );

// Don't insert duplicates
if( Array[ CurrentPos ].Info == Active )
return 0;

// Insert X as active
Array[ CurrentPos ] = HashEntry( X, Active );
if( ++CurrentSize < ArraySize / 2 )
return 1;

// REHASHING CODE
// Save old table
HashEntry *OldArray = Array;
int OldArraySize = ArraySize;

// Create a new double-sized, empty table
CurrentSize = 0;
ArraySize = NextPrime( 2 * OldArraySize );
AllocateArray( );

// Copy table over
for( int i = 0; i < OldArraySize; i++ )
if( OldArray[ i ].Info == Active )
Insert( OldArray[ i ].Element );

// Recycle OldArray
delete [ ] OldArray;
return 1;
}

// Deep copy of the hash table

template <class Etype>
const HashTable<Etype> &
HashTable<Etype>::operator=( const HashTable<Etype> & Rhs )
{
if( this != &Rhs )
{
delete [ ] Array;
ArraySize = Rhs.ArraySize;
AllocateArray( );
for( int i = 0; i < ArraySize; i++ )
Array[ i ] = Rhs.Array[ i ];
CurrentSize = Rhs.CurrentSize;
}

return *this;
}

// Phoney IsEmpty routine

template <class Etype>
int
HashTable<Etype>::IsEmpty( ) const
{
return CurrentSize == 0; // Doesn't work with deletions
}

milalik

ASKER

I need to create a database of all the restaurants in this towns and be able to search for them using
the hashtable. I have only managed to do this:

#include<iostream>

#include<string>

#include "Hash.h"

#include "Hash.cc"

//using namespace std;

unsigned int Hash(const string & Key, int SizeOfTable);

main()

{

HashTable <string> Restaurants;

string name;

cout<<"Enter Name: ";
getline(cin,name);

Restaurants.Insert(name);

//To see if it is hashing it

const string &Result2= Restaurants.Find(name);

if(Restaurants.WasFound())

{

cout<<"Found "<< Result2;

cout<< '\n';

}

else

{

cout<<"not found; ";

cout<<'\n';

}

const string &Result3= Restaurants.Find("El Buho");

if(Restaurants.WasFound())

{

cout<<"Found "<< Result3;

cout<< '\n';

}

else

{

cout<<"El Buho not found ";

cout<<'\n';

}

return 0;

}

milalik

ASKER

abesoft suggested this:

The problem is that your CGI needs to access the "database" of information every time that it is called, so you have to either create a disk-based database system(that stores hash tables, indeces, etc on disk), or use a simple format on disk that you can read into
memory and generate the advanced data structures each time you use it.

Reading in 30 records will _not_ take very long. If you had millions of records (or even thousands) I would suggest you look into the first alternative.

The approach you should take is simple: create your database classes:

class Database{
public:
void Add( const char *datarecord)
{!!!1!!!}

char *LookupByName( const char *n);
void Read( const char *fileName)
{
// open the named file
// Read in each line
// Call Add for each item read
}
};

Then, when your app starts, Read() the database, then Lookup() the data you need. Obviously, the Add() routine will need to build up a hash table, etc, and the Lookup() routines will need to use
those data structures, but you already know how to do all of that. which include things like Add(), Lookup(), etc, and then write a routine that reads the db from disk and.....

milalik

ASKER

Does that means I have to rewrite the class hashtable that I have? Or does it means that I need to make those classes friends of this new one? I really need some help, with this. Been two months working with this I am stuck. I'll appreciate your help.

thanx

ntdragon

i don't understand is your hashtable uses disk space or memory
as i understood it on the disk so what the problem???

milalik

ASKER

what you do not understand? What you mean if it used disk space or memory?
I'm trying to build a database using it, and need help. i also want to search this database using a form, since I want to make a cgi application.

1. How can I make a databse using this hashtable?

milalik

ASKER

what you do not understand? What you mean if it used disk space or memory?
I'm trying to build a database using it, and need help. i also want to search this database using a form, since I want to make a cgi application.

1. How can I make a databse using this hashtable?

milalik

ASKER

secondary index?

milalik

ASKER

what you mean by this?
>>The other part of your assignment was (as I recall) to also have a listing based on another key. To accomplish this, you can make a second "index", which I expect would be a list of pointers to restaurants, so that the second index will contain pointers to the original restaurants, and you don't have duplication of restaurant data. This secondary index would also be a data member of the Database class.

milalik

ASKER

help

milalik

ASKER

Working on it, will post some code as soon as possible

ntdragon

i already told someone how to do these
read
https://www.experts-exchange.com/jsp/qShow.jsp?ta=cplusprog&qid=10332249

milalik

ASKER

read the question, don't understand how to use folders

ntdragon

ok
lets see
you have restaurants like:"res","boss",
"abc"
the idea of the folders is that you should have folders with names made of two letters and you should have all the combinations
like folder:aa,ab,ac,...,za,...zz
now each restaurant is placed in the floder that named as the two first letters of the restaurant name
like:"res" will be in folder "re"
"boss" will be in folder "bo"
"abc" will be in "ab"
all the info about the restaurant will be placed in a file placed in the right folder
now when you"ll search for a restaurant
you"ll check the two first letters
then go to the right folder and read the file of the restaurant you searched for

milalik

ASKER

why do I need folders?

abesoft

Under a DOS FAT-style file system (which unfortunately includes NTFS and FAT32), directory access is proportional to the size of the directory. If you have more than 1,000 or so files in a directory, the performance is terrible, and over 2,000 it really stinks. That's the main reason for dividing a huge file set into subdirectories.

It's the same reason that we use hash tables that send us into small linked lists, instead of putting all of the data into a single linked list.

Of course, you only have a couple of hundred restaurants, so it shouldn't be the problem.

milalik

ASKER

Yes you are right abesoft. I am working on the codes you suggested. Hope they work. I will post them as soon as possible

thanx