Trie.cs

using System;
using System.Collections.Generic;

namespace DataStructures.Tries
{
    /// <summary>
    /// A Trie is a data structure (particular case of m-ary tree) used to efficiently represent strings with common prefixes.
    /// Originally posed by E. Fredkin in 1960.
    ///     Fredkin, Edward (Sept. 1960), "Trie Memory", Communications of the ACM 3 (9): 490-499.
    /// Its name is due to retrieval because its main application is in the field of "Information Retrieval" (information retrieval).
    /// </summary>
    public class Trie
    {
        /// <summary>
        /// This character marks the end of a string.
        /// </summary>
        private const char Mark = '$';

        /// <summary>
        /// This property represents the root node of the trie.
        /// </summary>
        private readonly TrieNode root;

        /// <summary>
        /// Initializes a new instance of the <see cref="Trie"/> class. This instances was created without text strings, generating the root node of the trie, without children.
        /// </summary>
        public Trie()
        {
            root = new TrieNode(Mark);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Trie"/> class. Given a set of text strings, each of those strings inserts them into the trie using the Insert (string) method.
        /// </summary>
        /// <param name="words">The array with text strings to insert in the trie.</param>
        public Trie(IEnumerable<string> words)
            : this()
        {
            foreach (string s in words)
            {
                Insert(s);
            }
        }

        /// <summary>
        /// Insert a string s to the trie. The $ mark is added to the end of the chain and then it is added, this in order to indicate the end of the chain in the trie.
        /// </summary>
        /// <param name="s">The string to insert into the trie.</param>
        public void Insert(string s)
        {
            s += Mark;

            int index = 0;
            TrieNode match = PrefixQuery(s, ref index);

            for (int i = index; i < s.Length; i++)
            {
                TrieNode t = new(s[i], match);
                match[s[i]] = t;
                match = t;
            }
        }

        /// <summary>
        /// Remove a text string from the trie.
        /// </summary>
        /// <param name="s">The text string to be removed from the trie.</param>
        public void Remove(string s)
        {
            s += Mark;
            int index = 0;
            TrieNode match = PrefixQuery(s, ref index);
            while(match.IsLeaf())
            {
                char c = match.Value;
                if(match.Parent == null)
                {
                    break;
                }

                match = match.Parent;
                match.Children.Remove(c);
            }
        }

        /// <summary>
        /// Know if a text string is in the trie.
        /// </summary>
        /// <param name="s">The string s that you want to know if it is in the trie.</param>
        /// <returns>If the string is found, it returns true, otherwise false.</returns>
        public bool Find(string s)
        {
            int index = 0;
            return PrefixQuery(s + Mark, ref index).IsLeaf();
        }

        /// <summary>
        /// This method analyzes which is the longest common prefix of a string s in the trie. If the string is in the trie then it is equivalent to doing Find (s).
        /// </summary>
        /// <param name="s">The string for which you want to know the longest common prefix.</param>
        /// <param name="index">The index to which the longest common prefix goes.</param>
        /// <returns>
        /// Returns the longest common prefix node found in the trie with the string s.
        /// </returns>
        private TrieNode PrefixQuery(string s, ref int index)
        {
            TrieNode current = root;
            for (int i = 0; i < s.Length && current != null; i++)
            {
                if (current[s[i]] != null)
                {
                    current = current[s[i]] ?? throw new NullReferenceException();
                    index = i + 1;
                }
                else
                {
                    break;
                }
            }

            return current ?? throw new NullReferenceException();
        }
    }
}