using System.Collections.Generic;

namespace XRLib.Collections
{
    public class Trie
    {
        private readonly TrieNode root;

        public Trie()
        {
            root = new TrieNode();
        }

        public void Insert(string word)
        {
            var currentNode = root;
            foreach (var ch in word)
            {
                if (!currentNode.Children.ContainsKey(ch))
                {
                    currentNode.Children[ch] = new TrieNode();
                }
                currentNode = currentNode.Children[ch];
            }
            currentNode.IsEndOfWord = true;
        }

        public bool Search(string word)
        {
            var currentNode = root;
            foreach (var ch in word)
            {
                if (!currentNode.Children.ContainsKey(ch))
                {
                    return false;
                }
                currentNode = currentNode.Children[ch];
            }
            return currentNode.IsEndOfWord;
        }

        public bool TryGetContainingWords(string substring, out List<string> result)
        {
            result = new List<string>();
            CollectWordsContainingSubstring(root, "", substring, result);

            if(result.Count == 0)
            {
                return false;
            }
            return true;
        }

        private void CollectWordsContainingSubstring(TrieNode node, string currentWord, string substring, List<string> result)
        {
            if (node.IsEndOfWord && currentWord.ToLower().Contains(substring.ToLower()))
            {
                result.Add(currentWord);
            }

            foreach (var child in node.Children)
            {
                CollectWordsContainingSubstring(child.Value, currentWord + child.Key, substring, result);
            }
        }
    }
}