#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 void findPrefix(Trie t, char *prefix, char *origPrefix);
static void doAutocomplete(Trie t, char key[], 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) {
	findPrefix(t, prefix, prefix);
}

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

	if (prefix[0] == '\0') {
		// print out all words in this subtrie
		char key[100];
		strcpy(key, origPrefix);
		doAutocomplete(t, key, strlen(key));
	} else {
		int first = prefix[0] - 'a';
		char *rest = &prefix[1];
		findPrefix(t->children[first], rest, origPrefix);
	}
}

static void doAutocomplete(Trie t, char key[], int i) {
	if (t == NULL) {
		return;
	}

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

	for (int j = 0; j < ALPHABET_SIZE; j++) {
		if (t->children[j] != NULL) {
			key[i] = 'a' + j;
			doAutocomplete(t->children[j], key, i + 1);
		}
	}
}