// Matt Kaliszewksi
// COMP411 - Lab 06
// October 16, 2002
// HashTable.cpp
#include "HashTable.h"
////////////////////////////////////////////////////////////
// Default constructor
HashTable::HashTable()
{
// Set the number of buckets
buckets = 10;
// Initialize each bucket in the table
for(int i=0;i<buckets;i++)
{
table[i] = new Link;
}
}
////////////////////////////////////////////////////////////
// Method to get a user
User* HashTable::getUser(string username)
{
int b;
bool found = false;
bool end = false;
User *foundUser;
Link *current;
// Get the bucket that the user would be in
b = hash(username);
// Set the current link to point to the start of the correct bucket
current = table[b];
// Go through the bucket and try to find the user
do
{
// If there are no links in the chain
if(current->user==NULL)
{
end = true;
}
// Go through the chain and try to find the user
else
{
// If the current link contains the user we are looking for
if(current->user->getUserName() == username)
{
foundUser = current->user;
found = true;
}
// If the current user is not the user we are looking for
if(!found)
{
// Check if we are at the end of the chain
if(current->next==NULL)
end = true;
// Else move to the next link in the chain
else
current = current->next;
}
}
}while(!end && !found);
// If the user was not found, return NULL
if(!found)
return NULL;
// Else return the user
return foundUser;
}
////////////////////////////////////////////////////////////
// Method to insert a user into the hash table
bool HashTable::insertUser(User *nuser)
{
int b;
Link *current;
Link *newLink;
// Make sure the user isn't already in the table
if(getUser(nuser->getUserName())!=NULL)
return false;
// Get the bucket number
b = hash(nuser->getUserName());
// Create a pointer to the correct bucket
current = table[b];
// If the first bucket is empty, add the user there
if(current->user==NULL)
{
current->user = nuser;
}
// Add a new link to the end of the last bucket
else
{
while(current->next != NULL)
current = current->next;
newLink = new Link;
newLink->next = NULL;
newLink->user = nuser;
current->next = newLink;
}
return true;
}
////////////////////////////////////////////////////////////
// Method to delete a user from the hash table
bool HashTable::deleteUser(string username)
{
int b;
Link *current;
Link *prev;
User *user;
bool deleted = false;
bool end = false;
// Make sure the user is in the table
if(getUser(username)==NULL)
return false;
// If the user is in the table, get the bucket
b = hash(username);
// Set the current link to point to the start of the correct bucket
current = table[b];
// If the user is the first link in the chain
if(current->user->getUserName() == username)
{
// If the user is the only one in the bucket
if(current->next == NULL)
{
current->user = NULL;
}
// If there are more than one user in the bucket
else
{
user = current->user;
current->user = current->next->user;
current->next = current->next->next;
delete user;
deleted = true;
}
}
// Else go through the bucket and try to find the user
else
{
do
{
if(current->next != NULL)
{
// Move to the next link
prev = current;
current = current->next;
// If the current link contains the user we are
looking for
if(current->user->getUserName() == username)
{
user = current->user;
prev->next = current->next;
delete user;
deleted = true;
}
// If the current user is not the user we are
looking for
if(!deleted)
{
// Check if we are at the end of the chain
if(current->next==NULL)
end = true;
}
}
}while(!deleted && !end);
}
return deleted;
}
////////////////////////////////////////////////////////////
// Method to calculate the hash based on the username
int HashTable::hash(string username)
{
int length;
int sum=0;
// Get the length of the username
length = username.length();
// Add up all of the values in the username
for(int i=0;i<length;i++)
sum+=(int)username[i];
// Mod the sum by the number of buckets
sum%=10;
return sum;
}
////////////////////////////////////////////////////////////
// Method to print the contents of the hash table
void HashTable::print()
{
Link *current;
bool end;
// Loop through all of the buckets and print out the users
for(int i=0;i<buckets;i++)
{
current = table[i];
end = false;
cout << i << " -> ";
// Go through the current bucket and print out all the users
do
{
// If there are no links in the chain
if(current->user==NULL)
{
end = true;
cout << endl;
}
// Print out the user in the current link
else
{
cout << current->user->getUserName();
// Check if we are at the end of the chain
if(current->next==NULL)
{
end = true;
cout << endl;
}
// Else move to the next user in the chain
else
{
cout << " -> ";
current = current->next;
}
}
}while(!end);
}
}
////////////////////////////////////////////////////////////
// Prints all information about a user
void HashTable::printUserInfo(string username)
{
User *user;
// Check if the user is in the table
user = getUser(username);
// If the user was not found, tell the user
if(user==NULL)
cout << "User not found!" << endl << endl;
// Print out the user's information
else
{
cout << "User Name: " << user->getUserName() << endl
<< "Name: " << user->getName() << endl
<< "Phone Number: " << user->getPhone() << endl
<< "Privilege: " << user->getPrivilege() << endl << endl;
}
}