/* 
* Code example for CP264 Data Structures II
* circular linked list (cllist)
* HBF 
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *next;
} node;
void display(node *);
node *search(node *, int);
void insert(node **, int);
void delete(node **);
void clean(node **);

int main() {
  node *start = NULL;
  printf("\ninsert:\n");
  insert(&start, 1);
  insert(&start, 2);
  insert(&start, 3);
  insert(&start, 4); 
  display(start); 
  
  int key = 2;
  printf("\nsearch: %d\n", key);
  node *ptr = search(start, key);
  if (ptr) printf("found: %d\n", ptr->data);
  else  printf("not found: %d\n", key);
  
  printf("\ndelete:\n");
  delete(&start);
  display(start);
  
  printf("\nclean:\n");
  clean(&start);
  display(start);
  return 0;
}

void display(node *start) {
  if (start == NULL) {
    printf("empty list\n");
  } 
  else {
    node *ptr = start;
    while (ptr->next != start) {
      printf("%d ", ptr->data);
      ptr = ptr->next;
    }
    printf("%d ", ptr->data);
  }
}

node *search(node *start, int key) {
  node *ptr = start;
  while (ptr->next != start && ptr->data != key ) {
    ptr = ptr->next;
  }
  
  if (ptr->data == key) 
    return ptr;
  else
    return NULL; 
}

void insert(node **startp, int val) {
  node *new_np = (node *) malloc(sizeof(node));
  new_np->data = val;
  if (*startp == NULL) {
    *startp = new_np;
    new_np->next = new_np;
  } 
  else {
    node *ptr = *startp;
    while (ptr->next != *startp) //traversal to the end of the cllist
	  ptr = ptr->next;
    ptr->next = new_np;
    new_np->next = *startp;
    *startp = new_np;
  }
}

void delete(node **startp) {
  if (*startp == NULL) return;
  
  node *ptr = *startp;
  node *start = ptr;
  
  if ( ptr->next == start) {
    free(ptr);
    *startp = NULL;
  } 
  else {
    node *ptr = *startp;
	node *start = ptr;
    while (ptr->next != start) 
	  ptr = ptr->next;
  
    ptr->next = start->next;
    free(start);
    *startp = ptr->next;
  }
}

void clean(node **startp) {
  if (*startp == NULL) return;

  node *ptr = *startp;
  node *start = ptr;
  node *temp;
  
  while (ptr->next != start) {
	temp = ptr;  
	ptr = ptr->next;
    free(temp);
  }
  *startp = NULL;
}

/*
insert:
4 3 2 1
search: 2
found: 2

delete:
3 2 1
clean:
empty list
*/