/* 
* Code example for CP264 Data Structures II
* Simple/singly linked list class test example 
* HBF 
*/

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

//#define usefree    // uncomment this line to test memory leaking
//#define test       // uncomment this line to test memory leaking
#ifdef test
#include <Windows.h> // for using Sleep(ms) in memory leaking testing
#endif

struct node {
  int data;
#ifdef test
  double ddata[1000]; // scale up for memory leaking test
#endif
  struct node *next;
};

struct node* new_node(int);
int get_data(struct node *);
void set_data(struct node *, int);
int length(struct node *);
void display_forward_iterative(struct node *);
void display_forward_recursive(struct node *);
void display_backward_recursive(struct node *);
void display_backward_iterative(struct node *); //using additional linked list as stack
struct node *search(struct node *, int);
void insert_node_beg(struct node **, struct node*);
void insert_beg(struct node **, int);
void insert_end(struct node **, int);
void insert_after(struct node **, struct node *, int);
int delete_beg(struct node **);
int delete_end(struct node **);
int delete(struct node **, int);
void clean(struct node **); 

int main() {
  struct node *start = NULL;
  struct node *np; 
   
  np = new_node(2);
  insert_node_beg(&start, np);
  insert_beg(&start, 1);
  insert_end(&start, 3);
  insert_end(&start, 4);
  insert_end(&start, 5);
  
  np = new_node(6);
  insert_after(&start, np, 4);
  display_forward_iterative(start);
  
  np = search(start, 4);
  printf("Value found %d\n", get_data(np));
  
  printf("Delete beginning\n");
  delete_beg(&start);
  display_forward_iterative(start);
  
  printf("Delete end\n");
  delete_end(&start);
  display_forward_iterative(start);
  
  printf("Delete node of value %d\n", 4);
  delete(&start, 4);
  display_forward_iterative(start);
 
  printf("display_forward_recursive\n");
  display_forward_recursive(start);
  
  printf("display_backward_recursive\n");
  display_backward_recursive(start);
 
  printf("display_backward_iterative, using additional linked list\n");
  display_backward_iterative(start);  
  clean(&start);
    
#ifdef test
  int i ;
  for (i = 0; i< 100000; i++){
    insert_beg(&start, 1);
    delete(&start, 1);
	Sleep(5);
  }
#endif  
  
  return 0;
}

struct node* new_node(int num) {
  struct node *np = (struct node *) malloc(sizeof(struct node));
  if (np == NULL) return NULL;
  np->data = num;
  np->next = NULL;  
  return np;
}

int get_data(struct node *np) {
	return np->data;
}

void set_data(struct node *np, int num) {
	np->data = num;
}

/*
* time: O(1), space: O(1)
*/
void insert_node_beg(struct node **startp, struct node* new_np) {
  new_np->next = *startp;
  *startp = new_np;
}

/*
* time: O(1), space: O(1)
*/
void insert_beg(struct node **startp, int num) {
  struct node* np = (struct node *)malloc(sizeof(struct node));
  if (np == NULL) {printf("malloc fails"); return;}
  np->data = num;
  np->next = NULL; 
  
  np->next = *startp;
  *startp = np;
}

/*
* time: O(n), space: O(1)
*/
void insert_end(struct node **startp, int num) {
  struct node *np = (struct node *) malloc(sizeof(struct node));
  if (np == NULL) {printf("malloc fails"); return;} //malloc failed 
  np->data = num;
  np->next = NULL;  
  
  if (*startp == NULL) {
	*startp = np;
  } else {
	 struct node *p = *startp;
	 while ( p->next != NULL) {
		p = p->next;
	 }
	 p->next  = np;
  }	
}

/*
* insert after a node given value if found, otherwise insert at end
* time: O(n), space: O(1)
*/
void insert_after(struct node **startp, struct node* new_np, int num) {
  if (*startp == NULL) {
	*startp = new_np;
  }
  
  struct node *np = *startp, *prev = NULL;
  while ( (np != NULL) && (np->data != num )) {
    prev = np;
    np = np->next;
  } 
  
  if (np == NULL) {  // not found 
	 prev->next = new_np;
     new_np->next = NULL;	 
  }
  else { // found at np
     new_np->next = np->next;
	 np->next = new_np; 
  }
}

/*
* time: O(1), space: O(1)
*/
int delete_beg(struct node **startp) {
  struct node *np = *startp;
  if (np == NULL) 
    return 0; 
  else {
    *startp = np->next;	  
    free(np); 
    return 1;
  } 
}

/*
* iterative alg, time: O(n), space: O(1)
*/
int delete_end(struct node **startp) {
  if (startp == NULL || *startp == NULL) return 0; 
  struct node *np = *startp;
  struct node *prev = NULL;
 
  while (np->next != NULL) {
    prev = np;
    np = np->next;
  } 
   
  if (prev == NULL)
    *startp = NULL;
  else
    prev->next = np->next;
  
   free(np); 
   return 1;

}

/*
* iterative alg, time: O(n), space: O(1)
*/
int delete(struct node **startp, int num) {
  struct node *np = *startp;
  struct node *prev = NULL;

  while ( (np != NULL) && (np->data != num )) {
    prev = np;
    np = np->next;
  } 
   
  if (np == NULL) 
    return 0; 
  else {
    if (prev == NULL)
      *startp = np->next;
    else
      prev->next = np->next;
	
#ifdef usefree	
    free(np);
#endif

    return 1;
  } 
}

/*
* iterative alg, time: O(n), space: O(1)
*/     
struct node* search(struct node *start, int num) {
  while((start != NULL) && (start->data != num)) {
    start = start->next;
  }
  return start;
}

/*
* iterative alg, time: O(n), space: O(1)
*/
void display_forward_iterative(struct node *start) {
  printf("Value Address\n");
  while(start != NULL) {
    printf("%5d %d\n", start->data, start);
    start = start->next;
  }
}

/*
* recursive alg by recursive function call, time: O(n), space: O(n)
*/
void display_forward_recursive(struct node *start) {
  if (start == NULL) return;
  printf("%5d %d\n", start->data, start);
  display_forward_recursive(start->next);
}

/*
* recursive function, time: O(n), space: O(n)
*/
void display_backward_recursive(struct node *start) {
  if (start == NULL) return;
  if (start->next == NULL) {
     printf("%5d %d\n", start->data, start);
  } else {
    display_backward_recursive(start->next);
    printf("%5d %d\n", start->data, start);
  }
}

/*
* iterative algorithm, time: O(n), SPACE: O(n), USING ADDITIONAL LINKED LIST AS STACK
*/
void display_backward_iterative(struct node *start) {
  if (start == NULL) return;
  struct node * stk = NULL, *ptr;
  while(start != NULL) {
    insert_beg(&stk, start->data);
    start = start->next;
  }
  
  while(stk != NULL) {
    printf("%5d %d\n", stk->data, stk);
    ptr = stk;
    stk = stk->next;
    free(ptr);
  }
}

/*
* iterative algorithm, time: O(n), space: O(1)
*/
int length(struct node *start) {
  int len = 0;
  while(start != NULL) {
    len++;
    start = start->next;
  }
  return len;
}

/*
* iterative algorithm, time: O(n), space: O(1)
*/
void clean(struct node **startp) {
  struct node *temp, *np = *startp;
  while (np != NULL) { 
    temp = np; 
    np = np -> next;
    free(temp);
  }
  *startp = NULL;
}

/*
Value Address
    1 6834880
    2 6834848
    3 6834896
    4 6834912
    6 6834944
    5 6834928
Value found 4
Delete beginning
Value Address
    2 6834848
    3 6834896
    4 6834912
    6 6834944
    5 6834928
Delete end
Value Address
    2 6834848
    3 6834896
    4 6834912
    6 6834944
Delete node of value 4
Value Address
    2 6834848
    3 6834896
    6 6834944
display_forward_recursive
    2 6834848
    3 6834896
    6 6834944
display_backward_recursive
    6 6834944
    3 6834896
    2 6834848
display_backward_iterative, using additional linked list
    6 6834960
    3 6834880
    2 6834928
*/