Order a list of Sorted Set of Strings by Count and then by strings

Question

I have a custom class called PairString

 public class PairString: IComparer<PairString>
    {
        public string first;
        public string second;
        public PairString(string f, string s)
        {
            first = f;
            second = s;
        }
        public int Compare([AllowNull] PairString x, [AllowNull] PairString y)
        {
            if (x == null || y == null) return -1;
            var f = string.Compare(x.first, y.first);
            var s = string.Compare(x.second, y.second);
            return f == s ? s : f;
        }
    }

I want to create groups by count and then by lexical order of strings in that groups, from a list of input PairString List. Below method does the grouping right. But when I try to sort the groups in lexical order for equal count groups, it throws "Atleast one object must implement IComparer error"

public static List<string> MaxItemAssociatoinGroup(List<PairString> input)
        {
            if (input == null || input.Count == 0) return null;
            List<SortedSet<string>> output = new List<SortedSet<string>>();
            foreach (var item in input)
            {
                if (output.Any(x => x.Contains(item.first) || x.Contains(item.second)))
                {
                    //Take the set containing one or two or both items
                    var set1 = output.FirstOrDefault(x => x.Contains(item.first));
                    var set2 = output.FirstOrDefault(x => x.Contains(item.second));
                    if (set1 == null)
                        set2.UnionWith(new SortedSet<string> { item.first, item.second });

                    else if (set2 == null)
                        set1.UnionWith(new SortedSet<string> { item.first, item.second });

                    else if (set1 != set2)
                    {
                        set1.UnionWith(set2);
                        output.Remove(set2);
                    }
                }
                else
                    output.Add(new SortedSet<string>(new List<string>() { item.first, item.second }));
            }
            var maxlistAssociation = output.OrderByDescending(x => x.Count).First();
            return new List<string>(maxlistAssociation);
        }

I am not sure how to achieve lexical order for same count groups, Sample input is

new PairString("item3","item4"),
            new PairString("item3","item6"),
            new PairString("item5","item6"),
            new PairString("item2","item8"),
            new PairString("item8","item9"),
            new PairString("item1","item2")

it groups into 2 groups of equal count {item3,item4,item5,item6} & {item1,item2,item8,item9} but returns {item3,item4,item5,item6} as its first in the list. but I want the second group as it contains the item that lexicographically first than first group. what am I missing here?

Answer 1

It appears that you're missing a method that will compare two SortedSet<string> objects and return the one which comes first lexically. One way to do this is to compare each item from one set with the corresponding one in the other set, and return the first non-equal comparison:

public class SortedSetComparer<T> : IComparer<SortedSet<T>> where T : IComparable<T>
{
    public int Compare(SortedSet<T> x, SortedSet<T> y)
    {
        // Null checks
        if (x == null) return y == null ? 0 : 1;
        if (y == null) return -1;

        var minCount = Math.Min(x.Count, y.Count);

        // Compare each item from one set with the corresponding one in the other set
        for (var i = 0; i < minCount; i++)
        {
            var result = x.ElementAt(i).CompareTo(y.ElementAt(i));

            // Return the first non-equal result
            if (result != 0) return result;
        }

        // If all the items were equal, return the comparison of the Count
        return x.Count.CompareTo(y.Count);
    }
}

Then we can order our results (after sorting by size) by passing an instance of this class to the ThenBy method:

var maxlistAssociation = output
    .OrderByDescending(x => x.Count)
    .ThenBy(x => x, new SortedSetComparer<string>())
    .First();

---

Depending on the behavior you want from this method, we could also incorporate the ordering by Count into our comparison method, so that it puts the sets with the most items first, then sorts them alphabetically:

public class SortedSetComparer<T> : IComparer<SortedSet<T>> where T : IComparable<T>
{
    public int Compare(SortedSet<T> x, SortedSet<T> y)
    {
        // Null checks
        if (x == null) return y == null ? 0 : 1;
        if (y == null) return -1;

        // Compare the counts first, in descending order
        var countComparison = x.Count.CompareTo(y.Count);
        if (countComparison != 0) return countComparison * -1;

        // Then compare each item from one set lecially 
        // with the corresponding one in the other set
        return x.Select((item, index) =>
            x.ElementAt(index).CompareTo(y.ElementAt(index)))
            .FirstOrDefault(result => result != 0);
    }
}

And now we only need one OrderBy clause:

var maxlistAssociation = output
    .OrderBy(x => x, new SortedSetComparer<string>())
    .First();