Tim Schmelter Tim Schmelter - 1 month ago 7
C# Question

How to modify list-indexes according to a list which contains only the changed indexes?

Update: Here is the complete code https://dotnetfiddle.net/eAeWp5

This one is much more difficult than i thought.
In the real project i need to update a database table which has a column

Position
(for the sort-order), but all the method gets is a list that contains only the changed objects with the new positions. The table and class is
WatchList
.

Here it is:

public class WatchList : IEquatable<WatchList>
{
public WatchList(int id)
{
Id = id;
}

public int Id { get; }

public string Name { get; set; }

public int UserId { get; set; }

public int Position { get; set; }

public bool Equals(WatchList other)
{
if (other == null) return false;
if (ReferenceEquals(this, other)) return true;
return this.Id == other.Id;
}

public override bool Equals(object obj)
{
WatchList other = obj as WatchList;
return this.Equals(other);
}

public override int GetHashCode()
{
return this.Id;
}

public override string ToString()
{
return $"WatchListId:{Id} Name:{Name} UserId:{UserId} Position:{Position}";
}
}


So the
WatchListId
is the primary key and the
Position
the column that i want to update.

Consider that this table contains following WatchLists:

WatchListId Position
1 1
2 2
3 3
4 4
5 5


The user wants to modify the order, drags and drops them and finally submits it to the server. The client will call
UpdateWatchListsSort
with a list that contains only the WatchLists that were moved by the user.

Consider the user moved

1 ---> 5
3 ---> 1
5 ---> 4


So the new (correct) order in the database was:

WatchListId Position
3 1
2 2
4 3
5 4
1 5


You notice that even some other WatchLists must be updated because the positions need to move up by 1 if their positions are affected. This is were it gets tricky. All items that are not moved to a position should keep a stable order (by
Position
). In this case ID=2 and ID=4 should stay in this order.

The sample:

class Program
{
static void Main(string[] args)
{
var changedWatchLists = new List<WatchList>
{
new WatchList(1) {Position = 5}, new WatchList(3) {Position = 1}, new WatchList(5) {Position = 4}
};
WatchList.UpdateWatchListsSort("123", changedWatchLists);
}
}


My approach is to load first the complete
List<WatchList>
(from DB) and then merge it with the passed list with the new Positions. This enables to validate the input before and should make it simpler because all can be done in memory.

The basic logic is to
Remove
all changed
WatchLists
from the complete list and then
Insert
it at the desired position.

I enumerate only the change-list ordered by the new position to avoid side-affects. Otherwise
List.Insert
could move up items that had already the target position.

However, at the end i still have items which are at the wrong position, so i'm stuck.

The complete method
UpdateWatchListsSort
:

public static void UpdateWatchListsSort(string userId, List<WatchList> watchListsWithModifiedPosition)
{
List<WatchList> allUserWatchLists = GetWatchListsFromDb(userId);
// mapping WatchListId --> WatchList (from DB)
Dictionary<int, WatchList> dbWatchListIdLookup = allUserWatchLists.ToDictionary(w => w.Id);

if (watchListsWithModifiedPosition.Count == allUserWatchLists.Count)
allUserWatchLists = watchListsWithModifiedPosition;
else
{
// enumerate all modified WatchLists ordered by position ascending (to avoid side affects)
foreach (WatchList modified in watchListsWithModifiedPosition.OrderBy(w => w.Position))
{
WatchList dbWatchList = dbWatchListIdLookup[modified.Id];
int newIndex = modified.Position - 1;
int oldIndex = allUserWatchLists.IndexOf(dbWatchList); // might be at a different position meanwhile( != db-position )
allUserWatchLists.RemoveAt(oldIndex);
// if moved forwards index is index-1 because the watchlist was already removed at List.RemoveAt,
// if moved backwards index isn't affected
bool movedForwards = newIndex > oldIndex;
if (movedForwards)
newIndex--;
allUserWatchLists.Insert(newIndex, dbWatchList);
}
}

var changeInfos = allUserWatchLists
.Select((wl, index) => new { WatchList = wl, NewPosition = index + 1 })
.Where(x => x.WatchList.Position != x.NewPosition)
.ToList();
foreach (var change in changeInfos)
{
WatchList wl = change.WatchList;
wl.Position = change.NewPosition;
// check if the new position is equal to the position given as parameter
Debug.Assert(wl.Position == watchListsWithModifiedPosition
.Where(w => w.Id == wl.Id)
.Select(w => w.Position)
.DefaultIfEmpty(wl.Position)
.First());
}
// check if allUserWatchLists contains duplicate Positions which is invalid
Debug.Assert(allUserWatchLists
.Select(w => w.Position)
.Distinct().Count() == allUserWatchLists.Count);

// update changeInfos.Select(x => x.WatchList) via table-valued-parameter in DB (not related) .....
}

private static List<WatchList> GetWatchListsFromDb(string userId)
{
var allDbWatchLists = new List<WatchList>
{
new WatchList(1) {Position = 1}, new WatchList(2) {Position = 2}, new WatchList(3) {Position = 3},
new WatchList(4) {Position = 4}, new WatchList(5) {Position = 5}
};
return allDbWatchLists;
}


If you execute this sample this
Debug.Assert
will fail:

// check if the new position is equal to the position given as parameter
Debug.Assert(wl.Position == watchListsWithModifiedPosition
.Where(w => w.Id == wl.Id)
.Select(w => w.Position)
.DefaultIfEmpty(wl.Position)
.First());


So the algorithm is wrong because a
WatchList
new
Position
is not the desired one (given as parameter).

I hope you understand this requirement and see what i'm doing wrong. I suspect this part but don't know how to fix it:

// if moved forwards index is index-1 because the watchlist was already removed at List.RemoveAt,
// if moved backwards index isn't affected
bool movedForwards = newIndex > oldIndex;
if (movedForwards)
newIndex--;


Maybe you have even a better approach, readability is important.

Answer

Your algorithm almost works, but you need to remove all the old watch lists first, and then reinsert them at their new positions.

The way it's currently written, you can remove a dbWatchList from position 1 after inserting a new one at position 2, and that will change the position of the inserted watch list.

The corrected function looks like this:

public static void UpdateWatchListsSort(string userId, List<WatchList> watchListsWithModifiedPosition)
{
    var modifiedIds = new HashSet<int>(watchListsWithModifiedPosition.Select( w=>w.Id ));

    List<WatchList> allUserWatchLists = GetWatchListsFromDb(userId);

    var modifiedWatchLists = allUserWatchLists.FindAll(w => modifiedIds.Contains(w.Id)).ToDictionary(w => w.Id);

    allUserWatchLists.RemoveAll( w => modifiedIds.Contains(w.Id));

    foreach (WatchList modified in watchListsWithModifiedPosition.OrderBy(w => w.Position))
    {
        int newIndex = modified.Position - 1;
        allUserWatchLists.Insert(newIndex, modifiedWatchLists[modified.Id]);
    }

    //... Your testing and Position fix-up code ...
}

Note, however that the above is an O(N^2) algorithm, since it inserts into the middle of a list. It's actually much faster to make a new list like this:

public static void UpdateWatchListsSort(string userId, List<WatchList> watchListsWithModifiedPosition)
{
    var modifiedIds = new HashSet<int>(watchListsWithModifiedPosition.Select( w=>w.Id ));

    List<WatchList> allUserWatchLists = GetWatchListsFromDb(userId);

    var modifiedWatchLists = allUserWatchLists.FindAll(w => modifiedIds.Contains(w.Id)).ToDictionary(w => w.Id);

    var newList = new List<WatchList>();
    var unmodifiedIter = allUserWatchLists.FindAll(w => !modifiedIds.Contains(w.Id)).GetEnumerator();

    foreach (WatchList modified in watchListsWithModifiedPosition.OrderBy(w => w.Position))
    {
        int newIndex = modified.Position - 1;
        while(newList.Count < newIndex && unmodifiedIter.MoveNext())
            newList.Add(unmodifiedIter.Current);

        newList.Add(modifiedWatchLists[modified.Id]);
    }
    while(unmodifiedIter.MoveNext())
        newList.Add(unmodifiedIter.Current);

    allUserWatchLists = newList;

    //... Your testing and Position fix-up code ...
}