को क्रमानुसार उपसर्ग पेड़

Question

मैं एक ProtoException मिल ("संभावित प्रत्यावर्तन का पता चला (ऑफसेट: 4 स्तर (रों)): ओ ईओडब्ल्यू") जब इतनी तरह एक वृक्ष संरचना serializing:

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

पेड़ कार्यान्वयन:

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

क्या मैं गलत विशेषताओं से सजा रहा हूं या क्या मैंने बस एक गैर-धारावाहिक पेड़ तैयार किया है?

संपादित करें: कोई लाभ नहीं हुआ इस की कोशिश की:

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

_parent और मूल्य _nodes के एक ही प्रकार (PrefixTree) के दोनों बिंदु है, लेकिन केवल _parent "AsReference" के रूप में चिह्नित है।

यदि आप क्रमबद्धता स्टैक चलते हैं तो आप देखेंगे कि शब्दकोश मान का मूल्य _parent आइटम से स्वतंत्र रूप से क्रमबद्ध किया गया है और डुप्लिकेट उदाहरण के लिए चेक नहीं किया गया है।

चूंकि यह पेड़ पर चलता है, वहां 25 की एक आंतरिक धारावाहिक गहराई की जांच होती है, जिस पर यह डुप्लिकेट उदाहरणों का पता लगाना शुरू कर देता है। यदि यह मान बड़ा था तो यह अपवाद नहीं फेंकता, अगर यह छोटा होता तो यह पेड़ को ऊपर नोड पर फेंक देगा।

मुझे यह भी नहीं लगता कि यह deserializable होगा, और निश्चित रूप से अगर ऐसा किया गया है कि प्रत्येक बच्चे नोड का _parent फ़ील्ड का मान _nodes कंटेनर के समान उदाहरण नहीं होगा।

आपको अपने स्वयं के शब्दकोश का प्रकार (उपclass शब्दकोश <,> या IDictionary <,> लागू करें) को बनाने की आवश्यकता है ताकि आप [ProtoContract] विशेषता को जोड़ सकें और शब्दकोश की वस्तुओं के क्रमबद्धकरण को नियंत्रित कर सकें।

यानी

[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 

कुंजी यहाँ AsReference मेटाडाटा नोड्स के PrefixTree से जुड़ी पाने के लिए है। यह भी ध्यान रखें कि आइटम एक ऐरे लौट रहे हैं, यदि आप इसे एक सूची के रूप में चाहते हैं, तो आपको ओवरराइटलिस्ट सूची सदस्य सेट करने की आवश्यकता है।

मुझे प्रीफिक्स ट्री प्रकार में प्रत्येक फ़ील्ड के लिए केवल पढ़ने योग्य कीवर्ड को हटाने की आवश्यकता है। यह यूनिट परीक्षण मेरे लिए पास हो गया।

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