Solved

Search engine

Posted on 2000-04-11
37
359 Views
Last Modified: 2010-04-10
Hi. As part of a class project of Data Structures in C++ I have to do a final project. It consist of making a search engine in C++ using at least two of the structures learned in class. The idea I have of the search engine is to let the user choose between two types of search. (the search engine is of restaurants). The person should be able to choose between search by restaurant name and search by location of it. The search by location of restaurant is gonna be done using a list. There would be a Record of the restaurants. It would look something like this:

restaurant name
type of food
next

next would be a pointer to the next record of the corresponding town. The list will have a series of towns like:

Aguadilla
Mayaguez
San Juan
.
.
.

Each town should have pointers to their town restaurant's records.  The result that is gonna be presented for the search is all the  restaurants name with their  type of food, its address..etc., of that town.

The search by restaurant name is gonna be made using a hash table that would have a pointer to the record of only that particular restaurant. the resutls that would appear in the html page would be the restaurant name, its address and type of food.


Like i said at the beggining my knowledge is limited to that class and some HTML. I need to find out as fast as possible how to make this work on a webpage. I need advice and help. Not that someone do the job for me. The structs that are mentioned here are being made. But i need to set up all the other details before May 8. Me passing the class depends on this.Any help as far as how do I make it work on the page, cuz that I have no idea, a book I can buy to learn this fast and any recommendations on the things explained would be greatly appreciated.

thanx,
milalic
0
Comment
Question by:milalik
  • 26
  • 8
  • 2
  • +1
37 Comments
 

Expert Comment

by:koniant
Comment Utility
You should do your own homework. But I trust you so far.

What you're going to want to do is hook this up with CGI. Let the web server take care of most of the stuff, right. I'll assume you want to read data when the program is started - quick and dirty. There are other ways to do it that are better, but you won't get extra points for them.

The first thing you need to know is that you're going to get info from the form in one of two ways - on the command line, or as part of the HTML header. I sugest going to the RFCs and checking the specs on those. Or taking apart any Perl CGI module might help. Second, the first thing you're going to write to cout is "Content-type: text/html\n\n". That tells it what you're sending. Now you can just feed it standard HTML to your hearts content.

Like I said, the RFCs will be helpful, and Perl modules because they are sometimes pretty forward.
0
 

Author Comment

by:milalik
Comment Utility
koniant......first, I am doing my homework...I am not asking for someone to do it...But i feel it is a little unfair that I have to do this to pass a class than only covers structures in C++ cuz this has to deal with CGI and HTML. About HTML I know a little, but I know nothing about CGI. I need help. and as part of this question I am gonna post codes of the classes I am making. I need help with the CGI part basically. Setting and making this work on the net. You haven't told me nothing so far that I haven't read about. If you could explain yourself some more it would be great.It is hard finding documentation about CGI and C++.
thanx
0
 

Author Comment

by:milalik
Comment Utility
Please try to post answer as comments if there ain't a problem with you. I want a few experts to get involved in this. Thanx
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
It sounds like you might want to talk to your instructor about this.  If you are having this much trouble with the assignment, then it is quite likely that others in your course are having the same problem.  Your instructor needs to know about it.  (They may also be able to point you in the right direction....)

Of course, doing research on your own is a good idea too.  The first step in running a CGI-based app is to get access to a web server.  You will probably be installing IIS on a Windows machine - There is a version called PWS that runs on NT, and also under 95/98.  Once you install this, there are online docs that can get you started on CGI's, etc.  PWS has a decent online help system that discusses "dynamic" web content.  Start there, if you can.

The most important thing to remember in CGI programming is that (for the most part) each output screen is generated by a separate run of your app, rather than a single app that responds to each request from the user.  In a conventional app, you respond to a whole bunch of operations from the user, and then exit when you are finished.  In a CGI, you exit as soon as you have displayed a "screen", and then another program (which could be the same one you are running) is run to perform the next user request.  [Did that help to confuse the issue?]

Hope this helps,
Gene
0
 

Expert Comment

by:koniant
Comment Utility
Alrighty - what you want to do is set up a little content server that will answer requests from your CGI. Sockets are easy - "man socket" on a UNIX machine will be quite helpful. So, you have a server sit there and loop forever accepting requests for data and sending the data back to the CGI.

The CGI only connects and the sends the pretty HTML down the cout pipe. As for HTML - read until you get two newlines in a row, I believe. Maybe not. Data either comes in on the command line (argv[]) or as part of the header you read in. I sugest going to perl.com and finding a Perl CGI library and taking it apart.
0
 

Author Comment

by:milalik
Comment Utility
koniant....I sugest going to perl.com and finding a Perl CGI library and taking it apart.
What you mean?
0
 

Author Comment

by:milalik
Comment Utility
abesoft... I talked to my instructor, he said that is the project. It was a random selection between papers he had. Nothing I could do in that part. So not everyone is having this problem. Just me and my partners.
0
 

Author Comment

by:milalik
Comment Utility
Suggestions about books are welcome. Cuz I need to get this going as soon as possible.The classes I need are almost done.
0
 
LVL 7

Expert Comment

by:KangaRoo
Comment Utility
Hi again.

There is a CGI topic area on EE, which may be usefull for that part of the problem at http://www1.experts-exchange.com/Computers/WWW/CGI/

The content server that koniant described could be developped using C++, correct?
0
 

Author Comment

by:milalik
Comment Utility
Can koniant or someone else explain this a little more:

Alrighty - what you want to do is set up a little content server that will answer requests from your CGI. Sockets are easy - "man socket" on a UNIX machine will be quite helpful. So, you have a server sit there and loop forever accepting requests for data and sending the data back to the CGI.

The CGI only connects and the sends the pretty HTML down the cout pipe. As for HTML - read until you get two newlines in a row, I believe. Maybe not. Data either comes in on the command line (argv[]) or as part of the header you read in. I sugest going to perl.com and finding a Perl CGI library and taking it apart.


thanx
0
 

Author Comment

by:milalik
Comment Utility
KangaRoo... I posted the question also there and both here and there are helping in different aspects I need to understand to make this work.Thing I appreciate a lot.

I am workinbg right know to make my classes work in the same program.My classes are being templates but I am having problems working with characters and reading info saved in a text.I'll post something soon if I keep stuck.

thanx again
0
 

Author Comment

by:milalik
Comment Utility
KangaRoo... I posted the question also there and both here and there are helping in different aspects I need to understand to make this work.Thing I appreciate a lot.

I am workinbg right know to make my classes work in the same program.My classes are being templates but I am having problems working with characters and reading info saved in a text.I'll post something soon if I keep stuck.

thanx again
0
 

Author Comment

by:milalik
Comment Utility
Help...its been since april 14, that a comment of an expert was made.
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
Have you looked into the suggestions that I made previously?  Specifically, have you installed a Web Server, and looked at the included documentation?  

I don't think you need to go to the low level that koniant was suggesting.  Basically, that suggestion was that you write your own web server, and also develop your software that will run on it.  (Not that that wouldn't work, but its really re-inventing the wheel.)
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
Have you looked into the suggestions that I made previously?  Specifically, have you installed a Web Server, and looked at the included documentation?  

I don't think you need to go to the low level that koniant was suggesting.  Basically, that suggestion was that you write your own web server, and also develop your software that will run on it.  (Not that that wouldn't work, but its really re-inventing the wheel.)
0
 

Author Comment

by:milalik
Comment Utility
Well, I'm using my university server for this. Is either UNIX or WINDOWS NT. I will use the web server they have. I just need to develop this application as I am doing it, with the hash table
0
 

Author Comment

by:milalik
Comment Utility
Does anyone knows how I can create folders In windows and Unix. Cuz I got and idea that is to make a folder called restaurants. inside that folder make folders with the first two letters of the restaurants I am going to hash. Inside each folder have a text for each restaurant that hash in the folder with their info. for example:

If i have allegy and algae, i will hash their first two letters al and make a folder of it inside the restaurants folder. Inside that folder named al there would be a file for algae.txt and allegy.txt


I have tried to find info on how to do this but I haven't found. I know the basics of how to read and write a file, but how do I make a folder?How do I make a folder inside a folder? How do I open a folder so I can open the file I want?
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
Under VC++, use _mkdir.  To "open" a folder, I guess you could use _chdir.
They are both in <direct.h>
0
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 

Author Comment

by:milalik
Comment Utility
does this work in unix?
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
Yes, unix uses
     #include <sys/types.h>
     #include <sys/stat.h>

     int mkdir(const char *path, mode_t mode);

IE: the leading underscore isn't there.  If you want to write code that compiles under both, then you can do something like:

#ifdef WIN32
int mkdir( const char *path, int /* unused*/)
{
   return _mkdir( path);
}
#endif

You had asked before how to "open" a directory, and I guessed that you would want to use _chdir/chdir.  On second thought, you probably want to use FindFirst and FindNext under NT, and something like this under UNIX

          #include <stdio.h>
          #include <dirent.h>

          main()
          {
               DIR *dirp;
               struct dirent *direntp;

               dirp = opendir( "." );
               while ( (direntp = readdir( dirp )) != NULL )
                    (void)printf( "%s\n", direntp->d_name );
               (void)closedir( dirp );
               return (0);
          }

Good luck!
0
 

Author Comment

by:milalik
Comment Utility
is this for C++? Can you explain it a little bit more?
Thanx for the goodluck, cuz I needit. trying to make a database using this and a hashtable. Need to make some folders iwhen I insert and put inside those folders some files. While inthe search I need to be able to open this folders and search and open the correspondin file.
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
Well, the code is actually C, but it will also work with a C++ compiler.  What it does is list the contents of a directory, which is one approach you could use to find the files you need to report to the user.

Personally, I'm not sure I would use the file system to implement a hash table.  Under DOS (IE: NT) systems, this is terribly slow when the directories get large.  Even for reasonably sized data sets, it seems pretty involved.

I think I would recommend using a single text file containing all of the data.  When your CGI starts, read in the file, and parse the data into your data structures (the hash table would be built in memory), then use those data structures to answer the question.  But there's always another way to do it, to quote Larry Wall.
0
 

Author Comment

by:milalik
Comment Utility
I just need to implement it in a way I use the insert and search function of the hash table. If i make the database in memory, would I have to compile it everytime the application runs? Do I have to do the insert and the search engine in the same program? can you explain me how to do this? i can post a hash table i have that do inserts and search. I have manage to do a main that do that.

but I need the search part to work with a database of like 30 restaurants. How I do this?
0
 

Author Comment

by:milalik
Comment Utility
Remeber this is for a CGI application.

thanx
0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
Yes, I know this is a CGI.  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.  And for a class assignment, that should be completely acceptable.  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 *LookupByCity( const char *city);
    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
0
 

Author Comment

by:milalik
Comment Utility
abesoft...I have a hashtable class done. With the hashtable I just need to implement the search byname. I don't understand why I have to do a class that makes a database if my hashtable has an insert function. Can you explain a more what you mean.
thanx
If you want I can paste or e-mail you the work that has been donde with this so far.
0
 

Author Comment

by:milalik
Comment Utility
Adjusted points from 200 to 250
0
 

Author Comment

by:milalik
Comment Utility
what this mean, the one in there?:

 void Add( const char *datarecord)
                     {!!!1!!!}
0
 

Author Comment

by:milalik
Comment Utility
how do i do this:

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.
0
 

Author Comment

by:milalik
Comment Utility
how do i do this:

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.
0
 

Author Comment

by:milalik
Comment Utility
I got ten files like this with ten restaurants 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

Name: Island View
Address: Route 102, km. 13.7
Phone number: 851-9264
Specialty: Sea Food

Name: Perichi's Restaurant
Address: Route 102, km. 14.3
Phone number: 851-3131
Specialty: Steak and Sea Food

Name: Tino's Restaurant
Address: Route 102, km. 13.5
Phone number: 851-2976
Specialty: Sea Food

Name: Tony's Restaurant
Address: Route 102, P.Arena
Phone number: 851-2500, 851-9565
Specialty: Puerto Rican and Sea Food

Name: Ocean Kitchen
Address: Route 101, km. 18.2, Boquer¢n
Phone number: 254-3040
Specialty: Sea Food

Name: Brisas de Joyuda
Address: Route 102, km. 14.2, Bo.Joyuda
Phone number: 851-2488
Specialty: Sea Food

Name: San Marino
Address: Route 102, km. 18.8
Phone number: 851-9520
Specialty: Italian

Name: Casa de Playa
Address: Route 102, km. 14.9, Bo.Joyuda
Phone number: 255-4265
Specialty: Sea Food

Name: Casona de Seraf¡n
Address: Route 102, km. 9.7
Phone number: 851-0066
Specialty: International, Steak and Sea Food


They are saved in a files with the town name.
0
 

Author Comment

by:milalik
Comment Utility
This is the program that is gonna do the search By Location:



#include<iostream>

#include<string> // for the string class

#include<fstream> // for file streams


/*This program is in charge of the search done by location.
What it does is that if the user enters the name of the town
it open that town file,if that file exists and printouts all
the info in that file*/

/*This file is missing the CGI manipulation stuff*/


main()

{

/*something goes here so that what is entered in the form is processed
and the assigned to the string townName, so it can be used by the
program*/

string townName, x("Mayaguez"), y("Aguada"), z("Aguadilla"), a("Rincon"), b("Cabo
Rojo");

cout<< "Enter the name of the town: "<<endl; //This is for purpose of testing
program

getline(cin,townName);

if (townName==x||townName==y||townName==z||townName==a||townName==b)

{

townName+=string(".txt");

fstream in(townName.c_str(),ios::in);
   if(!in)
   {
      /*if this happens the user should be sent to a page
      that tells to hit back button and start search again*/

      cout<<"The file does not exist";
      return 0;
   }
   string read;
   while(!in.eof())
   {
      getline(in,read);

      /*This are the results of this search which have to
      be output to the screen.If possible a link should be
      provided to a page with restaurant menu*/

      cout<<read<<"\n";
   }



}

return 0;

}
0
 

Author Comment

by:milalik
Comment Utility
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
0
 

Author Comment

by:milalik
Comment Utility
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
0
 

Author Comment

by:milalik
Comment Utility
// 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
}


0
 

Author Comment

by:milalik
Comment Utility
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;

}





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

{

   unsigned int HashedVal=0;

   for(int i=0;i<Key.length();i++)

     HashedVal=(HashedVal*127+Key[i])% SizeOfTable;

return HashedVal;

}


I'm lost. Need  help

thanx

0
 
LVL 2

Accepted Solution

by:
abesoft earned 250 total points
Comment Utility
The {!!!1!!!} was meant to mean "Fill in your own clever hash table code here".  This is the difficult part of your assignment, and that is where your instructor wanted you to figure out how to use a hash table in a real-world situation.

I think you will want to combine your hash routines into some class that does what my "Database" class does.  I was only writing up that class to give you an idea about how to do the read operation.

I'm getting a little lost in this question.  It looks like we've talked about three different topics now.  Perhaps it is time to close this thread and start a new one if you need help on some other aspect of the problem.
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now