Complicated Intersection With Maps

Question

I have two maps of the same K, V types such that

Key is the Country

Value is a Map of

so the overall Map structure is

 Map <String, Map<String, List<City>>> m1, m2;

Now I want to find out what entries of the map are same and which ones are different

For example:

m1 =    { India = [TA -> {City1, City2, City3}   KA -> {City1, City2}]
          USA =   [WI -> {City1, City2, City3},  OH -> {City1, City2}] }

m2 =    { India = [TA -> {City1, City2, City3} ]
          USA =   [WI -> {City1, City3},         DC -> {City1}] }

The output should be

Common = { India = [TA -> {City1, City2, City3} ]
           USA = [WI -> {City1, City3}] }

Is there a better way to get this information than to loop through the entire list and check line by line (even if there is an already defined method that does this, it would be great)?

I will use this so that I know that over the past few years the only thing that has changed is the few cities and few states.

Would be glad to clarify further if required.

Thanks in advance.

Answer 1

A lot depends on the type of collection you are going to use to store your data. The other factor is a technology you are going to use. Then it also depends on how efficient versus how readable is your code. My favorite language is C# so I would go for it. Then implement the whole thing - similarly to your suggestion - as Dictionary<string, Dictionary<string, List<City>>>.

To get the data I used LINQ as it gives you quite readable code.

I implemented your example as below (for the sake of simplicity the cities are simple strings):

var m1 = new Dictionary<string,Dictionary<string,List<string>>>
{
    {
        "India", new Dictionary<string, List<string>> 
                    {
                        {"TA", new List<string> {"City1", "City2", "City3"}},
                        {"KA", new List<string> {"City1", "City2"}}
                    }
    },
    {
        "USA", new Dictionary<string, List<string>> 
                    {
                        {"WI", new List<string> {"City1", "City2", "City3"}},
                        {"OH", new List<string> {"City1", "City2"}}
                    }
    }
};

var m2 = new Dictionary<string,Dictionary<string,List<string>>>
{
    {
        "India", new Dictionary<string, List<string>> 
                    {
                        {"TA", new List<string> {"City1", "City2", "City3"}},
                    }
    },
    {
        "USA", new Dictionary<string, List<string>> 
                    {
                        {"WI", new List<string> {"City1", "City3"}},
                        {"DC", new List<string> {"City1"}}
                    }
    }
};

And the operation to get your result is the Intersect method applied on each level of the nested collection:

var result = m1.Keys.Intersect(m2.Keys)
                    .ToDictionary(k => k, k => m1[k].Keys.Intersect(m2[k].Keys)
                        .ToDictionary(l => l, l => m1[k][l].Intersect(m2[k][l])));

If you debug that and expand result you will see it returns the values you expected in your example.

Note, that your City class has to implement the IEquatable<T> interface so it can be correctly processed in the Intersect method. Sample implementation on MSDN