Serialize the prefix tree

Question

I get a ProtoException ("Possible recursion detected (offset: 4 levels (s)): o EOW") when serializing the tree structure as follows:

 var tree = new PrefixTree(); tree.Add("racket".ToCharArray()); tree.Add("rambo".ToCharArray()); using (var stream = File.Open("test.prefix", FileMode.Create)) { Serializer.Serialize(stream, tree); } 

Tree implementation:

 [ProtoContract] public class PrefixTree { public PrefixTree() { _nodes = new Dictionary<char, PrefixTree>(); } public PrefixTree(char[] chars, PrefixTree parent) { if (chars == null) throw new ArgumentNullException("chars"); if (parent == null) throw new ArgumentNullException("parent"); if (chars.Length == 0) throw new ArgumentException(); _parent = parent; _nodes = new Dictionary<char, PrefixTree>(); _value = chars[0]; var overflow = chars.SubSet(1); if (!overflow.Any()) _endOfWord = true; else Add(overflow.ToArray()); } [ProtoMember(1)] private readonly char _value; [ProtoMember(2)] private readonly bool _endOfWord; [ProtoMember(3)] private readonly IDictionary<char, PrefixTree> _nodes; [ProtoMember(4, AsReference = true)] private readonly PrefixTree _parent; public void Add(char[] word) { if (word == null) throw new ArgumentNullException("word"); if (word.Length == 0) return; var character = word[0]; PrefixTree node; if (_nodes.TryGetValue(character, out node)) { node.Add(word.SubSet(1)); } else { node = new PrefixTree(word, this); _nodes.Add(character, node); } } public override string ToString() { return _endOfWord ? _value + " EOW" : _value.ToString(); } } public static class ListHelper { public static char[] SubSet(this char[] source, int start) { return source.SubSet(start, source.Length - start); } public static char[] SubSet(this char[] source, int start, int length) { if (start < 0) throw new ArgumentOutOfRangeException(); if (start > source.Length) throw new ArgumentOutOfRangeException(); if (length < 0) throw new ArgumentOutOfRangeException(); var result = new char[length]; Array.Copy(source, start, result, 0, length); return result; } } 

Am I decorating the wrong attributes or just creating a non-serializable tree?

Edit: tried this to no avail:

 var typeModel = RuntimeTypeModel.Default; var type = typeModel.Add(typeof(PrefixTree), false); type.AsReferenceDefault = true; type.Add("_value", "_endOfWord", "_nodes", "_parent"); var tree = new PrefixTree(); tree.Add("racket".ToCharArray()); tree.Add("rambo".ToCharArray()); using (var stream = File.Open("test.prefix", FileMode.Create)) { typeModel.Serialize(stream, tree); } 

Answer 1

The _parent and Value_nodes parameters point to the same type (PrefixTree), but only _parent is marked as "AsReference".

If you go on the serialization stack, you will see that the value of the dictionary value is serialized regardless of the _parent element and is not checked for duplicate instance.

When he walks the tree, an internal check is performed on the depth of serialization 25, at which he begins to detect duplicate instances. If this value were greater, it would not throw an exception; if it were less, it would select a node above the tree.

I also do not think that this would be deserializable, and, of course, if this happened, the value of the _parent field for each child node would not be the same instance as the _nodes container.

You need to create your own type of dictionary (a subclass of Dictionary <,> or implement IDictionary <,>) so that you can add the [ProtoContract] attribute and control the serialization of dictionary entries.

t

 [ProtoContract] public class NodeItem { [ProtoMember(1)] public char Key { get; set; } [ProtoMember(2, AsReference = true)] public PrefixTree Value { get; set; } } [ProtoContract] public class Nodes : IDictionary<char, PrefixTree> { private readonly IDictionary<char, PrefixTree> inner; [ProtoMember(1)] public NodeItem[] Items { get { return this.inner.Select(item => new NodeItem() {Key = item.Key, Value = item.Value}).ToArray(); } set { foreach( NodeItem item in value) { this.inner.Add(item.Key, item.Value); } } } ... // Omitted IDictionary members for clarity 

the key here is to get AsReference metadata attached to PrefixTree nodes. Also note that the elements return an array, if you want it to be a list, then you need to use the OverwriteList attribute parameter.

I also needed to remove the readonly keyword for each field in the PrefixTree type. This unit test passed for me.

  [TestMethod] public void TestMethod1() { var tree = new PrefixTree(); tree.Add("racket".ToCharArray()); tree.Add("rambo".ToCharArray()); PrefixTree tree2 = null; using (var stream = new MemoryStream()) { Serializer.Serialize(stream, tree); stream.Position = 0; tree2 = Serializer.Deserialize<PrefixTree>(stream); } Assert.IsNotNull(tree2); Assert.AreEqual(tree._nodes.Count, tree2._nodes.Count); Assert.AreEqual(2, tree2._nodes['r']._nodes['a']._nodes.Count); // 'c' and 'm' Assert.AreEqual('c', tree2._nodes['r']._nodes['a']._nodes.Values.First().Value); Assert.AreEqual('m', tree2._nodes['r']._nodes['a']._nodes.Values.Last().Value); }