Serialize Präfixbaums

Question

Ich erhalte eine ProtoException ("Mögliche Rekursion erkannt (Offset: 4 Level (s)): o EOW"), wenn die Serialisierung eine Baumstruktur wie folgt:

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); 
     } 

Der Baum Umsetzung:

[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; 
    } 
} 

bin ich mit den falschen Attributen schmücken oder habe ich einfach einen nicht serialisierbaren Baum entworfen?

Edit: versucht, dies ohne Erfolg:

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

Die _parent und den Wert des _nodes beide auf dem gleichen Typ (PrefixTree), sondern nur die _parent wird als "AsReference" gekennzeichnet.

Wenn Sie die Serialisierung Stapel laufen wird Ihnen der Wert des Dictionary-Wert sehen, dass unabhängig von der _parent Element serialisiert wird und nicht für eine doppelte Instanz geprüft.

Wie es geht um den Baum gibt es eine interne Serialisierung Tiefenprüfung von 25, in der es die doppelten Instanzen beginnt zu detektieren. Wenn dieser Wert größer wäre, würde es keine Ausnahme auslösen, wenn es kleiner wäre, würde es auf einen Knoten weiter oben im Baum werfen.

Ich glaube auch nicht, dass dies deserializable wäre, und wenn es das tat, würde der _parent-Feldwert jedes untergeordneten Knotens nicht dieselbe Instanz wie der _nodes-Container sein.

Sie müssen erstellen Sie eigenen Wörterbuchtyp (Unterklasse Wörterbuch <,> oder implementieren IDictionary <,>) sind so können Sie hinzugefügt, um das [ProtoContract] Attribut und steuern die Serialisierung von Produkten des Wörterbuch.

dh

[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 

der Schlüssel hier ist die AsReference Metadaten an den Knoten des PrefixTree angebracht zu bekommen. Beachten Sie auch, dass Artikel ein Array zurückgibt, wenn Sie es als eine Liste wollen, dann müssen Sie das Attribut OverwriteList Mitglied Satz verwenden.

ich auch das Nur-Lese-Schlüsselwort für jedes Feld in dem PrefixTree Typ entfernen benötigt. Dieser Unit Test ist für mich bestanden.

 [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); 
    }