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

/* --------------------------------------------------------------------- */

struct NumNodeType
{
    int dat;
    struct NumNodeType *next;
};

/* Define new type names:  BaseElem   and   BasePtr  
* to refer to the list nodes.  These new names can
* be used in place of struct NumNodeType and
* struct NumNodeType *  repsectively.
*/
typedef struct NumNodeType BaseElem;
typedef struct NumNodeType * BasePtr;

/* --------------------------------------------------------------------- */
int str_to_int(char s[])
{
  
   int i=0,j,d,num=0;
   char c;

   while (s[i] != '\0')
   {
      c = s[i];
      
      if ( c >= '0' && c <= '9')
       d = c - '0';
      if ( c >= 'A' && c <= 'K')
       d = (c - 'A') + 10;
        
      
      //printf("\nDigit %d\n", d);
      num = num * 21 + d;
      i++;
   }

   return num;
}


/* --------------------------------------------------------------------- */

BasePtr GetNode( int val )
{
    BasePtr node;
    node = malloc( sizeof(BaseElem) );
    node->dat = val;
    node->next = NULL;
    return node;    
}


int Length( BasePtr first )
{
    BasePtr move;
    int len=0;
    move = first;
    while (move != NULL)
    {
        len++;
        move = move->next;
    }
    return len;
}


void PrintNode( FILE *ofp, BasePtr node )
{
    fprintf(ofp, "Val: %d\n", node->dat);
    printf("Val: %d\n", node->dat);
}

void PrintList( FILE *ofp, BasePtr first )
{
    BasePtr move;
    move = first;
    while (move != NULL)
    {
        PrintNode( ofp, move);
        move = move->next;
    }
}

void PrintNodeFile( FILE *ofp, BasePtr node )
{
    fprintf(ofp, "Val: %d\n", node->dat);
}

void PrintListFile( FILE *ofp, BasePtr first )
{
    BasePtr move;
    move = first;
    while (move != NULL)
    {
        PrintNodeFile( ofp,  move );
        move = move->next;
    }
}

int Compare( int x, int y)
{
    if (x < y) return -1;
    else if (x == y) return 0;
    else if (x > y) return 1;
}

BasePtr FindInsLoc( BasePtr first, BasePtr node )
{
    BasePtr move, prev;
    int val1, val2;
    int res = -1;
    val2 = node->dat;
    move = first;
    prev = move;

    val1 = move->dat;
    res = Compare( val1, val2 );

    while ( res < 0 && move != NULL)
    {
        prev = move;
        move = move->next;
        if (move != NULL)
        {
            val1 = move->dat;
            res = Compare( val1, val2 );
        }
    }    
    return prev;
}

BasePtr InsertNodeAfter( BasePtr first, BasePtr loc, BasePtr node)
{
    //printf("Insert %d after %d\n", node->dat, loc->dat);
    node->next = loc->next;
    loc->next = node;
    return first;
}


/* --------------------------------------------------------------------- */

int main( int argc, char *argv[] )
{
    BasePtr head, tail, tmp;
    int i;

    FILE *infile, *outfile;
    /* verify that 2 parameters were passed */    
    if ( argc != 3)
    {
        printf("Usage: a.out infile outfile\n");
        return 1;
    }
    /* open input file */
    infile = fopen( argv[1], "r");
    if (!infile)
    {
        printf("ERROR: file %s not available\n", argv[1]);
        return 1;    
    }
    /* open output file */
    outfile = fopen( argv[2], "w");
    if (!outfile)
    {
        printf("ERROR: file %s not available\n", argv[2]);
        return 1;    
    }
    
    int z;
    fscanf(infile, "%d", &z);
  
    char str2[5];
    int k;
    fscanf(infile, "%s", str2);
    k = str_to_int(str2);
    tmp = GetNode(k);
    head=tmp;
    tail=tmp;

    
    fprintf(outfile, "List Size: %d\n", z);
    fprintf(outfile, "Sorted List: \n");
    PrintListFile(outfile, head);        
    printf("List size: %d\n", z);

    /*

    /* now make it work some some random data; the above
     * code is a test case in a controlled situation to make
     * sure things appear to work
     */
  /* insertion sort */

    BasePtr start, p, add;
    int x;
    tmp = GetNode(0);
    start=tmp;
    char str[5];
    
    

    for (i = 1; i < z; ++i)
    {
        fscanf(infile, "%s", str);  
        x = str_to_int(str);
        
        printf("Inserting %d\n", x);
        add = GetNode(x);
        p = FindInsLoc( start, add );
        start = InsertNodeAfter( start, p, add );
        
    }

    printf("----- Sorted list ----- \n");
    PrintList( outfile, start );

    return 0;
}