full-trie.cs

public class SimpleNode
{
    public SimpleNode[] Children;
    public string Prefix;
    public long? Value;
}

public class Trie 
{
    private SimpleNode[] _nodes = new SimpleNode[0];

    public bool TryWrite(string key, long value)
    {
        Insert(ref _nodes, key, 0, value);
        return true;
    }

    public bool TryRead(string key, out long value)
    {
        value = 0;
        return Find(_nodes, key, 0, ref value);
    }

    public void Delete(string key)
    {
        Delete(ref _nodes, key, 0);
    }

    private static void Insert(ref SimpleNode[] nodes, string key, int pos, long value)
    {
        if ((nodes == null) || (nodes.Length == 0))
        {
            nodes = new[]
            {
                new SimpleNode
                {
                    Value = value,
                    Prefix = key
                }
            };
            return;
        }
        int match;
        if (FindMatch(nodes, key, pos, out match))
        {
            var differenceStarts = FindDifference(key, nodes[match].Prefix, pos);
            // recurse into next level, but first might need to trim the current value
            if ((nodes[match].Children == null) && (nodes[match].Prefix.Length != differenceStarts))
                nodes[match] = new SimpleNode
                {
                    Prefix = nodes[match].Prefix.Substring(0, differenceStarts),
                    Children = new[]
                    {
                        new SimpleNode
                        {
                            Value = nodes[match].Value,
                            Prefix = nodes[match].Prefix
                        }
                    }
                };
            Insert(ref nodes[match].Children, key, pos + 1, value);

            return;
        }
        // this belong in this level, match tell us the position we need, using list because
        // it will take care of growing / moving the data
        var newNodes = new List<SimpleNode>(nodes.Length + 1);
        newNodes.AddRange(nodes);
        newNodes.Insert(match, new SimpleNode
        {
            Prefix = key,
            Value = value
        });
        nodes = newNodes.ToArray();
    }

    private static int FindDifference(string x, string y, int start)
    {
        var len = Math.Min(x.Length, y.Length);
        for (var i = start + 1; i < len; i++)
            if (x[i] != y[i])
                return i;
        return len;
    }

    private static bool FindMatch(SimpleNode[] nodes, string key, int pos, out int match)
    {
        match = -1;
        var firstChar = key[pos];
        int start = 0, end = nodes.Length - 1;
        var compareTo = 0;
        while (start <= end)
        {
            match = (start + end)/2;
            compareTo = nodes[match].Prefix[pos].CompareTo(firstChar);
            if (compareTo == 0)
                return true;

            if (compareTo < 0)
                start = match + 1;
            else
                end = match - 1;
        }
        if (compareTo < 0)
            match++;
        return false;
    }

    private static bool Find(SimpleNode[] nodes, string key, int pos, ref long value)
    {
        if ((nodes == null) || (nodes.Length == 0))
            return false;
        int match;
        if (FindMatch(nodes, key, pos, out match) == false)
            return false;

        if (nodes[match].Prefix.Length < key.Length)
            return Find(nodes[match].Children, key, pos + 1, ref value);

        if (nodes[match].Value == null)
            return false;

        value = nodes[match].Value.Value;
        return true;
    }

    private static void Delete(ref SimpleNode[] nodes, string key, int pos)
    {
        if ((nodes == null) || (nodes.Length == 0))
            return;

        int match;
        if (FindMatch(nodes, key, pos, out match) == false)
            return;

        if (nodes[match].Prefix.Length < key.Length)
        {
            Delete(ref nodes[match].Children, key, pos + 1);
            if (nodes[match].Children.Length == 1)
                nodes[match] = nodes[match].Children[0];
            return;
        }

        if (nodes[match].Value == null)
            return; // is is a match with no value, nothing to delete

        // actual delete
        if ((nodes[match].Children == null) || (nodes[match].Children.Length == 0))
        {
            // no children, so can just remove it.
            var newNodes = new List<SimpleNode>(nodes);
            newNodes.RemoveAt(match);
            nodes = newNodes.ToArray();
            return;
        }
        if (nodes[match].Children.Length == 1)
        {
            // just one child, so just promote it one level
            nodes[match] = nodes[match].Children[0];
            return;
        }
        // more than one child, so just set it to null
        nodes[match].Value = null;
    }
}