/* --------------------------------------------------------------------- 
**  Binary search.
**  Figures 22.7:  Calling on bsearch().
**          21.6:  Setting up the data structures.
**          20.15: Input into an array.       
**          20.16: Output from an array. 
**          22.8:  A comparison function for integers.  
** --------------------------------------------------------------------- 
*/
#include "tools.h"

#define NOT_FOUND   NULL
typedef struct { int* data; int n; int max; } data_pack; 
 
void setup( data_pack* spec, stream* infile );
void get_data( data_pack* searchp, stream instream );
int  sort_int_up( const void* ip1, const void* ip2 );

/* ------------------------------------------------------------------ */
void main( void )
{   
    stream fin;                  /* Stream for the input file. */
    data_pack search;            /* Array of data. */
    int key;                     /* Number to search for. */
    int* slot;                   /* Position at which key is found. */
    int stream_status;           /* For scanf()'s return value. */
  
    banner();
    puts( "\n Find a key value in an array of integers." );
    setup( &search, &fin );
    get_data( &search, fin );
    qsort( (void*)search.data, search.n, sizeof(int), sort_int_up ); 

    printf( " %i data items read; ready to search.\n", search.n );
    puts( "\n Enter numbers to search for; period to quit." );
    for(;;) {   
        printf( " What number do you wish to find? " );
        stream_status = scanf( "%i", &key );
        if (stream_status < 1) break;

        slot = bsearch( (const void*)&key, (const void*)search.data, 
                                search.n, sizeof(int), sort_int_up );  
        if (slot == NOT_FOUND) 
             printf( " Key value %i is not in table.\n\n", key );
        else printf( " Key value %i was found in slot %li.\n\n", 
                     key, slot - search.data );
    }  
    bye();   
}    

/* --------------------------------------------------------------------- 
**  Construct and initialize a data-pack and an input stream.
**      Read (from user) name of input file and open it.  
**      Allocate memory for MAX data items.  Errors are fatal.                
*/
#define MAX          1000
void 
setup( data_pack* spec, stream* infile )
{  
    char filename[80];                      /* For name of input file */

    spec->max = MAX;                        /* Space for MAX items. */
    spec->n = 0;                            /* Currently empty. */
    spec->data = malloc( MAX * sizeof(int) );  
    if (spec->data == NULL) 
       fatal( " Error: not enough memory for %i ints\n", MAX ); 

    printf( " Enter name of data file to be searched: " );
    scanf( "%79s",filename );
    *infile = fopen ( filename, "r" ); 
    if (*infile == NULL) 
       fatal( " Error: couldn't open input file %s\n", filename ); 
}

/* --------------------------------------------------------------------- 
** Read up to max integers from input stream and store in array. 
*/ 
void 
get_data( data_pack* searchp, stream instream )
{   
    int stream_status;            /* For scanf()'s return value. */
    int* cursor = searchp->data;        /* Scanning pointer.     */
    int* end = cursor + searchp->max;   /* An off-board sentinel */
 
    for( ; cursor<end; ++cursor) {
        stream_status = fscanf( instream, "%i", cursor );
        if( stream_status != 1 ) break;
    }
    searchp->n = cursor-searchp->data;  /* Actual # of items read. */
}

/* --------------------------------------------------------------------- 
**  Comparison function for qsort() and bsearch(). 
**  This simple comparison algorithm can be used for any integer type.
*/ 
int  
sort_int_up( const void* ip1, const void* ip2 )
{
    int i1 = *(int *)ip1;
    int i2 = *(int *)ip2;
    return i1 - i2 ;
}


/* Output ------------------------- Displayed on screen: ---------- /

 Find a key value in an array of integers.
 Please enter name of data file to be searched: rand.in

 Ready to read the file.
 1000 data items read; ready to search.

 Enter numbers to search for; period to quit.
 What number do you wish to find? 35
 Key value 35 is not in table.

 What number do you wish to find? 34
 Key value 34 is not in table.

 What number do you wish to find? 2447
 Key value 2447 was found in slot 233.

 What number do you wish to find? .


 Normal termination.
*/