Question

Following class is only part of my program that uses a hash table to simulate a market's client database, client class is my main class which asks user to input client names and then creates a hash table which then users can look up client names. wasn't able to upload everything as it is too much code, but what I need is to modify my client class instead of me inputting data line by line, the program should read from a file. File should include something like John Doe 12345 etc so please help modify my code so it reads data from a file rather than asking for input.

//client class

using namespace std;

#include <iostream>

#include <string>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include "htable.h"

// note that the second constructor of el_t can be used to

// create key+name to add to the table.

int main()

{

htable hashTable;

el_t empty;

// int input = 0;

// char str[20];

  

string inputStr = " ";

string firstName = " ";

string lastName = " ";

int key;

int i = 0;

//{ **

// Loop:

// Interactively add about 20 keys and names to the table,

// making sure some of them collide. (function add)

// You can create el_t containing a key and name using a constructor.

cout << "Thank you for joining Mini Market Rewards club!" << endl;

while (i != -1){

cout << "Please Enter Your 5-Digit Mini Market ID, Enter -1 to quit: " ;

cin >> inputStr;

  

if (inputStr != "-1"){

if (inputStr[4]!=NULL && inputStr[5] == NULL) {

cout << "Enter First Name: " ;

cin >> firstName;

cout << "Enter Last Name: " ;

cin >> lastName;

key = atoi(inputStr.c_str()) / 50;

  

//key = atoi(inputStr);

el_t elem(key, firstName, lastName);

hashTable.add(elem);

i++;

}

}

else

i = -1;

}

  

// DisplayTable.

hashTable.displayTable();

  

int loopInput = 0;

// Loop:

while (loopInput != -1){

// Interactively look up names using keys. (function find)

cout << "To Find Customer, Enter 5-Digit Mini Market ID, Enter -1 to quit" << endl;

cin >> loopInput;

  

if (loopInput != -1){

// Display the key + name if found else error message.

loopInput /= 50;

el_t found = hashTable.find(loopInput);

if (found == empty)

cout << "Error: Element not Found" << endl;

else

cout << "Found Customer: " << found << endl;

}

}

}

// elem.cpp

#include "elem.h"

// blank element

el_t::el_t()

{

key = 0;

firstName = "";

lastName = "";

}

// initializing constructor to create an el_t object

el_t::el_t(int akey, string aname, string bname)

{

key = akey;

firstName = aname;

lastName = bname;

}

// overload == for search based on the key part only

bool el_t::operator==(el_t OtherOne)

{

if (key == OtherOne.key) return true; else return false;

}

// overload cout

ostream& operator<<(ostream& os, const el_t& E)

{

os << E.firstName << " " << E.lastName;

return os;

}

// elem.h

#include <iostream>

#include <string>

using namespace std;

class el_t

{

private:

int key; // key

string firstName; // customer first name

string lastName; // customer first name

  

public:

  

el_t(); // to create a blank el_t object

el_t(int, string, string); // to create an initialized el_t object

  

bool operator==(el_t); // overload == for search

// In search == is used to compare node elements

// but what does it mean for this client to compare

// node elements?

  

// this overloads cout for the el_t object

// This is a friend function since the receiver object is not el_t

friend ostream& operator<<(ostream&, const el_t&);

  

friend class htable; // client of this class is htable which needs access to the key part of el_t

};

// htable.cpp

using namespace std;

#include <iostream>

#include "htable.h"

htable::htable()

{}

htable::~htable()

{}

// a simple hash function that uses % TSIZE simply

int htable::hash(int key){

return key % TSIZE;

}

// adds the element to the table and returns slot#

int htable::add(el_t element)

{

int slot = hash(element.key); // hash with the key part

table[slot].addRear(element);

return slot;

}

// finds element using the skey and returns the found element itself

// or a blank element

el_t htable::find(int skey)

{

el_t E; // a blank element

int slot = hash(skey); // hash with skey

el_t selement; // this is the element to look for in slist

  

// initialize it with just the skey

selement.key = skey;

// call slist's search2 with selement which returns the found element

E = table[slot].search2(selement);

// return the found element from here

return E;

}

// displays the entire table with slot#s too

void htable::displayTable()

{

for (int i = 0; i < 37; i++) {

cout << i << ":" ;

//** call slist's displayAll

table[i].displayAll();

}

}

// htable.h

#include "slist.h"

const int TSIZE = 37; // 37 slots ; a prime number

class htable

{

private:

slist table[TSIZE]; // each node of slist is el_t

// as defined in elem.h

int hash(int); // private hash function

  

public:

htable();

~htable();

  

int add(el_t); // adds an element to the table and returns slot#

el_t find(int); // finds an element based on key and returns it

void displayTable(); // displays the table with slot#s  

};

Answer 1

public class HashTable {

   /**
    * Keys that have the same hash code are placed together in a linked list.  
    * This private nested class is used internally to implement linked lists.  
    * A ListNode holds a (key,value) pair.  
    */
   private static class ListNode {
      String key;
      String value;
      ListNode next;  // Pointer to next node in the list;
                      // A null marks the end of the list.
   }

   private ListNode[] table;  // The hash table, represented as
                              // an array of linked lists.

   private int count;  // The number of (key,value) pairs in the
                       // hash table.

   
   /**
    * Create a hash table with an initial size of 64.
    */
   public HashTable() {
      table = new ListNode[64];
   }

   
   /**
    * Create a hash table with a specified initial size.
    * Precondition: initalSize > 0.
    */
   public HashTable(int initialSize) {
      if (initialSize <= 0)
         throw new IllegalArgumentException("Illegal table size");
      table = new ListNode[initialSize];
   }

   
   /**
    * This method is NOT part of the usual interface for a hash table.  
    * It is here only to be used for testing purposes, and should be 
    * removed before the class is released for general use.  This 
    * lists the (key,value) pairs in each location of the table.
    */
   void dump() {
      System.out.println();
      for (int i = 0; i < table.length; i++) {
             // Print out the location number and the list of
             // key/value pairs in this location.
         System.out.print(i + ":");
         ListNode list = table[i]; // For traversing linked list number i.
         while (list != null) {
            System.out.print("  (" + list.key + "," + list.value + ")");
            list = list.next;
         }
         System.out.println();
      }
   } // end dump()

   
   /**
    * Associate the specified value with the specified key.
    * Precondition:  The key is not null.
    */
   public void put(String key, String value) {
      
      assert key != null : "The key must be non-null";
      
      int bucket = hash(key); // Which location should this key be in?
      
      ListNode list = table[bucket]; // For traversing the linked list
                                     // at the appropriate location.
      while (list != null) {
            // Search the nodes in the list, to see if the key already exists.
         if (list.key.equals(key))
            break;
         list = list.next;
      }
      
      // At this point, either list is null, or list.key.equals(key).
      
      if (list != null) {
            // Since list is not null, we have found the key.
            // Just change the associated value.
         list.value = value;
      }
      else {
             // Since list == null, the key is not already in the list.
             // Add a new node at the head of the list to contain the
             // new key and its associated value.
         if (count >= 0.75*table.length) {
               // The table is becoming too full.  Increase its size
               // before adding the new node.
            resize();
            bucket = hash(key);  // Recompute hash code, since it
                                 // depends on the table size.
         }
         ListNode newNode = new ListNode();
         newNode.key = key;
         newNode.value = value;
         newNode.next = table[bucket];
         table[bucket] = newNode;
         count++;  // Count the newly added key.
      }
   }

   
   /**
    * Retrieve the value associated with the specified key in the table, 
    * if there is any.  If not, the value null will be returned.
    * @param key The key whose associated value we want to find
    * @return the associated value, or null if there is no associated value
    */
   public String get(String key) {
      
      int bucket = hash(key);  // At what location should the key be?
      
      ListNode list = table[bucket];  // For traversing the list.
      while (list != null) {
            // Check if the specified key is in the node that
            // list points to.  If so, return the associated value.
         if (list.key.equals(key))
            return list.value;
         list = list.next;  // Move on to next node in the list.
      }
      
      // If we get to this point, then we have looked at every
      // node in the list without finding the key.  Return
      // the value null to indicate that the key is not in the table.
      
      return null;  
   }

   
   /**
    * Remove the key and its associated value from the table,
    * if the key occurs in the table.  If it does not occur,
    * then nothing is done.
    */
   public void remove(String key) {  
      
      int bucket = hash(key);  // At what location should the key be?
      
      if (table[bucket] == null) {
            // There are no keys in that location, so key does not
            // occur in the table.  There is nothing to do, so return.
         return; 
      }
      
      if (table[bucket].key.equals(key)) {
            // If the key is the first node on the list, then
            // table[bucket] must be changed to eliminate the
            // first node from the list.
         table[bucket] = table[bucket].next;
         count--; // Remove new number of items in the table.
         return;
      }
      
      // We have to remove a node from somewhere in the middle
      // of the list, or at the end.  Use a pointer to traverse
      // the list, looking for a node that contains the
      // specified key, and remove it if it is found.
      
      ListNode prev = table[bucket];  // The node that precedes
                                      // curr in the list.  Prev.next
                                      // is always equal to curr.
      ListNode curr = prev.next;  // For traversing the list,
                                  // starting from the second node.
      while (curr != null && ! curr.key.equals(key)) {
         curr = curr.next;
         prev = curr;
      }
      
      // If we get to this point, then either curr is null,
      // or curr.key is equal to key.  In the latter case,
      // we have to remove curr from the list.  Do this
      // by making prev.next point to the node after curr,
      // instead of to curr.  If curr is null, it means that
      // the key was not found in the table, so there is nothing
      // to do.
      
      if (curr != null) {
         prev.next = curr.next;
         count--;  // Record new number of items in the table.
      }
   }

   
   /**
    * Test whether the specified key has an associated value in the table.
    * @param key The key that we want to search for.
    * @return true if the key exists in the table, false if not
    */
   public boolean containsKey(String key) {
      
      int bucket = hash(key);  // In what location should key be?
      
      ListNode list = table[bucket];  // For traversing the list.
      while (list != null) {
            // If we find the key in this node, return true.
         if (list.key.equals(key))
            return true;
         list = list.next;
      }
      
      // If we get to this point, we know that the key does
      // not exist in the table.
      
      return false;
   }

   
   /**
    * Return the number of key/value pairs in the table.
    */
   public int size() {
      return count;
   }


   /**
    * Compute a hash code for the key; key cannot be null.
    * The hash code depends on the size of the table as
    * well as on the value returned by key.hashCode().
    */
   private int hash(Object key) {
      return (Math.abs(key.hashCode())) % table.length;
   }

   
   /**
    * Double the size of the table, and redistribute the
    * key/value pairs to their proper locations in the
    * new table.
    */
   private void resize() {
      ListNode[] newtable = new ListNode[table.length*2];
      for (int i = 0; i < table.length; i++) {
             // Move all the nodes in linked list number i into the new table.  
             // No new ListNodes are created.  The existing ListNode for each
             // key/value pair is moved to the newtable.  This is done by 
             // changing the "next" pointer in the node and by making a pointer 
             // in the new table point to the node.
         ListNode list = table[i]; // For traversing linked list number i.
         while (list != null) {
               // Move the node pointed to by list to the new table.
            ListNode next = list.next;  // The is the next node in the list.
               // Remember it, before changing the value of list!
            int hash = (Math.abs(list.key.hashCode())) % newtable.length;
               // hash is the hash code of list.key that is 
               // appropriate for the new table size.  The
               // next two lines add the node pointed to by list
               // onto the head of the linked list in the new table
               // at position number hash.
            list.next = newtable[hash];
            newtable[hash] = list;
            list = next;  // Move on to the next node in the OLD table.
         }
      }
      table = newtable;  // Replace the table with the new table.
   } // end resize()
   

} // end class HashTable

A Class for Testing:

/**
 * A little program to test the HashTable class.  Note that I
 * start with a really small table so that I can easily test
 * the resize() method.
 */

public class TestHashTable {

   public static void main(String[] args){
      HashTable table = new HashTable(2);  // Initial size of table is 2.
      String key,value;
      while (true) {
         System.out.println("\nMenu:");
         System.out.println("   1. test put(key,value)");
         System.out.println("   2. test get(key)");
         System.out.println("   3. test containsKey(key)");
         System.out.println("   4. test remove(key)");
         System.out.println("   5. show complete contents of hash table.");
         System.out.println("   6. EXIT");
         System.out.print("Enter your command:  ");
         switch ( TextIO.getlnInt()) {
         case 1:
            System.out.print("\n   Key = ");
            key = TextIO.getln();
            System.out.print("   Value = ");
            value = TextIO.getln();
            table.put(key,value);
            break;         
         case 2:
            System.out.print("\n   Key = ");
            key = TextIO.getln();
            System.out.println("   Value is " + table.get(key));
            break;         
         case 3:
            System.out.print("\n   Key = ");
            key = TextIO.getln();
            System.out.println("   containsKey(" + key + ") is " 
                  + table.containsKey(key));
            break;         
         case 4:
            System.out.print("\n   Key = ");
            key = TextIO.getln();
            table.remove(key);
            break;         
         case 5:
            table.dump();
            break;
         case 6:
            return;  // End program by returning from main()         
         default:
            System.out.println("   Illegal command.");
         break;
         }
         System.out.println("\nHash table size is " + table.size());
      }
   }

} // end class TestHashTable