// Implementation of trie module

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

#include "trie.h"

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) {
	// TODO
	return t;
}

bool trieSearch(Trie t, char *key) {
	// TODO
	return false;
}

Trie trieDelete(Trie t, char *key) {
	// TODO
	return t;
}

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);
	}
}