I'm having trouble with these functions made for a C++ hash table...any and all pointers in the right direction would be greatly appreciated! EDIT: table.h is the problem file, but I included node.h just in case!
// FILE: table.h
#ifndef TABLE_H
#define TABLE_H
#include <cstdlib> // Provides size_t
#include <string> // Provides string
#include <sstream> // Provides stringstream
#include "node.h" // Provides the node type as used previously
template <class RecordType>
class table {
public:
static const std::size_t TABLE_SIZE = 811;
// CONSTRUCTORS AND DESTRUCTOR
table( );
table(const table& source);
~table( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
void operator =(const table& source);
// CONSTANT MEMBER FUNCTIONS
void find(int key, bool& found, RecordType& result) const;
bool is_present(int key) const;
std::size_t size( ) const { return total_records; }
std::string toString( ) const;
private:
node<RecordType> *data[TABLE_SIZE];
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
};
// NONMEMBER FUNCTION for the table class
template <class RecordType>
std::ostream& operator<<(std::ostream& outs, const table<RecordType>& seq);
// INVARIANT for the table ADT:
// STUDENT: Provide a solid and complete invariant for this implementation
#include <stdexcept> // Provides exceptions
#include <cstdlib> // Provides size_t
#include <iostream> // Provides <<
#include <sstream> // Provides stringstream
#include <string> // Provides string
template <class RecordType>
const std::size_t table<RecordType>::TABLE_SIZE;
// STUDENT -- implement ALL methods of the table class starting with
// constructors, destructor, etc.
template <class RecordType>
table<RecordType>::table( ) {
std::size_t index;
// STUDENT code here
total_records = 0;
for (index = 0; index < TABLE_SIZE; index++){
data[index] = NULL;
}
}
template <class RecordType>
table<RecordType>::table( const table& source ) {
std:size_t index;
// STUDENT code here
node<RecordType>* end;
for (index = 0; index < TABLE_SIZE; ++index){
list_copy(source.data[index], data[index], end);
}
total_records = source.total_records;
}
template <class RecordType>
table<RecordType>::~table( ) {
std::size_t index;
// STUDENT code here
/*
node<RecordType>* ptr = new node<RecordType>;
node<RecordType>* del = new node<RecordType>;
while(index < TABLE_SIZE){
ptr = data[index];
while(ptr != NULL){
del = ptr;
ptr = ptr->link();
delete del;
del = NULL;
}
data[index] = NULL;
++index;
}
*/
}
template <class RecordType>
void table<RecordType>::insert(const RecordType& entry) {
std::size_t index = hash(entry.key);
// STUDENT code here
bool present = false;
node<RecordType>* cursor = data[index];
while(cursor != NULL && !present){
if (cursor->data().key == entry.key){
cursor->data() = entry;
present = true;
} else
cursor = cursor->link();
}
if(!present){
node<RecordType>* add = new node<RecordType>(entry, data[index]);
data[index] = add;
}
total_records++;
}
template <class RecordType>
void table<RecordType>::remove(int key) {
//std::cout << "Entering remove with key = " << key << "\n";
std::size_t index = hash(key);
// STUDENT code here
/*
node<RecordType>* precursor = data[index];
node<RecordType>* cursor = precursor->link;
*/
}
template <class RecordType>
void table<RecordType>::operator =( const table& source ) {
size_t index;
// STUDENT code here
if (this != &source){
total_records = source.total_records;
for (index =0; index < TABLE_SIZE; index++){
data[index] = source.data[index];
}
}
}
template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const {
std::size_t index = hash(key);
// STUDENT code here
/*
node<RecordType> *cursor = data[index];
found = false;
while (cursor->link() != NULL && cursor->data().key != key){
cursor = cursor->link();
if (cursor->data().key == key){
found = true;
}
}
*/
}
template <class RecordType>
bool table<RecordType>::is_present(int key) const {
size_t index = hash(key);
bool found = false;
node<RecordType>* ptr = data[index];
// STUDENT code here
return found;
}
template <class RecordType>
std::string table<RecordType>::toString( ) const {
// Library facilities used string, sstream, node.h
std::stringstream outs;
outs << "Table: number records " << total_records << "\n";
outs << "[\n";
if ( total_records == 0 ) {
outs << "]";
return outs.str();
}
size_t index;
for ( index = 0; index < TABLE_SIZE; ++index ) {
if ( data[index] != NULL ) {
outs << "Slot " << index << ": ";
const node<RecordType>* ptr = data[index];
while ( ptr->link() != NULL ) {
outs << "(" << ptr->data().key << "," << ptr->data().data << ") ";
ptr = ptr->link();
}
outs << "(" << ptr->data().key << "," << ptr->data().data << ")\n";
}
}
outs << "]\n";
return outs.str();
}
template <class RecordType>
std::ostream& operator<<(std::ostream& outs, const table<RecordType>& tbl) {
//Library facilities used: iostream
outs << tbl.toString();
return outs;
}
template <class RecordType>
inline std::size_t table<RecordType>::hash(int key) const {
// returns value in range 0 <= retValue < TABLE_SIZE
return key % TABLE_SIZE;
}
#endif======================================
// FILE: node.h
// PROVIDES: A template class for a node in a linked list, and list manipulation
// functions. The template parameter is the type of the data in each node.
// This file also defines a template class: node_iterator<Item>.
// The node_iterator is a forward iterator with two constructors:
// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
// to the specified node in a linked list, and (2) a default constructor that
// creates a special iterator that marks the position that is beyond the end of a
// linked list. There is also a const_node_iterator for use with
// const node<Item>* .
//
// TYPEDEF for the node<Item> template class:
// Each node of the list contains a piece of data and a pointer to the
// next node. The type of the data (node<Item>::value_type) is the Item type
// from the template parameter. The type may be any of the built-in C++ classes
// (int, char, ...) or a class with a default constructor, an assignment
// operator, and a test for equality (x == y).
// NOTE:
// Many compilers require the use of the new keyword typename before using
// the expression node<Item>::value_type. Otherwise
// the compiler doesn't have enough information to realize that it is the
// name of a data type.
//
// CONSTRUCTOR for the node<Item> class:
// node(
// const Item& init_data = Item(),
// node* init_link = NULL
// )
// Postcondition: The node contains the specified data and link.
// NOTE: The default value for the init_data is obtained from the default
// constructor of the Item. In the ANSI/ISO standard, this notation
// is also allowed for the built-in types, providing a default value of
// zero. The init_link has a default value of NULL.
//
// NOTE about two versions of some functions:
// The data function returns a reference to the data field of a node and
// the link function returns a copy of the link field of a node.
// Each of these functions comes in two versions: a const version and a
// non-const version. If the function is activated by a const node, then the
// compiler choses the const version (and the return value is const).
// If the function is activated by a non-const node, then the compiler choses
// the non-const version (and the return value will be non-const).
// EXAMPLES:
// const node<int> *c;
// c->link( ) activates the const version of link returning const node*
// c->data( ) activates the const version of data returning const Item&
// c->data( ) = 42; ... is forbidden
// node<int> *p;
// p->link( ) activates the non-const version of link returning node*
// p->data( ) activates the non-const version of data returning Item&
// p->data( ) = 42; ... actually changes the data in p's node
//
// MEMBER FUNCTIONS for the node<Item> class:
// const Item& data( ) const <----- const version
// and
// Item& data( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is a reference to the data from this node.
//
// const node* link( ) const <----- const version
// and
// node* link( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is the link from this node.
//
// void set_data(const Item& new_data)
// Postcondition: The node now contains the specified new data.
//
// void set_link(node* new_link)
// Postcondition: The node now contains the specified new link.
//
// FUNCTIONS in the linked list toolkit:
// template <class Item>
// void list_clear(node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap,
// and the head_ptr is now NULL.
//
// template <class Item>
// void list_copy
// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
// a new list that contains the same items as the list pointed to by
// source_ptr. The original list is unaltered.
//
// template <class Item>
// void list_piece(
// const node* start_ptr, const node* end_ptr,
// node*& head_ptr, node*& tail_ptr
// )
// Precondition: start_ptr and end_ptr are pointers to nodes on the same
// linked list, with the start_ptr node at or before the end_ptr node
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for a
// new list that contains the items from start_ptr up to and including
// end_ptr. The end_ptr may NOT be NULL.
//
// template <class Item>
// void list_head_insert(node<Item>*& head_ptr, const Item& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the head of the linked list; head_ptr now points to the head of the new,
// longer linked list.
//
// template <class Item>
// void list_head_remove(node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// template <class Item>
// void list_insert(node<Item>* previous_ptr, const Item& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added
// after the node that previous_ptr points to.
//
// template <class Item>
// size_t list_length(const node<Item>* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked
// list.
//
// template <class NodePtr, class SizeType>
// NodePtr list_locate(NodePtr head_ptr, SizeType position)
// The NodePtr may be either node<Item>* or const node<Item>*
// Precondition: head_ptr is the head pointer of a linked list, and
// position > 0.
// Postcondition: The return value is a pointer that points to the node at
// the specified position in the list. (The head node is position 1, the
// next node is position 2, and so on). If there is no such position, then
// the null pointer is returned.
//
// template <class Item>
// void list_remove(node<Item>* previous_ptr)
// Precondition: previous_ptr points to a node in a linked list, and this
// is not the tail node of the list.
// Postcondition: The node after previous_ptr has been removed from the
// linked list.
//
// template <class NodePtr, class Item>
// NodePtr list_search
// (NodePtr head_ptr, const Item& target)
// The NodePtr may be either node<Item>* or const node<Item>*
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The return value is a pointer that points to the first
// node containing the specified target in its data member. If there is no
// such node, the null pointer is returned.
//
// DYNAMIC MEMORY usage by the toolkit:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.
#ifndef NODE_H
#define NODE_H
#include <cstdlib> // Provides NULL and size_t
#include <iterator> // Provides iterator and forward_iterator_tag
template <class Item>
class node {
public:
// TYPEDEF
typedef Item value_type;
// CONSTRUCTOR
node(const Item& init_data=Item( ), node* init_link=NULL) {
data_field = init_data;
link_field = init_link;
}
// MODIFICATION MEMBER FUNCTIONS
Item& data( ) { return data_field; }
node*& link( ) { return link_field; }
void set_data(const Item& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// CONST MEMBER FUNCTIONS
const Item& data( ) const { return data_field; }
const node* link( ) const { return link_field; }
private:
Item data_field;
node<Item> *link_field;
};
// FUNCTIONS to manipulate a linked list:
template <class Item>
void list_clear(node<Item>*& head_ptr);
template <class Item>
void list_copy (const node<Item>* source_ptr,
node<Item>*& head_ptr,
node<Item>*& tail_ptr);
template <class Item>
void list_piece (const node<Item>* start_ptr,
const node<Item>* end_ptr,
node<Item>*& head_ptr,
node<Item>*& tail_ptr);
template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry);
template <class Item>
void list_head_remove(node<Item>*& head_ptr);
template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry);
template <class Item>
std::size_t list_length(const node<Item>* head_ptr);
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position);
template <class Item>
void list_remove(node<Item>* previous_ptr);
template <class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item& target);
// FORWARD ITERATORS to step through the nodes of a linked list
// A node_iterator can change the underlying linked list through the
// * operator, so it may not be used with a const node. The
// node_const_iterator cannot change the underlying linked list
// through the * operator, so it may be used with a const node.
// WARNING:
// This class uses std::iterator as its base class;
// Older compilers that do not support the std::iterator class can
// delete everything after the word iterator in the second line:
template <class Item>
class node_iterator
: public std::iterator<std::forward_iterator_tag, Item> {
public:
node_iterator(node<Item>* initial = NULL) {
cursor = initial;
}
Item& operator *( ) const {
return cursor->data( );
}
node_iterator& operator ++( ) /* Prefix ++ */{
cursor = cursor->link( );
return *this;
}
node_iterator operator ++(int) /* Postfix ++*/ {
node_iterator original(cursor);
cursor = cursor->link( );
return original;
}
bool operator ==(const node_iterator other) const {
return cursor == other.cursor;
}
bool operator !=(const node_iterator other) const {
return cursor != other.cursor;
}
private:
node<Item>* cursor;
};
template <class Item>
class const_node_iterator
: public std::iterator<std::forward_iterator_tag, const Item> {
public:
const_node_iterator(const node<Item>* initial = NULL) {
cursor = initial;
}
const Item& operator *( ) const {
return cursor->data( );
}
const_node_iterator& operator ++( ) /* Prefix ++ */ {
cursor = cursor->link( );
return *this;
}
const_node_iterator operator ++(int) /* Postfix ++ */ {
const_node_iterator original(cursor);
cursor = cursor->link( );
return original;
}
bool operator ==(const const_node_iterator other) const {
return cursor == other.cursor;
}
bool operator !=(const const_node_iterator other) const {
return cursor != other.cursor;
}
private:
const node<Item>* cursor;
};
// INVARIANT for the node class:
// The data of a node is stored in data_field, and the link in link_field.
#include <cstdlib> // Provides NULL and size_t
#include <stdexcept> // Provides exception classes
template <class Item>
void list_clear(node<Item>*& head_ptr) {
// Library facilities used: cstdlib
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
template <class Item>
void list_copy( const node<Item>* source_ptr,
node<Item>*& head_ptr,
node<Item>*& tail_ptr ) {
// Library facilities used: cstdlib
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, source_ptr->data( ));
tail_ptr = head_ptr;
// Copy rest of the nodes one at a time, adding at the tail of new list
source_ptr = source_ptr->link( );
while (source_ptr != NULL) {
list_insert(tail_ptr, source_ptr->data( ));
tail_ptr = tail_ptr->link( );
source_ptr = source_ptr->link( );
}
}
template <class Item>
void list_piece( const node<Item>* start_ptr, const node<Item>* end_ptr,
node<Item>*& head_ptr, node<Item>*& tail_ptr ) {
// Library facilities used: cstdlib
head_ptr = tail_ptr = NULL;
if ( start_ptr == NULL || end_ptr == NULL ) return;
// Make the head node for the newly created list, and put data in it
list_head_insert( head_ptr, start_ptr->data() );
tail_ptr = head_ptr;
// Copy the nodes one at a time, adding to the tail of new list
start_ptr = start_ptr->link();
while ( start_ptr != end_ptr->link() ) {
list_insert( tail_ptr, start_ptr->data( ) );
tail_ptr = tail_ptr->link( );
start_ptr = start_ptr->link( );
}
}
template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry) {
head_ptr = new node<Item>(entry, head_ptr);
}
template <class Item>
void list_head_remove(node<Item>*& head_ptr) {
node<Item> *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link( );
delete remove_ptr;
}
template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry) {
node<Item> *insert_ptr;
insert_ptr = new node<Item>(entry, previous_ptr->link( ));
previous_ptr->set_link(insert_ptr);
}
template <class Item>
std::size_t list_length(const node<Item>* head_ptr) {
// Library facilities used: cstdlib
const node<Item> *cursor;
std::size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
++answer;
return answer;
}
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position) {
// Library facilities used: stdexcept, cstdlib
NodePtr cursor;
SizeType i;
if (position < 1)
throw std::invalid_argument("position must be >= 1");
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); ++i)
cursor = cursor->link( );
return cursor;
}
template <class Item>
void list_remove(node<Item>* previous_ptr) {
node<Item> *remove_ptr;
remove_ptr = previous_ptr->link( );
previous_ptr->set_link(remove_ptr->link( ));
delete remove_ptr;
}
template <class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item& target) {
// Library facilities used: cstdlib
NodePtr cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
if (target == cursor->data( ))
return cursor;
return NULL;
}
#endif
