#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

class Hash
{
 private :
  char * HA[ ] ;
  int size ;

 public :
  Hash( );                               //
  int hashValue( char * , int );        //    Done
  int numOfData( );                    //    Done
  int isPrime( int );                 //    Done
  int firstPrimeAfter( int );        //    Done
  void readFromFile( );             // 1  Done
  void printHArray(  );            // 2  Done
  void search( );                 // 3
  void insert( );                // 4  Done
  void del( );                  // 5
};

class Heap
{
 friend class Hash ;

 private :
  char * H[ ] ;

 public :
  Heap(  );
  void sorting( char *[ ] , int );      // 6  Done
  char delMin(  ) ;                    //    Done
  void boubleSort( char *[ ] , int ); // 7  Done
  void outToFile( );                 // 8


};



//////////////////////////////////////////////////////////////////////


  Hash::Hash(  )
 {
   size = firstPrimeAfter( (numOfData( )) * 2 ) ;

   for( int i = 0 ; i < size ; i++ )
      HA[i] = "0" ; 
 }


//////////////////////////////////////////////////////////////////////


  int Hash::hashValue( char * key , int Hsize)
 {
  int hashValue = 0 ;
  while( * key != '\n' )
  {
   hashValue = ( hashValue<<5 ) + ( * key ) ;
   key++ ;
  }
  return hashValue % Hsize ;
 }


//////////////////////////////////////////////////////////////////////


int Hash::numOfData( )
{
 ifstream inf( "data.txt" );
 if ( !inf )
 {
  cout<< "could not be opened\n";
  exit( 0 );
 }

 char name[10] ;
 char number[10];

 int count = 0 ;

 cout<< " Name  " << "\t" << " Number " << "\n" ;
 while( inf>> name >> number )
 {
  count ++ ;
 }
 inf.close( );

 return count ;
}


//////////////////////////////////////////////////////////////////////


  int Hash::firstPrimeAfter( int n )
 {
  n++ ;
  while( ! isPrime( n ) )
  {
   n++ ;
  }
  return n ;
 }



//////////////////////////////////////////////////////////////////////


int Hash::isPrime( int x )
{
 for( int i = 2 ; i < x/2 ; i++ )
   if( x%i == 0 )
      return 0 ;
   return 1 ;
}


//////////////////////////////////////////////////////////////////////


 void Hash::readFromFile( )
 {
  ifstream inf( "data.txt" , ios::in );
  if ( !inf )
 {
  cout<< "could not be opened\n";
  exit(0);
 }

  char name[10] ;
  char number[10];

  cout<< " Name  " << "\t" << " Number " << "\n" ;
  while( inf>> name >> number )
  {
   cout<< name << "\t" << number << "\n" ;
  }
  inf.close( );
 }


//////////////////////////////////////////////////////////////////////


 void Hash::printHArray(  )
{
 ifstream inf( "data.txt" );
 if ( !inf )
 {
  cout<< "could not be opened\n";
  exit(0);
 }

 char name[10] ;
 char number[10];

 while( inf>> name >> number )
 {
  int v = hashValue( name , size );
  if( HA[v] == "0" )
   {
    HA[v] = name ;
    strcat( HA[v] , number );
   }
  else
   {
    for( int i=0 ; i < size ; i++ )
    {
     if(HA[ v + (i*i) ] == "0")
      {
       HA[ v + (i*i) ] = name ;
       strcat( HA[ v + (i*i) ] , number );
       break ;
      }
    }
 }

 cout<< " HashArray contains : \n\n " ;
 for( int i = 0; i < size ; i++ )
   cout<< HA[i] << "\n" ;
}


//////////////////////////////////////////////////////////////////////


 void Hash::insert( )
{
 char N[30] ;
 cout<< " Enter your friend name and his number to add " ;
 cin>> N ;
 
 hv = hashValue( N , Hsize );
 if( HA[hv] == "0" )
 {
  HA[hv] = N ;
 }
 else
 {
  for( int i=0 ; i < size ; i++ )
   {
    if(HA[ hv + (i*i) ] == "0")
     { 
       HA[ hv + (i*i) ] = N ;
       break ;
     }
    else
     continue;
   }
 }
}


/*********************************************************************/

void main( )
{

 Hash hash ;

 hash.readFromFile( );


}

/*********************************************************************/

  Heap::Heap( )
 {
  H[ ] = HA[ ];
 }


//////////////////////////////////////////////////////////////////////


  void Heap::boubleSort( char * H[ ] ,int size )
 {
  char * hold ;
  for( int p = 1 ; p < size ; p++ )
   for( int p = 1 ; p < size ; p++ )
    if( (strcmp ( H[i] , H[i+1] )) > 0 )
   {
     hold = H[i] ;
     H[i]  = H[i+1];
     H[i+1] = hold ; ss
   }
 }


//////////////////////////////////////////////////////////////////////


 void Heap::delMin(   )
{


 int i , child ;
 int minEl , lastEl ;

 minEl = H[0] ;
 lastEl = H[size--] ;

 for( i =1 ; i*2 < size ; i++ )
 {
  child = i*2 ;

  if( (child < size) && ( H[child +1] < H[size] )
     child++ ;

  if( lastEl > H[child] )
     H[i] = H[child] ;

  else
     break;
 }

  H[i] = lastEl ;

 return minEl ;

}


//////////////////////////////////////////////////////////////////////


  Heap::sorting( char * H[ ] )
 {

 }


//////////////////////////////////////////////////////////////////////


  void Heap::outToFile( char A[6][10], int Hsize )
 {
    char i = 'a' ;

    while( i <= 'z' )
   {
    cout<< "\n\n" << i << "\n" ;

    for( int j = 0 ; j < Hsize ; j++ )  // for each name

    if( A[j][0] == i )
     {
       for( int k = 0 ; k < Hsize ; k++ )
       cout<< A[j][k]   ;
       cout<< "\n" ;
     }
    else
     break ;

    i++ ;

   }
 }