Skip to content

Instantly share code, notes, and snippets.

@ayende
Created Nov 11, 2016
Embed
What would you like to do?
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment