#ifndef LIST_H
#define LIST_H
#include <stdio.h>
// Single linked list with a single type
#if 0
#define MAKE_LIST(type) \
struct type##_node_t; \
typedef struct { \
    type data; \
    struct type##_node_t *next;  \
} type##_node_t;                 \
typedef struct type##_node_t* type##_node_t_ptr


MAKE_LIST(int);
MAKE_LIST(char);
#endif

// Single linked list with fat struct

#if 1
typedef struct node_ node_t;
typedef struct node_* node_ptr;
typedef enum { INT, UINT, CHAR, FLOAT, DOUBLE, CHAR_PTR, VOID_PTR } node_value_t;

typedef struct node_ {
    int type;
    union {
        int vi;
        unsigned int vui;
        char vc;
        float vf;
        double vd;
        char* vcp;
        void *vptr;
    };
    node_ptr next;
} node_t;

void list_append(node_t *start, node_t *tail)
{
    node_t *n = start;

    while (n->next)
        n = n->next;
    n->next = tail;
}

int list_size(node_t *start)
{
    node_t *n = start;
    int size = 1;
    while (n->next)
    {
        n = n->next;
        ++size;
    }
    return size;
}

node_t *list_nth(node_t *head, int idx)
{
    int i = 0;
    node_t *n = head;
    while (i < idx && n->next)
    {
        ++i;
        n = n->next;
    }
    if (i == idx)
        return n;
    else
        return 0;
}

// TODO: Free memory option
int list_delete_nth(node_t *head, int idx)
{
    int i = 0;
    node_t *n = head;
    node_t *p;
    while (i < idx && n->next)
    {
        ++i;
        p = n;
        n = n->next;
    }
    if (i == idx)
    {
        if (n->next)
        {
            p->next = n->next;
        }
        else
            p->next = 0;

        return 0;
    }
    else
    {
        return -1;
    }
}

node_t *list_tail(node_t *head)
{
    node_t *n = head;
    while (n->next)
        n = n->next;

    return n;
}

int list_is_circular(node_t* start)
{
    node_t* n = start;
    while ((n = n->next) && n != start);
    return start->next && n == start;
}


#endif

//Doubly linked list
#if 1
typedef struct dnode_ dnode_t;
typedef struct dnode_* dnode_ptr;
//typedef enum { INT, UINT, CHAR, FLOAT, DOUBLE, CHAR_PTR, VOID_PTR } dnode_value_t;

typedef struct dnode_ {
    int type;
    union {
        int vi;
        unsigned int vui;
        char vc;
        float vf;
        double vd;
        char* vcp;
        void *vptr;
    };
    dnode_ptr next;
    dnode_ptr prev;
} dnode_t;

void dlist_append(dnode_t *start, dnode_t *tail)
{
    dnode_t *n = start;

    while (n->next)
        n = n->next;
    n->next = tail;
	tail->prev = n;
}

int dlist_size(dnode_t *node)
{
    dnode_t *forward = node;
    dnode_t *backward = node;
    int size = 1;

    while ((backward = backward->prev)) ++size;
    while ((forward = forward->next)) ++size;

    return size;
}

dnode_t *dlist_nth(int idx, dnode_t *start, dnode_t *end, unsigned int size)
{
    int i = 0;
	dnode_t *current = 0;
	int reverse = 0;
	if(end && size) {
        int half = size / 2;
		if(idx > half) {
			reverse = 1;
			i = size - 1;
		}
	}

	current = (reverse) ? end : start;
	while(i != idx && current) {
		current = (reverse) ? current->prev : current->next;
        i += reverse ? -1 : +1;
    }

    return current;
}

dnode_t *dlist_nth_circular(int steps, dnode_t* start)
{
	int i = 0;
	dnode_t* current = start;
	int absteps = steps < 0 ? -steps : steps;
	//for(int i = 0; i != absteps && current; i++)
	while(i++ != absteps && current)
		current = (steps < 0) ? current->prev : current->next;
	return current;
}

int dlist_is_circular(dnode_t* start)
{
	dnode_t* n = start;
    while ((n = n->next) && n != start);
    return start->next && n == start;
}

/*node_t *list_nth(node_t *head, int idx)
*{
*    int i = 0;
*    node_t *n = head;
*    while (i < idx && n->next)
*    {
*        ++i;
*        n = n->next;
*    }
*    if (i == idx)
*        return n;
*    else
*        return 0;
*}
*/
// TODO: Free memory option
/*int list_delete_nth(node_t *head, int idx)
*{
*    int i = 0;
*    node_t *n = head;
*    node_t *p;
*    while (i < idx && n->next)
*    {
*        ++i;
*        p = n;
*        n = n->next;
*    }
*    if (i == idx)
*    {
*        if (n->next)
*        {
*            p->next = n->next;
*        }
*        else
*            p->next = 0;
*
*        return 0;
*    }
*    else
*    {
*        return -1;
*    }
*}
*
*node_t *list_tail(node_t *head)
*{
*    node_t *n = head;
*    while (n->next)
*        n = n->next;
*
*    return n;
*}
*/
#endif
#endif //LIST_H