/*
 * https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#ifndef NNODES
#define NNODES 25
#endif

/*
 * non-list misc functions
 */

/** rand_int for use with shuffle */
static int rand_int (int n)
{
    int limit = RAND_MAX - RAND_MAX % n, rnd;

    rnd = rand();
    for (; rnd >= limit; )
        rnd = rand();

    return rnd % n;
}

/** shuffle integer array of size 'n'
 *  (using fisher-yates method)
 */
void shuffle (int *a, int n)
{
    int i, tmp;
    while (n-- > 1) {
        i = rand_int (n + 1);
        tmp  = a[i];
        a[i] = a[n];
        a[n] = tmp;
    }
}

/*
 * list structs and functions
 */

typedef struct node_t {     /* list node */
    int data;
    struct node_t *prev, *next;
} node_t;

typedef struct {            /* list wrapper with head & tail pointers */
    node_t *head, *tail;
    size_t size;
} list_t;

/** create new node initialize all members */
node_t *createnode (int v)
{
    node_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node) {                            /* validate allocation */
        perror ("malloc-node");
        return NULL;
    }
    node->data = v;                         /* initialize members values */
    node->prev = node->next = NULL;
    
    return node;    /* return new node */
}

/** add node at end of list, update tail to end */
node_t *add (list_t *l, int v)
{
    node_t *node = createnode (v);      /* allocate node */
    if (!node)                          /* validate allocation */
        return NULL;
    
    if (!l->head)                       /* if 1st node, node is head/tail */
        l->head = l->tail = node;
    else {                              /* otherwise */
        node->prev = l->tail;           /* set prev to tail */
        l->tail->next = node;           /* add at end, update tail pointer */
        l->tail = node;
    }
    l->size++;
    
    return node;    /* return new node */
}

/** add node in-order */
node_t *add_ordered (list_t *l, int v)
{
    node_t **ppn = &l->head;            /* pointer to pointer */
    node_t *pn = l->head;               /* pointer to node */
    
    node_t *node = createnode (v);      /* allocate node */
    if (!node)                          /* validate allocation */
        return NULL;
    
    l->size++;                      /* increment list size */
    
    if (!l->head) {                 /* if 1st node, node is head/tail */
        l->head = l->tail = node;
        return l->tail;
    }
    
    while (pn) {                        /* iterate over list */
        if (v < pn->data) {             /* if new node goes before current */
            node->prev = (*ppn)->prev;  /* set node prev to current prev */
            *ppn = node;                /* set current address to node */
            pn->prev = node;            /* set next->prev to current */
            node->next = pn;            /* set current->next to next */
            return node;
        }
        ppn = &pn->next;            /* get address of next node */
        pn = pn->next;              /* get next node pointer */
    }
    
    node->prev = l->tail;
    l->tail->next = node;           /* node goes at end, update tail pointer */
    l->tail = node;
    
    return node;
}

/** print all nodes in list */
void prn (list_t *l)
{
    if (!l->head) {
        puts ("list-empty");
        return;
    }
    for (node_t *n = l->head; n; n = n->next)
        printf (" %d", n->data);
    putchar ('\n');
}

/** print all nodes in list in reverse */
void prnrev (list_t *l)
{
    if (!l->tail) {
        puts ("list-empty");
        return;
    }
    for (node_t *n = l->tail; n; n = n->prev)
        printf (" %d", n->data);
    putchar ('\n');
}

/** delete node with value v from list (for loop) */
void del_node (list_t *l, int v)
{
    node_t **ppn = &l->head;    /* pointer to pointer */
    node_t *pn = l->head;       /* pointer to node */
    
    for (; pn; ppn = &pn->next, pn = pn->next) {
        if (pn->data == v) {
            *ppn = pn->next;            /* set node at address to next */
            
            if (pn != l->tail)          /* prev is next prev */
                (*ppn)->prev = pn->prev;
            else                        /* deleting tail, set tail to prev */
                l->tail = pn->prev;
            
            free (pn);                  /* free current */
            
            if (l->size)
                l->size--;
            else
                fputs ("error: size negative warning.\n", stderr);
                
            break;
        }
    }
}

/** delete all nodes in list */
void del_list (list_t *l)
{
    node_t *n = l->head;
    
    while (n) {
        node_t *victim = n;
        n = n->next;
        free (victim);
    }
    
    l->head = l->tail = NULL;
    l->size = 0;
}

int main (void) {
    
    list_t l = { NULL, NULL, 0 };   /* initialize list pointers NULL */
    int a[NNODES];                  /* array to shuffle */
    
    srand (time (NULL));            /* seed random number generator */
    
    for (int i = 0; i < NNODES; i++) {  /* fill array 1 - 10 */
        // add (&l, i+1);
        a[i] = i+1;
    }
    shuffle (a, NNODES);            /* shuffle array */
    
    for (int i = 0; i < NNODES; i++) {  /* add shuffled values in order */
#ifdef DEBUG
        printf ("adding  : %d\n", a[i]);
#endif
        // add (&l, a[i]);
        add_ordered (&l, a[i]);
    }
    
    printf ("list size: %zu\n\n", l.size);
    
    prn (&l);                   /* print list forward */
    putchar ('\n');
    
    prnrev (&l);                /* print list reverse */
    putchar ('\n');
    
    add (&l, NNODES + 1);       /* add at end for tail-pointer test */
    
    printf ("list size: %zu\n\n", l.size);
    
    prn (&l);                   /* print list forward */
    putchar ('\n');
    
    prnrev (&l);                /* print list reverse */
    putchar ('\n');
    
    del_node (&l, NNODES + 1);  /* delete tail node */
    
    printf ("list size: %zu\n\n", l.size);
    
    prn (&l);                   /* print list forward */
    putchar ('\n');
    
    prnrev (&l);                /* print list reverse */
    putchar ('\n');
        
    shuffle (a, NNODES);        /* shuffle array again */
    
    for (int i = 0; i < NNODES; i++) {  /* remove nodes in random order */
#ifdef DEBUG
        printf ("deleting: %d\n", a[i]);
#endif
        del_node (&l, a[i]);
    }
    printf ("list size: %zu\n\n", l.size);
    
    prn (&l);           /* print list ("list-empty") */
    prnrev (&l);        /* print list reverse ("list-empty") */
    
    del_list (&l);      /* delete list (does nothing list-empty) */
}

/** delete node with value v from list (for loop) */
// void del_node (list_t *l, int v)
// {
//     node_t **ppn = &l->head;    /* pointer to pointer */
//     node_t *pn = l->head;       /* pointer to node */
//     
//     for (; pn; ppn = &pn->next, pn = pn->next) {
//         if (pn->data == v) {
//             node_t *pprev = pn->prev;   /* save current prev */
//             *ppn = pn->next;            /* set node at address to next */
//             
//             if (pn == l->head)          /* deleting head, prev is NULL */
//                 (*ppn)->prev = NULL;
//             else if (pn == l->tail)     /* deleting tail, tail is prev */
//                 l->tail = pn->prev;
//             else                        /* set prev to saved prev */
//                 (*ppn)->prev = pprev;
//             
//             free (pn);                  /* free current */
//             break;
//         }
//     }
// }