// Copyright (C) 2004-2009 Christoph Kubisch & Eike Decker
// This file is part of the "Luxinia Engine".
// For conditions of distribution and use, see copyright notice in luxiniapublicsdk.txt
//
// <Authors: Christoph Kubisch, Eike Decker>


#ifndef __LUXCORE_MACROLINKEDLIST_H__
#define __LUXCORE_MACROLINKEDLIST_H__

//////////////////////////////////////////////////////////////////////////
// Macro-based Double Linked List
//
// Each struct must contain 2 pointers (next & prev) to own type
// The LN_ - macros allows manual naming of next & prev variables
// The ListNode_ macros assume next & prev as variable names
// Don't use this in C++, prefer templates


#ifndef NULL
	#define NULL 0
#endif

#ifndef XOrSwap
	#define XOrSwap(a,b) {*(int*)&(a)^=*(int*)&(b);*(int*)&(b)^=*(int*)&(a);*(int*)&(a)^=*(int*)&(b);}
#endif


////////////////////////////////////////////////////////////////////////////////
// LN_
// Generalized linked list node system

// initialises the node - next = prev = this
#define LN_init(node,next,prev) {node->next=node; node->prev=node;}

#define LN_next(node,next,prev) (node->next)
#define LN_prev(node,next,prev) (node->prev)

// inserts a node next to the prevNode
#define LN_insertNext(prevNode,insertNode,next,prev) {\
	if (prevNode!=NULL) { \
		prevNode->next->prev = insertNode;\
		prevNode->next->prev->next = prevNode->next;\
		prevNode->next->prev->prev = prevNode;\
		prevNode->next = prevNode->next->prev;\
	} else prevNode = insertNode;\
}
// inserts a node before nextNode
#define LN_insertPrev(nextNode,insertNode,next,prev) {\
	if (nextNode!=NULL) { \
		nextNode->prev->next = insertNode;\
		nextNode->prev->next->prev = nextNode->prev;\
		nextNode->prev = nextNode->prev->next;\
		nextNode->prev->next = nextNode;\
	} else nextNode = insertNode;\
}

// appends listB to the end of listA
#define LN_append(listA,listB,next,prev) {\
	XOrSwap(listA->prev,listB->prev); \
	listA->prev->next = listA;\
	listB->prev->next = listB;}

// we will try to set browse to the node at given index
// if we cant find it, we will set browse = NULL
// and indexCounter will have the amount of nodes to be 
// added to make the Index happen
#define LN_getAtIndex(listNodeHead, browse, indexCounter,next,prev)\
	LN_getAtOffset(listNodeHead,listNodeHead, browse, indexCounter,next,prev)
#define LN_getAtOffset(listNodeHead,base, browse, indexCounter,next,prev) { \
	browse = base; \
	if (indexCounter && browse){\
		if (indexCounter>0){\
			while (indexCounter > 0){\
				if (browse->next == listNodeHead)\
					break;\
				browse = browse->next;\
				indexCounter--;\
			}\
		}\
		else if (indexCounter<0){\
			while (indexCounter < 0){\
				if (browse->prev == listNodeHead->prev)\
					break;\
				browse = browse->prev;\
				indexCounter++;\
			}\
		}\
		/* we havent found anything */\
		if (indexCounter != 0)\
			browse = NULL;\
	}\
	if (!listNodeHead)\
		indexCounter++;\
}
// stores position within the list in "pos"
#define LN_getNodeIndex(listNodeHead, browse, pos,next,prev) { \
	pos = 0;\
	browse = listNodeHead; \
	do { \
		pos++; browse = browse->next; \
	} while (listNodeHead!=browse); \
}

// removes a node - the head could be any listnodepointer
#define LN_remove(listNodeHead,removeNode,next,prev) {\
	if (listNodeHead && removeNode){\
	if (listNodeHead == removeNode || listNodeHead==NULL) listNodeHead = removeNode->next;\
	removeNode->prev->next = removeNode->next;\
	removeNode->next->prev = removeNode->prev;\
	removeNode->next = removeNode->prev = removeNode; \
	if (listNodeHead == removeNode) listNodeHead = NULL; \
	}\
}

// remove a node from a list without head - results in a singleitem list
#define LN_rip(listnode,next,prev) {\
	if (listnode->next!=listnode) {\
		listnode->prev->next = listnode->next;\
		listnode->next->prev = listnode->prev;\
		listnode->next = listnode->prev = listnode;\
	}\
}

// counts size of nodes, 
// listNode: node of the listn; 
// browse: valid browsing variable (will be used)
// iSize: integer - result of counting
#define LN_countSize(listNode,browse,iSize,next,prev) {\
	iSize = 0;\
	browse = listNode;\
	if (browse != NULL)\
	do {\
		browse = browse->next;\
		iSize++;\
	} while (browse != listNode);\
}

// forEachConinue for continuing
#define LN_forEachContinue(listNode,browse,next,prev) \
	{browse = browse->next; \
	if (browse == listNode) break; else continue;}

// ListNode_forEach using next
#define LN_forEach(listNode,browse,next,prev) {\
	if (listNode != NULL){ \
	browse = (listNode);\
	do { 
#define LN_forEachEnd(listNode,browse,next,prev) \
		browse = browse->next;\
	} while (browse!=(listNode) && listNode!=NULL);\
	} \
}

// add last
#define LN_addLast(listNodeHead,node,next,prev) {\
	if (listNodeHead){\
		LN_insertPrev(listNodeHead,node,next,prev);\
	}else\
		listNodeHead = node;\
}
// add first
#define LN_addFirst(listNodeHead,node,next,prev)  {\
	LN_insertPrev(listNodeHead,node,next,prev); \
	listNodeHead = node; \
}

// Push / Pop
// popps the first node of the list 
// thePoppedNode: any valid pointer for the node
#define LN_pushFront(listNodeHead, pushedNode,next,prev) \
		LN_addFirst(listNodeHead, pushedNode,next,prev)
#define LN_popFront(listNodeHead, thePopedNode,next,prev) {\
	thePopedNode = listNodeHead;\
	LN_remove(listNodeHead, thePopedNode,next,prev); \
}

#define LN_pushBack(listNodeHead, pushedNode,next,prev)	LN_addLast(listNodeHead,pushedNode,next,prev)
#define LN_popBack(listNodeHead, thePopedNode,next,prev)	{\
	if (listNodeHead){	\
		thePopedNode = listNodeHead->prev;	\
		LN_remove(listNodeHead,thePopedNode,next,prev);	\
	}\
	else thePopedNode = NULL;	\
}


// swaps nodes that are next to each other
#define LN_swapNeighbor(listNodeHead,a, b,next,prev) {\
	if ( a && b && listNodeHead){\
	if (a->next == b){\
		LN_remove(listNodeHead,a,next,prev);\
		LN_insertNext(b,a,next,prev);\
	}\
	else{\
		LN_remove(listNodeHead,b,next,prev);\
		LN_insertNext(a,b,next,prev);\
	}\
	}\
}

#define LN_swapContent(Type,a,b,next,prev) {\
	Type d_temp;	\
	memcpy(&d_temp, a, sizeof(Type));\
	memcpy(a,b,sizeof(Type));\
	memcpy(b,&d_temp,sizeof(Type));\
	b->next = a->next;\
	a->next = d_temp.next;\
	b->prev = a->prev;\
	a->prev = d_temp.prev;\
}

#define LN_destroyList(listNodeHead, Type, destroyFunc,next,prev) {\
	while (listNodeHead != NULL)							\
	{														\
		Type *d_node;										\
		LN_popFront(listNodeHead, d_node,next,prev);			\
		destroyFunc(d_node);									\
	}														\
}

// sorts the nodes using cmpTest func
// if cmpTest returns a value a swap is done
#define LN_sortBubble(listNodeHead,Type,cmpFunc,next,prev) {\
	if (listNodeHead){\
		uchar d_change = 1;		\
		int	d_count,d_i;		\
		Type *d_browse;				\
		LN_countSize(listNodeHead,d_browse,d_count,next,prev);	\
		d_count--;					\
		while(d_change){			\
			d_change = 0;			\
			d_i = 0;				\
			LN_forEach(listNodeHead,d_browse,next,prev)					\
				if (d_i < d_count){							\
					if (cmpFunc(d_browse,d_browse->next)){	\
						LN_swapContent(Type,d_browse,d_browse->next,next,prev);\
						d_change = 1;\
					}\
				}\
				else break;\
				d_i++;\
			LN_forEachEnd(listNodeHead,d_browse,next,prev);\
			d_count--;\
		}\
	}\
}

// From http://efgh.com/software/llmsort.htm
// Author: Philip J. Erdelsky
#define LN_sortTapeMerge(listNodeHead,Type,cmpFunc,next,prev)		\
{																	\
  uint d_base;														\
  uint d_block_size;												\
  Type	*d_browse;													\
																	\
  struct tape_s														\
  {																	\
    Type *first, *last;												\
    uint count;														\
  } d_tape[4];														\
																	\
  /* Distribute the records alternately to tape[0] and tape[1]. */	\
  memset(d_tape,0,sizeof(struct tape_s)*4);							\
																	\
  d_tape[0].count = d_tape[1].count = 0;							\
  d_tape[0].first = NULL;											\
  d_base = 0;														\
  while (listNodeHead != NULL)										\
  {																	\
    LN_popFront(listNodeHead,d_browse,next,prev);					\
    LN_pushBack(d_tape[d_base].first,d_browse,next,prev);			\
    d_tape[d_base].count++;											\
    d_base ^= 1;													\
  }																	\
																	\
  /* If the list is empty or contains only a single record, then */	\
  /* tape[1].count == 0L and this part is vacuous.               */	\
																	\
  for (d_base = 0, d_block_size = 1; d_tape[d_base+1].count != 0;	\
    d_base ^= 2, d_block_size <<= 1)								\
  {																	\
    int d_dest;														\
    struct tape_s *d_tape0, *d_tape1;								\
    d_tape0 = d_tape + d_base;										\
    d_tape1 = d_tape + d_base + 1;									\
    d_dest = d_base ^ 2;											\
    d_tape[d_dest].count = d_tape[d_dest+1].count = 0;				\
    for (; d_tape0->count != 0; d_dest ^= 1)						\
    {																\
      uint n0, n1;													\
      struct tape_s *d_output_tape = d_tape + d_dest;				\
      n0 = n1 = d_block_size;										\
      while (1)														\
      {																\
        Type *d_chosen_record;										\
        struct tape_s *d_chosen_tape;								\
        if (n0 == 0 || d_tape0->count == 0)							\
        {															\
          if (n1 == 0 || d_tape1->count == 0)						\
            break;													\
          d_chosen_tape = d_tape1;									\
          n1--;														\
        }															\
        else if (n1 == 0 || d_tape1->count == 0)					\
        {															\
          d_chosen_tape = d_tape0;									\
          n0--;														\
        }															\
		else if (cmpFunc(d_tape0->first,d_tape1->first))			\
        {															\
          d_chosen_tape = d_tape1;									\
          n1--;														\
        }															\
        else														\
        {															\
          d_chosen_tape = d_tape0;									\
          n0--;														\
        }															\
		d_chosen_tape->count--;										\
		LN_popFront(d_chosen_tape->first,d_chosen_record,next,prev);\
		if (d_output_tape->count == 0)								\
			d_output_tape->first = NULL;							\
        LN_pushBack(d_output_tape->first,d_chosen_record,next,prev);\
        d_output_tape->count++;										\
      }																\
    }																\
  }																	\
																	\
  listNodeHead = d_tape[d_base].first;								\
}

//////////////////////////////////////////////////////////////////////////
// ListNode_
// next,prev as names predefinition

#define LISTNODEVARS *prev, *next

// initialises the node - next = prev = this
#define ListNode_init(node) LN_init(node,next,prev)

#define ListNode_next(node) LN_next(node,next,prev)
#define ListNode_prev(node) LN_prev(node,next,prev)

// inserts a node next to the prevNode
#define ListNode_insertNext(prevNode,insertNode)	LN_insertNext(prevNode,insertNode,next,prev)
// inserts a node before nextNode
#define ListNode_insertPrev(nextNode,insertNode)	LN_insertPrev(nextNode,insertNode,next,prev)

// appends listB to the end of listA
#define ListNode_append(listA,listB)				LN_append(listA,listB,next,prev)

// we will try to set browse to the node at given index
// if we cant find it, we will set browse = NULL
// and indexCounter will have the amount of nodes to be 
// added to make the Index happen
#define ListNode_getAtIndex(listNodeHead, browse, indexCounter)\
	ListNode_getAtOffset(listNodeHead,listNodeHead, browse, indexCounter)
#define ListNode_getAtOffset(listNodeHead,base, browse, indexCounter)	LN_getAtOffset(listNodeHead,base, browse, indexCounter,next,prev)
// stores position within the list in "pos"
#define ListNode_getNodeIndex(listNodeHead, browse, pos)				LN_getNodeIndex(listNodeHead, browse, pos,next,prev)

// removes a node - the head could be any listnodepointer
#define ListNode_remove(listNodeHead,removeNode)						LN_remove(listNodeHead,removeNode,next,prev)

// remove a node from a list without head - results in a singleitem list
#define ListNode_rip(listnode)		LN_rip(listnode,next,prev)

// counts size of nodes, 
// listNode: node of the list; 
// browse: valid browsing variable (will be used)
// iSize: integer - result of counting
#define ListNode_countSize(listNode,browse,iSize)	LN_countSize(listNode,browse,iSize,next,prev)			

// forEachConinue for continuing
#define ListNode_forEachContinue(listNode,browse)	LN_forEachContinue(listNode,browse,next,prev)

// ListNode_forEach iteration using next
#define ListNode_forEach(listNode,browse)			LN_forEach(listNode,browse,next,prev)
#define ListNode_forEachEnd(listNode,browse)		LN_forEachEnd(listNode,browse,next,prev)

// add last, in case node is the first, it must be inited
#define ListNode_addLast(listNodeHead,node)			LN_addLast(listNodeHead,node,next,prev)
// add first
#define ListNode_addFirst(listNodeHead,node)		LN_addFirst(listNodeHead,node,next,prev)

// Push / Pop
// popps the first node of the list 
// thePoppedNode: any valid pointer for the node
#define ListNode_pushFront(listNodeHead, pushedNode)	LN_addFirst(listNodeHead, pushedNode,next,prev)
#define ListNode_popFront(listNodeHead, thePoppedNode)	LN_popFront(listNodeHead, thePoppedNode, next,prev)

#define ListNode_pushBack(listNodeHead, pushedNode)		LN_addLast(listNodeHead,pushedNode,next,prev)
#define ListNode_popBack(listNodeHead, thePoppedNode)	LN_popBack(listNodeHead, thePoppedNode, next,prev)


// swaps nodes that are next to each other
#define ListNode_swapNeighbor(listNodeHead,a, b)		LN_swapNeighbor(listNodeHead,a, b, next,prev)
#define	ListNode_swapContent(Type,a,b)					LN_swapContent(Type,a,b,next,prev)

#define ListNode_destroyList(listNodeHead, Type, destroyFunc) LN_destroyList(listNodeHead, Type, destroyFunc, next,prev)


// sorts the nodes using cmpTest func
// if cmpTest returns a value a swap is done
#define ListNode_sortBubble(listNodeHead,Type,cmpFunc)		LN_sortBubble(listNodeHead,Type,cmpFunc,next,prev)
#define ListNode_sortTapeMerge(listNodeHead,Type,cmpFunc)	LN_sortTapeMerge(listNodeHead,Type,cmpFunc, next,prev)



#endif
