I am implementing a templated hash table that handles collision but I keep getting a segfault when I try testing it.
I have tried debugging it without any success and I was wondering if anyone could please help me discover the problem.
I am using my own linked list class and I have tested it well so I don't think the issue is there.
I am pretty new to Stack overflow so any help is appreciated
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <iostream>
#include <iomanip>
#include <functional>
#include "linkedlist.h"
using namespace std;
template<class K, class V>
class Hashtable{
private:
struct info{
K key;
V value;
info(K newKey, V newValue){
key = newKey;
value = newValue;
}
K getkey(){
return key;
}
V getValue(){
return value;
}
};
int size;
LinkedList<info> datalist[20];
public:
Hashtable();
Hashtable(Hashtable &rhs);
Hashtable& operator=(Hashtable &rhs);
~Hashtable();
void insert(K, V);
void remove(K);
V getValueByKey(K);
bool containsValue(K);
int getSize();
bool isHashtableEmpty();
};
template<class K, class V>
Hashtable<K, V>::Hashtable(int newsize)
{
if(newsize<20){
size=20;
}
else
{
size=newsize;
}
datalist = new LinkedList<info>[size];
// for(int i = 0; i < size; i++) {
// datalist[i] = new LinkedList<info>();
// }
}
template<class K, class V>
Hashtable<K, V>::Hashtable(Hashtable &rhs)
{
size=rhs.size;
datalist=new LinkedList<info> [size];
for(int i =0; i<size; i++)
{
datalist[i]=rhs.datalist[i];
}
}
template<class K, class V>
Hashtable<K, V>& Hashtable<K, V>::operator=(Hashtable<K, V> &rhs)
{
size=rhs.size;
if(datalist !=nullptr)
{
delete [] datalist;
}
datalist=new LinkedList<V> [size];
for(int i =0; i<size; i++)
{
datalist[i]=rhs.datalist[i];
}
return *this;
}
template<class K, class V>
Hashtable<K, V>::~Hashtable()
{
delete[] datalist;
datalist=nullptr;
}
template<class K, class V>
void Hashtable<K, V>::insert(K key, V value)
{
int index = hash<K>()(key) % size;
info obj(key, value);
datalist[index].add(obj);
}
template<class K, class V>
void Hashtable<K, V>::remove(K key)
{
int index=hash<K>()(key) % size;
datalist[index].remove(getValueByKey(key));
}
template<class K, class V>
V Hashtable<K, V>::getValueByKey(K newKey)
{
for(int i=0; i<size; i++)
{
for(int j=0; j<datalist[i].size(); j++)
{
if((datalist[i].operator [](j)).getkey()==newKey){
return datalist[i][j].getValue();
}
}
}
//need to throw an excpetion
}
template<class K, class V>
bool Hashtable<K, V>::containsValue(K newKey)
{
for(int i=0; i<size; i++)
{
for(int j=0; j<datalist[i].size(); j++)
{
if(datalist[i][j].getkey() == newKey){
return true;
}
}
}
return false;
}
template<class K, class V>
int Hashtable<K, V>::getSize()
{
return size;
}
template<class K, class V>
bool Hashtable<K, V>::isHashtableEmpty()
{
for(int i=0; i<size; i++)
{
if(datalist[i].size()!=0){
return false;
}
}
return true;
}
#endif // HASHTABLE_H
And here is my linked list
#ifndef LINKED_LIST
#define LINKED_LIST
#include<iostream>
#include <stdexcept>
//linked list class used for operating the nodes
template<class T>
class LinkedList {
//node class holds the data and pointer to the front and back of the node
class ListNode {
public:
template <class U> friend class LinkedList;
private:
ListNode* next;
ListNode* prev;
T data;
public:
ListNode() {next = nullptr; prev = nullptr;}
ListNode(T val): next(nullptr), prev(nullptr), data(val) {}
ListNode(const ListNode& rhs): next(nullptr), prev(nullptr), data(rhs.data) {}
};
public:
LinkedList();
LinkedList(T);
LinkedList(const LinkedList<T>&);
void add(T);
void addToFront(T);
T get(int);
int size();
T remove(int);
bool isEmpty();
bool find(T);
//T getNext();
//bool hasNext();
//void reset();
~LinkedList();
T& operator[] (int);
LinkedList<T>& operator=(LinkedList<T>&);
//encapsulation to protect data
private:
ListNode*head;
//ListNode* iterator;
int num_elements;
};
//defualt constractor intializes the list
template <class T>
LinkedList<T>::LinkedList(){
head = nullptr;
//iterator=nullptr;
num_elements = 0;
}
//head constructor initializes the list with one head element/object
template <class T>
LinkedList<T>::LinkedList(T data){
//node is dynamically allocated
ListNode* temp=new ListNode();
temp->data=data;
head=temp;
//iterator=head;
num_elements=1;
}
//copy constructor does a deep copy of another list
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& list){
if(this!=&list)
{
if(list.head == nullptr){
head = nullptr;
num_elements = 0;
}
else{
//The following constrcor part was partially taken from an algorithm from Cplusplus.com
//to node pointers are needed for each list
ListNode* curr1=nullptr;
ListNode* curr2=nullptr;
//number of elements is assignend by memebr acess
num_elements=list.num_elements;
curr2=list.head;
//head is dynamically allocated with curr2
head=new ListNode(*curr2);
//curr2=curr2->next;
curr1=head;
//while loop iterates over every element untill the list being copied reaches a nullpointer/the end
while(curr2->next!=nullptr){
//next allows us to jump to the next node
curr2=curr2->next;
curr1->next=new ListNode(*curr2);
curr1->next->prev=curr1;
curr1=curr1->next;
}
}
}
//iterator=head;
}
//destractor (rule of three)
template <class T>
LinkedList<T>::~LinkedList(){
ListNode* temp=nullptr;
//if the list is empty then destructor is complete
if(head==nullptr){
return;
}
else
{
//while loop iterates over every head untill everyithing is deleter
while(head!=nullptr){
temp=head;
head=head->next;
delete temp;
//delete iterator;
}
}
//members are initialized to null
num_elements=0;
head=nullptr;
//iterator=nullptr;
}
//add function
template <class T>
void LinkedList<T>::add(T data){
//dynamically alocates a new Node
ListNode* temp=new ListNode(data);
//curr is used to iterate through the list
ListNode* curr=head;
//if the list is empty then the data is assigned the first element
if(head==nullptr){
temp->data=data;
head=temp;
}
else
{
//while loop iterats through the list to find the last elment
while(curr->next!=nullptr){
curr=curr->next;
}
//once we reach the last element the data and the pointers are assgined
temp->data=data;
temp->prev=curr;
curr->next=temp;
}
//iterator=head;
num_elements++;
}
template <class T>
void LinkedList<T>::addToFront(T data){
//dynamically alocates a new Node
ListNode* temp=new ListNode();
//if the list is empty then the data is assigned the first element
if(head==nullptr){
temp->data=data;
head=temp;
}
else
{
//once we reach the last element the data and the pointers are assgined
temp->data=data;
temp->next=head;
head->prev=temp;
head=temp;
}
//iterator=head;
num_elements++;
}
template <class T>
T LinkedList<T>::get(int val){
//if the list is empty no
if(!isEmpty()){
//curr is used to iterate through the list
ListNode* curr=head;
int count=0;
//if the index is out of bound an exception is thrown
if(val <0 || val>num_elements){
throw std::out_of_range ("index is out of bound");
}
else
{
//while loop iterats through the list to find the desired index
while(val!=count){
count++;
curr=curr->next;
}
}
return curr->data;
} else {
throw std::out_of_range("List is empty");
}
//iterator=head;
}
//size function returns the number of elements
template <class T>
int LinkedList<T>::size(){
return num_elements;
}
//remove fuction
template <class T>
T LinkedList<T>::remove(int val){
ListNode* temp=head;
int count=0;
//if stament used to check if the list is empty
if(!isEmpty()){
//if the index is out of bound an exception is thrown
if(val <0 || val>num_elements){
throw std::out_of_range ("index is out of bound");
}
else
{
//while loop iterats through the list to find the desired index
while(val!=count){
count++;
temp=temp->next;
}
//if statments check for the apopraite way to remove an elment
//if there is only one element
if(temp->prev == nullptr && temp->next == nullptr){
head=nullptr;
}
//if the last element is being removed
else if(temp->next==nullptr && temp->prev != nullptr)
{
temp->prev->next=nullptr;
}
//if the first element is being remeoved
else if(temp->next!=nullptr && temp->prev == nullptr)
{
temp->next->prev=nullptr;
head = temp->next;
}
//if the middel element is being removed
else if(temp->next!=nullptr && temp->prev != nullptr)
{
//pointers are reassined to assure that data isnt lost
temp->prev->next=temp->next;
temp->next->prev=temp->prev;
}
}
}
T copy = temp->data;
//delete is used to remove the data that is requested
delete temp;
//number of elements is decreased by oe every time
num_elements--;
return copy;
}
//is empty uses number of elements to determine if the list contains data
template <class T>
bool LinkedList<T>::isEmpty(){
if(num_elements<=0){
return true;
}
return false;
}
//[] operatior funcition in exactly the same way a get function operates
template <class T>
T& LinkedList<T>::operator[] (int val){
ListNode* curr=head;
int count=0;
if(!isEmpty()){
if(val <0 || val>num_elements){
throw std::out_of_range ("index is out of bound");
}
else
{
while(val!=count){
count++;
curr=curr->next;
}
}
}
return curr->data;
}
//overloaded assignment operatior
template <class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList<T>& rhs){
if(this!=&rhs)
{
if(rhs.head == nullptr){
head = nullptr;
num_elements = 0;
}
else{
//The following constrcor part was partially taken from an algorithm from Cplusplus.com
//to node pointers are needed for each list
ListNode* curr1=nullptr;
ListNode* curr2=nullptr;
//number of elements is assignend by memebr acess
num_elements=rhs.num_elements;
curr2=rhs.head;
//head is dynamically allocated with curr2
head=new ListNode(*curr2);
//curr1->next=new ListNode(*curr2);
//curr2=curr2->next;
curr1=head;
//while loop iterates over every element untill the list being copied reaches a nullpointer/the end
while(curr2->next!=nullptr){
curr2=curr2->next;
curr1->next=new ListNode(*curr2);
curr1->next->prev=curr1;
//next allows us to jump to the next node
curr1=curr1->next;
}
}
}
//iterator=head;
return *this;
}
//find function(not part of the requirment)
template<class T>
bool LinkedList<T>::find(T data){
ListNode* temp=head;
if(!isEmpty()){
//While is used to go through the whole list
while(temp!=nullptr){
//if the desiderd data is in there then true is returned
if(temp->data==data){
return true;
}
temp=temp->next;
}
}
return false;
}
#endif
Aucun commentaire:
Enregistrer un commentaire