//==============================================================================
//
//  llist.c
//  linked list implementation
//  
//==============================================================================
#include  <stdio.h>
#include  <stdlib.h>

//------------------------------------------------------------------------------
typedef struct  _SNode
{
	int element;
	struct _SNode* pNext;
} SNode;

//------------------------------------------------------------------------------
int LListNodeCreate(SNode** ppN, int n)
{
	*ppN = (SNode*) malloc(sizeof(SNode));
	(*ppN)->element = n;
	(*ppN)->pNext = NULL;
	return 0;
}

//------------------------------------------------------------------------------
int LListNodeFree(SNode* pNode)
{
	if(pNode->pNext == NULL)
	{
		free(pNode);
	}
	else return 1;
}

//------------------------------------------------------------------------------
int LListNodeDump(SNode* pNode)
{
	if(pNode)
	{
		printf("SNode: pointer= %x   data= %d\n", pNode, pNode->element);
		return 0;
	}
	else
	{
		printf("SNode:  NULL\n");
		return 1;
	}
}

//------------------------------------------------------------------------------
int LListLength(SNode* pHead)
{
	int count=0;
	SNode* pH = pHead;
	
	while(pH) 
	{
		count++;
		pH = pH->pNext;
	}
	return count;
}

//------------------------------------------------------------------------------
void LListDisplayAll(SNode* pHead)
{
	int n=0;
	SNode* pH = pHead;
	do
	{
		printf("#= %d    ", n);
		LListNodeDump(pH);
		n++;
		if(pH) pH = pH->pNext;
	}
	while(pH);
}

//------------------------------------------------------------------------------
// Add to the head
int LListAddToHead(SNode** ppHead, int element )
{
	SNode* pNode;
	LListNodeCreate(&pNode, element);
	
	pNode->pNext = *ppHead;
	*ppHead =  pNode;
	
	return 0;
}

//------------------------------------------------------------------------------
// Add to the head
int LListPush(SNode** ppHead, int element)
{
	LListAddToHead(ppHead, element);
	return 0;
}

//------------------------------------------------------------------------------
// Get from the Begin (remove from the begin)
int LListGetFromHead(SNode** ppHead, SNode** ppNode  )
{
	if(*ppHead)
	{
	}
	else
	{
		*ppNode = NULL;
	}
	return 0;
}

//------------------------------------------------------------------------------
// Get from the Begin
int LListPop(SNode** ppHead, SNode** ppNode  )
{
	LListGetFromHead(ppHead, ppNode);
	return 0;
}

//------------------------------------------------------------------------------
// Read the Begin Node
int LListReadHead(SNode* pHead, SNode** ppNode)
{
	*ppNode = pHead;
	return 0;
}

//------------------------------------------------------------------------------
int LListReadEnd(SNode* pHead, SNode** ppEnd)
{
	SNode* pN = pHead;
	
	if(pN==NULL)
	{
		*ppEnd = NULL;
		return 1;
	}
	while(pN->pNext)
	{
		pN = pN->pNext;
	}
	*ppEnd = pN;
	return 0;
}

//------------------------------------------------------------------------------
int LListAddAfter(SNode** ppHead, int position,  int element)
{
	int n=0;
	SNode* pN = *ppHead;
	while(1)
	{
		if(pN==NULL) break;
		if(n == position)
		{
			SNode* pM;
			LListNodeCreate(&pM, element);
			pM->pNext = pN->pNext;
			pN->pNext = pM;
			return 0;
		}
		pN = pN->pNext;
		n++;
	}
	return 1;
}

//------------------------------------------------------------------------------
int LListAddBefore(SNode** ppHead, int position,  int element)
{
	int n=0;
	SNode* pN  = *ppHead;
	SNode* pN0 = *ppHead;
	
	while(1)
	{
		if(pN==NULL  ||  n==0) 
		{
			LListAddToHead(ppHead, element);
			return 0;;
		}
		if(n == position)
		{
			SNode* pM;
			LListNodeCreate(&pM, element);
			pM->pNext = pN->pNext;
			pN0->pNext = pM;
			return 0;
		}
		pN0 = pN;
		pN = pN->pNext;
		n++;
	}
	return 1;
}

//------------------------------------------------------------------------------
int LListInsertByOrder(SNode** ppHead,  int element)
{
	SNode* pN;
	SNode* pC;
	SNode* pA;
	
	pC = *ppHead;
	if(pC==NULL)
	{
		LListNodeCreate(&pN, element);
		*ppHead = pN;
		return 0;
	}

	if(element < (pC->element) ) // insert in head
	{
		LListAddToHead(ppHead, element );
		return 0;
	}

	LListNodeCreate(&pN, element);
	while(1) // (pC->pNext!=NULL))
	{
		pA = pC;
		pC = pC->pNext;
		
		// achive end of the list:  add to the end
		if(pC==NULL) 
		{
			pA->pNext = pN;
			break;
		}
		
		// go to the next node
		if(element > pC->element) continue;
		
		// insert between nodes
		pN->pNext= pC;
		pA->pNext = pN;
		break;
	}
	
	return 0;
}

//------------------------------------------------------------------------------
int LListSearch(SNode* pHead, int element, SNode** ppResult)
{
	SNode* pN=pHead;
	
	if(pN==NULL) 
	{
		*ppResult = NULL;
		return 1;
	}
	while(1)
	{
		if(pN==NULL) 
		{
			*ppResult = NULL;
			break;
		}
		if(pN->element == element)
		{
			*ppResult = pN;
			return 0;
		}
		pN = pN->pNext;
	}
	return 1;
}

//------------------------------------------------------------------------------
int LListNext(SNode** ppNode)
{
	if(*ppNode == NULL) return 1;
	*ppNode = (*ppNode)->pNext;
	return 0;
}

//------------------------------------------------------------------------------
int LListRemoveHead(SNode** ppHead)
{
	SNode* pNode;
	if(*ppHead == NULL) return 1;
	pNode = *ppHead;
	*ppHead = pNode->pNext;
	pNode->pNext = NULL;
	LListNodeFree(pNode);
	return 0;
}

//------------------------------------------------------------------------------
int LListRemoveEnd(SNode** ppHead)
{
	SNode* pN = *ppHead;
	SNode* pM = *ppHead;
	
	if(*ppHead==NULL) return 1;
	
	while(pN->pNext!=NULL)
	{
		pM = pN; // previous node
		pN = pN->pNext;
	}
	pM->pNext = NULL;
	pN->pNext = NULL;	
	LListNodeFree(pN);

	return 0;
}

//------------------------------------------------------------------------------
int LListRemove(SNode** ppHead, int element)
{
	SNode* pN = *ppHead;
	SNode* pM = *ppHead;
	
	if(*ppHead==NULL) return 1;

	while(1)
	{
		if( pN->element == element)
		{
			if(pN == *ppHead)
			{
				*ppHead = pN->pNext;
			}
			else
			{
				pM->pNext = pN->pNext;
			}
			LListNodeFree(pN);
			return 0;
		}
		if(pN == NULL) break;
		pM = pN;
		pN = pN->pNext;
	}		
	return 1;
}

//------------------------------------------------------------------------------
int LListRemovePosition(SNode** ppHead, int position)
{
	int nCurrent = 0;
	SNode* pN = *ppHead;
	SNode* pM = *ppHead;
	
	if(*ppHead==NULL) return 1;

	while(1)
	{
		if( nCurrent == position)
		{
			if(nCurrent == 0)
			{
				*ppHead = pN->pNext;
			}
			else
			{
				pM->pNext = pN->pNext;
			}
			LListNodeFree(pN);
			return 0;
		}
		if(pN == NULL) break;
		pM = pN;
		pN = pN->pNext;
		nCurrent++;
	}
	 
	return 0;
}

//------------------------------------------------------------------------------
int LListFree(SNode** ppHead)
{
	SNode* pN;
	
	if(*ppHead == NULL) return 1;
	
	while(1)
	{
		pN = *ppHead;
		if(pN==NULL) break;
		(*ppHead) = pN->pNext;
		pN->pNext = NULL;
		LListNodeFree(pN);
	}
	return 0;
}

//==============================================================================
int main(int nArg, char** ppArg)
{
	SNode* pHead = NULL;
	SNode* pN;
	int nSelect;
	int k;
	int position;

	while(1)
    {
		printf("=========================================\n");
		printf("Menu:\n");
		printf("0  Display LList\n");
		printf("1  Display Node at the head\n");
		printf("2  Display Node at the end \n");
		printf("3  LList Size (number of nodes)\n");
		printf("4  Add Node to the LList Head (Insert)\n");
		printf("5  Insert new Node by position before\n");
		printf("6  Insert new Node by position after\n");
		printf("7  Insert new Node by order\n");
		printf("8  Search the Node with defined element\n");
		printf("9  Delete Node with defined element ... \n");
		printf("10 Delete Node at the LList Head\n");
		printf("11 Delete Node at the LList End ...\n");
		printf("12 Delete Node with defined position ...\n");
		printf("90 Delete all Linked List\n");
		printf("99 Exit\n");
		
		printf("=========================================\n");
		printf("Select: "); scanf("%d",&nSelect); 
		
        switch(nSelect)
        {
        case 0:
			LListDisplayAll(pHead);
            break;
        case 1:
			LListNodeDump(pHead);
            break;
        case 2:
			LListReadEnd(pHead, &pN);
			LListNodeDump(pN);
            break;
        case 3:
			k = LListLength(pHead);
			printf("Number of nodes= %d\n", k); 
            break;
        case 4:      
			printf("Enter the number to insert: "); scanf("%d", &k);
			LListAddToHead(&pHead, k);
            break;
        case 5:
			printf("Enter the number to insert: "); scanf("%d", &k);
			printf("Enter the position where to insert: "); scanf("%d", &position);
			LListAddBefore(&pHead, position, k);		
            break;
        case 6:      
			printf("Enter the number to insert: "); scanf("%d", &k);
			printf("Enter the position where to insert: "); scanf("%d", &position);
			LListAddAfter(&pHead, position, k);		
            break;
        case 7:      
			printf("Enter the number to insert: "); scanf("%d", &k);
			LListInsertByOrder(&pHead, k);
            break;
        case 8:
			printf("Enter the number to search: "); scanf("%d", &k);
			LListSearch(pHead, k, &pN);	
			LListNodeDump(pN);	
            break;
        case 9:
			printf("Enter the number to delete: "); scanf("%d", &k);
			LListRemove(&pHead, k);
            break;
        case 10:
			LListRemoveHead(&pHead);		
            break;
		case 11: 
			LListRemoveEnd(&pHead);
            break;
		case 12: 
			printf("Enter the position where to delete: "); scanf("%d", &position);
			LListRemovePosition(&pHead, position);
            break;	
		case 90:
			LListFree(&pHead);
            break;        
		case 99:
			// delete list
			LListFree(&pHead);
			exit(0);
            break;
		default:
            break;
		}
	}
			
	return 0;
}