// Implementation of trie module

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

#include "trie.h"

static bool isLeafNode(Trie t);
typedef unsigned long long uint64;
static void doShow(Trie t, int level, uint64 arms);

Trie trieNew(void) {
	Trie t = calloc(1, sizeof(*t));
	if (t == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	return t;
}

void trieFree(Trie t) {
	if (t == NULL) return;

	for (int i = 0; i < ALPHABET_SIZE; i++) {
		if (t->children[i] != NULL) {
			trieFree(t->children[i]);
		}
	}
	free(t);
}

Trie trieInsert(Trie t, char *key) {
	Trie current = t;
	int i=0;
	while (key[i]!='\0') {
		if (current->children[key[i]-'a'] == NULL) {
			current->children[key[i]-'a'] = calloc(1, sizeof(*t));
		}
		current = current->children[key[i]-'a'];
		i++;
	}
	current->finish = true;	
	
	return t;
}

Trie trieInsertRec(Trie t, char *key) {
	if (t == NULL) {
		t = calloc(1, sizeof(*t));
	}
	if (key[0] == '\0') {
		t->finish = true;
		return t;
	}

	int i = key[0] - 'a';
	t->children[i] = trieInsert(t->children[i], &key[1]);
	return t;
}

bool trieSearch(Trie t, char *key) {
	if (t == NULL) {
		return false;
	}
	if (key[0] == '\0') {
		return t->finish;
	}

	int first = key[0] - 'a';
	char *rest = &key[1];
	return trieSearch(t->children[first], rest);
}

Trie trieDelete(Trie t, char *key) {
	if (t == NULL) {
		return t;
	}

	if (key[0] == '\0') {
		t->finish = false;
	} else {
		int first = key[0] - 'a';
		char *rest = &key[1];
		t->children[first] = trieDelete(t->children[first], rest);
	}

	if (!t->finish && isLeafNode(t)) {
		free(t);
		return NULL;
	} else {
		return t;
	}
}

static bool isLeafNode(Trie t) {
	for (int i = 0; i < ALPHABET_SIZE; i++) {
		if (t->children[i] != NULL) {
			return false;
		}
	}
	return true;
}

void trieShow(Trie t) {
	printf("root\n|");
	doShow(t, 0, 0);
}

static void doShow(Trie t, int level, uint64 arms) {
	if (t == NULL) return;

	printf("%s\n", t->finish ? " (finish)" : "");

	int numChildren = 0;
	for (int i = 0; i < ALPHABET_SIZE; i++) {
		if (t->children[i] != NULL) {
			numChildren++;
		}
	}

	int childNo = 0;
	for (int i = 0; i < ALPHABET_SIZE; i++) {
		if (t->children[i] == NULL) continue;

		childNo++;
		for (int i = 0; i < level; i++) {
			if ((1LLU << i) & arms) {
				printf("|   ");
			} else {
				printf("    ");
			}
		}
		printf("+-- ");
		printf("%c", i + 'a');
		if (childNo < numChildren) {
			arms |= (1LLU << level);
		} else {
			arms &= ~(1LLU << level);
		}
		doShow(t->children[i], level + 1, arms);
	}
}