c# - 如何根据仅包含已更改索引的列表修改列表索引？

Question

更新:这是完整的代码https://dotnetfiddle.net/eAeWp5

这个比我想象的要难得多。在实际项目中，我需要更新一个包含列 Position 的数据库表(对于排序顺序)，但所有方法获取的是一个列表，其中仅包含具有新位置的已更改对象。表和类是 WatchList .

这里是:

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}";
    }
}

所以 WatchListId是主键，Position我要更新的列。

考虑到此表包含以下观察列表:

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

用户想修改订单，拖拽，最后提交给服务器。客户将调用 UpdateWatchListsSort列表仅包含用户移动的监视列表。

考虑用户移动

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

所以数据库中的新(正确)顺序是:

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

您注意到甚至一些其他观察列表也必须更新，因为如果它们的位置受到影响，则位置需要向上移动 1。这是它变得棘手。所有未移动到某个位置的项目应保持稳定的顺序(通过 Position )。在这种情况下，ID=2 和 ID=4 应保持此顺序。

样本:

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

我的方法是先加载完整的 List<WatchList> (来自数据库)，然后将其与传递的列表与新位置合并。这使得能够在之前验证输入并且应该使它更简单，因为所有都可以在内存中完成。

基本逻辑是Remove都变了WatchLists从完整列表然后Insert它在所需的位置。

为了避免副作用，我只列举了新职位排序的变更列表。否则List.Insert可以向上移动已经具有目标位置的项目。

但是，最后我仍然有一些项目在错误的位置，所以我被卡住了。

完整方法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;
}

如果您执行此示例此 Debug.Assert会失败:

// 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());

所以算法是错误的，因为 WatchList新Position不是所需的(作为参数给出)。

我希望你理解这个要求并看看我做错了什么。我怀疑这部分但不知道如何解决:

 // 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--;

也许您有更好的方法，可读性很重要。

Answer 1

我建议使用插入排序算法原理。算法步骤为:

1. 获取原始对象列表(original)和输入对象列表(input)
2. 丢弃input 中original 中的所有对象。按 Position 字段排序其余部分。将这个新列表称为 ordered
3. 对于输入中的每个对象，找到将其放入 ordered 的位置并将其放置在那里

最后你会得到一个正确排序的对象列表，但是位置已经过时了。但是位置现在对应于对象在 ordered 列表中的索引，所以这很容易修复。

代码来说明我的意思。我对定义做了一些简化以使其简短:

class WatchList
{
    public int WatchListId;
    public int Position;
}

List<WatchList> original = new List<WatchList>
{
    new WatchList{WatchListId=1, Position=1},
    new WatchList{WatchListId=2, Position=2},
    new WatchList{WatchListId=3, Position=3},
    new WatchList{WatchListId=4, Position=4},
    new WatchList{WatchListId=5, Position=5}
};

List<WatchList> input = new List<WatchList>
{
    new WatchList{WatchListId=1, Position=5},
    new WatchList{WatchListId=3, Position=1},
    new WatchList{WatchListId=5, Position=4}
};

现在算法是这样的:

List<WatchList> ordered = original.Where(w => !input.Any(iw => iw.WatchListId == w.WatchListId)).OrderBy(w => w.Position).ToList();
foreach (var inputWatchlist in input)
{
    int indexToInsert = 0;
    while (indexToInsert < ordered.Count)
    {
        if (ordered[indexToInsert].Position <= inputWatchlist.Position)
        {
            indexToInsert++;
        } 
        else
        {
            break;
        }
    }

    ordered.Insert(indexToInsert, inputWatchlist);
}

这输出

foreach (var w in ordered)
{
    Console.WriteLine("Id: " + w.WatchListId + " P: " + w.Position);
}

Id: 3 P: 1
Id: 2 P: 2
Id: 4 P: 4
Id: 5 P: 4
Id: 1 P: 5

样本 fiddle 链接:https://dotnetfiddle.net/7MtjVZ

如您所见，对象按预期顺序排列，但位置不合适。然而，现在更新位置是微不足道的。