Эффективная сортировка IList <T>без копирования списка источников

Question

Учитывая приведенный ниже тестовый пример, как я могу:

1. Сортировать IList<TestObject> на основе индекса совпадения Id в списке IList<int>.
2. Unmatchedзначения перемещаются в конец списка и сортируются по их первоначальному индексу.В этом случае, поскольку 3 и 4 не существуют в списке индексов, мы ожидаем увидеть list[3] == 3 и list[4] == 4.
3. Хотя я знаю, что этого можно достичь с помощью linq, мне нужно прибегнуть к оригинальный список, а не создание нового (из-за того, как хранится список).
4. Исходный список должен быть IList (я не могу использовать List<T>)

Вот тест:

    public class TestObject
    {
        public int Id { get; set; }
    }

    [Test]
    public void Can_reorder_using_index_list()
    {
        IList<TestObject> list = new List<TestObject>
        {
            new TestObject { Id = 1 },
            new TestObject { Id = 2 },
            new TestObject { Id = 3 },
            new TestObject { Id = 4 },
            new TestObject { Id = 5 }
        };

        IList<int> indexList = new[] { 10, 5, 1, 9, 2 };

        // TODO sort

        Assert.That(list[0].Id, Is.EqualTo(5));
        Assert.That(list[1].Id, Is.EqualTo(1));
        Assert.That(list[2].Id, Is.EqualTo(2));
        Assert.That(list[3].Id, Is.EqualTo(3));
        Assert.That(list[4].Id, Is.EqualTo(4));
    }

Обновление:

По запросу я попробовал, но 1) он работает только с List<T> и 2) Я не уверен, что это самый эффективный способ:

       var clone = list.ToList();
        list.Sort((x, y) =>
        {
            var xIndex = indexList.IndexOf(x.Id);
            var yIndex = indexList.IndexOf(y.Id);

            if (xIndex == -1)
            {
                xIndex = list.Count + clone.IndexOf(x);
            }
            if (yIndex == -1)
            {
                yIndex = list.Count + clone.IndexOf(y);
            }

            return xIndex.CompareTo(yIndex);
        });

Обновление 2:

Благодаря @leppie, @jamiec, @mitch wheat - это рабочий код:

    public class TestObjectComparer : Comparer<TestObject>
    {
        private readonly IList<int> indexList;
        private readonly Func<TestObject, int> currentIndexFunc;
        private readonly int listCount;

        public TestObjectComparer(IList<int> indexList, Func<TestObject, int> currentIndexFunc, int listCount)
        {
            this.indexList = indexList;
            this.currentIndexFunc = currentIndexFunc;
            this.listCount = listCount;
        }

        public override int Compare(TestObject x, TestObject y)
        {
            var xIndex = indexList.IndexOf(x.Id);
            var yIndex = indexList.IndexOf(y.Id);

            if (xIndex == -1)
            {
                xIndex = listCount + currentIndexFunc(x);
            }
            if (yIndex == -1)
            {
                yIndex = listCount + currentIndexFunc(y);
            }

            return xIndex.CompareTo(yIndex);
        }
    }

    [Test]
    public void Can_reorder_using_index_list()
    {
        IList<TestObject> list = new List<TestObject>
        {
            new TestObject { Id = 1 },
            new TestObject { Id = 2 },
            new TestObject { Id = 3 },
            new TestObject { Id = 4 },
            new TestObject { Id = 5 }
        };

        IList<int> indexList = new[] { 10, 5, 1, 9, 2, 4 };

        ArrayList.Adapter((IList)list).Sort(new TestObjectComparer(indexList, x => list.IndexOf(x), list.Count));

        Assert.That(list[0].Id, Is.EqualTo(5));
        Assert.That(list[1].Id, Is.EqualTo(1));
        Assert.That(list[2].Id, Is.EqualTo(2));
        Assert.That(list[3].Id, Is.EqualTo(3));
        Assert.That(list[4].Id, Is.EqualTo(4));
    }

Answer 1

Рассматривая это немного, и, как уже говорилось ранее, вам понадобится ArrayList.Adapter , однако вы заметите, что для этого требуется неуниверсальный IList, поэтому потребуется некоторое приведение:

ArrayList.Adapter((IList)list)

Вам также нужно написать компаратор, в котором будет содержаться логика для вашей сортировки. Извините, но имя:

public class WeirdComparer : IComparer,IComparer<TestObject>
{
    private IList<int> order;
    public WeirdComparer(IList<int> order)
    {
        this.order = order;
    }
    public int Compare(object x, object y)
    {
        return Compare((TestObject) x, (TestObject) y);
    }

    public int Compare(TestObject x, TestObject y)
    {
        if(order.Contains(x.Id))
        {
            if(order.Contains(y.Id))
            {
                return order.IndexOf(x.Id).CompareTo(order.IndexOf(y.Id));    
            }
            return -1;
        }
        else
        {
            if (order.Contains(y.Id))
            {
                return 1;
            }
            return x.Id.CompareTo(y.Id);
        }
    }
}

РЕДАКТИРОВАТЬ: Добавлена ​​реализация к сравнению выше

Тогда использование будет следующим:

IList<int> indexList = new[] { 10, 5, 1, 9, 2 };
ArrayList.Adapter((IList)list).Sort(new WeirdComparer(indexList));

Кстати, этот поток объясняет хороший способ превратить это в метод расширения, который сделает ваш код более пригодным для повторного использования и более легким для чтения IMO.

Answer 2

Вы можете попробовать следующее:

ArrayList.Adapter(yourilist).Sort();

Обновление:

Общий компаратор:

class Comparer<T> : IComparer<T>, IComparer
{
  internal Func<T, T, int> pred;

  public int Compare(T x, T y)
  {
    return pred(x, y);  
  }

  public int Compare(object x, object y)
  {
    return Compare((T)x, (T)y);
  }
}

static class ComparerExtensions
{
  static IComparer Create<T>(Func<T, T, int> pred)
  {
    return new Comparer<T> { pred = pred };
  }

  public static void Sort<T>(this ArrayList l, Func<T, T, int> pred)
  {
    l.Sort(Create(pred));
  }
}

Usage:

ArrayList.Adapter(list).Sort<int>((x,y) => x - y);

Answer 3

Вот общая версия компаратора. IEntity<TId> - это простой интерфейс со свойством «Id» типа TId:

public class IndexComparer<T, TId> : Comparer<T> where T : IEntity<TId> where TId : IComparable
{
    private readonly IList<TId> order;
    private readonly int listCount;
    private readonly Func<T, int> currentIndexFunc;

    public IndexComparer(Func<T, int> currentIndexFunc, IList<TId> order, int listCount) {
        this.order = order;
        this.listCount = listCount;
        this.currentIndexFunc = currentIndexFunc;
    }

    public override int Compare(T x, T y)
    {
        var xIndex = order.IndexOf(x.Id);
        var yIndex = order.IndexOf(y.Id);

        if (xIndex == -1)
        {
            xIndex = listCount + currentIndexFunc(x);
        }
        if (yIndex == -1)
        {
            yIndex = listCount + currentIndexFunc(y);
        }

        return xIndex.CompareTo(yIndex);
    }
}

Рабочий тест:

[TestFixture]
public class OrderingTests
{
    public class TestObject : IEntity<int>
    {
        public int Id { get; set; }
    }

    [Test]
    public void Can_reorder_using_index_list()
    {
        IList<TestObject> list = new List<TestObject>
        {
            new TestObject { Id = 1 },
            new TestObject { Id = 2 },
            new TestObject { Id = 3 },
            new TestObject { Id = 4 },
            new TestObject { Id = 5 }
        };

        IList<int> indexList = new[] { 10, 5, 1, 9, 2, 4 };
        ArrayList.Adapter((IList)list)
            .Sort(new IndexComparer<TestObject, int>(x => list.IndexOf(x), indexList, list.Count));

        Assert.That(list[0].Id, Is.EqualTo(5));
        Assert.That(list[1].Id, Is.EqualTo(1));
        Assert.That(list[2].Id, Is.EqualTo(2));
        Assert.That(list[3].Id, Is.EqualTo(4));
        Assert.That(list[4].Id, Is.EqualTo(3));
    }
}

Это соответствует требованиям, изложенным в моем первоначальном вопросе. Несовпадающие элементы перемещаются в конец списка, а затем упорядочиваются по их исходному индексу.