Как заставить устойчивую сортировку для ArrayList с пользовательским IComparer? - PullRequest
Новая
       94

Как заставить устойчивую сортировку для ArrayList с пользовательским IComparer?

0 голосов
/ 18 апреля 2020

Согласно документам :

Для выполнения стабильной сортировки необходимо реализовать пользовательский интерфейс IComparer.

Но согласно этот пост .

Документация говорит о том, что единственный способ получить стабильную сортировку с ArrayList.Sort - это использовать IComparer, который каким-то образом "знает" индексы элементов, которые сравниваются (можно представить, что это выполняется путем запуска первоначального прохода по коллекции) и использует эту информацию как на ie -разрушителе для других равных элементов.

Так кто-нибудь знает, как правильно реализовать IComparer, который каким-то образом «знает» индексы сравниваемых элементов?

1 Ответ

0 голосов
/ 18 апреля 2020

Вы можете построить что-то вроде этого (заимствуя код из этого ответа у Джона Скита ) 

public sealed class IdentityEqualityComparer<T> : IEqualityComparer<T>
    where T : class
{
    public int GetHashCode(T value) => RuntimeHelpers.GetHashCode(value);

    public bool Equals(T left, T right) => left == right;
}

public class StableComparer : IComparer
{
    private readonly Dictionary<object, int> _itemsPosition = 
        new Dictionary<object, int>(new IdentityEqualityComparer<object>());

    private readonly IComparer _baseComparer;

    public StableComparer(IEnumerable collection, IComparer baseComparer)
    {
        _baseComparer = baseComparer;

        int index = 0;
        foreach (object item in collection)
        {
            _itemsPosition.Add(item, index);
            index++;
        }
    }

    public int Compare(object x, object y)
    {
        int baseResult = _baseComparer.Compare(x, y);
        if (baseResult != 0)
        {
            return baseResult;
        }

        int xIndex = _itemsPosition[x];
        int yIndex = _itemsPosition[y];

        return xIndex.CompareTo(yIndex);
    }
}

(я добавил часть сравнения равенства, чтобы убедиться, что ссылочное равенство используется в соответствии с предложением @PeterDuniho).

Этот код можно использовать следующим образом: 

class Item
{
    public int Id { get; }
    public string Description { get; }

    public Item(int id, string description)
    {
        Id = id;
        Description = description;
    }
}

class ItemComparer : IComparer
{
    public int Compare(object x, object y) => ((Item)x).Id.CompareTo(((Item)y).Id);
}

и 

class Program
{
    static void Main(string[] args)
    {
        var items = new ArrayList()
        {
            new Item(1, "Item 0 (1)"),
            new Item(3, "Item 1 (3)"),
            new Item(2, "Item 2 (2)"),
            new Item(3, "Item 3 (3)"),
            new Item(1, "Item 4 (1)"),
            new Item(4, "Item 5 (4)"),
            new Item(1, "Item 6 (1)")
        };

        Console.WriteLine("Not stable");
        SortAndDisplay((ArrayList)items.Clone(), new ItemComparer());

        Console.WriteLine("Stable");
        SortAndDisplay((ArrayList)items.Clone(), 
          new StableComparer(items, new ItemComparer()));
    }

    static void SortAndDisplay(ArrayList items, IComparer comparer)
    {
        items.Sort(comparer);

        foreach (var item in items)
        {
            Console.WriteLine(((Item)item).Description);
        }
    }
}

Обратите внимание, что в Sort 4.5 произошли изменения, которые могут изменить порядок «равных» предметов. Если я запускаю этот код в Framework 4, я получаю: 

Not stable
Item 6 (1)
Item 4 (1)
Item 0 (1)
Item 2 (2)
Item 3 (3)
Item 1 (3)
Item 5 (4)
Stable
Item 0 (1)
Item 4 (1)
Item 6 (1)
Item 2 (2)
Item 1 (3)
Item 3 (3)
Item 5 (4)

Я пытался опубликовать этот код на. net Fiddle, но он не позволяет использовать framework 4. Вы можете использовать OrderBy Linq тоже стабильный.

...