// Continuing from the same code from week 7 and 8
// To address a bug in insert_at_position

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

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

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
struct node *insert_at_tail(int data, struct node *head);
struct node *insert_at_position(int data, int position, struct node *head);
struct node *delete_node(struct node *head, int value_to_be_deleted);

int main(void) {
	// struct node *head = malloc(sizeof(struct node));
	// head->data = 7; // (*head).data = 7
	// head->next = NULL;

	// struct node *head2 = malloc(sizeof(struct node));
	// head2->data = 8;
	// head2->next = head;

	// // TODO: put it in function!
	// struct node *head3 = malloc (sizeof(struct node));
	// head3->data = 11;
	// head3->next = head2; // link node with 11 to node with 8

	struct node *head = create_node(7, NULL);
	head = create_node(8, head);
	head = create_node(11, head);

	// traverse the list and print out the list
	print_list(head);

	insert_at_tail(6, head);

	// check that the 6 has been aded to the tail of list
	print_list(head);

	insert_at_position(5, 2, head);

	print_list(head);

	delete_node(head, 5);

	print_list(head);

	insert_at_position(0, 5, head);

	print_list(head);

	// TODO: if we/you have time, to rid memory leaks in this code,
	// we should free all the nodes of the list we have created/malloc-ed

	return 0;
}

struct node *create_node(int data, struct node *next) {
	struct node *head = malloc(sizeof(struct node));
	head->data = data;
	head->next = next;

	// return that node
	return head;
}


void print_list(struct node *head) {
	struct node *current = head;
	while (current != NULL) { // while we have not reached the end of the list
		printf("%d ", current->data);
		current = current->next;
	}
	printf("\n");
}

// insert a given value at the tail of a given list
struct node *insert_at_tail(int data, struct node *head) {
	struct node *new_node = create_node(data, NULL);
	
	// TODO empty list case
	if (head == NULL) {
		head = new_node;
		return head;
	}
	
	struct node *current = head;
	// loop the current pointer until ????
	while (current->next != NULL) {
		current = current->next;
	}
	// at this pt, current->next == NULL
	// which means current is pointing at the last node
	current->next = new_node;
	return head;
}

struct node *insert_at_position(int data, int position, struct node *head) {
	struct node *new_node = create_node(data, NULL);

	if (position == 0 && head == NULL) {
		head = new_node;
		return head;
	}

	if (position == 0 && head != NULL) {
		new_node->next = head;
		head = new_node;
		return head;
	}

	// loop until we reach location just before where
	// we want to insert
	struct node *current = head;
	int counter = 1;
	while (current != NULL && counter != position) {
		counter++;
		current = current->next;
	}
	// current == NULL --- reached the end of the list 
	// OR/AND 
	// counter == position --- we have reached the position we want to insert
	if (counter == position && current != NULL) {
		new_node->next = current->next;
		current->next = new_node;
		return head;
	}
	// we have reached end of list
	// but counter is not yet the position number
	printf("Hey the position number is too big\n");
	// free the node we have malloced
	free(new_node);
	return head;

}

// delete a specific node value and return head of list
struct node *delete_node(struct node *head, int value_to_be_deleted) {
	// empty list
	if (head == NULL) {
		// do nothing
		return head;
	}
	// the node we want to delete is the only element in the list
	if (head->next == NULL && head->data == value_to_be_deleted) {
		free(head);
		// head = NULL;
		// return head;
		return NULL;
	}

	// delete node at head, but list has more than one element
	if (head->data == value_to_be_deleted) { // head->next != NULL
		struct node *temp = head;
		head = head->next;
		free(temp);
		return head;
	}

	struct node *current = head;
	// keep looping until we reach the node where the next node is 
	// the one we want to delete
	while (current->next != NULL && current->next->data != value_to_be_deleted) { // BUG???
		current = current->next;
	}
	if (current->next == NULL) {
		return head;
	}

	// so that i am at the node just before the one we want to delete here
	// current->next->data == value_to_be_deleted
	struct node *temp = current->next;
	current->next = temp->next; // current->next->next
	free(temp);


	return head;
}