#include <stdio.h>
#include <kiss-compat.h>
#include <kiss-graphics.h>
#include <kiss-serial.h>
#include <kiss-create.h>
#include <kiss-input.h>

typedef struct Node_structure {
	int key;
	float data;
	struct Node_structure* previous;
	struct Node_structure* next;
} Node;

typedef struct LinkedList_structure {
	Node* firstNode;
	Node* lastNode;
} LinkedList;

Node* make_node(int key, float data);
void insert_before_beginning(LinkedList* list, Node* node);
void insert_after_end(LinkedList* list, Node* node);
void insert_after(LinkedList* list, Node* node, Node* newNode);
void insert_before(LinkedList* list, Node* node, Node* newNode);
void print_nodes(LinkedList* list);
void print_nodes_helper(Node* node);

int main() {
	LinkedList* list;
	Node* node;
	int k;
	
	list = (LinkedList*) malloc(1 * sizeof(LinkedList));
	list->firstNode = list->lastNode = NULL;
	
	for (k = 0; k < 10; ++k) {
		node = make_node((int) (rand() % 100), (float) rand() / (float) RAND_MAX);
		insert_before_beginning(list, node);
	}
	
	print_nodes(list);
}

// Allocates space for a Node and sets the Node's key and data to the given values.
// Returns a pointer to the Node.
Node* make_node(int key, float data) {
	// TODO:  Allocate space.
	// TODO:  Set the key to the given key.
	// TODO:  Set the data to the given data.
	// TODO:  Return a pointer to the allocated space.
}

// Insert the given Node at the beginning of the given LinkedList.
void insert_before_beginning(LinkedList* list, Node* newNode) {
	if (list->firstNode == NULL) {
		
		// TODO: Set the list's firstNode and lastNode.
		
		// TODO: Set the newNode's previous and next.
		
	} else {
		Node* oldFirstNode = list->firstNode;
		
		// TODO: Set the list's ...
		
		// TODO: Set the newNode's previous and next.
	}
}

// Insert the given Node at the end of the given LinkedList.
void insert_after_end(LinkedList* list, Node* newNode) {
	if (list->lastNode == NULL) {
		
		// TODO: Set the list's firstNode and lastNode.
		
		// TODO: Set the newNode's previous and next.
		
	} else {
		Node* oldLastNode = list->lastNode;
		
		// TODO: Set the list's ...
		
		// TODO: Set the newNode's previous and next.
	}
}

// Insert the given newNode after the given Node.
// Modify the given LinkedList's lastNode if necessary.
void insert_after(LinkedList* list, Node* node, Node* newNode) {
	if (node->next == NULL) {
		// TODO: Set node's ...
		
		// TODO: Set the newNode's previous and next.
		
		// TODO: Set list's ...
		
	} else {
		Node* nodeAfterGivenNode = node->next;
		
		// TODO: Set node's ...
		
		// TODO: Set nodeAfterGivenNode's ...
		
		// TODO: Set the newNode's previous and next.
	}
}

// Insert the given newNode before the given Node.
// Modify the given LinkedList's firstNode if necessary.
void insert_before(LinkedList* list, Node* node, Node* newNode) {
	if (node->previous == NULL) {
		// TODO: Set node's ...
		
		// TODO: Set the newNode's previous and next.
		
		// TODO: Set list's ...
		
	} else {
		Node* nodeBeforeGivenNode = node->previous;
		
		// TODO: Set node's ...
		
		// TODO: Set nodeBeforeGivenNode's ...
		
		// TODO: Set the newNode's previous and next.
	}
}

// Print the nodes in the given list, one per line.
void print_nodes(LinkedList* list) {
	if (list->firstNode == NULL) {
		return;
	} else {
		print_nodes_helper(NULL); // TODO: replace NULL by ...
	}
}

// Prints the given node (which must be non-null)
// and recursively prints the rest of the nodes after it.
void print_nodes_helper(Node* node) {
	printf("%x %3d %5.3f\n", node, node->key, node->data);
	// TODO: Recurse IF ...
}