Somewhat complex list sorting

Question

I have a number of objects each with 3 numerical properties: "high", "low" and "tiebreaker". They are to be sorted as such: if an object's low is higher than another object's high, it appears before it in the list. Likewise if an object's high is lower than another's low, it appears later in the list. But in the case that two objects have conflicting ranges (eg one's high is between the other object's low and high), the tiebreaker property is considered wherein the object with the higher tiebreaker value gets placed earlier on the list.

I am specifically working with c#, but I think the ideas here are language agnostic enough such that code of any sort (no puns) would be welcome.

Also, I have worked on this myself. I have a nested for-loop that is just not working out for me so far. I'd give up some code but I'm on my phone and that makes it a chore. Besides, this is probably a fun one for you and you don't need my ugly code in your way anyhow.

Answer 1

Are you assuming that Min <= Tie <= Max? You do not say so in your question, and if you do not, the sort order is not well defined because it is not transitive. For instance, writing your ranges as [Min, Tie, Max], consider:

A: [5,-10,  6]
B: [0,  1, 10]
C: [2,  3,  4]

A < B (because they overlap and -10 < 1)

B < C (because they overlap and 1 < 3)

but A > C (because they don't overlap and 5 > 4)

If they are you can define a custom IComparer<Range> for your Range class, and pass it to any c# sort method.

Update and here's one such implementation.

public struct RangeWithTie<T> where T : IEquatable<T>, IComparable<T>
{
    readonly T min;
    readonly T max;
    readonly T tie;
    readonly bool isNonEmpty;

    public static Range<T> Empty = new Range<T>();

    public static IComparer<RangeWithTie<T>> CreateSortingComparer()
    {
        return new RangeWithTieComparer();
    }

    public RangeWithTie(T start, T tie, T end)
    {
        // Enfore start <= tie <= end
        var comparer = Comparer<T>.Default;
        if (comparer.Compare(start, end) > 0) // if start > end
        {
            throw new ArgumentOutOfRangeException("start and end are reversed");
        }
        else if (comparer.Compare(start, tie) > 0)
        {
            throw new ArgumentOutOfRangeException("tie is less than start");
        }
        else if (comparer.Compare(tie, end) > 0)
        {
            throw new ArgumentOutOfRangeException("tie is bigger than end");
        }
        else
        {
            this.min = start;
            this.max = end;
            this.tie = tie;
        }
        this.isNonEmpty = true;
    }

    public T Min { get { return min; } }

    public T Max { get { return max; } }

    public T Tie { get { return tie; } }

    public bool IsEmpty { get { return !isNonEmpty; } }

    public class RangeWithTieComparer : IComparer<RangeWithTie<T>>
    {
        #region IComparer<RangeWithTie<T>> Members

        public int Compare(RangeWithTie<T> x, RangeWithTie<T> y)
        {
            // return x - y.
            if (x.IsEmpty)
            {
                if (y.IsEmpty)
                    return 0;
                else
                    return -1;
            }
            else if (y.IsEmpty)
            {
                return 1;
            }
            var comparer = Comparer<T>.Default;
            if (comparer.Compare(y.Min, x.Max) > 0)
                return -1;
            else if (comparer.Compare(x.Min, y.Max) > 0)
                return 1;
            return comparer.Compare(x.Tie, y.Tie);
        }

        #endregion
    }

    public override string ToString()
    {
        if (IsEmpty)
            return "Empty";
        StringBuilder s = new StringBuilder();
        s.Append('[');
        if (Min != null)
        {
            s.Append(Min.ToString());
        }
        s.Append(", ");
        if (Tie != null)
        {
            s.Append(Tie.ToString());
        }
        s.Append(", ");
        if (Max != null)
        {
            s.Append(Max.ToString());
        }
        s.Append(']');
        return s.ToString();
    }
}

This could be used like so:

var sortedRanges = ranges.OrderBy(x => x, RangeWithTie<double>.CreateSortingComparer()).ToArray();

I didn't make the struct implement IComparer<RangeWithTie<T>> directly because ranges with identical comparisons aren't necessarily equal. For instance, [-1,0,1] and [-2,0,1] have identical comparisons but are not equal.

Answer 2

A quick solution, and a console application to test it. This method will return the larger of two objects. Just replace dynamic with the appropriate object type you need.

class Program
{
    private static object Sort(dynamic first, dynamic second)
    {
        if (OverlapExists(first, second))
        {
            // Note: If tiebreakers are equal, the first will be returned:
            return first.tiebreaker >= second.tiebreaker ? first : second;
        }
        else
        {
            // Note: Only need to test one value (just high); Since we know 
            // there is no overlap, the whole object (both high and low) must 
            // be either over  or under that which it is compared to:
            return first.high > second.high ? first : second;
        }
    }

    private static bool OverlapExists(dynamic first, dynamic second)
    {
        return (first.low < second.high) && (second.low < first.high);
    }

    static void Main(string[] args)
    {

        dynamic first = new {name="first", high = 10, 
                             tiebreaker = 5, low = 1 };
        dynamic second = new {name="second", high = 15, 
                              tiebreaker = 12, low = 11 };
        dynamic third = new {name="third", high = 20, 
                             tiebreaker = 9, low = 6 };

        var firstResult = Sort(first, second);
        var secondResult = Sort(first, third);
        var thirdResult = Sort(second, third);

        Console.WriteLine("1) " + first.ToString() 
                             + "\nVS: " + second.ToString());
        Console.WriteLine("Winner: " + firstResult.name);

        Console.WriteLine("\n2) " + first.ToString() 
                             + "\nVS: " + third.ToString());
        Console.WriteLine("Winner: " + secondResult.name);

        Console.WriteLine("\n3) " + second.ToString() 
                             + "\nVS: " + third.ToString());
        Console.WriteLine("Winner: " + thirdResult.name);

        Console.ReadKey();
    }
}

Answer 3

Let’s say you have a List<T> (T being your objects with High-, Low- and Tie- Property), then you can use

list.Sort(…);

with a Comparison<T> as a Parameter. That’s a delegate that takes 2 of you objects and should return < 0, when the first instance of your object should be a head of the other instance or 0 if they are of equal order (or > 0 if the second second object should be ahead of first).
Or you could pass an custom comparer (implementing IComparer<T>) which does basically the same as the Comparison<T> but inform of an interface.

Answer 4

No matter what your logic is, you may implement IComparable to enable an Array or List's sorting capability. So, as the follow code shows,

public class MyStuff : IComparable<MyStuff>
{
    public int High { get; set; }
    public int Low { get; set; }
    public int TieBreaker { get; set; }

    public int CompareTo(MyStuff other)
    {
        // if an object's low is higher than another object's high, 
        // it appears before it in the list
        if ((this.Low > other.High) ||
            // if its high is between the other object's low and 
            // high then compare their tiebreaker
            (this.High > other.Low && this.High < other.High && 
                this.TieBreaker > other.TieBreaker))
            return 1;
        else if (this.Low == other.High)
            return 0;
        else
            return -1;
    }
}

The basic idea is CompareTo returns either 1 (move this before other), 0 (retain both positions) or -1 (move this after other), depending on your ordering logic.

Answer 5

See IComparable<T>

class DataObject : IComparable<DataObject>
{
    public double High, Low, Tiebreaker;

    public int CompareTo(DataObject obj) 
    {
        // this doesn't seem to make sense as a range sort, but seems to match your question...
        // low > another high
        if (this.Low != obj.High)
            return this.Low.CompareTo(obj.High);
        // otherwise sort tiebreaker ascending
        else this.TieBreaker.CompareTo(obj.TieBreaker);
    }
}

used as

var items = new[] { new DataObject(1,2,3), new DataObject(4,5,6) };
Array.Sort<DataObject>(items);

// items is now sorted