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

#define pp(x)      printf("%s = %p\n", #x, x);
#define pi(x)      printf("%s = %d\n", #x, x);
#define pc(x)      printf("%s = %c\n", #x, x);
#define psize_t(x) printf("%s = %zu\n", #x, x);

// A C program to demonstrate linked list based implementation of queue 
// A linked list (LL) node to store a queue entry
int index_start = -1;
int ref_start = 0;
int global_indent = 0;

#define node_init(t, i, r, n) t->index = i; t->ref = r; t->next = n; t->level = global_indent;

#define STORE_NORMAL 1
#define STORE_EMPTY 2

#define NODE_TYPE_NORMAL 1
#define NODE_TYPE_BRANCH_START 2
#define NODE_TYPE_BRANCH_END 3
#define NODE_TYPE_BRANCH_CHOICE_START 4
#define NODE_TYPE_BRANCH_CHOICE_END 5

#define POINTER_LIST_TYPE int

POINTER_LIST_TYPE ** ptr_list = NULL;
ssize_t ptr_list_size = 0;

int last_ref = 0;

int ptr_add(POINTER_LIST_TYPE * ptr) {
	if (!ptr) return -1;
	if (!ptr_list) {
		ptr_list = malloc(sizeof(ptr_list)*2);
		ptr_list_size++;
	}
	else if (ptr_list) {
		ptr_list = realloc(ptr_list, sizeof(ptr_list)*(ptr_list_size+1));
	}
	ptr_list[ptr_list_size-1] = ptr;
	ptr_list_size++;
	ptr_list[ptr_list_size-1] = NULL;
	return 0;
}

int ptr_print(void) {
	if (!ptr_list) return -1;
	POINTER_LIST_TYPE ** pl;
	for (pl = ptr_list; *pl; pl++) pp(*pl);
	return 0;
}

int ptr_set(POINTER_LIST_TYPE data) {
	if (!ptr_list) return -1;
	POINTER_LIST_TYPE ** pl;
	for (pl = ptr_list; *pl; pl++) **pl = data;
	return 0;
}

int ptr_set_free(void) {
	if (!ptr_list) return -1;
	POINTER_LIST_TYPE ** pl;
	for (pl = ptr_list; *pl; pl++) {
		free(*pl);
		*pl = NULL;
	}
	return 0;
}

int ptr_free(void) {
	if (!ptr_list) return -1;
	POINTER_LIST_TYPE ** pl;
	for (pl = ptr_list; *pl; pl++) *pl = NULL;
	free(ptr_list);
	ptr_list = NULL;
	ptr_list_size = 0;
	return 0;
}

struct QNode
{
	int level;
	int index;
	int ref;
	int type;
	struct QNode *next;
};

// The queue, front stores the front node of LL and rear stores ths
// last node of LL
struct Queue
{
	struct QNode *front, *rear;
};


// A utility function to create a new linked list node.
struct QNode* newNode(int type)
{
	struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
	if (type == STORE_NORMAL) {
		node_init(temp, index_start++, ref_start++, NULL);
	} else if (type == STORE_EMPTY) {
		node_init(temp, 0, 0, NULL);
	}
	return temp;
}

// A utility function to create an empty queue
struct Queue *createQueue()
{
	struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
	q->front = q->rear = NULL;
	return q;
}
int prev_type = 0;
int curr_type = 0;
void store_asm(struct Queue *q, int type)
{
	if (curr_type) prev_type = curr_type;
	curr_type = type;
	// Create a new LL node
	int t = 0;
	if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
	else if (
		type == NODE_TYPE_BRANCH_START
		||
		type == NODE_TYPE_BRANCH_END
		||
		type == NODE_TYPE_BRANCH_CHOICE_START
		||
		type == NODE_TYPE_BRANCH_CHOICE_END
			) t = STORE_EMPTY;
	struct QNode *temp = newNode(t);
	temp->type = type;

	// If queue is empty, then new node is front and rear both
	if (q->rear == NULL)
	{
		q->front = q->rear = temp;
		return;
	}
	if (prev_type == NODE_TYPE_NORMAL) {
		
		if (type == NODE_TYPE_BRANCH_CHOICE_END) {
	// 		pp(&q->rear->ref)
			last_ref = q->rear->ref;
			pi(last_ref);
			ptr_add(&q->rear->ref);
		}
	}
	else if(type == NODE_TYPE_NORMAL && prev_type == NODE_TYPE_BRANCH_END) {
		pi(last_ref);
		ptr_set(last_ref);
		ptr_free();
	}
	// Add the new node at the end of queue and change rear
	
	// allocate a new array for our new item
	if (!q->rear->next) {
		q->rear->next = malloc(sizeof(struct QNode));
	} else {
		abort();
	}
	// update rear->next to point to the new item
	q->rear->next = temp;
	
	// update rear to point to the rear->next, which is the item we just added, updating the pointer rear from our old item to our new item
	q->rear = q->rear->next;
}

struct QNode * load_asm(struct Queue **q)
{
	// If queue is empty, return NULL.
	if ((q) == NULL) return NULL;
	if ((*q) == NULL) return NULL;
	if ((*q)->front == NULL)
	return NULL;

	// Store previous front and move front one node ahead
	struct QNode *temp = (*q)->front;
	// check if front->next is NULL, if NULL it means we have reached the end of the queue
	(*q)->front = (*q)->front->next;

	// If front becomes NULL, then change rear also as NULL
	if ((*q)->front == NULL)
	(*q)->rear = NULL;
	return temp;
}

ssize_t free_asm(struct Queue **q)
{
	puts("");
	pp(*q)
	ssize_t frees = 0;
	// If queue is empty, return NULL.
	if ((q) == NULL) return frees;
	if ((*q) == NULL) return frees;
	struct QNode *temp = NULL, *next = NULL;
	temp = (*q)->front;
	while (temp) {
		next = (*q)->front->next;
		frees++;
		free(temp);
		temp = NULL;
		(*q)->front = next;
		temp = next;
// 		pp((*q)->front)
// 		// Store previous front and move front one node ahead
// 		ptr_add((*q)->front);
// 		// check if front->next is NULL, if NULL it means we have reached the end of the queue
// 
// 		// If front becomes NULL, then change rear also as NULL
// 		if ((*q)->front == NULL)
// 		(*q)->rear = NULL;
	}
	frees++;
	free(*q);
	*q = NULL;
// 	ptr_add(*q);
// 	ptr_print();
// 	ptr_set_free();
// 	ptr_free();
	return frees;
}

void add(struct Queue **q) {
	if (!(*q)) (*q) = createQueue();
	store_asm((*q), NODE_TYPE_NORMAL);
}


#define add_indent(indent) { int i = 0; for (; i < indent; i++) printf("    "); }

struct Queue * list = NULL;

void print(struct QNode * p) {
	int indentation = 0;
	while(p) {
		indentation = p->level;
		add_indent(indentation);
		if (p->type == NODE_TYPE_BRANCH_START) {
			add_indent(indentation);
			printf("branch start\n");
		}
		else if (p->type == NODE_TYPE_BRANCH_END) {
			add_indent(indentation);
			printf("branch end\n");
		}
		else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
			add_indent(indentation);
			printf("branch choice start\n");
		}
		else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
			add_indent(indentation);
			printf("branch choice end\n");
		}
		else if (p->type == NODE_TYPE_NORMAL) {
			add_indent(indentation);
			printf("%d -> %d\n", p->index, p->ref);
		}
		p = p->next;
	}
	add_indent(indentation);
	puts("NULL");
}

void add_branch(struct Queue **q) {
	if (!(*q)) (*q) = createQueue();
	store_asm((*q), NODE_TYPE_BRANCH_START);
	global_indent++;
}

void end_branch(struct Queue **q) {
	global_indent--;
	if (!(*q)) (*q) = createQueue();
	store_asm((*q), NODE_TYPE_BRANCH_END);
}

void add_branch_choice(struct Queue **q) {
	if (!(*q)) (*q) = createQueue();
	store_asm((*q), NODE_TYPE_BRANCH_CHOICE_START);
	global_indent++;
}

void end_branch_choice(struct Queue **q) {
	global_indent--;
	if (!(*q)) (*q) = createQueue();
	store_asm((*q), NODE_TYPE_BRANCH_CHOICE_END);
}

int main(void) {
	index_start = 0;
	ref_start = 1;
	add(&list);
	add_branch(&list);
		add_branch_choice(&list);
			add(&list);
			add(&list);
			add_branch(&list);
				add_branch_choice(&list);
					add(&list);
					add(&list);
				end_branch_choice(&list);
			end_branch(&list);
		end_branch_choice(&list);
		add_branch_choice(&list);
			add(&list);
			add(&list);
			add_branch(&list);
				add_branch_choice(&list);
					add(&list);
					add(&list);
					add_branch(&list);
						add_branch_choice(&list);
							add(&list);
							add(&list);
							add_branch(&list);
								add_branch_choice(&list);
									add_branch(&list);
										add_branch_choice(&list);
											add(&list);
											add(&list);
											add_branch(&list);
												add_branch_choice(&list);
													add(&list);
													add(&list);
												end_branch_choice(&list);
											end_branch(&list);
										end_branch_choice(&list);
										add_branch_choice(&list);
											add(&list);
											add(&list);
											add_branch(&list);
												add_branch_choice(&list);
													add(&list);
													add(&list);
													add_branch(&list);
														add_branch_choice(&list);
															add(&list);
															add(&list);
															add_branch(&list);
																add_branch_choice(&list);
																	add(&list);
																	add(&list);
																	add_branch(&list);
																		add_branch_choice(&list);
																			add(&list);
																			add(&list);
																		end_branch_choice(&list);
																	end_branch(&list);
																	add(&list);
																	add(&list);
																	add(&list);
																end_branch_choice(&list);
																add_branch_choice(&list);
																	add(&list);
																	add(&list);
																	add_branch(&list);
																		add_branch_choice(&list);
																			add(&list);
																			add(&list);
																		end_branch_choice(&list);
																	end_branch(&list);
																	add(&list);
																	add(&list);
																	add(&list);
																end_branch_choice(&list);
															end_branch(&list);
															add_branch(&list);
																add_branch_choice(&list);
																	add(&list);
																	add(&list);
																end_branch_choice(&list);
															end_branch(&list);
														end_branch_choice(&list);
														add_branch_choice(&list);
															add(&list);
															add(&list);
															add_branch(&list);
																add_branch_choice(&list);
																	add(&list);
																	add(&list);
																end_branch_choice(&list);
															end_branch(&list);
														end_branch_choice(&list);
													end_branch(&list);
												end_branch_choice(&list);
											end_branch(&list);
										end_branch_choice(&list);
									end_branch(&list);
									add(&list);
									add(&list);
									add_branch(&list);
										add_branch_choice(&list);
											add(&list);
											add(&list);
										end_branch_choice(&list);
									end_branch(&list);
									add(&list);
									add(&list);
									add(&list);
								end_branch_choice(&list);
								add_branch_choice(&list);
									add(&list);
									add(&list);
									add_branch(&list);
										add_branch_choice(&list);
											add(&list);
											add(&list);
										end_branch_choice(&list);
									end_branch(&list);
									add(&list);
									add(&list);
									add(&list);
								end_branch_choice(&list);
							end_branch(&list);
							add_branch(&list);
								add_branch_choice(&list);
									add(&list);
									add(&list);
								end_branch_choice(&list);
							end_branch(&list);
						end_branch_choice(&list);
						add_branch_choice(&list);
							add(&list);
							add(&list);
							add_branch(&list);
								add_branch_choice(&list);
									add(&list);
									add(&list);
								end_branch_choice(&list);
							end_branch(&list);
						end_branch_choice(&list);
					end_branch(&list);
				end_branch_choice(&list);
			end_branch(&list);
		end_branch_choice(&list);
	end_branch(&list);
	add(&list);
	print(list->front);
	
	// this part should be left to the garbage collector to clean up
// 	psize_t(free_asm(&list));
	return 0;
}