Sort and update list of objects based on variable change

algorithm, c#, int, list

Solution

Let us look at the four situations for an element in your list (as we iterate through them). If (for terseness) we take `old` to be the item that is moving's old position and `new` to be its new position we have the following cases for an item in your list (draw them out on paper to make this clear).

- the current item is the one to be moved: move it directly

- the current item's order is < `new` and < `old`: don't move it

- the current item's order is ≥ `new` and < `old`: move it right

- the current item's order is ≤ `new` and > `old`: move it left

- the current item's order is > `new` and > `old`: don't move it

When we start enumerating, we know the where the item to be moved will end up (at `new`) but we do not know where it has come from (`old`). However, as we start our enumeration at the beginning of the list, we know at each step that it must be further down in the list until we have actually seen it! So we can use a flag (`seen`) to say whether we have seen it yet. So `seen` of false means < `old` whilst true means >= `old`.

bool seen = false;
for (int i = 0; i < items.Length; i++)
{
    if (items[i].ID == inputID)
    {
        items[i].Order = inputNewPosition;
        seen = true;
    }
}

This flag tells us whether the current item is >= old. So now can start shunting stuff around based on this knowledge and the above rules. (So `new` in the above discussion is `inputNewPosition` and whether we are before or after `old` we represent with our `seen` variable.)

bool seen;
for (int i = 0; i < items.Count; i++)
{
    if (items[i].ID == inputID) // case 1
    {
        items[i].Order = inputNewPosition;
        seen = true;
    }
    else if (seen) // cases 4 & 5
    {
        if (items[i].Order <= inputNewPosition) // case 4
        {
           items[i].Order--; // move it left
        }
    }
    else // case 2 & 3
    {
        if (items[i].Order >= inputNewPosition) // case 3
        {
            items[i].Order++; // move it right
        }            
    }
}

Having said all of that, it is probably simpler to sort the collection on each change. The default sorting algorithm should be quite nippy with a nearly sorted collection.

Problem

I am working on a algorithm which will solve a problem I have, but I am finding myself a little stuck. Here is the scenario: I have an object which contains a variable called order. ``` public class Item { public int Order{get; set;}; public int ID{get; set;}; // not incremented can be any value! } ``` So I have a list of these: ``` List<Item> list = new List<Item>().OrderBy((o) => o.Order); ``` And at any time the order value can be changed. So if I want to change the first an items order value all other order values should update accordingly so there are no duplicates. ``` for (int i = 0; i <= list .Count - 1; i++) { if (list [i].ID == inputID) { list [i].Order = inputNewPosition; } else { if (list [i].Order < inputNewPosition) { list [i].Order --; } else { list [i].Order ++; } } } ``` This fails if I change the last item order to be the first, as this would make the first item order be 0! Can anyone help? Thanks

Original source