Search code examples
c#algorithmlistsortingpseudocode

Algorithm to "synchronize" (side effect) a list with another? (Without using swaps)


I'm trying to write a method to synchronize a list with another under some constraints, and so far I haven't managed to think of a proper algorithm to do that.

Here are all the details:

  • After the method call, the target list will have the exact same elements of the source list, in the same order
  • Some elements in the target list could be removed, others could be added, others could have a different position
  • I can't sort the target list nor can I use swap operations (as the UI is shown to the user and I don't want the UI to flicker)

Edit: to add some details, the list is an ObservableCollection object, and I don't want to just assign the second list to the first one as that'd make the whole ListView control (UWP app) refresh the content. Instead, I want the "right" items to remain where they are, and I'd like the other items to nicely being added/removed at the right positions. Also, the items in the wrong positions should just "slide" in the right position where possible, for example if I'm removing an item that was before an item that was one position ahead of its right final position.

As a result, I can only do the following operations on the target list:

  • Insert an item at a given index
  • Remove an item from a given index

I need the algorithm to perform as few operations as possible on the target list.

Example:

target = { "tree", "house", "beach" }
source = { "tree", "beach", "house", "peach" }

In this case I'd remove the "house" item from the first list, so that "beach" would slide in the right position, then add "house" again (in the right position) and finally "peach" at the end of the list.

Here's the general prototype I thought about:

/// <summary>
/// Synchronizes a list with the items in the second list
/// </summary>
/// <typeparam name="T">The type of the items in the lists</typeparam>
/// <param name="target">The target list to edit</param>
/// <param name="source">The source list (ordered)</param>
/// <param name="comparer">A comparer function to check if two items are the same, and if a list contains a given item (by using the Any LINQ)</param>
/// <param name="indexer">An action used to assign the right final index to an element in the target list</param>
public static void Synchronize<T>([NotNull] IList<T> target, [NotNull] IReadOnlyList<T> source, 
    [NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
    // Edge case
    if (target.Count == 0)
    {
        foreach (T item in source)
            target.Add(item);
        return;
    }

    if (target.Count < source.Count)
    {
        /* At least a new item has been added, but there's
         * no guarantee it'll be at the end of the source list */
    }
    else if (target.Count > source.Count)
    {
        /* One or more items have been removed from the target list,
         * but at the same time the source list could have one or more new items
         * that weren't present in the target list before */
    }
    else
    {
        /* The two lists have the same length, but I can make no assumptions
         * on their content. Every item could be different, or they could have the same
         * items but in different positions, or some items right, some in the wrong 
         * positions and some new items as well */
    }
}

Note: each list will not have more than 20 items, so I don't care about the algorithm cost, it could be O(n^2) and it'd still be absolutely fine.

Note #2: the indexer function is needed as at the end of the synchronization, each item in the target list will have to know its position inside the list, so I can use that action on all the items that ended up in a different position (and on all the new items) to let them know their final position.

I need a help with the pseudocode, I didn't just started writing the code as I wanted to come up with a decent algorithm for the problem first, I've been thinking about it for a while but I'm not sure I know the right approach to solve this.

Thanks for your help!


Solution: here's the final implementation I wrote (tested, it works great)

/// <summary>
/// Synchronizes a list with the items in the second list
/// </summary>
/// <typeparam name="T">The type of the items in the lists</typeparam>
/// <param name="target">The target list to edit</param>
/// <param name="source">The source list (ordered)</param>
/// <param name="comparer">A comparer function to check if two items are the same, and if a list contains a given item (by using the Any LINQ)</param>
/// <param name="indexer">An action used to assign the right final index to an element in the target list</param>
public static void Synchronize<T>([NotNull] this IList<T> target, [NotNull] IReadOnlyList<T> source, 
    [NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
    // Edge case
    if (target.Count == 0)
    {
        foreach (T item in source)
            target.Add(item);
        return;
    }

    // Step 1
    for (int i = 0; i < target.Count; i++)
    {
        // Remove all the items in target that are not in source
        if (!source.Any(item => comparer(item, target[i])))
        {
            target.RemoveAt(i--);
        }
    }

    // Step 2
    List<T> copy = source.Where(item => target.Any(test => comparer(test, item))).ToList();
    List<(T, int, int)> lookup = new List<(T, int, int)>();
    for (int i = 0; i < target.Count; i++)
    {
        // Check if the item is out of place
        T current = target[i];
        if (!comparer(current, copy[i]))
        {
            // Store the item and its target index in the lookup table
            int index = copy.IndexOf(item => comparer(item, current));
            lookup.Add((current, i, index));
        }
    }

    // Adjust the items in the wrong positions
    lookup.Sort(tuple => -(tuple.Item3 - tuple.Item2).Abs());
    while (lookup.Count > 0)
    {
        // Move the items in the right position
        (T item, int current, int desired) = lookup.First();
        lookup.RemoveAt(0);

        // Adjust the current index if the element has shifted
        if (!comparer(target[current], item))
        {
            current = target.IndexOf(pick => comparer(pick, item));
        }

        // Skip if the element has already been shifted into its right place
        if (current == desired) continue;

        // Adjust the current item
        target.RemoveAt(current);
        target.Insert(desired, item);
    }

    // Step 3
    for (int i = 0; i < source.Count; i++)
    {
        // Insert the missing elements
        if (!target.Any(item => comparer(item, source[i])))
        {
            target.Insert(i, source[i]);
        }
    }

    // Adjust the indexes
    for (int i = 0; i < target.Count; i++)
    {
        indexer(target[i], i);
    }
}

Solution

  • Step 1: Iterate over the target list, and remove any element that is not in the source list.

    Step 2: Iterate over the target list again, noting how far each element is from its correct place (not counting missing elements). Remove the most out-of-place element, and insert it in its correct place. Repeat until the elements are in the correct order.

    Step 3: Iterate over both lists, inserting the elements that are missing.

    I think that's minimal.