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

#include "trie.h"

void predict(Trie t, char *keypad[], char *keyPresses);
static void doPredict(Trie t, char *keypad[], char *keyPresses, char word[],
		int index);

int main(void) {
	char *keypad[] = {
		[0] = "",
		[1] = "",
		[2] = "abc",
		[3] = "def",
		[4] = "ghi",
		[5] = "jkl",
		[6] = "mno",
		[7] = "pqrs",
		[8] = "tuv",
		[9] = "wxyz",
	};

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

	predict(t, keypad, "4663");

	trieFree(t);
}

void predict(Trie t, char *keypad[], char *keyPresses) {
	// TODO
	char word[100];
	doPredict(t, keypad, keyPresses, word, 0);
}

static void doPredict(Trie t, char *keypad[], char *keyPresses, char word[],
		int index) {
	if (t == NULL) {
		return;
	}

	// In the lecture, we forgot this if statement
	if (keyPresses[0] == '\0') {
		if (t->finish) {
			word[index] = '\0';
			printf("%s\n", word);
		}

		// Return because no more key presses so no need to recurse
		return;
	}

	int keyIndex = keyPresses[0] - '0';
	char *possibleLetters = keypad[keyIndex];
	for (int i = 0; possibleLetters[i] != '\0'; i++) {
		word[index] = possibleLetters[i];
		doPredict(t->children[possibleLetters[i] - 'a'], keypad,
				&keyPresses[1], word, index + 1);
	}
}