#include <iostream>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cctype>
using namespace std;

const int header_size = 256;
const char Taken = 'T';
const char Free = 'F';
const char Deleted = 'D';

class frandom : public fstream {
public:
   frandom();
   frandom( const char* ); // open existing file
   frandom( const char*, int, int, int ); // open new file
   ~frandom();
   void open( const char* ); // open existing file
   void open( const char*, int, int, int ); // open new file
   void close();
   long get_slots() const { return slots; }
   long get_record_size() const { return record_size; }
   long get_key_size() const { return key_size; }
   long get_total_bytes() const { return total_bytes; }
   long get_no_records() const { return no_records; }
   bool add_record( const char* );
   bool find_record( char* );
   bool remove_record( const char* );
private:
   long slots;
   long record_size; // includes 1-byte flag
   long key_size;
   long total_bytes;
   long no_records; // no of records stored
   long loc_address; // computed by locate
   char* buffer; // holds one record
   char* stored_key; // holds one key
   long get_address( const char* ) const;
   bool locate( const char* );
};

frandom::~frandom() {
   if ( is_open() ) {
      delete [ ] stored_key;
      delete [ ] buffer;
      char buff[ header_size ];
      for ( int i = 0; i < header_size; i++ )
         buff[ i ] = ' ';
      sprintf( buff, "%ld %ld %ld %ld",
               slots, record_size,
               key_size, no_records );
      seekp( 0, ios_base::beg );
      write( buff, header_size );
   }
}

frandom::frandom() : fstream() {
   buffer = stored_key = 0;
   slots = record_size = key_size = 0;
   total_bytes = no_records = 0;
}

frandom::frandom( const char* filename ) : fstream() {
   buffer = stored_key = 0;
   open( filename );
}

frandom::frandom( const char* filename,
                  int sl,
                  int actual_record_size,
                  int ks ) : fstream() {
   buffer = stored_key = 0;
   open( filename, sl, actual_record_size, ks );
}

// open an existing file
void frandom::open( const char* filename ) {
   fstream::open( filename,
                  ios_base::in |
                  ios_base::out |
                  ios_base::binary );

   if ( is_open() ) {
      char buff[ header_size ];
      read( buff, header_size );
      sscanf( buff, "%ld%ld%ld%ld",
              &slots, &record_size, &key_size,
              &no_records );
      total_bytes = slots * record_size + header_size;
      // get_address needs \0
      stored_key = new char [ key_size + 1 ];
      buffer = new char [ record_size ];
   }
}

// open a new file
void frandom::open( const char* filename,
                    int sl,
                    int actual_record_size,
                    int ks ) {
   fstream::open( filename,
                  ios_base::in |
                  ios_base::out |
                  ios_base::binary );
   // if open succeeds, file already exists
   if ( is_open() ) {
      setstate( ios_base::failbit );
      fstream::close();
      return;
   }

   // file does not exist; create it
   fstream::open( filename, ios_base::out | ios_base::binary );
   if ( is_open() )
      fstream::close();

   // file created; now open it for input and output
   fstream::open( filename,
                  ios_base::in |
                  ios_base::out |
                  ios_base::binary );

   if ( is_open() ) {
      clear(); // clear failbit flag set by open failure
      char buff[ header_size ];
      slots = sl;
      record_size = actual_record_size + 1;
      key_size = ks;
      total_bytes = slots * record_size + header_size;
      no_records = 0;
      // get_address needs \0
      stored_key = new char [ key_size + 1 ];
      for ( int i = 0; i < header_size; i++ )
         buff[ i ] = ' ';
      sprintf( buff, "%ld %ld %ld %ld",
               slots, record_size,
               key_size, no_records );
      write( buff, header_size );
      buffer = new char [ record_size ];
      for ( i = 1; i < record_size; i++ )
         buffer[ i ] = ' ';
      buffer[ 0 ] = Free;
      for ( i = 0; i < slots; i++ )
         write( buffer, record_size );
   }
}

// hash function
long frandom::get_address( const char* key ) const {
   memcpy( stored_key, key, key_size );
   stored_key[ key_size ] = '\0';
   return ( atol( stored_key ) % slots ) 
            * record_size + header_size;
}

// locate searches for a record with the specified key.
// If successful, locate returns true.
// If unsuccessful, locate returns false.
// locate sets data member loc_address to the address
// of the record if the record is found. This
// address can be then used by find_record
// or remove_record.
//
// If the record is not found, locate sets loc_address
// to the first D or F slot encountered in its search
// for the record. This address can be used by add_record.
// If there is no D or F slot (full file), locate sets
// loc_address to the hash address of key.
bool frandom::locate( const char* key ) {
   // address = current offset in file
   // start_address = hash offset in file
   // unocc_address = first D slot in file
   //               = start_address, if no D slot
   long address, start_address, unocc_address;

   // delete_flag = false, if no D slot is found
   //             = true, if D slot is found
   int delete_flag = false;

   address = get_address( key );
   unocc_address = start_address = address;
   do {
      seekg( address, ios_base::beg );
      switch( get() ) {
      case Deleted:
         if ( !delete_flag ) {
            unocc_address = address;
            delete_flag = true;
         }
         break;
      case Free:
         loc_address = delete_flag ? unocc_address : address;     
    return false;
      case Taken:
         seekg( address + 1, ios_base::beg );
         read( stored_key, key_size );
         if ( memcmp( key, stored_key, key_size ) == 0 ) {
            loc_address = address;
            return true;
         }
         break;
      }
      address += record_size;
      if ( address >= total_bytes )
         address = header_size;
   } while ( address != start_address );

   loc_address = unocc_address;
   return false;
}

bool frandom::add_record( const char* record ) {
   if ( no_records >= slots || locate( record ) )
      return false;

   seekp( loc_address, ios_base::beg );
   write( &Taken, 1 );
   write( record, record_size - 1 );
   no_records++;
   return true;
}

bool frandom::find_record( char* record ) {
   if ( locate( record ) ) {
      seekg( loc_address + 1, ios_base::beg );
      read( record, record_size - 1 );
      return true;
   }
   else
      return false;
}

bool frandom::remove_record( const char* key ) {
   if ( locate( key ) ) {
      --no_records;
      seekp( loc_address, ios_base::beg );
      write( &Deleted, 1 );
      return true;
   }
   else
      return false;
}

void frandom::close() {
   if ( is_open() ) {
      delete [ ] stored_key;
      delete [ ] buffer;
      char buff[ header_size ];
      for ( int i = 0; i < header_size; i++ )
         buff[ i ] = ' ';
      sprintf( buff, "%ld %ld %ld %ld",
               slots, record_size,
               key_size, no_records );
      seekp( 0, ios_base::beg );
      write( buff, header_size );
      fstream::close();
   }
}

int main() {
   char b[ 10 ], c;

   frandom finout;

   cout << "New file (Y/N)? ";
   cin >> c;
   if ( toupper( c ) == 'Y' ) {
      finout.open( "data.dat", 15, 5, 3 );
      if ( !finout ) {
         cerr << "Couldn't open file\n";
         return EXIT_FAILURE;
      }
   }
   else {
      finout.open( "data.dat" );
      if ( !finout ) {
         cerr << "Couldn't open file\n";
         return EXIT_FAILURE;
      }
   }

   do {
      cout << "\n\n[A]dd\n[F]ind\n[R]emove\n[Q]uit? ";
      cin >> c;
      switch ( toupper( c ) ) {
      case 'A':
         cout << "Which record to add? ";
         cin >> b;
         if ( finout.add_record( b ) )
            cout << "Record added\n";
         else
            cout << "Record not added\n";
         break;
      case 'F':
         cout << "Key? ";
         cin >> b;
         if ( finout.find_record( b ) ) {
            b[ 5 ] = '\0';
            cout << "Record found: " << b << '\n';
         }
         else
            cout << "Record not found\n";
         break;
      case 'R':
         cout << "Key? ";
         cin >> b;
         if ( finout.remove_record( b ) )
            cout << "Record removed\n";
         else
            cout << "Record not removed\n";
         break;
      case 'Q':
         break;
      default:
         cout << "Illegal choice\n";
         break;
      }
   } while ( toupper( c ) != 'Q' );

   return 0;
}