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

#include "trie.h"

void autocomplete(Trie t, char *prefix);
static Trie findPrefixNode(Trie t, char *prefix);
static void printSuggestions(Trie t, char *prefix, char suffix[], int i);

int main(void) {
	Trie t = trieNew();
	char *keys[] = {
		"hive", "five", "goop", "good", "gold",
		"home", "hood", "hoof", "horn", "hoop",
		"mood", "goodie"
	};
	for (int i = 0; i < 12; i++) {
		trieInsert(t, keys[i]);
	}

	autocomplete(t, "goo");

	trieFree(t);
}

void autocomplete(Trie t, char *prefix) {
	// TODO
	
	Trie prefixNode = findPrefixNode(t, prefix);
	char suffix[100];
	printSuggestions(prefixNode, prefix, suffix, 0);
}

static Trie findPrefixNode(Trie t, char *prefix) {
	if (t == NULL) {
		return NULL;
	}

	if (prefix[0] == '\0') {
		return t;
	}

	int first = prefix[0] - 'a';
	return findPrefixNode(t->children[first], &prefix[1]);
}

static void printSuggestions(Trie t, char *prefix, char suffix[], int i) {
	if (t == NULL) {
		return;
	}

	if (t->finish) {
		suffix[i] = '\0';
		printf("%s%s\n", prefix, suffix);
	}

	for (int j = 0; j < ALPHABET_SIZE; j++) {
		suffix[i] = 'a' + j;
		printSuggestions(t->children[j], prefix, suffix, i + 1);
	}
}