/* Created by Anjuta version 0.1.7 */
/*	This file will not be overwritten */

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
// use a single ptr to traverse back and forth
// //////////////////////////////////////////////
// | 0   |   | 1  |  | 2   | |  3  | | 4   | | 5   |
// |-----|   |-----| |-----| |-----| |-----| |-----|
// |(1^0)|   |(2^0)| |(3^1)| |(4^2)| |(5^3)| |(4^0)|
//
// Numerator of a node is the element.
// (m^n) is the exclusive or of ptr to m, and ptr to n.
// pStart points to element 0, pEnd points to 5 in this example
//
//
// pStart = pEnd = NULL => list is empty
// pStart = pEnd <> NULL => list is singleton


typedef int T;

//
// dbly link represented by ptr distance
//
typedef struct listNode{
	T elm;
	struct listNode * ptrdiff;
};

typedef struct listNode *plistNode;

//
// conventional dbly link representaion
//
typedef struct dlistNode {
	T elm;
	struct dlistNode *next;
	struct dlistNode *prev;
};

typedef struct dlistNode *pdlistNode;
//

//globls for ptrdiff ds
plistNode pStart, pEnd;

//glbls for conventional
pdlistNode pdHead, pdEnd;

// * for ptrdiff
plistNode NextNode( plistNode pNode, plistNode pPrevNode)
{

	return ((plistNode) ((int) pNode->ptrdiff ^ ( int)pPrevNode) );
}
//conventional
pdlistNode dNextNode ( pdlistNode pdNode)
{

	return (pdNode->next );
}

pdlistNode dPrevNode ( pdlistNode pdNode)
{

	return (pdNode->prev );
}
// ptr.dist list delete
void delList ()
{
	//
	plistNode pPrev, pCurrent;
	pPrev = NULL;
	pCurrent = pStart;
	
	while ( pCurrent ) {
		pCurrent->ptrdiff = NextNode( pCurrent, pPrev);
		if (pPrev)
			free(pPrev);
		if ( !pCurrent->ptrdiff ){
			printf(" Final node being deleted in prt.dist. =%d\n", pCurrent->elm);
			free(pCurrent);
			pCurrent = NULL;
			continue;
		}
		pPrev = pCurrent;
		pCurrent = pCurrent->ptrdiff;
	}
}
// conventional list delete
void ddelList()
{
	pdlistNode pdCurrent, pdNext;
	pdCurrent = pdHead;
	while (pdCurrent) {
		pdNext = dNextNode(pdCurrent);
		free(pdCurrent);
		pdCurrent = pdNext;
	}
}
	
// for dist. ptr.
void insertAfter ( plistNode pNew, T theElm )
{
	plistNode pPrev, pCurrent, pNext;
	pPrev = NULL;
	pCurrent = pStart;
	
	while (pCurrent) {
		pNext =  NextNode(pCurrent, pPrev);
		if (pCurrent->elm == theElm ) {
			/*fw traversal is done */
			//
			if (pNext ) { // fix the existing next node
				pNext->ptrdiff = (plistNode) ((int)pNext->ptrdiff ^ ( int) pCurrent ^ (int)pNew );
			}
			//fix the current node
			pCurrent->ptrdiff = (plistNode) ((int)pNew ^  (int)pNext ^ (int)pCurrent->ptrdiff);
			//fix the new node
			pNew->ptrdiff = (plistNode) ( (int)pCurrent ^ (int)pNext );
			break;
		}
		pPrev = pCurrent;
		pCurrent = pNext;
	}
}
// * for conventional insertAfter()
void dinsertAfter(pdlistNode pdNew, T theElm )
{
	pdlistNode pdPrev, pdCurrent, pdNext;
	pdCurrent= pdHead;
	
	while (pdCurrent) {
		pdNext = dNextNode(pdCurrent);
		if (pdCurrent->elm == theElm ) {
			if (pdNext ) {//fix the existing next node
				pdNext->prev = pdNew;
			}
			//fix the current node
			pdCurrent->next = pdNew;
			//fix the new node
			pdNew->next = pdNext;
			pdNew->prev = pdCurrent;
			break;
		}
		pdCurrent = pdNext;
	}
}

// ptr. dist. struct. traversal
void traverse( plistNode pRoot )
{
	//
	plistNode pCurrent, pPrev, pNext;

	pPrev = NULL;	
	pCurrent = pRoot; 

	while (pCurrent) 
	{
		//printf(" -> %d\n", pCurrent->elm) ;
		pNext = NextNode(pCurrent, pPrev );
		pPrev = pCurrent;
		pCurrent = pNext;
		
	}
}
// conventional forward traversal
void dtraversefw( pdlistNode pdHead )
{
	//
	pdlistNode pCurrent;
	pCurrent = pdHead; 
	while (pCurrent) 
	{
		
		//printf(" -> %d\n", pCurrent->elm) ;
		pCurrent = dNextNode(pCurrent);

		
	}
}
// conventional backward traversal
void dtraversebw( pdlistNode pdHead )
{
	//
	pdlistNode pCurrent;
	pCurrent = pdHead; 
	while (pCurrent) 
	{
		//printf(" -> %d\n", pCurrent->elm) ;
		pCurrent = dPrevNode(pCurrent);
	}
}
//
// dist. ptr.  insertion
void insert( T elm)
{
	//
	plistNode pnewNode = (plistNode)malloc(sizeof(struct listNode) );
	if (! pnewNode) {
		printf(" malloc failed in insert( T elm) \n");
		return;
	}
	pnewNode->elm = elm;
	pnewNode->ptrdiff = NULL;
	
	//brand new
	if ( !pStart ) {
		pStart = pEnd = pnewNode;
		
	}else {
		insertAfter( pnewNode, pEnd->elm);
		pEnd = pnewNode;
	}
	return ;
	
}
//conventional insert	
void dinsert ( T elm)
{
	pdlistNode pdnewNode = (pdlistNode)malloc(sizeof(struct dlistNode) );
	if (! pdnewNode) return;
	pdnewNode->elm = elm;
	pdnewNode->next = pdnewNode->prev = NULL;
	
	//brand new
	if ( !pdHead ) {
		pdHead = pdEnd = pdnewNode;
	}else {
		dinsertAfter(pdnewNode, pdEnd->elm );
		pdEnd = pdnewNode;
	}
	return ;	
}

#define NO_OF_ITEM_IN_LIST		30000
//#define EXERCISE_PTR_DIST		1


void doTimeStamp (char * strArg)
{
	char *pcharTime ;
	time_t c_time;
	
	time(&c_time);
	pcharTime = ctime(&c_time);
	printf("%s %s\n",strArg, pcharTime);
	
}
// exercise the conventional struct
void exerciseDlist()
{
	char *pcharTime ;
	time_t c_time;
	int  i;

	doTimeStamp("Before conventional insert() " );
	for (i = 0; i < NO_OF_ITEM_IN_LIST; i++)
		dinsert ( (T) i );
	doTimeStamp("After conventional insert() " );

	printf ("Total Memory taken by conventional structure = %d bytes.\n", NO_OF_ITEM_IN_LIST *sizeof(struct dlistNode) );
	
	//forward
	doTimeStamp("Before conventioal  dtraversefw(pdHead ) " );
	dtraversefw(pdHead );
	doTimeStamp("After conventioal  dtraversefw(pdHead ) " );
	
	//backward
	doTimeStamp("Before conventioal dtraversebw(pdEnd) " );
	dtraversebw(pdEnd);
	doTimeStamp("After conventioal dtraversebw(pdEnd) " );

	
	//delete
	doTimeStamp("Before conventioal ddelList () " );
	ddelList ();
	doTimeStamp("After conventioal ddelList () " );
}

void exerciseDistptrlist()
{
	int i;

	doTimeStamp("Before insert(prt.dist.)");
	// exercise the ptr distance structure
	for (i = 0; i < NO_OF_ITEM_IN_LIST ; i++)
		insert ( (T) i );
	doTimeStamp( "After insert(prt.dist.)" );
		
	printf ("Total Memory taken by ptr distance structure = %d bytes.\n", NO_OF_ITEM_IN_LIST *sizeof(struct listNode) );
	
	//forward traversal
	doTimeStamp ("Before traverse(pStart) of (prt.dist.) ");
	traverse(pStart);
	doTimeStamp( "After traverse(pStart) of(prt.dist.) ");
	//backward traversal
	doTimeStamp("Before traverse(pEnd) of (prt.dist.) ");
	traverse(pEnd);
	doTimeStamp( "After traverse(pEnd) of (prt.dist.) ");

	//delete the whole list
	doTimeStamp( "Before delList () of (prt.dist.) ");
	delList ();
	doTimeStamp("After delList () of (prt.dist.) ");

}

int main()

{
	//exerciseDlist();
#ifdef EXERCISE_PTR_DIST
	exerciseDistptrlist();
#else
	exerciseDlist();	
#endif	

	printf("Hello world\n");
	return (0);
}