Something wrong with hash table?

[Lukvang]

I'm pretty confused about this function I am trying to modify.. I was under the impression that templates can be used to replace any type of generic data.. I don't understand why this headInsert function giving me a no matching function error.. This is a lab assignment, but i'm having trouble understanding what is going wrong. We are learning hash tables right now.. and this part of the lab deals with chained hash tables for collision.

HashTable.cpp

#include <iostream>
#include <string>
#include "ListTools.cpp"
#include "HashTable.h"

using SavitchListTools::Node;
using SavitchListTools::search;
using SavitchListTools::headInsert;

namespace SavitchHashTable {

HashTable::HashTable() {
	for (int i = 0; i < SIZE; i++)
		hashArray[i] = NULL;
}

HashTable::~HashTable() {
	for (int i = 0; i < SIZE; i++) {
		Node<string> *next = hashArray[i];
		while (next != NULL) {
			Node<string> *discard = next;
			next = next->getLink();
			delete discard;
		}
	}
}

int HashTable::computeHash(string s) {
	int hash = 0;
	for (unsigned int i = 0; i < s.length(); i++) {
		hash += s[i];
	}
	return hash % SIZE;
}

bool HashTable::containsString(string target) const {
	int hash = this->computeHash(target);
	Node<string>* result = search(hashArray[hash], target);
	if (result == NULL)
		return false;
	else
		return true;
}

int HashTable::get(string target) const {
	int hash = this->computeHash(target);
	if(hashArray[hash] == NULL)
		return -1;
	else
		return hash;
}
/*
void HashTable::put(string s) {
	int hash = computeHash(s);
	if (search(hashArray[hash], s) == NULL) {
		// Only add the target if it's not in the list
		headInsert(hashArray[hash], s);
	}
}*/

void HashTable::put(string s, int n){
	int index = computeHash(s);
	if (search(hashArray[index],s) != NULL)
		return;
	else
		headInsert(hashArray[index],n ,s);


}

} /* namespace SavitchHashTable */

HashTable.h

#ifndef HASHTABLE_H_
#define HASHTABLE_H_

using SavitchListTools::Node;
using std::string;

namespace SavitchHashTable {

const int SIZE = 10;

class HashTable {
public:
   HashTable(); // Initialize empty hash table
      // Normally a copy constructor and overloaded assignment
      // operator would be included.  They have been omitted
      // to save space.
   virtual ~HashTable();  // Destructor destroys hash table

   bool containsString(string target) const;
      // Returns true if target is in the hash table,
      // false otherwise
  int get(string target) const;

   void put(string s);
      // Adds a new string to the hash table

   void put(string s, const int n);

 private:
      Node<string> *hashArray[SIZE];
      static int computeHash(string s);   // Compute hash value for string
      static int computeHash(string s, int n);
}; // HashTable

} /* namespace SavitchHashTable */
#endif /* HASHTABLE_H_ */ 

ListTools.cpp

#include "ListTools.h"
#include <cstddef>
namespace SavitchListTools {

template<class T>
void headInsert(Node<T>*& head, const T& strData, const T& intData) {
	head = new Node<T>(strData, intData, head);
}

template<class T>
void insert(Node<T>* afterMe, const T& strData, const T& intData) {
	afterMe->setLink(new Node<T>(strData, intData, afterMe->getLink()));
}

template<class T>
void deleteNode(Node<T>* before) {
	Node<T> *discard;
	discard = before->getLink();
	before->setLink(discard->getLink());
	delete discard;
}

template<class T>
void deleteFirstNode(Node<T>*& head) {
	Node<T> *discard;
	discard = head;
	head = head->getLink();
	delete discard;
}

template<class T>
Node<T>* search(Node<T>* head, const T& target) {
	Node<T>* here = head;

	if (here == NULL) { //if empty list
		return NULL;
	} else {
		while (here->getData() != target && here->getLink() != NULL)
			here = here->getLink();

		if (here->getData() == target)
			return here;
		else
			return NULL;
	}
}

} /* namespace SavitchListTools */

ListTools.h

#ifndef LISTTOOLS_H_
#define LISTTOOLS_H_

namespace SavitchListTools {

/*
 * Node class - a single node in a linked list
 */
template<class T>
class Node {
public:
	Node(const T& strData, const T& intData, Node<T>* theLink) :
			strData(strData),intData(intData), link(theLink) {
	}
	Node<T>* getLink() const {
		return link;
	}
	const T& getData() const {
		return strData;
	}
	void setData(const T& iStrData, const T& iIntData) {
		iStrData = strData;
		iIntData = intData;
	}
	void setLink(Node<T>* pointer) {
		link = pointer;
	}
private:
	T strData;
	T intData;
	Node<T> *link;
};

/*
 * headInsert
 * - Precondition: The pointer variable head points to the head of
 *   a linked list.
 * - Postcondition: A new node containing "theData" has been added
 *   at the head of the linked list.
 */
template<class T>
void headInsert(Node<T>*& head, const T& strData, const T& intData);

/*
 * insert function
 * - Precondition: afterMe points to a node in a linked list.
 * - Postcondition: A new node containing "theData" has been added
 *   after the node pointed to by afterMe.
 */
template<class T>
void insert(Node<T>* afterMe, const T& strData, const T& intData);

/*
 * deleteNode
 * - Precondition: The pointers before point to nodes that has at
 *   least one node after it in the linked list.
 * - Postcondition: The node after the node pointed to by before
 *   has been removed from the linked list and its storage
 *   returned to the freestore.
 */
template<class T>
void deleteNode(Node<T>* before);

/*
 * deleteFirstNode
 * - Precondition: The pointers head points to the first node in a
 *   linked list; with at least one node.
 * - Postcondition: The node pointed to by head has been removed for
 *   the linked list and its storage returned to the freestore.
 */
template<class T>
void deleteFirstNode(Node<T>*& head);

/*
 * search function
 * - Precondition: The pointer head points to the head of a linked list.
 *   The pointer variable in the last node is NULL.
 *
 * head (first) node - should be defined for type T.
 *
 * (== is used as the criterion for being equal).
 * If the list is empty, then head is NULL.
 *
 * Returns a pointer that points to the first node that is equal to
 *  the target. If no node equals the target, the function returns NULL.
 */
template<class T>
Node<T>* search(Node<T>* head, const T& target);

} /* namespace SavitchListTools */
#endif /* LISTTOOLS_H_ */ 

Lab9D.cpp

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

#include "ListTools.h"
#include "HashTable.h"

using SavitchHashTable::HashTable;

int main(){
	cout << "CSIS 237 Lab 9 D - Hash Tables" << endl;

	HashTable h;

	cout << "Adding dog, cat, turtle, bird" << endl;
	h.put("dog");
	h.put("cat");
	h.put("turtle");
	h.put("bird");

	cout << "Contains dog? " << h.containsString("dog") << endl;
	cout << "Contains cat? " << h.containsString("cat") << endl;
	cout << "Contains turtle? " << h.containsString("turtle") << endl;
	cout << "Contains bird? "   << h.containsString("bird")   << endl;

	cout << "Contains fish? " << h.containsString("fish") << endl;
	cout << "Contains cow? "  << h.containsString("cow")  << endl;


	h.put("dog",    23);
	h.put("cat",    52);
	h.put("turtle", 234);
	h.put("bird"  , 162);

	cout << "dog     corresponds to the value " << h.get("dog") << endl;
	cout << "cat     corresponds to the value " << h.get("cat") << endl;
	cout << "turtle  corresponds to the value " << h.get("turtle") << endl;
	cout << "bird    corresponds to the value " << h.get("bird")   << endl;

	cout << "Contains fish? " << h.containsString("fish") << endl;
	cout << "Contains cow? "  << h.containsString("cow")  << endl;

}

[Cubbi]

headInsert() is defined so that the type of its second parameter (type T) must match the type of the element held by the node in the first parameter (type Node<T>).

When you're calling it in HashTable.cpp, you're passing a Node<string> as the first argument, and an int as the second argument. There is no matching function to call.

Also, note that you're trying to define your templates in cpp files, this won't work: move them to header files.

[Lukvang]

Ah!! That solved the issue!! Thanks ALOT!!