C # Nested dictionary of various depths

Question

Essentially, I need to map the various int variables in the dictionary. Or at least the way I thought about it. The easiest way I can do this is to explain what I want is to use switch statements.

string s = ""; int a = 1; int b = 2; int c = 0; switch (a){ case 0: s = "a0"; break; case 1: switch (b){ case 0: s = "b0"; break case 1: switch (c){ case 0: s = "c0"; break; case 1: s = "c1"; break; } break case 2: s = "b2"; break; } break; case 2: s = "a2"; break; } 

This is a simplified version for brevity, where you could potentially have many sockets and in more than one case and much more. I thought that a good solution for this would be a dictionary for quickly choosing the right value, but it doesn’t fit very well, because most of the internal sockets of a nested dictionary do not need values.

The reason I thought about dictionaries in the first place was because the syntax of the declaration like the following would be nice (which is similar to what would be for a dictionary of dictionaries).

 thing = { {0, "a0"}, {1, { {0, "b0"}, {1, { {0, "c0"}, {1, "c1"} } }, {2, "b2"} } }, {2, "a2"} } // Next line is sort of hopeful but potentially unrealistic syntax s = thing[a][b][c]; // or = thing(a,b,c); 

EDIT: This is not a required declaration syntax, but its brevity and ease of understanding are what I am looking for.

EDIT: or LINQ, I have seen many LINQ suggestions for similar questions, but I am not very familiar with it.

Answer 1

Given that you are looking for a partial key match, you will not be able to accomplish this with a single dictionary. That's why:

Suppose you have a class of "rules". We will call it the "Key". You can create it this way:

 Key.Create(0) // this "rule" would match any query key starting with 0 (eg, {0}, {0, 1}, or {0, 1, 9, 2, 23, 243}) 

Now suppose you want to query it using some kind of "fact" or "query key" class. Since you are querying the dictionary using the value type that was used as the key during the add operation, you will have to reuse the same type:

 Key.Create(0, 2, 13) // this fact should be matched by rules {0}, {0,2} or {0, 2, 13} 

Now you will try to get the value:

 var value = map[Key.Create(0, 2, 13)] 

The Key class can override Equals to provide partial matching. However, the dictionary will first use the hash code, and the hash code for Key.Create (0, 2, 13) will never match the key identifier Key.Create (0). You cannot get around this using any type of base / derived type.

The best option is probably to descend your own class. Something like this should do:

 class ResultMap { public void Add(int[] key, string value) { Debug.Assert(key != null); Debug.Assert(key.Length > 0); var currentMap = _root; foreach (var i in key.Take(key.Length - 1)) { object levelValue; if (currentMap.TryGetValue(i, out levelValue)) { currentMap = levelValue as Dictionary<int, object>; if (currentMap == null) throw new Exception("A rule is already defined for this key."); } else { var newMap = new Dictionary<int, object>(); currentMap.Add(i, newMap); currentMap = newMap; } } var leaf = key[key.Length - 1]; if (currentMap.ContainsKey(leaf)) throw new Exception("A rule is already defined for this key."); currentMap.Add(leaf, value); } public string TryGetValue(params int[] key) { Debug.Assert(key != null); Debug.Assert(key.Length > 0); var currentMap = _root; foreach (var i in key) { object levelValue; if (!currentMap.TryGetValue(i, out levelValue)) return null; currentMap = levelValue as Dictionary<int, object>; if (currentMap == null) return (string) levelValue; } return null; } private readonly Dictionary<int, object> _root = new Dictionary<int, object>(); } 

Here's the unit test:

  public void Test() { var resultMap = new ResultMap(); resultMap.Add(new[] {0}, "a0"); resultMap.Add(new[] {1, 0}, "b0"); resultMap.Add(new[] {1, 1, 0}, "c0"); resultMap.Add(new[] {1, 1, 1}, "c1"); resultMap.Add(new[] {1, 2}, "b2"); resultMap.Add(new[] {2}, "a2"); Debug.Assert("a0" == resultMap.TryGetValue(0)); Debug.Assert("a0" == resultMap.TryGetValue(0, 0)); Debug.Assert("a0" == resultMap.TryGetValue(0, 1)); Debug.Assert("a0" == resultMap.TryGetValue(0, 2)); Debug.Assert("a0" == resultMap.TryGetValue(0, 0, 0)); Debug.Assert("a0" == resultMap.TryGetValue(0, 0, 1)); Debug.Assert("a0" == resultMap.TryGetValue(0, 0, 2)); Debug.Assert("a0" == resultMap.TryGetValue(0, 1, 0)); Debug.Assert("a0" == resultMap.TryGetValue(0, 1, 1)); Debug.Assert("a0" == resultMap.TryGetValue(0, 1, 2)); Debug.Assert("a0" == resultMap.TryGetValue(0, 2, 0)); Debug.Assert("a0" == resultMap.TryGetValue(0, 2, 1)); Debug.Assert("a0" == resultMap.TryGetValue(0, 2, 2)); Debug.Assert(null == resultMap.TryGetValue(1)); Debug.Assert("b0" == resultMap.TryGetValue(1, 0)); Debug.Assert(null == resultMap.TryGetValue(1, 1)); Debug.Assert("b2" == resultMap.TryGetValue(1, 2)); Debug.Assert("b0" == resultMap.TryGetValue(1, 0, 0)); Debug.Assert("b0" == resultMap.TryGetValue(1, 0, 1)); Debug.Assert("b0" == resultMap.TryGetValue(1, 0, 2)); Debug.Assert("c0" == resultMap.TryGetValue(1, 1, 0)); Debug.Assert("c1" == resultMap.TryGetValue(1, 1, 1)); Debug.Assert(null == resultMap.TryGetValue(1, 1, 2)); Debug.Assert("b2" == resultMap.TryGetValue(1, 2, 0)); Debug.Assert("b2" == resultMap.TryGetValue(1, 2, 1)); Debug.Assert("b2" == resultMap.TryGetValue(1, 2, 2)); Debug.Assert("a2" == resultMap.TryGetValue(2)); Debug.Assert("a2" == resultMap.TryGetValue(2, 0)); Debug.Assert("a2" == resultMap.TryGetValue(2, 1)); Debug.Assert("a2" == resultMap.TryGetValue(2, 2)); Debug.Assert("a2" == resultMap.TryGetValue(2, 0, 0)); Debug.Assert("a2" == resultMap.TryGetValue(2, 0, 1)); Debug.Assert("a2" == resultMap.TryGetValue(2, 0, 2)); Debug.Assert("a2" == resultMap.TryGetValue(2, 1, 0)); Debug.Assert("a2" == resultMap.TryGetValue(2, 1, 1)); Debug.Assert("a2" == resultMap.TryGetValue(2, 1, 2)); Debug.Assert("a2" == resultMap.TryGetValue(2, 2, 0)); Debug.Assert("a2" == resultMap.TryGetValue(2, 2, 1)); Debug.Assert("a2" == resultMap.TryGetValue(2, 2, 2)); } 

Answer 2

Thus, the problem is not as simple as it might seem at first glance. The big thing that I see when I look at it is a complex template, so we will start with an interface that can reveal the functions we need:

 public interface INode<TParam, TResult> { TResult GetValue(TParam[] parameters, int depth); } 

I did this generic rather than hard coding in the int and string return value to make it more reusable in terms of general purpose MultiKeyLookup .

Then we have a simple case, Leaf nodes that simply return a specific value regardless of the parameters:

 class Leaf<TParam, TResult> : INode<TParam, TResult> { private TResult value; public Leaf(TResult value) { this.value = value; } public TResult GetValue(TParam[] parameters, int depth) { return value; } } 

Then we have a less trivial case. Own class Node . It takes several values, and then maps each of these values ​​to an INode . Where magic happens. INode that it maps can be either a leaf of a node with a specific value, or it can be another node. Then, when asked to get the value, it simply displays the input parameter at the appropriate depth, and in the recursive estate, it gets the INode value for this value:

 class Node<TParam, TResult> : INode<TParam, TResult> { //private Tuple<TParam, INode<TParam, TResult>>[] values; private Dictionary<TParam, INode<TParam, TResult>> lookup; public Node(params Tuple<TParam, INode<TParam, TResult>>[] values) { lookup = values.ToDictionary(pair => pair.Item1, pair => pair.Item2); } public TResult GetValue(TParam[] parameters, int depth) { return lookup[parameters[depth]].GetValue(parameters, depth + 1); } } 

So at this moment we can do. Here is an example of a (slightly simplified) example:

 var node = new Node<int, string>( Tuple.Create(0, (INode<int, string>)new Leaf<int, string>("a0")), Tuple.Create(1, (INode<int, string>)new Node<int, string>( Tuple.Create(0, (INode<int, string>)new Leaf<int, string>("b0"))))); Console.WriteLine(node.GetValue(new int[] { 0 }, 0)); //prints a0 

Now that is a bit of a mess. In particular, she has a ton of general argument specifications that we know will always be the same, as well as the need to cast each type of INode to an interface type so that Tuple correctly printed.

To make this simpler, I created a builder class, MultiKeyLookup . It will have several helper methods for creating the leaf and node, so that general arguments can be specified once for this class. In addition, since these Leaf and Node not needed thanks to these collectors, I made both of these classes private MultiKeyLookup inner classes, in addition to the content of these two classes, which it also has:

 public class MultiKeyLookup<TParam, TResult> { public INode<TParam, TResult> CreateLeaf(TResult result) { return new Leaf<TParam, TResult>(result); } public INode<TParam, TResult> CreateNode( params Tuple<TParam, INode<TParam, TResult>>[] values) { return new Node<TParam, TResult>(values); } public INode<TParam, TResult> Root { get; set; } public TResult GetValue(TParam[] parameters) { return Root.GetValue(parameters, 0); } //definition of Leaf goes here //definition of Node goes here } 

Using this class, we can now write:

 var map = new MultiKeyLookup<int, string>(); map.Root = map.CreateNode( Tuple.Create(0, map.CreateLeaf("a0")), Tuple.Create(1, map.CreateNode( Tuple.Create(0, map.CreateLeaf("b0")), Tuple.Create(1, map.CreateNode( Tuple.Create(0, map.CreateLeaf("c0")), Tuple.Create(1, map.CreateLeaf("c1")))), Tuple.Create(2, map.CreateLeaf("b2")))), Tuple.Create(2, map.CreateLeaf("a2"))); Console.WriteLine(map.GetValue(new int[] { 0 })); //prints a0 Console.WriteLine(map.GetValue(new int[] { 0, 0, 4 })); //prints a0 Console.WriteLine(map.GetValue(new int[] { 1, 0 })); // prints b0 Console.WriteLine(map.GetValue(new int[] { 1, 1, 0 })); //prints c0 

Note that this is a complete creation of what you defined in the OP, not a simplified example.

Answer 3

Perhaps it uses classes something like this:

 public class A { public string result; public A(int case) { if(case == 0) { this.result = "a0"; } else if(case == 2) { this.result = "a2"; } else { return new B(case).result; } } } public class B { public string result; public B(int case) { if(case == 0) { this.result = "b0"; } else if(case == 2) { this.result = "b2" } else { return new C(case).result; } } } public class C { public string result; public C(int case) { if(case == 0) { this.result = "C0"; } else { this.result = "c1"; } } } 

Answer 4

I know that you have already chosen the answer, but I came up with a new idea, and I think it's cool. Using nested dictionaries for int keys and object values ​​as follows:

  Dictionary<int, object> baseDictionary = new Dictionary<int, object>(); baseDictionary.Add(0, new object[] { "a1" }); baseDictionary.Add(1, new Dictionary<int, object>()); baseDictionary.Add(2, new object[] { "a2" }); Dictionary<int, object> childDictionary = baseDictionary[1] as Dictionary<int, object>; childDictionary.Add(0, new object[] { "b1" }); childDictionary.Add(1, new Dictionary<int, object>()); childDictionary.Add(2, new object[] { "b2" }); Dictionary<int, object> childTwoDictionary = childDictionary[1] as Dictionary<int, object>; childTwoDictionary.Add(0, new object[] { "c1" }); childTwoDictionary.Add(1, new object[] { "c2" }); 

Then access the record you want to use with the recursion method with this array of keys:

 private object GetResult(int keyIndex, int[] keys, Dictionary<int, object> inputDictionary) { Dictionary<int, object> nextDictionary = inputDictionary[keys[keyIndex]] as Dictionary<int, object>; object result; if (nextDictionary != null && keyIndex < keys.Length) { keyIndex++; return GetResult(keyIndex, keys, nextDictionary); } else if(!string.IsNullOrEmpty(inputDictionary[keys[keyIndex]].ToString())) { result = inputDictionary[keys[keyIndex]] as object; keyIndex++; return result; } return new object[] { "Failed" }; } 

and call it the following:

 private void simpleButton1_Click(object sender, EventArgs e) { int keyIndex = 0; int[] keys = { 1, 1, 1 }; object result = this.GetResult(keyIndex, keys, this.baseDictionary); labelControl1.Text = (((object[])(result))[0]).ToString(); } 

Answer 5

If you can know your “key structure” in advance, it may be cheaper for you to use Dictionary<string, string> and create a key that is a concatenation of three parts: "ABC" ... Avoids a nest and offers a direct search.

If you know that a = 1, b = 2 and c = 3, for example, you can associate them with the string "123" and the key to search for the dictionary. This essentially works with HttpContext and .NET 4.0 MemoryCache caching.

EDIT:

If you do not always have all 3 values, use string.Format with a key structure that provides a separator / separator between the values. In any case, this is best practice, otherwise you may easily run into key collisions:

 private const string _keyFormat = "{0}_{1}_{2}"; private string GenerateKey(object a, object b, object c) { return string.Format(_keyFormat, a, b, c); }