c# - sort list-of-lists using linq and custom sorting rules

Question

I have a list of lists, with each inner list being a list of integers like this (code is simplified for clarity):

var listOfLists = new List<List<int>>
{
     new List<int> {6, 0, 2, 5, 6},      // #3 in sort order
     new List<int> {6, 0, 2, 2, 5, 6},   // #2 in sort order
     new List<int> {0, -1, 0, 0, 7},     // #1 in sort order
     new List<int> {11, 3, 5, 5, 12},    // #4 in sort order
};

I want to sort these lists using LINQ-to-Objects according to the following rules:

1. If either list is empty, the non-empty list sorts first
2. The list with the lowest minimum number is sorted first
3. If there's a tie, the largest number of duplicates of the minimum is sorted first. Example: {2,2} sorts before {2}.
4. If there's still a tie, remove the minimums from both lists and goto Step #1

Background:

Each list represents locations which each have 1+ retail stores. Each retail store is assigned an "urgency" number defining how badly that location needs to be restocked. The "worst" is -1, which usually means a customer has complained about empty products. 0 usually means the store has run out of high-selling products. 1 is usually a store that's almost empty. And so on. In practice the urgengy calculation is complex and based on multiple criteria validated by data-mining, but how we get the numbers isn't important for the sorting.

I want to find the most urgent locations, which I'm defining as the location with the most urgent store, with the number of stores at that level of urgency used as a tie-breaker.

Answer 1

I divided the problem into two:

First, I dealt with the tiebreaking by duplicates part of the problem by subtracting a small floating-point number (e.g. .0000001) for every duplicate, e.g.:

from m in list
group m by m.Urgency into g
orderby g.Key
select g.Key - (g.Count()-1) *.0000001

This left me with a much simpler problem: simply comparing two sequences item-by-item.

For this task I adapted Jon Skeet's answer to Is there a built-in way to compare IEnumerable (by their elements)?. I had to change his comparer to fix a code bug and because my sorting rules treated longer sequences as sorted before shorter sequences, but otherwise I copied the code verbatim.

Here's the resulting solution, somewhat simplified for posting here:

var urgentLocations = 
               (   from m in Stores
                   group m by m.Location into g
                   where g.Min(m => m.Urgency) < 14
                   select new {Name = g.Key, Stores = g.OrderBy(m=>m.Urgency).ToList()})
               .OrderBy (g=>g.Stores, new LocationComparer())
               .ToList();


public class LocationComparer : IComparer<List<Machine>>
{

    public int Compare(List<Store> source1, List<Store> source2)
    {
        var reduced1 = from m in source1
                        group m by m.Urgency into g
                        orderby g.Key
                        select g.Key - (g.Count() - 1) * .0000001;
        var reduced2 = from m in source2
                        group m by m.Urgency into g
                        orderby g.Key
                        select g.Key - (g.Count() - 1) * .0000001;
        return SequenceCompare(reduced1, reduced2);
    }

    // adapted from https://stackoverflow.com/a/2811805/126352 but modified so that 
    // shorter sequences are sorted last
    public int SequenceCompare<T>(IEnumerable<T> source1, IEnumerable<T> source2)
    {
        // You could add an overload with this as a parameter 
        IComparer<T> elementComparer = Comparer<T>.Default;
        using (IEnumerator<T> iterator1 = source1.GetEnumerator())
        using (IEnumerator<T> iterator2 = source2.GetEnumerator())
        {
            while (true)
            {
                bool next1 = iterator1.MoveNext();
                bool next2 = iterator2.MoveNext();
                if (!next1 && !next2) // Both sequences finished 
                {
                    return 0;
                }
                if (!next1) // Only the first sequence has finished
                {
                    return 1;
                }
                if (!next2) // Only the second sequence has finished 
                {
                    return -1;
                }
                // Both are still going, compare current elements 
                int comparison = elementComparer.Compare(iterator1.Current,
                                                 iterator2.Current);
                // If elements are non-equal, we're done 
                if (comparison != 0)
                {
                    return comparison;
                }
            }
        }
    }
}

Answer 2

这也适用于Compare，对吧？

public int Compare(List<Store> source1, List<Store> source2)
{        
    var reduced1 = source1.Select(s => s.Urgency).OrderBy(u => u);
    var reduced2 = source2.Select(s => s.Urgency).OrderBy(u => u);
    return SequenceCompare(reduced1, reduced2);
}