/*   The PHONE program reads NUMB_RECS records from the file
     students.dat into the two-dimensional array students. The
     records occur one to a line, with a maximum length of
     MAX_REC_SIZE and fields formatted as follows:

         25 chars    25 chars      12 chars
       <last name> <first name> <phone number>
       /|\         /|\          /|\
        |           |            |
     Column 1    Column 26    Column 51

     MAX_REC_SIZE is thus LNAME_SIZE + FNAME_SIZE + PNUM_SIZE.
     One record occurs per line.

     PHONE sorts the records--as character strings--in ascending
     order and then does lookups. It prompts for a last name, padding
     it if necessary with blanks to LNAME_SIZE, and then searches
     the array. If the name is found, the entire record is written to
     to the terminal in data-processing format, i.e., the fields are
     printed in their file column positions. If the name is not
     found, a message is written.

     PHONE uses selection sort for the sorting and binary search for
     the searching. The program consists of the functions: main,
     selection_sort, binary_search, and swap.                      */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define  NUMB_RECS    30 /* number of records in students.dat */
#define  LNAME_SIZE   25 /* first 25 chars */
#define  FNAME_SIZE   25 /* next 25 chars */
#define  PNUM_SIZE    12 /* last 12 chars */
#define  MAX_REC_SIZE (LNAME_SIZE + FNAME_SIZE + PNUM_SIZE)
#define  NO_FIND      (-999) /* flag to signal lookup failure */
#define  BLANK        ' '    /* used to pad candidate name so
                                that it, too, has LNAME chars */

void selection_sort( char array[][ MAX_REC_SIZE + 2 ],
                     int size1 );
void swap( char array[][ MAX_REC_SIZE + 2 ],
           int current,
           int low );
int binary_search( char candidate[],
                   char array[][ MAX_REC_SIZE + 2 ],
                   int size );

main()
{
     /* student records (+2 is for the newline and the
        null terminator) */
     char students[ NUMB_RECS ][ MAX_REC_SIZE + 2 ];

     /* candidate in search (+2 is for the newline and the
        null terminator) */
     char candidate[ LNAME_SIZE + 2 ];

     int cand_len; /* length of candidate's name */
     int index; /* index into students */
     int i;
     FILE *fp;

     /* read the names of NUMB_RECS records into array students */
     fp = fopen( "students.dat", "r" );

     for ( i = 0; i < NUMB_RECS; ++i )
          fgets( students[ i ], MAX_REC_SIZE + 2, fp );

     /* sort the records into ascending order, by name */
     selection_sort( students, NUMB_RECS );

     /* Prompt the user for a student's name and look for it in the
        array students. Halt when the user signals EOF at the
        prompt. */

     printf( "\n\n\Enter a student's name, "
             "or signal EOF to halt:  " );
     while ( fgets( candidate, LNAME_SIZE + 2, stdin ) != NULL ) {

          /* Pad candidate with blanks to LNAME_SIZE chars. */
          cand_len = strlen( candidate ) - 1; /* -1 for newline
                                                 stored by fgets */
          for ( i = cand_len; i < LNAME_SIZE; i++ )
                  candidate[ i ] = BLANK;
          candidate[ LNAME_SIZE ] = '\0';  /* null terminate */

          index = binary_search( candidate, students, NUMB_RECS );
          if ( index != NO_FIND )
               printf( "\nRecord:  %s", students[ index ] );
          else {
               candidate[ cand_len ] = '\0'; /* knock off blanks */
               printf( "\n\t%s is not in our directory.",
                       candidate );
          }
          printf( "\n\n\Enter a student's name, "
                  "or signal EOF to halt:  " );
     }

     return EXIT_SUCCESS;
}

/*   selection_sort ( array, size1 )

     The function expects an array and its size. It sorts the
     elements into ascending order. It does not return a value.

     The algorithm can be sketched as follows:

          1. Repeat steps 2 and 3 for ind equals 0,1,...,size1 - 2.

          2. Select the smallest item among

             array[ ind ], array[ ind + 1 ], ..., array[ size1 - 1 ].

          3. Swap the smallest with array[ ind ].
                                                                   */

void selection_sort( char array[][ MAX_REC_SIZE + 2 ], int size1 )
{
     int   smallest_index; /* index of smallest string seen */
     int   i, j;

     /* loop size1 - 1 times, selecting smallest string each time */
     for ( i = 0; i < size1 - 1; ++i ) {
        /* assume ith string is smallest */
        smallest_index = i;
        /* compare smallest against remaining strings */
        for ( j = i + 1; j < size1; ++j )
           /* look for smaller string */
           if ( strcmp( array[ j ], array[ smallest_index ] ) < 0 )
             smallest_index = j;
        /* put smallest at index i */
        if ( i != smallest_index )
           swap( array, i, smallest_index );
     }
}

/* Swap array[ current ] and array[ low ]. */

void swap( char array[][ MAX_REC_SIZE + 2 ], int current, int low )
{
     char  temp[ MAX_REC_SIZE + 2 ];

     strcpy( temp, array[ current ] );
     strcpy( array[ current ], array[ low ] );
     strcpy( array[ low ], temp );
}

/*   binary_search( candidate, array, size )

     The function searches the sorted array

               array[ 0 ], array[ 1 ] , ..., array[ size - 1]

     for candidate, returning the appropriate index if
     candidate is found, and the NO_FIND flag otherwise.

     The algorithm can be sketched as follows:

          1. Repeat steps 2 through 4 until either the candidate is
             found or there is nothing left to search.

          2. Find the (approximate) midpoint in the array. (This is
             an index into the array.)

          3. Compare the array's midpoint item with candidate: if
             they match, return the midpoint value and halt
             (success).

          4. If the candidate is less than the midpoint item, search
             the first half of the array, discarding the second
             half; otherwise, search the second half, discarding the
             first.

          5. Return NO_FIND (failure).                             */

int binary_search( char candidate[],
                   char array[][ MAX_REC_SIZE + 2 ],
                   int size )
{
     int   len;              /* length of candidate string */
     int   first = 0;        /* first position in array */
     int   last = size - 1;  /* last position in array */
     int   mid;              /* midpoint in array */
     int   flag;             /* holds result of string comparison */

     len = strlen( candidate );

     /* search until list is empty */
     while ( first <= last ) {
          /* find (approximate) midpoint */
          mid = ( first + last ) / 2;
          /* Compare only len - 1 characters. - 1 is so we don't
             include the terminating newline. */
          flag = strncmp( candidate, array[ mid ], len - 1 );
          if ( flag == 0 ) /* candidate == array[ mid ] */
               return mid; /* signal success--candidate found */
          if ( flag > 0 ) /* candidate > array[ mid ] */
               first = mid + 1;  /* search right half */
          else /* candidate < array[ mid ] */
               last = mid - 1;   /* search left half */
     }

     return NO_FIND;
}