/*	290803 for OSN & Graphics
//	METHOD DESIGN AND IMPLEMENTATION
//	1 functional versus procedural design
//	  functional: the function returns the new list as its returnvalue
//	  procedural: the function exports the new list by reference
//	2 recursive versus iterative approach
//	  recursive: the function is implemented by calling itself
//	  iterative: the function is implemented using a loop
//	As an example consider the insertion of new last node with element E
//	As a further exercise we construct lists that satisfy some properties
//		1 the list contains duplicates and is not sorted
//		2 the list contains no duplicates and is not sorted
//		3 the list contains duplicates and is sorted
//		4 the list contains no duplicates and is sorted
//
//	Remarks on iterative implementation
//	1	when you know pointer p to the last node in the list  
//		ie p->next == NULL then you can give p->next a new value
//		see insertFuncIter1 and insertProcIter1
//	2	when you know the address of the next field of the last node
//		then you can give this field its new value
//		see insertFuncIter2 and insertProcIter2
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE (12)                 // my testlists contain 12 elements 
#define MAX_RAND ( 9)                 // with random values from 0 .. 9
#define	randomInt(lbnd, ubnd)	((lbnd) + rand() % ((ubnd) - (lbnd) +1))
#define eltType int                   // elements as simple as possible

typedef struct listNode *listNodePtr;
typedef struct listNode {
	eltType		elt;
	listNodePtr	next;
} listNode;
typedef listNodePtr list;              // renaming listNodePtr to list

list createList(void);                 // L => []
list newList(eltType E, list L);       // L => [E:L]
// for all insert methods declared below  L => [L:E] ie E as new last elt of L

// methods that return the new list as value of the function
list insertFuncRec  (eltType E, list L);
list insertFuncIter1(eltType E, list L);
list insertFuncIter2(eltType E, list L);
list insertFuncIter4(eltType E, list L); // nodup
list insertFuncIter5(eltType E, list L); // sorted
list insertFuncIter6(eltType E, list L); // nodup and sorted

// methods that export the new list using a reference parameter
void insertProcRec  (eltType E, list *L);
void insertProcIter1(eltType E, list *L);
void insertProcIter2(eltType E, list *L);
void insertProcIter4(eltType E, list *L); // no dup
void insertProcIter5(eltType E, list *L); // sorted
void insertProcIter6(eltType E, list *L); // no dup and sorted 

void releaseList(list *L);                // release memory of all nodes
void printList(list L);                   // print elements if list is not empty

int main(void)
{
	list L = createList();
	int count;
		
	printf("Test insertFuncRec\n");
	for (count = 0; count < MAX_SIZE; count++)
		L = insertFuncRec(randomInt(0, MAX_RAND), L);
	printList(L);
	releaseList(&L); 

	printf("Test insertFuncIter1\n");
	for (count = 0; count < MAX_SIZE; count++)
		L = insertFuncIter1(randomInt(0, MAX_RAND), L);
	printList(L);
	releaseList(&L); 

	printf("Test insertFuncIter2\n");
	for (count = 0; count < MAX_SIZE; count++)
		L = insertFuncIter2(randomInt(0, MAX_RAND), L);
	printList(L);
	releaseList(&L); 

	printf("Test insertFuncIter nodup\n");
	for (count = 0; count < MAX_SIZE; count++)
		L = insertFuncIter4(randomInt(0, MAX_RAND), L);
	printList(L);
	releaseList(&L); 

	printf("Test insertFuncIter sorted\n");
	for (count = 0; count < MAX_SIZE; count++)
		L = insertFuncIter5(randomInt(0, MAX_RAND), L);
	printList(L);
	releaseList(&L); 

	printf("Test insertFuncIter sorted nodup\n");
	for (count = 0; count < MAX_SIZE; count++)
		L = insertFuncIter6(randomInt(0, MAX_RAND), L);
	printList(L);
	releaseList(&L); 

	printf("Test insertProcRec\n");
	for (count = 0; count < MAX_SIZE; count++)
		insertProcRec(randomInt(0, MAX_RAND), &L);
	printList(L);
	releaseList(&L); 
	
	printf("Test insertProcIter1\n");
	for (count = 0; count < MAX_SIZE; count++)
		insertProcIter1(randomInt(0, MAX_RAND), &L);
	printList(L);
	releaseList(&L); 
	
	printf("Test insertProcIter2\n");
	for (count = 0; count < MAX_SIZE; count++)
		insertProcIter2(randomInt(0, MAX_RAND), &L);
	printList(L);
	releaseList(&L); 
	
	printf("Test insertProcIter nodup\n");
	for (count = 0; count < MAX_SIZE; count++)
		insertProcIter4(randomInt(0, MAX_RAND), &L);
	printList(L);
	releaseList(&L); 
	
	printf("Test insertProcIter sorted\n");
	for (count = 0; count < MAX_SIZE; count++)
		insertProcIter5(randomInt(0, MAX_RAND), &L);
	printList(L);
	releaseList(&L); 
	
	printf("Test insertProcIter sorted nodup\n");
	for (count = 0; count < MAX_SIZE; count++)
		insertProcIter6(randomInt(0, MAX_RAND), &L);
	printList(L);
	releaseList(&L); 
	
	
	return(0);
}

list insertFuncRec(eltType E, list L) {
	if (!L)	
		L = newList(E, NULL);
	else
		L->next = insertFuncRec(E, L->next);
	return(L);
}

list insertFuncIter1(eltType E, list L) {
	if (!L)	
		L = newList(E, NULL);
	else {
		listNodePtr p = L;
		while (p->next) 
			p = p->next;             // loop exit: p->next == NULL
		p->next = newList(E, NULL);
	}
	return(L);	
}

list insertFuncIter2(eltType E, list L) {
	listNodePtr *p = &L;
	while (*p) 
		p = &(*p)->next;            // loop exit: p == NULL 
	*p = newList(E, NULL);
	return(L);	
}


list insertFuncIter4(eltType E, list L) { // nodup 
	listNodePtr *p = &L;
	while ((*p) && (E != (*p)->elt)) 
		p = &(*p)->next; 
	if (*p == NULL) 
		*p = newList(E, *p);
	return(L);	
}

list insertFuncIter5(eltType E, list L) { // sorted 
	listNodePtr *p = &L;
	while ((*p) && (E > (*p)->elt)) 
		p = &(*p)->next; 
	*p = newList(E, *p);
	return(L);	
}

list insertFuncIter6(eltType E, list L) { // sorted nodup 
	listNodePtr *p = &L;
	while ((*p) && (E > (*p)->elt)) 
		p = &(*p)->next; 
	if ((*p == NULL) || (E < (*p)->elt)) 
		*p = newList(E, *p);
	return(L);	
}

void insertProcRec(eltType E, list *L) {
	if (!*L)	
		*L = newList(E, NULL);
	else	
		insertProcRec(E, &(*L)->next);
}

void insertProcIter1(eltType E, list *L) {
	if (!*L)	
		*L = newList(E, NULL);
	else {
		listNodePtr cur = *L;
		while (cur->next)
			cur = cur->next;
		cur->next = newList(E, NULL);
	}
}

void insertProcIter2(eltType E, list *L) {
	listNodePtr *p = L;
	while (*p) 
		p = &(*p)->next; 
	*p = newList(E, NULL);
}
void insertProcIter4(eltType E, list *L) { // nodup 
	listNodePtr *p = L;
	while ((*p) && (E != (*p)->elt)) 
		p = &(*p)->next; 
	if (*p == NULL) 
		*p = newList(E, *p);
}
void insertProcIter5(eltType E, list *L) { // sorted 
	listNodePtr *p = L;
	while ((*p) && (E > (*p)->elt)) 
		p = &(*p)->next; 
	*p = newList(E, *p);
}
void insertProcIter6(eltType E, list *L) { // sorted nodup
	listNodePtr *p = L;
	while ((*p) && (E > (*p)->elt)) 
		p = &(*p)->next; 
	if ((*p == NULL) || (E < (*p)->elt)) 
		*p = newList(E, *p);
}

list createList(void) {
	return(NULL);
}

listNodePtr newList(eltType E, listNodePtr p) {
	listNodePtr q = (listNodePtr)malloc(sizeof(listNode));
	q->elt = E;
	q->next = p;
	return(q);
}
	
void printList(list L) {
	while (L) {
		printf("%4d", L->elt);
		L = L->next;
	}
	printf("\n");
}

void releaseList(list *L) {
	while (*L) {
		listNodePtr p = *L;
		*L = (*L)->next;
		free(p);
	}
}