Sorting ArrayList of shapes

Question

I have an ArrayList of MCommand objects (cmdList) and I want to sort it so that shapes with closest points are next to each other in the ArrayList. For example, say I have three lines in the ArrayList: line(xs, ys, zs, xe, ye, ze)

cmdList[0] = line1(1.3, 2.5, 3, 4, 5, 6)

cmdList[1] = line2(1, 5, 6.77, 7, 8, 2)

cmdList[2] = line3(1, 6, 3, 1, 1.1, 1)

Points that need to be close are LastPosition of line with BeginPosition of other line. LastPosition of line is (xe, ye, ze) and BeginPosition of line is (xs, ys, zs). I now do my sorting by executing a built in sorting:

cmdList.Sort(new MCommandComparer());

This is how my MCommand looks like and how i calculate distance of two points:

public abstract class MCommand
{
    //...
    public abstract Point3 LastPosition { get; }
    public abstract Point3 BeginPosition { get; }

    public double CompareTo(Object obj)
    {
        Point3 p1, p2;
        p1 = this.BeginPosition;
        p2 = ((MCommand)obj).LastPosition;
        return Math.Sqrt(Math.Pow((p2.x - p1.x), 2) +
                     Math.Pow((p2.y - p1.y), 2) +
                     Math.Pow((p2.z - p1.z), 2));
    }
}

This is the comparer i use:

public class MCommandComparer : IComparer
{
    private MCommand prev;
    double distanceFromPrev = 0;
    double distanceFromCurr = 0;
    public int Compare(object o1, object o2)
    {
        if ((MCommand)o2 == prev)
            return 0;
        if (prev != null)
            distanceFromPrev = ((MCommand)o1).CompareTo(prev);
        distanceFromCurr = ((MCommand)o1).CompareTo(o2);
        prev = (MCommand)o2;
        return (int)(distanceFromCurr - distanceFromPrev);
    }
}

I've tried many ways and got lost... This doesnt sort shapes the way I want to. My question is, what I could be doing wrong? Should i try writing sorting from scratch? My ArrayList can contain couple thousands elements, and i need to have an efficient sort.

Answer 1

What could I be doing wrong?

You're assuming the elements will be presented to you in a particular order - you're remembering the "previous" element, which is a huge red flag.

The way various sorts work won't do this at all. Basically your comparer should be stateless. It sounds like you don't really have a total ordering here - there's no way of taking any two arbitrary elements and saying which should be before or after the other one.

I don't know exactly how you'd do whatever you need, but I don't think the standard sorting built into .NET is going to help you much.

Answer 2

You could make your MCommand class subscribe to IComparable. In doing this you would allow your list to sort your shapes without the need for additional Comparer Object. All the sorting functionality would be handled by the list and the objects within it.