Make your own free website on Tripod.com

Back

// 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;
       }
}

Back