/* 
* Code example for CP264 Data Structures II
* doubly linked list
* HBF 
*/

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

struct node {
  int data;
  struct node *next;
  struct node *prev;
};

typedef struct node node;  // define node as stuct node

typedef struct dllist {
  node *head; 
  node *tail;
} dllist; 

node *new_node(int);
node *search(dllist *, int);
void insert_beg(dllist *, node *);
void insert_end(dllist *, node *);
void delete_node(dllist *, int);
void display_forward(dllist);
void display_backward(dllist);
void clean(dllist*);

int main() {
  dllist dl = {0};
 
  int i;
  for(i = 1; i <= 4; i++) {
    insert_end(&dl, new_node(i));
  }

  /* print the dllist */
  printf("print doubly linked list forward\n");
  display_forward(dl);
  
  printf("print doubly linked list backward\n");
  display_backward(dl);
  
  insert_beg(&dl, new_node(10));
  printf("print forward after insert at beginning\n");
  display_forward(dl);
  
  node *np = new_node(20);
  insert_end(&dl, np);
  printf("print forward after insert at end\n");
  display_forward(dl);
  
  np = search(&dl, 20);
  if (np) printf("find %d\n", np->data);
  
  delete_node(&dl,20);
  printf("print forward after remove node\n");
  display_forward(dl);

  clean(&dl);
  printf("dl has been deleted\n");
  display_forward(dl);
  return 0;
}

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

node *search(dllist *dlp, int value) {
  if (dlp == NULL) return NULL;	
  node *np = dlp->head;
  while (np != NULL && np->data != value) {
    np = np->next;	
  }
  return np;
}

void insert_beg(dllist *dlp, node *np) {
  if (dlp == NULL) return;	
  if(dlp->head == NULL) {
    dlp->head = np;
    dlp->tail = np;
  }  
  else {
    dlp->head->prev = np; 
    np->next = dlp->head;  
  }
  dlp->head= np; 
  np->prev = NULL;
}

void insert_end(dllist *dlp, node *np) {
  if (dlp == NULL) return;	
  if(dlp->head == NULL) {
    dlp->head = np;
    np->prev = NULL;
  } else {
    dlp->tail->next = np;
    np->prev = dlp->tail;
  }
  dlp->tail = np;
  np->next = NULL;
}

void delete_node(dllist *dlp, int value) { 
  if (dlp == NULL) return;
  node *np = dlp->head;
  
  while (np != NULL && np->data != value) {
    np = np->next;	
  }
  
  if (np == NULL) return;
  else if(np->prev == NULL) { 
    dlp->head = np->next;
	dlp->head->prev = NULL;
  }	
  else {
    np->prev->next = np->next;
  }
  
  if(np->next == NULL) 
    dlp->tail = np->prev;
  else
    np->next->prev = np->prev;

  free(np);
}

void display_forward(dllist dl) {
   if (dl.head == NULL) printf("empty\n");
   node *np;
   for(np = dl.head; np != NULL; np = np->next) {
    printf("%d\n", np->data);
  }
}

void display_backward(dllist dl) {
  if (dl.head == NULL) printf("empty\n");
  node *np;
  for(np = dl.tail; np != NULL; np = np->prev) {
    printf("%d\n", np->data);
  }
}

void clean(dllist *dlp) {
  if (dlp == NULL) return;
  node *temp, *np = dlp->head;
  
  while (np != NULL)
  { 
    temp = np; 
    np = np -> next;
    free(temp);
  }
  dlp->head = NULL;
  dlp->tail = NULL;
}

/*
print doubly linked list forward
1
2
3
4
print doubly linked list backward
4
3
2
1
print forward after insert at beginning
10
1
2
3
4
print forward after insert at end
10
1
2
3
4
20
find 20
print forward after remove node
10
1
2
3
4
dl has been deleted
empty
*/