This is a post from 2017 but as I was re-learning Trie I read it over and made it available here 🙂
I was implementing a trie, which is a tree data structure, usually for storing strings for searching. Since it’s a tree, it has a “Children” for holding child nodes.
But then I ran into a problem where simply calls to adding children to a collection (Line# 9) didn’t work.
private void Insert(TrieNode current, string word) | |
{ | |
foreach (char c in word) | |
{ | |
current.Children.TryGetValue(c, out TrieNode node); | |
if (node == null) | |
{ | |
node = new TrieNode(); | |
current.Children.Add(c, node); | |
} | |
current = node; | |
} | |
current.IsCompleteWord = true; | |
} |
After 30 minutes of debugging, I was like…
Just what the h**l happened?
TL;DR
Auto Property initialization creates a backing field while Expression Bodied property one does not
▬ Introduction ▬
According to Wikpedia, you can declare a trie like this (in Haskell).
import Data.Map | |
data Trie a = Trie { value :: Maybe a, | |
children :: Map Char (Trie a) } |
So I created a TrieNode
class as shown below.
public class TrieNode | |
{ | |
public bool IsCompleteWord { get; set; } = false; | |
public Dictionary<char, TrieNode> Children => new Dictionary<char, TrieNode>(); | |
} |
*If you are an astute reader, you might have already spotted the problem. Congratulations!*
▬ Problem ▬
The complete source for building a trie, TrieBuilder
is declared as below.
public class TrieBuilder | |
{ | |
public TrieNode BuildTrie(IEnumerable<string> words) | |
{ | |
TrieNode root = new TrieNode(); | |
foreach (var word in words) | |
{ | |
Insert(root, word); | |
} | |
return root; | |
} | |
private void Insert(TrieNode current, string word) | |
{ | |
foreach (char c in word) | |
{ | |
current.Children.TryGetValue(c, out TrieNode node); | |
if (node == null) | |
{ | |
node = new TrieNode(); | |
current.Children.Add(c, node); | |
} | |
current = node; | |
} | |
current.IsCompleteWord = true; | |
} | |
} |
Given a list of words passed to BuildTrie
method, it populates a trie and returns an object instance.
Insert
method simply checks for an existence of a character and maps current character to a node to the trie object instance , current
.
This is where the problem occurred. current.Children.Add(...)
wasn’t adding node
object instance.
▬ Investigation ▬
Later on, I found out a StackOverflow answer explanating that declaring a property with =>
syntax (introduced in C# 6) does NOT create a backing field.
So my declaration below,
public Dictionary<char, TrieNode> Children => new Dictionary<char, TrieNode>(); |
is equivalent to
public Dictionary<char, TrieNode> Children | |
{ | |
get { return new Dictionary<char, TrieNode>(); } | |
} |
returning a new array whenever Children
property was accessed, thus not adding a new node to it.
▬ Solution ▬
The fix is simple. Declare Children with a backing field or use an auto property initialization syntax.
public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>(); |
Above declaration is equivalent to
private readonly Dictionary<char, TrieNode> _children = new Dictionary<char, TrieNode>(); | |
public Dictionary<char, TrieNode> Children | |
{ | |
get { return _children; } | |
} |
That was all it took to make me a happy camper ?.
▬ Takeaway ▬
Auto Property initialization creates a backing field while Expression Bodied property one does not.
The post Expression Bodied Collection Property Initialization Gotcha in C# appeared first on Slight Edge Coder.
Top comments (0)