mercredi 31 mai 2017

Hash table doesn't read last line off of test file

I was assigned to create a chained hash table using a vector of vectors. It is designed to hold objects of type Entry. I have written all of the functions and the constructor but when I try to use the constructor that reads an input and then output it back to me in order of keys, whichever string was on the last line of the .txt file its reading from is gone. I think its a problem with my constructor because when I try to use get to get that specific value from the table before printing it its gone. I was hoping for some insight to where I might be going wrong from someone with a little more experience. Thanks. Heres my code:

Entry Header File:

#ifndef entry_h
#define entry_h

// entry.h - defines class Entry            


#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 */

Table header file:

//
//  table.h
//  
//
#ifndef table_h
#define table_h

#include <string>
#include <vector>
#include <algorithm>
#include "entry.h"

using namespace std;

class Table {

 public:
  Table(unsigned int max_entries = 100);
  //Builds empty table to hold 100 entries
  Table(unsigned int entries, std::istream& input);
  //Builds table to hold entries, reads and puts them 1 at a time
  ~Table();
  //Destructor
  void put(unsigned int key, std::string data);
  //Creates new entry for the table
  //Updates if key is used
  void put(Entry e);
  //Creates a copy of e in the table
  string get(unsigned int key) const;
  //Returns string associated with key
  //Returns empty string if key isnt used
  bool remove(unsigned int key);
  //Removes entry in given key
  //Returns true of removed, false of no entry
  int find(Entry e);
  //index in second array that e exists, 0 if not found
  friend std::ostream& operator<< (std::ostream& out, const Table& t);
  //Prints each entry in the table in order of their key


 private:
  int size;
  int num_entries;
  unsigned int hashkey(unsigned int key) const;

  vector<vector<Entry> > A;
};

#endif /* table_h */

Table Implementation File:

//table.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include "table.h"

using namespace std;


Table::Table(unsigned int max_entries){
  max_entries = 100;
  size = max_entries * 2;
  A.resize(size);
}

Table::Table(unsigned int entries, std::istream& input){
  size = entries*2;
  A.resize(size);
  num_entries = entries;
  Entry temp;
  for (size_t i = 0; i < entries; i++) {
    input >> temp;
    put(temp);
  }
}

/*
Table::~Table() {
  for (int i = 0; i <size; i++) {
    for (int j = 0; j < A[i].size(); j++) {
      delete A[i][j];
    }
  }
  }*/

Table::~Table() {
  A.clear();
}

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

void Table::put(Entry e) {
  /*if (!A[hashkey(e.get_key())].empty()) {
  // if (find(e) != 0) {
    for(int i = 0; i < A[hashkey(e.get_key())].size(); i++) {
      if(A[hashkey(e.get_key())][i].get_key() == e.get_key()){
    A[hashkey(e.get_key())][i] = e;
    return;
      }
    }
  }
  else {
    A[hashkey(e.get_key())].push_back(e);
    num_entries++;
    }*/

  if (A[hashkey(e.get_key())].empty()) {
    A[hashkey(e.get_key())].push_back(e);
    }
  else {
    for(size_t i = 0; i < A[hashkey(e.get_key())].size(); i++) {
    if (A[hashkey(e.get_key())][i].get_key() == e.get_key()) {
      remove(A[hashkey(e.get_key())][i].get_key());
      break;
    }
      }
   A[hashkey(e.get_key())].push_back(e);
  } 
}

string Table::get(unsigned int key) const {
  if( A[hashkey(key)].size() == 0) {
    return "";
  }
  else {
    for (size_t i = 0; i < A[hashkey(key)].size(); i++) {
      if (A[hashkey(key)][i].get_key() == key) {
    return A[hashkey(key)][i].get_data();
      }
      else {
    return "";
      }
    }
  }
}

bool Table::remove(unsigned int key) {
  for (size_t i = 0; i < A[hashkey(key)].size(); i++) {
    if (A[hashkey(key)][i].get_key() == key) {
    swap(A[hashkey(key)][i],A[hashkey(key)][A[hashkey(key)].size() - 1]);
    A[hashkey(key)].pop_back();
    num_entries--; 
        return true;
      }
      else {
    return false;
      }
  }
}

int Table::find(Entry e) {
  for (size_t i = 0; i < A[hashkey(e.get_key())].size(); i++) {
      if (A[hashkey(e.get_key())][i] == e) {
    return i;
      }
      else {
    return 0;
      }
  }
}

ostream& operator << (ostream& out, const Table& t) {
  vector<Entry> order;
  for(size_t i = 0; i < t.A.size(); i++) {
    for (size_t j = 0; j < t.A[i].size(); j++) {
      order.push_back(t.A[i][j]);
    }
  }
  sort(order.begin(), order.end());
  for(Entry k: order) {
    out << k << endl;
  }
  return out;
}

unsigned int Table::hashkey(unsigned int key) const{
  const double c = 1.61803;
  // return key % size;
  return (int)(size*((key * c) - (int)(key * c)));
}

Aucun commentaire:

Enregistrer un commentaire