c# - Compare two Dictionary for know each "add" operations and each "remove" operations

I have 2 dictionnary with similaire struture

Dictionary<string, List<int>> Origins

and

Dictionary<string, List<int>> Changes

I have create Origins in the beginning. It is a copy of the begining state. Example :

Origins["toto"] = new List<int>(){1,2,3};
Origins["tata"] = new List<int>();
Origins["titi"] = new List<int>(){1,2};

After an user action, I keep the changes in the Changes dictionnary. Basicly t开发者_StackOverflowhe user can add or remove some number linked to the string. So i keep all the trace of any change like this:

example: if the user add a 1 in "tata" in the dictionary Changes a have "tata" have 1

if the user add a 4 in "toto" in the dictionary Changes a have "toto" have 1,2,3,4

if the user remove 1 in "titi" in the dictionary Changes a have "titi" have 2

I need the Changes dictionnary for know when the user return to original state, with a simple comparaison.

If no change is done for a string, the Changes dictionnary do not have any entry for this string.

After many changes, the user can Save the changes. So now i need to find all the add and remove operations.

My first idea is to compare the two dictionnary , to see the operation add and the operation remove. But how ? If I compare the lists for the same string, i may know the difference,but i'm stuck here. And maybe there are a better way to do this ? Any suggestion ?

You have the following cases:

1. A new string key is added to Changes, along with some associated values.
2. The values for an existing string key are changed (values added or removed).

In case (1) you'll have an entry in Changes that does not exist in Origins. In case (2) you'll have an entry in both but with a different list of values.

(The values I'm going to assume are a mathematical set, i.e. that a particular value can appear in there only once and that the ordering insignificant. If that's not the case then you will have to modify the approach somewhat.)

To detect case (1), you can find the keys that are unique:

IEnumerable<string> newKeys = Changes.Keys.Except(Origins.Keys);

Obviously every value in Changes for a new key will need to be 'added'. You can simply iterate the newKeys enumerable and retrieve the values from Changes:

foreach (string key in newKeys)
{
    IEnumerable<int> addedValues = Changes[key];
    // your processing here
}

To detect case (2), you will need to iterate the dictionary and compare the set of values in Changes with Origins. To do that we'll iterate Origins to get the key and original values and then retrieve the item using the key from Changes. (We will do it this way around as, if we iterated Changes instead we would potentially end up with new, added keys that do not exist in Origins and that is another case we would have to deal with.)

foreach (KeyValuePair<string, List<int>> entry in Origins)
{
    List<int> originsValues = entry.Value;
    List<int> changesValues;

    // handle no key in Changes (as pointed out by Guillaume V). 
    if (!Changes.TryGet(entry.Key, out changesValues)) changesValues = originsValues;

    IEnumerable<int> removedValues = originsValues.Except(changesValues);
    IEnumerable<int> addedValues = changesValues.Except(originsValues);

    // your processing here
}

You could try this:

        Dictionary<string, List<int>> Origin = new Dictionary<string, List<int>>();

        Origin["toto"] = new List<int>(){1,2,3};
        Origin["tata"] = new List<int>();
        Origin["titi"] = new List<int>(){1,2};


        Dictionary<string, List<int>> Changes = new Dictionary<string,List<int>>();

        Changes["toto"] = new List<int>() { 1, 2, 3, 4 };
        Changes["tata"] = new List<int>(){1};
        Changes["titi"] = new List<int>() { 2 };

        Dictionary<string, List<int>> ToRemove = new Dictionary<string, List<int>>();
        Dictionary<string, List<int>> ToAdd = new Dictionary<string, List<int>>();

        foreach (string key in Origin.Keys)
        {
            ToRemove[key] = Origin[key];
            ToAdd[key] = Changes[key];


            foreach (int i in ToRemove[key])
            {

                if (ToAdd[key].Contains(i)) //There is no change
                {
                    ToAdd[key].Remove(i);
                    ToRemove[key].Remove(i);
                }
            }
        }

If all you need to do is determine if two objects are equal, I'd suggest creating your own class, and overriding Equals() and GetHashInfo():

public class ComparableDictionary : Dictionary<string, List<int>>
{
    private const int CouldBeAnyConstant = 392;

    public override bool Equals(object other)
    {
        return Equals((ComparableDictionary)other);
    }

    public bool Equals(ComparableDictionary other)
    {
        return other != null && (GetHashCode() == other.GetHashCode());
    }

    public override int GetHashCode()
    {
        int result = CouldBeAnyConstant;
        unchecked
        {
            foreach (var list in Values)
                foreach (var value in list)
                    result = result*value.GetHashCode();

            foreach (var value in Keys)
                result = result * value.GetHashCode();
        }

        return result;
    }

}

Then all you have to do to use it is:

public bool UserHasMadeChanges(ComparableDictionary Origins, ComparableDictionary Changes)
{
    return !Origins.Equals(Changes)
}

inspired by Paul Ruane and matmot i develop my own way :

foreach (var change in this.Changes)
        {
            List<int> origin = this.Origins[change.Key];

            List<int> newValue = change.Value;

            //find the basic add and remove
            IEnumerable<int> remove = origin.Except(newValue);
            IEnumerable<int> add = newValue.Except(origin);

            if (!add.Any() && remove.Any())
            {
              //remove all in the remove list 
                continue;

            }
            else if (add.Any() && !remove.Any())
            {
              //add all in the add list
                continue;
            }

            //if in the same change there are add and remove 
            IEnumerable<int> dif1 = add.Except(remove);
            IEnumerable<int> dif2 = remove.Except(add);

            if (dif1.Any())
            {
                //add all in the dif1 list 

            }
            if (dif2.Any())
            {
                //remove all in  dif2 list


            }
        }

What do you think about this ?