// Lab Problem 11.2 (incorporates 11A.2 and 11B.2)

// CS211 ADS2

// T Naughton, CS NUIM

// 30 Apr 2000

#include<iostream>

#include<string>



/*

** A class to implement a hash table of airports and their locations is

** required. Each airport has the following properties: a name, a three

** digit serial code, and a grid reference. The airport grid reference

** (the key) is stored as a floating point number, the airport name is

** stored as a character string, and the three digit code is stored as an

** integer.

** Problem 11A.2 Write a suitable hash() function, countfree() method, and

** insert() method.

** Problem 11B.2 (a) Write a suitable class definition for this class.

** Include all necessary data structures and method signatures. (b) Write

** a method Ratio() to determine the ratio of deleted locations to free

** locations in your hash table. (c) Write a Contains() method that

** determines if a given grid reference appears in the hash table.

*/



enum States {EMPTY, USED, DELETED};



class HashEntry {

 public:

  double grid;

  string name;

  int code;

  States status;

};



class AirTable {

  HashEntry * Airports;

  int TableSize; // size of array



 public:

  AirTable(int size);

  ~AirTable();

  void Add(double grid, string name, int code);

  void Remove(double grid);

//  void PrintDetails(double grid);

  void Clear();

  int CountIf(States status);

//  void Print();

  void Ratio();

  bool Contains(double grid);



 private:

  int Hash(double grid);

  void Delete();

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

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

};



AirTable::AirTable(int size){

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

  Airports = new HashEntry[size];

  TableSize = size;

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

}



AirTable::~AirTable(){

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

  // dynamically created array.

  Delete();

}



void AirTable::Add(double grid, string name, int code){

  // Add a (grid, name, code) triple 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 (CountIf(EMPTY) > 0) {

    index = Hash(grid);

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

      index = NextIndex(index);

    }

    Airports[index].grid = grid;

    Airports[index].name = name;

    Airports[index].code = code;

    Airports[index].status = USED;

  } else {

    cout << "\nNo room to add " << grid << '.';

  }

}



void AirTable::Clear(){

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

  int count;

  count = 0;

  while (count < TableSize) {

    Airports[count].status = EMPTY;

    count++;

  }

}



void AirTable::Delete(){

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

  // array when we are finished.

  delete [] Airports;

}



int AirTable::CountIf(States status){

  // Return the number of hash table elements that have a given status

  int count;

  int index;

  count = 0;

  index = 0;

  while (index < TableSize) {

    if (Airports[index].status == status) {

      count++;

    }

    index++;

  }

  return count;

}



int AirTable::Hash(double grid){

  // We would like grid to generate a number very much larger than

  // TableSize so that % by TableSize will give us indexes well distributed

  // in the table. This function moves the decimal point in grid to

  // make sure it is very much greater than TableSize, before % by TableSize.



  // First check for awkward floats...

  if (grid < 0) {

    grid = grid * -1;

  } else if (grid == 0) {

    grid = 1;

  }

  while (grid < (TableSize * 10)) {

    grid = grid * 10;

  }

  return (int(grid) % TableSize);

}



int AirTable::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 AirTable::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 AirTable::Ratio(){

  int a, b;

  a = CountIf(DELETED);

  b = CountIf(EMPTY);

  cout << "\nRatio of deleted locations to free locations is ";

  cout << a << " / " << b << " = ";

  if ((b == 0) && (a == 0)) {

    cout << 0;

  } else if (b == 0) {

     cout << "inf";

  } else {

    cout << double(a) / double(b);

  }

}



bool AirTable::Contains(double grid){

  // If we encounter an empty location we return false.

  // 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 'grid' is not in the table.

  int index;

  int count;

  index = Hash(grid);

  count = 0;

  while ((count < TableSize) && (grid != Airports[index].grid)

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

    index = NextIndex(index);

    count++;

  }

  return (grid == Airports[index].grid);

}



void main(void){



  AirTable test(100);



  cout << endl;



  test.Ratio();

  test.Add(0.673, "Dublin", 123);

  test.Add(1.567, "Paris", 505);

  test.Add(23.445, "San Francisco", 452);

  test.Ratio();

  cout << "\nAirport 1.567 is ";

  if (!test.Contains(1.567)) {

    cout << "not ";

  }

  cout << "in the table";

  cout << "\nAirport 1.777 is ";

  if (!test.Contains(1.777)) {

    cout << "not ";

  }

  cout << "in the table";



}