/*
 *  mergel.c
 *  
 *
 *  Created by Herbert J. Bernstein on 2/23/11.
 *  Copyright 2011 All rights reserved.
 *
 */

/*To test this program the data you need is
 
 2
 1
 2
 2
 -5
 10
 6
 7
 3
 12
 42
 9
 -7
 4
 12
 1
 0
 18
 
 
 which will produce the output 
 
 
 number of items list a:  2
 a element 0:  1
 a element 1:  2
 number of items list b:  2
 b element 0:  -5
 b element 1:  10
 merged list c:
 -5
 1
 2
 10
 
 number of items list a:  6
 a element 0:  7
 a element 1:  3
 a element 2:  12
 a element 3:  42
 a element 4:  9
 a element 5:  -7
 number of items list b:  4
 b element 0:  12
 b element 1:  1
 b element 2:  0
 b element 3:  18
 merged list a:
 -7
 3
 7
 9
 12
 42
 
 merged list b:
 0
 1
 12
 18
 
 merged list c:
 -7
 0
 1
 3
 7
 9
 12
 12
 18
 42
 
 updated list c:
 0
 1
 2
 3
 4
 5
 6
 -7
 0
 1
 3
 7
 9
 12
 12
 18
 42
 
 reupdated list c:
 0
 1
 2
 3
 4
 5
 6
 -7
 0
 1
 3
 7
 9
 12
 12
 18
 42
 0
 0
 0
 0
 22
 
 
 */


#include "mergel.h"
#include <stdio.h>
#include <stdlib.h>

/* Create a listnode handle */

int listnodecreate( listnodehandle * ln ) {
    *ln = (listnodehandle) malloc(sizeof(listnode));
    if (! (*ln)) return 1;
    (*ln)->next = NULL;
    (*ln)->value = 0;
    return 0;
}

/* Free a listnode handle */

int listnodefree( listnodehandle * ln ) {
    if (!ln) return 1;
    free(*ln);
    *ln = 0;
    return 0;
}

/* Free a list */

int listfree( listnodehandle  * l ) {
    listnodehandle ln;
    if (!l) return 1;
    while (*l) {
        ln = (*l)->next;
        if (listnodefree(l)) return 1;
        (*l) = ln;
    }
    return 0;
}

/* Append a data at the end of the list */

int listappend ( listnodehandle *l, int value ){
    listnodehandle ln, cn;
    if (!l) return 1;
    if ( listnodecreate(&cn)) return 1;
    cn->value = value;
    if (!(*l)) {
        *l = cn;
        return 0;
    }
    ln = *l;
    while (ln) {
        if (!ln->next) {
            ln->next = cn;
            return 0;
        }
        ln = ln->next;
    }
    return 0;
}

/* Insert data in front of the list */

int listprepend ( listnodehandle *l, int value ){
    listnodehandle cn;
    if (!l) return 1;
    if ( listnodecreate(&cn)) return 1;
    cn->value = value;
    if (*l) cn->next = *l;
    *l = cn;
    return 0;
}

/* Insert data at a particular index of a list */

int listinsert ( listnodehandle *l, int value, size_t index ){
    listnodehandle ln, pn, cn, dn;
    size_t jindex;
    if (!l) return 1;
    if ( listnodecreate(&cn)) return 1;
    cn->value = value;
    if (!(*l)) {
        *l = cn;
        return 0;
    }
    
    /* index 0 is the front of the list */
    
    jindex = 0;
    if (index == 0) {
        return listprepend(l,value);
    }
    
    /* scan forward past jindex-1 nodes */
    
    ln = *l;
    pn = NULL;
    while (ln && jindex < index) {
        pn = ln;
        ln = ln->next;
        jindex++;
    }
    
    /* If jindex is less than index-1, the current
       list is too short, we need to pad */
    
    while (jindex < index-1) {
        if ( listnodecreate(&dn)) return 1;
        pn->next = dn;
        pn = dn;
        jindex++;
    }
    
    if (ln) {
        cn->next = ln;
    }
    pn->next = cn;
    
    return 0;
    
}

/* print list l */

int printl( listnodehandle l ) {
    if (!l) return 1;
    while (l) {
        fprintf(stdout,"%d\n",l->value);
        l = l->next;
    }
    return 0;
}

/* merge list a and b and create list c */

int mergel( listnodehandle a, listnodehandle b, listnodehandle * c) {
    
    listnodehandle af = a;
    listnodehandle bf = b;
    listnodehandle cn;        /* next node */
    listnodehandle cp = NULL; /* previous node */
        
    while (af && bf) {
        if (listnodecreate(&cn)) return 1;
        if (af->value < bf->value) {
            cn->value = af->value;
            af = af->next;
        } else {
            cn->value = bf->value;
            bf = bf->next;
        }
        if (cp) {
            cp->next = cn;
            cp = cn;
        } else {
            *c = cn;
            cp = cn;
        }
    }

    if (bf) af = bf;

    while (af) {
        if (listnodecreate(&cn)) return 1;
        cn->value = af->value;
        af = af->next;
        if (cp) {
            cp->next = cn;
            cp = cn;
        } else {
            *c = cn;
            cp = cn;
        }
    }
    
    return 0;

}

int main(int argc, char **argv) {
    listnodehandle a=NULL, b=NULL, c;
    int ka, kb, kc, i, value;
    listnode cn;
    
    /* First assume pre-sorted lists */
    
    /* Read in list a*/
    
    fprintf(stdout,"\nnumber of items list a: ");
    fscanf(stdin,"%d",&ka);
    fprintf(stdout," %d", ka);
    for(i = 0; i < ka; i++) {
        fprintf(stdout,"\na element %d: ",i);
        fscanf(stdin,"%d",&value);
        fprintf(stdout," %d", value);
        listappend(&a,value);
    }
    
    /* Read in list b */
    fprintf(stdout,"\nnumber of items list b: ");
    fscanf(stdin,"%d",&kb);
    fprintf(stdout," %d", kb);
    for(i = 0; i < kb; i++) {
        fprintf(stdout,"\nb element %d: ",i);
        fscanf(stdin,"%d",&value);
        fprintf(stdout," %d", value);
        listappend(&b,value);
    }
    
    /* Create merged list c */
    
    mergel(a,b,&c);
    fprintf(stdout,"\n merged list c:\n");
    printl(c);
    
    /* Now get rid of all three lists and do it again with unsorted
       data by merging in each element as we get it */
    
    listfree(&a);
    listfree(&b);
    listfree(&c);

    /* Read in list a*/
    
    fprintf(stdout,"\nnumber of items list a: ");
    fscanf(stdin,"%d",&ka);
    fprintf(stdout," %d",ka);
    
    /* Put the element onto list a via cn using mergel to do the sort */
    
    for(i = 0; i < ka; i++) {
        fprintf(stdout,"\na element %d: ",i);
        fscanf(stdin,"%d",&value);
        fprintf(stdout," %d", value);
        cn.value = value;
        cn.next = NULL;
        mergel(a,&cn,&c);
        listfree(&a);
        a = c;
        c = NULL;
     }

    /* Read in list b*/
    
    fprintf(stdout,"\nnumber of items list b: ");
    fscanf(stdin,"%d",&kb);
    fprintf(stdout," %d", kb);
    
    /* Put the element onto list a via cn using mergl to do the sort */
    
    for(i = 0; i < kb; i++) {
        fprintf(stdout,"\nb element %d: ",i);
        fscanf(stdin,"%d",&value);
        fprintf(stdout," %d", value);
        cn.value = value;
        cn.next = NULL;
        mergel(b,&cn,&c);
        listfree(&b);
        b = c;
        c = NULL;
    }
    
    /* Create merged list c */
    
    mergel(a,b,&c);
    fprintf(stdout,"\n merged list a:\n");
    printl(a);
    fprintf(stdout,"\n merged list b:\n");
    printl(b);
    fprintf(stdout,"\n merged list c:\n");
    printl(c);
    
    /* test the insert operations */
    
    listinsert(&c,0,0);
    listinsert(&c,4,1);
    listinsert(&c,1,1);
    listinsert(&c,5,3);
    listinsert(&c,2,2);
    listinsert(&c,6,5);
    listinsert(&c,3,3);
    fprintf(stdout,"\n updated list c:\n");
    printl(c);
    listinsert(&c,22,22);
    fprintf(stdout,"\n reupdated list c:\n");
    printl(c);

    return 0;
}