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

#include "trie.h"

void autocomplete(Trie t, char *prefix);

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

static void doAutocomplete(Trie t, char key[], int i) {
	if (t == NULL) {
		return;
	}
	if (t->finish) {
		key[i] = '\0';
		printf("%s\n", key);
	}
	// 1. Go through each character to find each child
	for (int j=0; j<ALPHABET_SIZE; j++) {
		if (t->children[j] != NULL) {
			key[i] = 'a'+j;
			key[i+1] = '\0';
			// Do autocomplete on each child we find
			doAutocomplete(t->children[j], key, i+1);
		}
	}

}

void autocomplete(Trie t, char *prefix) {
	// TODO

	// 1. Find the prefix
	int i=0;
	Trie current = t;
	char key[100];
	while (prefix[i] != '\0') {
		// Assume it's in there somewhere
		key[i] = prefix[i];
		current = current->children[prefix[i]-'a'];
		i++;
	}	
	key[i] = '\0';
	// 2. Turn trie into list of possible words
	doAutocomplete(current, key, i);
}