C++11 Table class implementation using std::vector and chained hashing. any othe

Question

C++11 Table class implementation using std::vector and chained hashing. any other solutions are wrong

Write table.h to define class Table as it is used in the demonstration program named tabledemo.cpp. Write table.cpp to implement your class Table. You may use tools from any of the standard libraries except <map>, <set>, <unordered_map> and <unordered_set>. Your Table must hold Entry objects as defined in entry.h (and implemented in entry.cpp). For the demonstration program to compile successfully, your table.h must define at least the following public functions:

One constructor that builds an empty Table designed to hold a maximum number of entries equal to the only parameter. This parameter should have a default value of 100:
   Table(unsigned int max_entries = 100)

Another constructor that builds a Table designed to hold the number of entries specified by the first parameter, and puts that many entries into the Table by reading them one at a time from the input stream that is the second parameter:
   Table(unsigned int entries, std::istream& input)
Do not input more than the specified number of entries. If you always read all of input, you will lose points for not satisfying this requirement.

Two (overloaded) member functions named put, each of which puts a new Entry into the Table:
   void put(unsigned int key, std::string data)
   void put(Entry e)
The first of these functions creates a new Entry to put in the Table. The second one puts a copy of the parameter in the Table. In cases where the Table already contains an Entry with the given key, these functions act to update the Entry for that key. The Table is not allowed to contain duplicate keys.

A constant member function named get that returns the string associated with the parameter:
   std::string get(unsigned int key) const
This function returns an empty string if the Table has no Entry with the given key.

A member function named remove that removes the Entry containing the given key:
   bool remove(unsigned int key)
This function returns true if it removes an Entry, or false if the Table has no such Entry.

A non-member output function that overloads the << operator to print the Table:
   std::ostream& operator<< (std::ostream& out, const Table& t)
This function is expected to print each Entry in the Table to a separate line of the given output stream in the order of their key values.

Your class may define other functions too, either public or private ones. In particular, you will probably want to add a hashing function to transform the key values - in our version, function hashkey is a private function. And of course, your class must define the private data a Table object stores.

HINT: You will probably want to use chained hashing for this lab. That means that each row in your Table will be of type std::vector<Entry>. It is often convenient to typedef that type to some shorter name, so your method signatures don’t get clunky.

//THIS IS ENTRY.H FILE provided

#ifndef entry_h

#define entry_h

// entry.h - defines class Entry for CS 32 PA1

#include <string>

#include <iosfwd>

class Entry {

  

public:

// constructor

Entry(unsigned int key = 0, std::string data = "");

  

// access and mutator functions

unsigned int get_key() const;

std::string get_data() const;

static unsigned int access_count();

void set_key(unsigned int k);

void set_data(std::string d);

  

// operator conversion function simplifies comparisons

operator unsigned int () const;

  

// input and output friends

friend std::istream& operator>>

(std::istream& inp, Entry &e);

friend std::ostream& operator<<

(std::ostream& out, Entry &e);

  

private:

unsigned int key;

std::string data;

static unsigned int accesses;

};

#endif /* entry_h */

//THIS IS ENTRY.CPP File provided

//

// entry.cpp

// Lab05

//

// entry.cpp - implements class Entry

#include <stdio.h>

#include <iostream>

#include "entry.h"

using namespace std;

unsigned int Entry::accesses = 0;

Entry::Entry(unsigned int key, std::string data)

: key(key), data(data) { }

unsigned int Entry::get_key() const

{ ++accesses; return key; }

std::string Entry::get_data() const

{ return data; }

unsigned int Entry::access_count()

{ return accesses; }

void Entry::set_key(unsigned int k)

{ key = k; }

void Entry::set_data(std::string d)

{ data = d; }

Entry::operator unsigned int () const

{ return get_key(); }

istream& operator>> (istream& inp, Entry &e) {

inp >> e.key;

// get data in two parts to handle white space

string first_word, rest_of_line;

inp >> first_word;

getline(inp, rest_of_line);

e.data = first_word + rest_of_line;

return inp;

}

ostream& operator<< (ostream& out, Entry &e) {

out << e.get_key() << ": " << e.get_data();

return out;

}

//THIS IS tabledemo.cpp file provided

//

// tabledemo.cpp

// Lab05

// tabledemo.cpp - demonstration program for Table

// cmc, 4/4/2016

#include <stdio.h>

#include <iostream>

#include <fstream>

#include "table.h"

using namespace std;

unsigned int user_get(Table &t);

unsigned int user_remove(Table &t);

int main() {

  

cout << "Demonstrate very small table ";

Table t(5);

t.put(7, "seven");

t.put(9, "nine");

t.put(17, "Seventeen");

t.put(4, "four");

t.put(36, "Thirty-six");

cout << t;

cout << "key accesses: " << Entry::access_count() << endl;

  

cout << " Now demonstrate default size table ";

Table t2;

Entry e;

unsigned int count = 0;

cout << "Enter up to 100 entries for a new table. "

<< "(enter 0 key and random data to quit) ";

do {

cin >> e;

if (e.get_key() == 0) break;

t2.put(e);

++count;

} while(count < 100);

cout << t2;

cout << "Try removing some entries (enter 0 to quit) ";

while (user_remove(t2) != 0)

;

cout << t2;

  

cout << " Finally demonstrate larger table ";

ifstream input;

input.open("fips.txt");

if (!input.good()) {

cout << "No fips.txt in current directory. Quitting ";

return 1;

}

Table t3(3142, input);

cout << "Try getting some entries by FIPS code keys "

<< "(enter 0 key to quit) ";

while (user_get(t3) != 0)

;

cout << "Print large table to sortedfips.txt? ";

char ans;

cin >> ans;

if (ans == 'Y' || ans == 'y') {

unsigned int start = Entry::access_count();

ofstream out;

out.open("sortedfips.txt");

out << t3;

out.close();

cout << "done writing to sortedfips.txt ... required "

<< Entry::access_count() - start << " accesses ";

}

return 0;

}

unsigned int user_get(Table &t) {

unsigned int key;

cout << "Enter key to get: ";

cin >> key;

if (key != 0) {

unsigned int start = Entry::access_count();

cout << "data at key " << key << ": " << t.get(key) << endl;

cout << "(accesses: " <<

Entry::access_count() - start << ") ";

}

return key;

}

unsigned int user_remove(Table &t) {

unsigned int key;

cout << "Enter key to remove: ";

cin >> key;

if (key != 0) {

unsigned int start = Entry::access_count();

if (t.remove(key))

cout << "removed key: " << key << endl;

else

cout << "did not find key: " << key << endl;

cout << "(accesses: "

<< Entry::access_count() - start << ") ";

}

return key;

}

Explanation / Answer

tabledemo.cpp

// tabledemo.cpp - demonstration program for Table

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

unsigned int user_get(Table &t);
unsigned int user_remove(Table &t);

int main() {
  
    cout << "Demonstrate very small table ";
    Table t(5);
    t.put(7, "seven");
    t.put(9, "nine");
    t.put(17, "Seventeen");
    t.put(4, "four"); //changed
    t.put(36, "Thirty-six");
    cout << "key accesses: " << Entry::access_count() << endl;
    cout << t;
    cout << "key accesses: " << Entry::access_count() << endl;
  
    cout << " Now demonstrate default size table ";
    Table t2;
    Entry e;
    unsigned int count = 0;
    cout << "Enter up to 100 entries for a new table. "
        << "(enter 0 key and random data to quit) ";
    do {
        cin >> e;
        if (e.get_key() == 0) break;
        t2.put(e);
        ++count;
    } while(count < 100);
    cout << t2;
    cout << "Try removing some entries (enter 0 to quit) ";
    while (user_remove(t2) != 0)
        ;
    cout << t2;
  
    cout << " Finally demonstrate larger table ";
    ifstream input;
    input.open("fips.txt");
    if (!input.good()) {
        cout << "No fips.txt in current directory. Quitting ";
        return 1;
    }
    Table t3(3142, input);
    cout << "Try getting some entries by FIPS code keys "
        << "(enter 0 key to quit) ";
    while (user_get(t3) != 0)
        ;
    cout << "Print large table to sortedfips.txt? ";
    char ans;
    cin >> ans;
    if (ans == 'Y' || ans == 'y') {
        unsigned int start = Entry::access_count();
        ofstream out;
        out.open("sortedfips.txt");
        out << t3;
        out.close();
        cout << "done writing to sortedfips.txt ... required "
             << Entry::access_count() - start << " accesses ";
    }
    return 0;
}

unsigned int user_get(Table &t) {
    unsigned int key;
    cout << "Enter key to get: ";
    cin >> key;
    if (key != 0) {
        unsigned int start = Entry::access_count();
        cout << "data at key " << key << ": " << t.get(key) << endl;
        cout << "(accesses: " <<
            Entry::access_count() - start << ") ";
    }
    return key;
}

unsigned int user_remove(Table &t) {
    unsigned int key;
    cout << "Enter key to remove: ";
    cin >> key;
    if (key != 0) {
        unsigned int start = Entry::access_count();
        if (t.remove(key))
            cout << "removed key: " << key << endl;
        else
            cout << "did not find key: " << key << endl;
        cout << "(accesses: "
            << Entry::access_count() - start << ") ";
    }
    return key;
}

entry.cpp

// entry.cpp - implements class Entry,
// including instance counts for PA2

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

unsigned int Entry::accesses = 0;
unsigned int Entry::instances = 0;

Entry::Entry(unsigned int key, std::string data)
: key(key), data(data) { ++instances; }

Entry::Entry(const Entry &other)
: key(other.key), data(other.data){ ++instances; }

Entry::~Entry() { --instances; }

unsigned int Entry::get_key() const
{ ++accesses; return key; }

std::string Entry::get_data() const
{ return data; }

unsigned int Entry::access_count()
{ return accesses; }

unsigned int Entry::instance_count()
{ return instances; }

void Entry::set_key(unsigned int k)
{ key = k; }

void Entry::set_data(std::string d)
{ data = d; }
  
Entry::operator unsigned int () const
{ return get_key(); }

istream& operator>> (istream& inp, Entry &e) {
    inp >> e.key;
    // get data in two parts to handle white space
    string first_word, rest_of_line;
    inp >> first_word;
    getline(inp, rest_of_line);
    e.data = first_word + rest_of_line;
    return inp;
}

ostream& operator<< (ostream& out, Entry &e) {
    out << e.get_key() << ": " << e.get_data();
    return out;
}

entry.h

// entry.h - defines class Entry for CS 32 PA2

#ifndef ENTRY_H
#define ENTRY_H

#include <string>
#include <iosfwd>

class Entry {

public:
    // constructors and destructor
    Entry(unsigned int key = 0, std::string data = "");
    Entry(const Entry &other);
    ~Entry();
  
    // access and mutator functions
    unsigned int get_key() const;
    std::string get_data() const;
    static unsigned int access_count();
    static unsigned int instance_count();
    void set_key(unsigned int k);
    void set_data(std::string d);
  
    // operator conversion function simplifies comparisons
    operator unsigned int () const;
  
    // input and output friends
    friend std::istream& operator>>
        (std::istream& inp, Entry &e);
    friend std::ostream& operator<<
        (std::ostream& out, Entry &e);
  
private:
    unsigned int key;
    std::string data;
    static unsigned int accesses;
    static unsigned int instances;
};

#endif

table.cpp
// entry.cpp - implements class Entry

#include "entry.h"
#include "table.h"
#include <iostream>
#include <sstream>

#include <typeinfo>

using namespace std;

//functions: put, get and remove

Table::Table(unsigned int max_entries)
   : entries(max_entries), capacity(6*max_entries+1), used(0) {
   //string mynewTable[max_entries]; //put above instead
   for (int i=0; i<capacity; i++) {
       Entry empty;
       myTable.push_back(empty);
   }
}

Table::Table(unsigned int entries, std::istream &input)
   : entries(entries), capacity(6*entries+1), used(0) {
   int count =0;
   for (int i=0; i<capacity; i++) {
       Entry empty;
       myTable.push_back(empty);
   }
   for (int i=0; i<entries; i++) {
       Entry newEntry;
       input >> newEntry;
       put(newEntry);
   }
}

/*
Table::Table(const Table &t) {
   cout << "Copy constructor is alive" << endl;
}*/

void Table::put(unsigned int key, std::string data) {
   Entry newEntry;
   newEntry.set_key(key);
   newEntry.set_data(data);
   put(newEntry);
}

void Table::put(Entry e) {
   int quad = 5;
   int putKey = hash(e.get_key(), capacity);
   while( ( (myTable[putKey]).get_data() != "") && ( (myTable[putKey]).get_data() != "removed") ) {
       if(e.get_key() == (myTable[putKey]).get_key()){
           myTable[putKey] = e;
           return;
       }
       putKey = hash(putKey + quad^2, capacity);
       quad++;
   }  
   myTable[putKey] = e;
   used++;
}

string Table::get(unsigned int key) const {
   int quad = 5;
   int getKey = hash(key, capacity);
   while( (myTable[getKey]).get_data() != "" ) {
       if( (myTable[getKey]).get_key() == key ) {
           if( (myTable[getKey]).get_data() == "removed" ) {
               return "";
           } else {
               return (myTable[getKey]).get_data();
           }
       }
       getKey = hash(getKey + quad^2, capacity);
       quad++;
   }
   return "";
}

bool Table::remove(unsigned int key) {
   Entry delEnt(key, "removed");
   int quad = 5;
   int remKey = hash(key, capacity);
   if((myTable[remKey]).get_data() == "") {
       return false;
   }
   while((myTable[remKey]).get_key() != key){
       if(((myTable[remKey]).get_data() == "")) {
           return false;
       }
       remKey = hash(remKey + quad^2, capacity);
       quad++;
   }
   if((myTable[remKey]).get_data() == "removed") {
       return false;
   }
   myTable[remKey] = delEnt;
   used--;
   return true;
}

int Table::hash(unsigned int key, int mod_value) const {
   return key*611953 % (mod_value);
}

void Table::print() {
   string s = "";
   for(int n=0; n<entries; n++) {
       s += toString(myTable[n]) + " ";
   }
   cout << s << endl;
}

string Table::toString(Entry e) {
    stringstream s;
    s << e;
    return s.str();
}

int Table::tellMax() const {
   return capacity;
}

Entry Table::tellEntry(int i) const {
   return myTable[i];
}

int Table::partition(vector<Entry>& A, int left, int right, int who) {
for (int i=left; i<right; ++i) {
    if (A[i] <= who) {
      swap(A[i], A[left]);
      left ++;
    }
}
return left - 1;
}

void Table::qsort(vector<Entry>& A, int left, int right) {
if (left >= right) {
   return;
}
int middle = left + (right - left) / 2;
swap(A[middle], A[left]);
int midpoint = partition(A, left + 1, right, A[left]);
swap(A[left], A[midpoint]);
qsort(A, left, midpoint);
qsort(A, midpoint + 1, right);
}

int Table::getUsed() const {
   return used;
}

/*
Table& Table::operator=(Table t) {
return *this;
}

Table::~Table() {
   delete [] ptrmyTable;
}*/

ostream& operator<< (ostream &out, const Table &paramTable) {
   //
   int next = 0;
   Table t = paramTable;
   vector<Entry> temp;
   //Entry temp[t.getUsed()];
   for(int i = 0; i < t.tellMax(); i++) {
       if(((t.myTable[i]).get_data() != "") && ((t.myTable[i]).get_data() != "removed")){
           temp.push_back(t.myTable[i]);
       }
   }
   t.qsort(temp, 0, t.getUsed());
   //printer
   for(int n=0; n<t.getUsed(); n++) {
       Entry e = temp[n];
       out << e << endl;
   }
   return out;
}

unsigned int Table::accesses = 0;

table.h

//table.h - defines class Table for CS 32 PA1

#ifndef TABLE_H
#define TABLE_H

#include <string>
#include <iosfwd>
#include "entry.h"
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class Table {

public:

    //typedef Entry* EntryType;

    // constructor
    Table(unsigned int max_entries = 100); //given
    Table(unsigned int entries, istream &input); //given
    //Table(const Table &t); //copy constructor

    //read one at a time from the input stream,
    //do not input more than entries

    // access and mutator functions
    void put(unsigned int key, string data); //given
    void put(Entry e); //given
    //if table already contains entry with key then update
    string get(unsigned int key) const; //given
    //returns just the string attached to the key
   bool remove(unsigned int key); //given
    //returns true if Entry was there, false otherwise

    //MY FUNCTIONS
    void print(); //prints table
    string toString(Entry e); //returns string of entry
    int tellMax() const;
    Entry tellEntry(int i) const;
    int partition(vector<Entry>& A, int left, int right, int who);
    void qsort(vector<Entry>& A, int left, int right);
    int getUsed() const;

    //FOR HW2
    //Table& operator=(Table t);
    //~Table();
    // operator conversion function simplifies comparisons
    //operator unsigned int () const;
  
    // input and output friends
    /*friend istream& operator>>
        (istream& inp, Entry &e);*/
    friend ostream& operator<<
        (ostream &out, const Table &t);
  
private:
    static unsigned int accesses;
    unsigned int max_entries;
    string data;
    unsigned int entries;
    string input;

    vector<Entry> myTable;
    int hash(unsigned int key, int mod_value) const; //hashes key
    unsigned int used;
    unsigned int capacity;

    //vector<Entry> *ptrmyTable;
};

ostream& operator<< (ostream &out, const Table &paramTable); //given
//print each entry in the table in a separate line of the given output stream
//in order of their key values

#endif

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.