// Lab Problem 10.1 (incorporates 10.2)

// CS211 ADS2

// T Naughton, CS NUIM

// 28 Apr 2000

#include<iostream>

#include<string>



/* A class to maintain a hash table of names against telephone numbers.

** Both names and telephone numbers are stored as character strings. We

** use C++ strings in this program. The name will be the key of the

** hash table.

** The hash function simply returns the ASCII value of the first

** character of the name string. A function PrintStatus() prints out

** the status of the hash table and allows us to see the problems with

** our choice of hash function.

** In case of collisions, we simply advance to the next empty table

** element.

*/



enum States {EMPTY, USED, DELETED};



class TelDirEntry {

 // The contents of each hash table element

 public:

  string name;

  string number;

  States status;

};



class TelDir {

  TelDirEntry * Directory;

  int TableSize; // size of array



 public:

  TelDir(int size);

  ~TelDir();

  void Add(string name, string number);

  void Remove(string name);

  string GetNumber(string name);

  void Clear();

  int CountFree();

  void Print();

  void PrintStatus();

  int Hash(string name);



 private:

  void Delete();

  int NextIndex(int currentIndex); // return the subsequent index

  int PrevIndex(int currentIndex); // return the previous index

};



TelDir::TelDir(int size){

  // Dynamically create the array with dimensions passed by the user.

  Directory = new TelDirEntry[size];

  TableSize = size;

  Clear(); // set the status of all table elements to EMPTY

}



TelDir::~TelDir(){

  // We must call a special delete function because the table is a

  // dynamically created array.

  Delete();

}



void TelDir::Add(string name, string number){

  // Add a (name, string) pair to the hash table. In case of collisions,

  // advance to the next empty table element. If (CountFree() > 0) then

  // we are guaranteed to find a free table element eventually.

  int index;

  if (CountFree() > 0) {

    index = Hash(name);

    while (Directory[index].status != EMPTY) {

      index = NextIndex(index);

    }

    Directory[index].name = name;

    Directory[index].number = number;

    Directory[index].status = USED;

  } else {

    cout << "\nCould not add " << name << '.';

  }

}



void TelDir::Remove(string name){

  // When we remove an element we simply set its status to deleted.

  // If we encounter a free entry then name is not in the table.

  // A variable 'count' is also used to count the number of table elements

  // we have searched. If we have searched 'TableSize' then we can be

  // sure that 'name' is not in the table.

  int index;

  int count;

  index = Hash(name);

  count = 0;

  while ((count < TableSize) && (name != Directory[index].name)

                             && (Directory[index].status != EMPTY)) {

    index = NextIndex(index);

    count++;

  }

  if (name == Directory[index].name) {

    Directory[index].status = DELETED;

  } else {

    cout << "\nCould not remove " << name << '.';

  }

}



string TelDir::GetNumber(string name){

  // If we encounter a free entry then name is not in the table.

  // A variable 'count' is also used to count the number of table elements

  // we have searched. If we have searched 'TableSize' then we can be

  // sure that 'name' is not in the table.

  int index;

  int count;

  index = Hash(name);

  count = 0;

  while ((count < TableSize) && (name != Directory[index].name)

                             && (Directory[index].status != EMPTY)) {

    index = NextIndex(index);

    count++;

  }

  if (name == Directory[index].name) {

    return Directory[index].number;

  } else {

    return "*not in table*";

  }

}



void TelDir::Clear(){

  // Clear() simply sets all table element status values to EMPTY

  int count;

  count = 0;

  while (count < TableSize) {

    Directory[count].status = EMPTY;

    count++;

  }

}



void TelDir::Delete(){

  // The hash table has been created dynamically so we must delete the

  // array when we are finished.

  delete [] Directory;

}



int TelDir::CountFree(){

  // Return the number of hash table elements whose status is EMPTY

  int count;

  int index;

  count = 0;

  index = 0;

  while (index < TableSize) {

    if (Directory[index].status == EMPTY) {

      count++;

    }

    index++;

  }

  return count;

}



void TelDir::Print(){

  // Print out the contents of all non-EMPTY elements of the table

  int count;

  cout << endl << "Table Contents (Free = " << CountFree() << "):";

  count = 0;

  while (count < TableSize) {

    if (Directory[count].status != EMPTY) {

      cout << "\n  " << count << '\t';

      switch (Directory[count].status) {

        case USED :

          cout << "USED    "; break;

        case DELETED :

          cout << "DELETED "; break;

        default:

          cout << "??????? ";

      }

      cout << Directory[count].name << ' ' << Directory[count].number;

    }

    count++;

  }

}



void TelDir::PrintStatus(){

  // Print the status of each element (whether it is EMPTY, USED, or

  // DELETED).

  int count;

  cout << endl << "Here is the table:";

  count = 0;

  while (count < TableSize) {

    if (Directory[count].status == EMPTY) {

      cout << '.';

    } else if (Directory[count].status == USED) {

      cout << 'O';

    } else {

      // must be a deleted element

      cout << 'X';

    }

    count++;

  }

}



int TelDir::Hash(string name){

  // This hash function simply returns the ASCII value of the first

  // character of name, rounded to the range of indexes in the table.

  return (int(name[0]) % TableSize);

}



int TelDir::NextIndex(int currentIndex){

  // Return the subsequent index of a given index. Allow wrapping

  // around to the beginning of the table.

  return ((currentIndex + 1) % TableSize);

}



int TelDir::PrevIndex(int currentIndex){

  // Return the previous index to a given index. Allow wrapping

  // back to the end of the table.

  return ((currentIndex + TableSize - 1) % TableSize);

}



void main(void){



  TelDir AddressBook(100);



  cout << endl;



  AddressBook.Print();

  AddressBook.Add("John", "0102");

  AddressBook.Add("Paul", "0222");

  AddressBook.Add("George", "033");

  AddressBook.Add("Ringo", "0414");

  AddressBook.Print();

  cout << "\nJohn's number is " << AddressBook.GetNumber("John");

  cout << "\nSimon's number is " << AddressBook.GetNumber("Simon");

  AddressBook.Remove("Paul");

  AddressBook.Remove("Robert");

  AddressBook.Print();

  AddressBook.PrintStatus();

  AddressBook.Clear();

  AddressBook.Print();

  AddressBook.Add("Dr", "999");

  AddressBook.Print();

  AddressBook.PrintStatus();

}



/* A sample output from main() follows:



Table Contents (Free = 100):

Table Contents (Free = 96):

  71    USED    George 033

  74    USED    John 0102

  80    USED    Paul 0222

  82    USED    Ringo 0414

John's number is 0102

Simon's number is *not in table*

Could not remove Robert.

Table Contents (Free = 96):

  71    USED    George 033

  74    USED    John 0102

  80    DELETED Paul 0222

  82    USED    Ringo 0414

Here is the table:..............................................................

.........O..O.....X.O.................

Table Contents (Free = 100):

Table Contents (Free = 99):

  68    USED    Dr 999

Here is the table:..............................................................

......O...............................



*/