Sort only specific items in a list of items-CodePudding

Consider the following code:

// Apple
internal record class Apple(int Id);

// Orange
internal record class Orange(int Id);

// Input
// Note how Apple(1) is followed by Apple(3) and not by Apple(2)
List<object> list = new List<object>();
list.Add(new Apple(1));
list.Add(new Apple(3));
list.Add(new Orange(1));
list.Add(new Apple(2));
list.Add(new Orange(3));
list.Add(new Orange(2));

I want to sort all Apples in the list, however indexes that are currently used by Oranges shall also be used by Oranges after sorting. Also, I don't want to sort Oranges at all.

My expected output is therefore a list like this:

List<object> expected = new List<object>();
list.Add(new Apple(1));
list.Add(new Apple(2)); // changed
list.Add(new Orange(1));
list.Add(new Apple(3)); // changed
list.Add(new Orange(3));
list.Add(new Orange(2)); // don't sort oranges, so this remains after Orange(3)

I tried it with

internal class MyComparer : IComparer<object>
{
    public int Compare(object? x, object? y)
    {
        if(x is Apple a1 && y is Apple a2)
        {
            Console.WriteLine($"Compare {a1.Id} and {a2.Id}");
            return a1.Id.CompareTo(a2.Id);
        }

        return 0; //don't compare apples and oranges or oranges and oranges
    }
}

// use comparer
var sorted = list.OrderBy(key => key, new MyComparer()).ToList();

but that does not change any order in the list, because it only compares an Apple directly following an Apple (console output is only "Compare 3 and 1").

Any elegant way to do such special sort? Note that this is a reduced example and I have reasons not to have Apples and Oranges in different lists.

CodePudding user response：

What a weird requirement! I suspect there is some rationale behind this that might make for a more clever solution, but given the bare requirements, I see no way to do it but brute force. Extract the list you want to sort, sort it, then reintegrate it into the original list.

static IEnumerable<object> Sort(List<object> list)
{
    var apples = new Queue(list.OfType<Apple>().OrderBy( x => x.Id ).ToArray());
    foreach (var item in list)
    {
        if (item.GetType() == typeof(Apple))
        {
            yield return apples.Dequeue();
        }
        else
        {
            yield return item;
        }
    }
}

Example on DotNetFiddle

CodePudding user response：

A slightly more efficient version of @JohnWu's answer. We remove the Queue and just use the IEnumerator directly.

static IEnumerable<object> SortByType<T, TKey>(this List<object> source, Func<T, TKey> keySelector, IComparer<TKey> comparer = null)
{
    using var toSort = source.OfType<T>().OrderBy(keySelector, comparer).GetEnumerator();

    foreach (var item in source)
    {
        if (item is Apple)
        {
            toSort.MoveNext();
            yield return toSort.Current;
        }
        else
        {
            yield return item;
        }
    }
}

dotnetfiddle