/*
Author:		Martin RobinSon
Email:		saloparenator@gmail.com
Project:	No Idea ???
*/

/*
Title: 		single linked list
Detail:		using a dummy node
*/

typedef struct NOIDEA_linkedlist
{
	void * data;				//void* ptr is the most versatile type in C , but its best for a ptr to a given data
	struct NOIDEA_linkedlist * next;	//following node in the linked list array
}NOIDEA_linkedlist;


//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
//stack basic function 
//mean lifo is the fastest way for such list
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-

/* simple function a the begining of the list */

NOIDEA_linkedlist * NOIDEA_linkedlist_push(NOIDEA_linkedlist * noidea_head, void * noidea_data, void * noidea_ptr)
/* put the given item at first place on the list (first IN) */
{
	if (noidea_ptr == 0)	//case that there no ptr for data allocation
	{
		return 0;	//without ptr for data allocation , there no hope
	}

	if (noidea_head == 0)	//case that there no head , then the node become lonely
	{
		NOIDEA_linkedlist * noidea_head = (NOIDEA_linkedlist*) noidea_ptr;
		noidea_head->data = noidea_data;
		noidea_head->next = 0;
		return noidea_head;
	}
	else			//but if there is a head node !!!
	{
		NOIDEA_linkedlist * noidea_item = (NOIDEA_linkedlist*) noidea_ptr;
		noidea_item->data = noidea_data;
		noidea_item->next = noidea_head->next;
		noidea_head->next = noidea_item;	
		return noidea_item;
	}
}

void * NOIDEA_linkedlist_pop(NOIDEA_linkedlist * noidea_head, void (*noidea_free)(void*))
/* eleminate first item in the list then return data ptr (last IN first OUT) */
/* noidea_free() function assume that the function dont need to know the size of the data to free at given ptr */
{
	if ((noidea_head == 0)||(noidea_head->next == 0)||(noidea_free == 0))
	/*case there no free() function or no head specified or a list containing only dummy node (empty)*/
	{
		return 0;	//then there nothing to do here
	}
	NOIDEA_linkedlist * noidea_toremove = noidea_head->next;
	void * noidea_data = noidea_toremove->data;
	noidea_head->next = noidea_toremove->next;	//the head->next will be linked to the 2nd->next 
	noidea_free((void*)noidea_toremove);		//then removing the node with specified function
	return noidea_data;				//return the data ptr
}
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
//tail operation
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-

/* simple function at the end of the list */

NOIDEA_linkedlist * NOIDEA_linkedlist_gotoTail(NOIDEA_linkedlist * noidea_head)
/* loop entire list then return the last node */
{
	NOIDEA_linkedlist * noidea_tail = noidea_head;
	if(noidea_tail != 0)
	{
		while (noidea_tail->next != 0)			//loop entire list
		{						//while node->next 
			noidea_tail = noidea_tail->next;	//is equal to zero
		}
	}
	return noidea_tail;
}

void * NOIDEA_linkedlist_getTail(NOIDEA_linkedlist * noidea_head)
/*loop entire list then return data ptr of the last node*/
{
	return NOIDEA_linkedlist_gotoTail(noidea_head)->data;	//using above function , return ->data ptr
}

NOIDEA_linkedlist * NOIDEA_linkedlist_append(NOIDEA_linkedlist * noidea_head, void * noidea_data, void * noidea_ptr)
/* APPEND() function is the same as PUSH() but its done a the end of the list */
/* the gototail() function is useful for that purpose , because we can simply pass
   that funct as argument to the PUSH() function */
{
	return NOIDEA_linkedlist_push(NOIDEA_linkedlist_gotoTail(noidea_head),noidea_data,noidea_ptr);
}

//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
//Nth operation
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-

/* basic function , moving through the list */

NOIDEA_linkedlist * NOIDEA_linkedlist_gotoNth(NOIDEA_linkedlist * noidea_head, int Nth)
/* return Nth node of the list or the last if bigger */
{
	if (noidea_head == 0)
	{
		return 0;	//if there no list there no point here
	}
	NOIDEA_linkedlist * noidea_Nth = noidea_head;
	while(Nth > 0)		//count dowm Nth to zero will limit the loop
	{
		if(noidea_Nth->next == 0)
		{
			Nth = 0;	//but if the list is shorter than Nth , simply return the last node
		}
		else
		{
			Nth -= 1;			//decrease Nth
			noidea_Nth = noidea_Nth->next;	//advance one node
		}
	}
	return noidea_Nth;	//return it
}

void * NOIDEA_linkedlist_getNth(NOIDEA_linkedlist * noidea_head, int Nth)
/* i see that like a list[Nth] in python */
/* return data of the Nth node of the list */
/* using above function will return the needed node , so we can easily return its data */
{
	return NOIDEA_linkedlist_gotoNth(noidea_head,Nth)->data;
}

NOIDEA_linkedlist * NOIDEA_linkedlist_insert(NOIDEA_linkedlist * noidea_head, int Nth, void * noidea_data, void * noidea_ptr)
/* insert data after the Nth node */
/* like push() , it add a node in the list , but after Nth node instead of the dummy
   using gotoNth() function as argument of the push() funct , it take one line */
{
	return NOIDEA_linkedlist_push(NOIDEA_linkedlist_gotoNth(noidea_head,Nth),noidea_data,noidea_ptr);
}

void * NOIDEA_linkedlist_remove(NOIDEA_linkedlist * noidea_head, int Nth, void (*noidea_free)(void*))
/*remove Nth node*/
{
	if (noidea_head == 0)
	{
		return 0;	//no list enh ???
	}
	int NthMinusOne = Nth-1;	//if we use POP() then we need to step back one node
	if (NthMinusOne < 0)
	{
		return 0;		//there is no negative node and its no a good idea to remove dummy node
	}
	NOIDEA_linkedlist * noidea_NthMinusOne = NOIDEA_linkedlist_gotoNth(noidea_head,(NthMinusOne));
	if ((noidea_NthMinusOne == 0)||(noidea_NthMinusOne->next == 0))
	{
		return 0;		//if there no such node to remove , there no point fooling around anymore
	}
	return NOIDEA_linkedlist_pop(noidea_NthMinusOne,noidea_free);	//finale pop the node
}
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
//recursive function
//those function use those higher
//they have performance penalty
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-

int NOIDEA_linkedlist_lenght(NOIDEA_linkedlist * noidea_head)
/*loop the entire list and count every unit*/
{
	int cnt = 0;
	NOIDEA_linkedlist * noidea_tail = noidea_head;
	while (noidea_tail->next != 0)
	{
		cnt +=1;
		noidea_tail = noidea_tail->next;
	}
	return cnt;
}

int NOIDEA_linkedlist_count(NOIDEA_linkedlist * noidea_head,void * noidea_data)
/*loop entire list and count all matching ptr to the given param*/
{
	int count= 0;
	NOIDEA_linkedlist * noidea_pivot = noidea_head;
	while(noidea_pivot->next != 0)
	{
		noidea_pivot = noidea_pivot->next;
		if (noidea_pivot->data == noidea_data)
		{
			count += 1;
		}
	}
	return count;
}

//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
//full list function
//they have performance penalty
//-==-==-==-==-==-==-==-==-==-==-==-==-==-==-

NOIDEA_linkedlist * NOIDEA_linkedlist_copylist(NOIDEA_linkedlist * noidea_head,void * noidea_ptr)
/*assum that the given ptr is the same size as the source list
it will duplicate the entire list*/
{
	int leap = sizeof(NOIDEA_linkedlist);
	NOIDEA_linkedlist * noidea_newhead = NOIDEA_linkedlist_push(0,noidea_head->data,noidea_ptr);
	void * noidea_newptr = noidea_ptr + leap;

	NOIDEA_linkedlist * noidea_tail = noidea_head;
	while (noidea_tail->next != 0)
	{
		noidea_tail = noidea_tail->next;
		NOIDEA_linkedlist_append(noidea_newhead,noidea_tail->data,noidea_newptr);
		noidea_newptr += leap;
	}
	return noidea_newhead;
}

NOIDEA_linkedlist * NOIDEA_linkedlist_emptylist(NOIDEA_linkedlist * noidea_head, void noidea_free(void*))
/*will loop entire list then free memory with given function , return head node*/
{
	if (noidea_head==0)
	{
		return 0;
	}
	while (NOIDEA_linkedlist_lenght(noidea_head) != 0)
	{
		NOIDEA_linkedlist_pop(noidea_head,noidea_free);
	}
	return noidea_head;
}



//=================================================


NOIDEA_linkedlist * NOIDEA_linkedlist_join(NOIDEA_linkedlist * noidea_first, NOIDEA_linkedlist * noidea_second)
/* will plug second list at the end of the first list */
{
	if ((noidea_first == 0)||(noidea_second == 0))
	{
		return 0;
	}
	NOIDEA_linkedlist * noidea_join = NOIDEA_linkedlist_gotoTail(noidea_first);	//get the last node
	noidea_join->next = noidea_second->next;	//append the 2ndlist to the last node of the 1stlist
	return noidea_first;		//return first list , 2nd still point the its list
}

NOIDEA_linkedlist * NOIDEA_linkedlist_split(NOIDEA_linkedlist * noidea_src, int Nth, void * ptr)
/* will create a new list with data that follow Nth in list
   those node will be remove from the first list , 
   a free memory space is needed for allocating a new dummy node */
{
	if ((noidea_src == 0)||(ptr == 0))
	{
		return 0;
	}
	NOIDEA_linkedlist * noidea_newlast = NOIDEA_linkedlist_gotoNth(noidea_src,Nth);
	NOIDEA_linkedlist * noidea_newlist = NOIDEA_linkedlist_push(noidea_newlast,0,ptr);
	noidea_newlast->next = 0;
	return noidea_newlist;
}

NOIDEA_linkedlist * NOIDEA_linkedlist_movenode(NOIDEA_linkedlist * noidea_head, int noidea_srcNth, int noidea_desNth)
//untested
{
	if ((noidea_head == 0)||(noidea_srcNth - 1 < 0)||(noidea_desNth - 1 < 0))
	{
		return 0;
	}
	NOIDEA_linkedlist * noidea_srcMinus = NOIDEA_linkedlist_gotoNth(noidea_head,noidea_srcNth - 1);
	NOIDEA_linkedlist * noidea_desMinus = NOIDEA_linkedlist_gotoNth(noidea_head,noidea_desNth - 1);
	NOIDEA_linkedlist * noidea_pivot = noidea_srcMinus->next;
	if ((noidea_pivot == 0)||(noidea_pivot == noidea_desMinus)||(noidea_srcMinus == 0)||(noidea_desMinus == 0))
	{
		return 0;
	}
	//noidea_srcMinus->next = noidea_pivot->next;
	//noidea_pivot->next = noidea_desMinus->next;
	//noidea_desMinus->next = noidea_pivot; 
	return noidea_pivot;	
}

NOIDEA_linkedlist * NOIDEA_linkedlist_swapnode(NOIDEA_linkedlist * noidea_head, int noidea_Nth)
{

}

NOIDEA_linkedlist * NOIDEA_linkedlist_removeduplicate(NOIDEA_linkedlist * noidea_head,void(*noidea_free)(void*))
{

}





NOIDEA_linkedlist * NOIDEA_linkedlist_sort(NOIDEA_linkedlist * noidea_head)
/* sort the list using first INTEGER contained a data ptr of the node */
{
	
}