Best algorithm to determine added and removed items when comparing to collections

Question

I am looking for the best algorithm to compare 2 collections and determine which element got added and which element got removed.

private string GetInvolvementLogging(ICollection<UserInvolvement> newInvolvement, ICollection<UserInvolvement> oldInvolvement)
{
    //I defined the new and old dictionary's for you to know what useful data is inside UserInvolvement. 
    //Both are Dictionary<int, int>, because The Involvement is just a enum flag. Integer. UserId is also Integer.
    var newDict = newInvolvement.ToDictionary(x => x.UserID, x => x.Involvement);
    var oldDict = oldInvolvement.ToDictionary(x => x.UserID, x => x.Involvement);

    //I Want to compare new to old -> and get 2 dictionaries: added and removed.
    var usersAdded = new Dictionary<int, Involvement>();
    var usersRemoved = new Dictionary<int, Involvement>();

    //What is the best algoritm to accomplish this?

    return GetInvolvementLogging(usersAdded, usersRemoved);
}

private string GetInvolvementLogging(Dictionary<int, Involvement> usersAdded, Dictionary<int, Involvement> usersRemoved)
{
    //TODO: generate a string based on those dictionaries. 
    return "Change in userinvolvement: ";
}

Answer 1

Finally this is my implementation of GetInvolvementLogging:

(the implementation of the string builder method is irrelevant for my question here)

private string GetInvolvementLogging(ICollection<UserInvolvement> newInvolvement, ICollection<UserInvolvement> oldInvolvement)
{
    //I defined the new and old dictionary's to focus on the relevant data inside UserInvolvement. 
    var newDict = newInvolvement.ToDictionary(x => x.UserID, x => (Involvement)x.Involvement);
    var oldDict = oldInvolvement.ToDictionary(x => x.UserID, x => (Involvement)x.Involvement);

    var intersection = newDict.Keys.Intersect(oldDict.Keys); //These are the id's of the users that were and remain involved. 
    var usersAdded = newDict.Keys.Except(intersection);
    var usersRemoved = oldDict.Keys.Except(intersection);

    var addedInvolvement = newDict.Where(x => usersAdded.Contains(x.Key)).ToDictionary(x => x.Key, x => x.Value); 
    var removedInvolvement = oldDict.Where(x => usersRemoved.Contains(x.Key)).ToDictionary(x => x.Key, x => x.Value);

    //Check if the already involved users have a changed involvement.
    foreach(var userId in intersection)
    {
        var newInvolvementFlags = newDict[userId];
        var oldInvolvementFlags = oldDict[userId];

        if ((int)newInvolvementFlags != (int)oldInvolvementFlags)
        {
            var xor = newInvolvementFlags ^ oldInvolvementFlags;
            var added = newInvolvementFlags & xor;
            var removed = oldInvolvementFlags & xor;

            if (added != 0)
            {
                addedInvolvement.Add(userId, added);
            }
            if (removed != 0)
            {
                removedInvolvement.Add(userId, removed);
            }
        }
    }

    return GetInvolvementLogging(addedInvolvement, removedInvolvement);
}

Answer 2

Added elements are only in newDict removed only in oldDict

var intersection = newDict.Keys.Intersect(oldDict.Keys);

var added = newDict.Keys.Except(intersection);
var removed = oldDict.Keys.Except(intersection);

EDIT

I modify your base function, dictionaries is no neded.

Example UserInvolvement implementation

class UserInvolvement
{
    public int UserId;
    public string Name;
    public string OtherInfo;

    public override bool Equals(object obj)
    {
        if (obj == null)
        {
            return false;
        }

        UserInvolvement p = obj as UserInvolvement;
        if ((System.Object)p == null)
        {
            return false;
        }

        return (UserId == p.UserId) && (Name == p.Name) && (OtherInfo == p.OtherInfo);
    }

    public override string ToString()
    {
        return $"{UserId} - {Name} - {OtherInfo}";
    }
}

And example function:

private static string GetInvolvementLogging(ICollection<UserInvolvement> newInvolvement,
            ICollection<UserInvolvement> oldInvolvement)
{
    var intersection = newInvolvement.Select(x => x.UserId).Intersect(oldInvolvement.Select(x => x.UserId));
    var addedIds = newInvolvement.Select(x => x.UserId).Except(intersection);
    var removedIds = oldInvolvement.Select(x => x.UserId).Except(intersection);

    List<UserInvolvement> modifiedUI = new List<UserInvolvement>();

    foreach (var i in intersection)
    {
        var ni = newInvolvement.First(a => a.UserId == i);
        var oi = oldInvolvement.First(a => a.UserId == i);

        if (!ni.Equals(oi))
        {
            modifiedUI.Add(ni);                 
        }
    }

    List<UserInvolvement> addedUI = newInvolvement.Where(x => addedIds.Contains(x.UserId)).Select(w => w).ToList();
    List<UserInvolvement> removedUI = oldInvolvement.Where(x => removedIds.Contains(x.UserId)).Select(w => w).ToList();

    StringBuilder sb = new StringBuilder();

    sb.AppendLine("Added");
    foreach (var added in addedUI)
    {
        sb.AppendLine(added.ToString());                
    }
    sb.AppendLine("Removed");
    foreach (var removed in removedUI)
    {
        sb.AppendLine(removed.ToString());
    }
    sb.AppendLine("Modified");
    foreach (var modified in modifiedUI)
    {
        sb.AppendLine(modified.ToString());
    }

    return sb.ToString();
}

And my test function:

static void Main(string[] args)
{
    List<UserInvolvement> newUI = new List<UserInvolvement>()
    {
        new UserInvolvement()
        {
            UserId = 1,
            Name = "AAA",
            OtherInfo = "QQQ"
        },
        new UserInvolvement()
        {
            UserId = 2,
            Name = "BBB",
            OtherInfo = "123"
        },
        new UserInvolvement()
        {
            UserId = 4,
            Name = "DDD",
            OtherInfo = "123ert"
        }


    };

    List<UserInvolvement> oldUI = new List<UserInvolvement>()
    {
        new UserInvolvement()
        {
            UserId = 2,
            Name = "BBBC",
            OtherInfo = "123"
        },
        new UserInvolvement()
        {
            UserId = 3,
            Name = "CCC",
            OtherInfo = "QQ44"
        },
        new UserInvolvement()
        {
            UserId = 4,
            Name = "DDD",
            OtherInfo = "123ert"
        }

    };

    string resp = GetInvolvementLogging(newUI, oldUI);
    WriteLine(resp);

    ReadKey();

    WriteLine("CU");
}

Result is:

Added
1 - AAA - QQQ
Removed
3 - CCC - QQ44
Modified
2 - BBB - 123

Answer 3

Think best algorithm will be

foreach (var newItem in newDict)    
    if (!oldDict.ContainsKey(newItem.Key) || oldDict[newItem.Key]!=newItem.Value) 
        usersAdded.Add(newItem.Key, newItem.Value);

foreach (var oldItem in oldDict)
    if (!newDict.ContainsKey(oldItem.Key) || newDict[oldItem.Key]!=oldItem.Value) 
        usersRemoved.Add(oldItem.Key, oldItem.Value);

Answer 4

You could try with Linq:

var usersAdded = newDict.Except(oldDict);
var usersRemoved = oldDict.Except(newDict);

If you need dictionaries as a result you can cast:

var usersAdded = newDict.Except(oldDict).ToDictionary(x => x.Key, x => x.Value);
var usersRemoved = oldDict.Except(newDict).ToDictionary(x => x.Key, x => x.Value);