/* --------------------------------------------------------------------------
**  Insertion sort.
**      Figure 20.17:  the main() program for insertion sort.
**      Figure 20.18:  Setup for insertion sort.  
**      Figure 20.15:  Input into an array.
**      Figure 20.16:  Output from an array. 
**      Figure 20.19:  Insertion sort for ascending order.
** --------------------------------------------------------------------------
*/
#include "tools.h"

typedef struct { float* data;   /* Dynamic data array. */
                 int n;         /* Data length. */
                 int max;       /* Allocation length. */
} data_pack; 
 
void setup( data_pack* sortp );                  /* Data-pack constructor. */
void get_data( data_pack* sort, stream instream );     /* Fill data array. */
void print_data( data_pack sort, stream outstream ); /* Output data array. */ 
void sort_data( data_pack sort );                       /* Insertion sort. */

/* ----------------------------------------------------------------------- */
void main( void )
{   
    data_pack sort;     /* Data array package */
    banner();

    setup( &sort );

    say( " Reading data from stdin." );     
    get_data( &sort, stdin );

    say( " %i data items read:", sort.n );
    print_data( sort, stderr );

    say( " Beginning to sort." );     
    sort_data( sort );

    say( " Data sorted; writing to output stream." );           
    print_data( sort, stdout );   
    bye();
}    

/* ----------------------------------------------------------------------- */
/*  Constructs and initializes a data package ---------------------------- */
#define LENGTH 20
void                       /* Allocate memory for data.  Errors are fatal. */
setup( data_pack* sortp )
{  
    sortp->max = LENGTH;                       /* Read up to LENGTH items. */
    sortp->n = 0;                              /* Array is currently empty.*/
    sortp->data = malloc( LENGTH * sizeof(float) ); 
    if (sortp->data == NULL) 
       fatal( " Error: not enough memory for %i floats\n", LENGTH ); 
}

/* ----------------------------------------------------------------------- */
/* Read data values from instream and store in the data package. --------- */ 
void 
get_data( data_pack* sortp, stream instream )
{   
    int stream_status;
    float* cursor = sortp->data; 
    float* end = cursor + sortp->max;  /* off-board sentinel */
 
    for( ; cursor < end; ++cursor) {
        stream_status = fscanf( instream, "%g", cursor );
        if( stream_status != 1 ) break;
    }
    sortp->n = cursor - sortp->data;  /* Actual # of items read, stored. */
}

/* ----------------------------------------------------------------------- */
/* Print data package values, one per line, to selected stream. ---------- */ 
void 
print_data( data_pack sort, stream outstream )
{   
    float* cursor = sort.data; 
    float* end = cursor + sort.n;   /* an off-board sentinel */

    for( ; cursor<end; ++cursor) {   
        fprintf( outstream, "%.7g\n", *cursor );     
    }
}

/* ----------------------------------------------------------------------- */
/* Sort n values starting at head by an insertion sort algorithm. -------- */
void
sort_data( data_pack sort )  
{
    float* end = sort.data + sort.n;                /* Off-board sentinel. */
    float* pass;                /* Starting point for pass through array.  */
    float* hole;                /* Array slot containing no data.          */
    float newcomer;             /* Data value being inserted on this pass. */

    for (pass = sort.data + 1; pass < end; ++pass) { 
        newcomer = *pass;       /* Pick up next item. */

        /* ...and insert into the sorted portion of the array. */
        for (hole = pass; hole > sort.data; --hole) {
            if (*(hole-1) <= newcomer) break;  /* Insertion slot is found. */
            *hole = *(hole-1);                 /* Move item back one slot. */
        }
        *hole = newcomer;
    }
}