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:
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:
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);
}
}
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.