CSCI 340 assignment8.cc

#include <iostream>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include<string>
#include <fstream>
#include <cstdio>
//Terina Burr
//Section One
//Due 10/30/15
//Assignment 6


#include "assignment8.h"
using namespace std;

// key is in form of letter-letter-digit
// compute sum <-- ascii(pos1)+ascii(pos2)+ascii(pos3)
// compute sum%htable_size
Entry* get_entry (const string& line) ;
string get_key (const string& line) ;

/***************************************************************
Function: HT

Use:    It is a contructor it initializes the hash table and sets table_size to s
Arguments:  1. s: hash table size default size is 11

Returns:   nothing
***************************************************************/

HT::HT(int s= 11 )
{
    hTable = new vector <Entry>(s);
    table_size = s;

}

/***************************************************************
Function: ~HT

Use:    it is a deconstructor that deletes the hash table
Arguments: none

Returns:   nothing
***************************************************************/


HT::~HT()
{

    delete hTable;

}

/***************************************************************
Function: search
Use:    it is a function that searches the hash table for certain key
Arguments:  1. key: item searching for

Returns:   - 1 if couldn’t find the key if the key is found then the position is returned
***************************************************************/

int HT::search(const string& key)
{
    int index = hashing(key);
    int x = 0;
 while ((*hTable)[(index + x) % table_size].key != key)//loop through the table till found
        {
                x++;
                if (x >= table_size)//if its not in there
                {
                        return -1;
                }
        }
    //return position
        return (index + x) % table_size;
}

/***************************************************************
Function: insert
Use:    used to insert an entry into hash table
Arguments:  1. e: entry that is inserted

Returns:   true or false if the item was inserted
***************************************************************/

bool HT :: insert ( const Entry& e )
{
    if (search(e.key) != -1)//if search was correct then
        {
                cerr << "Table already contains key " << e.key << endl;
                return false;
        }
        if (item_count >= table_size) //if table is full
        {
                cerr << "Table is full" << endl;
                return false;
        }
        int index = hashing(e.key);
        int x = 0;
        while ((*hTable)[(index+x)%table_size].key != "---") //while the entry is not empty
        {
                x++;
        }
        (*hTable)[(index + x)%table_size] = e;
        item_count++;
        return true;
}

/***************************************************************
Function: remove
Use:    it is a function that removes an item with the key s
Arguments:  1. s: key being removed

Returns:   false if not found true if removed and found
***************************************************************/

bool HT::remove(const string& s)
{
    int index = hashing(s);
        int x = 0;
        while ((*hTable)[(index + x) % table_size].key != s) //loop thru hash table while key isnt in there
        {
                x++;
                if (x >= table_size)
                {
                        return false;
                }
        }
        (*hTable)[(index + x) % table_size].key = "---";
        item_count--;
        return true;
}
/***************************************************************
Function: print
Use:    prints hash table entries
Arguments:  none

Returns:   none
***************************************************************/

void HT :: print ( )
{
        cout << endl;
        cout << "----Hash Table-----" << endl;
        Entry e;
        for (int i = 0; i < table_size; i++) //go through the hash tbale
        {
                if ((*hTable)[i].key != "---") //if the key isnt null
                {
                        e = (*hTable)[i];
                        cout << setw(2) << i;
                        cout << ": " << e.key << " " << e.description << endl;
                }
        }
        cout << "-------------------" << endl;
        cout << endl;
}

int HT::hashing(const string& key)
{
   return ((int)key[0] + (int)key[1] + (int)key[2])%table_size;
}

/***************************************************************
Function: get entry
Use:    gets entry from line of string
Arguments:  1. line: string being converted to entry

Returns:   pointer to an entry
***************************************************************/

Entry* get_entry (const string& line)
{
    Entry *h = new Entry();
        h->key = get_key(line);

    h->description = line.substr(6, line.length() - 1);

    return h;
}

/***************************************************************
Function: get_key
Use:    it gets line of input and parses it to return the key
Arguments:  1. line: string being converted to key

Returns:   string of key
***************************************************************/

string get_key (const string& line)
{
    if (line.length() < 5)
        return "";

    return line.substr(2, 3);
}

int main(int argc, char** argv ) {
    if ( argc < 2 ) {
        cerr << "argument: file-name\n";
        return 1;
    }

    HT ht;
    ifstream infile(argv[1], ios::in);
    string line;
    infile >> line;
    while ( !infile.eof() ) {
        if ( line[0] == 'A' ) {
            Entry* e = get_entry( line );
            ht.insert( *e );
            delete e;
        }
        else {
            string key = get_key(line);
            if ( line[0] == 'D' ) {
                cout << "Removing " << key << "...\n";
                bool removed = ht.remove( key );
                if ( removed )
                    cout << key << " is removed successfully...\n\n";
                else
                    cout << key << " does not exist, no key is removed...\n\n";
            }
            else if ( line[0] == 'S' ) {
                int found = ht.search( key );
                if ( found < 0 )
                    cout << key << " does not exit in the hash table ..." << endl << endl;
                else
                   cout << key << " is found at table position " << found << endl << endl;
            }
            else if ( line[0] == 'P' ) {
                cout << "\nDisplaying the table: " << endl;
                ht.print();
            }
            else
                cerr << "wrong input: " << line << endl;
        }
        infile >> line;

    }

    infile.close();
    return 0;
}