Sort a List by enum where enum is out of order

Question

I have a List of messages. Each message has a type.

public enum MessageType
{
    Foo = 0,
    Bar = 1,
    Boo = 2,
    Doo = 3
}

The enum names are arbitrary and cannot be changed.

I need to return the list sorted as: Boo, Bar, Foo, Doo

My current solution is to create a tempList, add the values in the order I want, return the new list.

List<Message> tempList = new List<Message>();
tempList.AddRange(messageList.Where(m => m.MessageType == MessageType.Boo));
tempList.AddRange(messageList.Where(m => m.MessageType == MessageType.Bar));
tempList.AddRange(messageList.Where(m => m.MessageType == MessageType.Foo));
tempList.AddRange(messageList.Where(m => m.MessageType == MessageType.Doo));
messageList = tempList;

How can I do this with an IComparer?

Answer 1

An alternative to using IComparer would be to build an ordering dictionary.

var orderMap = new Dictionary<MessageType, int>() {
    { MessageType.Boo, 0 },
    { MessageType.Bar, 1 },
    { MessageType.Foo, 2 },
    { MessageType.Doo, 3 }
};

var orderedList = messageList.OrderBy(m => orderMap[m.MessageType]);

Answer 2

So, let's write our own comparer:

public class MyMessageComparer : IComparer<MessageType> {
    protected IList<MessageType> orderedTypes {get; set;}

    public MyMessageComparer() {
        // you can reorder it's all as you want
        orderedTypes = new List<MessageType>() {
            MessageType.Boo,
            MessageType.Bar,
            MessageType.Foo,
            MessageType.Doo,
        };
    }

    public int Compare(MessageType x, MessageType y) {
        var xIndex = orderedTypes.IndexOf(x);
        var yIndex = orderedTypes.IndexOf(y);

        return xIndex.CompareTo(yIndex);
    }
};

How to use:

messages.OrderBy(m => m.MessageType, new MyMessageComparer())

There is a easier way: just create ordereTypes list and use another overload of OrderBy:

var orderedTypes = new List<MessageType>() {        
            MessageType.Boo,
            MessageType.Bar,
            MessageType.Foo,
            MessageType.Doo,
    };

messages.OrderBy(m => orderedTypes.IndexOf(m.MessageType)).ToList();

Hm.. Let's try to take advantages from writing our own IComparer. Idea: write it like our last example but in some other semantic. Like this:

messages.OrderBy(
      m => m.MessageType, 
      new EnumComparer<MessageType>() { 
          MessageType.Boo, 
          MessageType.Foo }
);

Or this:

messages.OrderBy(m => m.MessageType, EnumComparer<MessageType>());

Okay, so what we need. Our own comparer:

1. Must accept enum as generic type (how to solve)
2. Must be usable with collection initializer syntax (how to)
3. Must sort by default order, when we have no enum values in our comparer (or some enum values aren't in our comparer)

So, here is the code:

public class EnumComparer<TEnum>: IComparer<TEnum>, IEnumerable<TEnum> where TEnum: struct, IConvertible {
    protected static IList<TEnum> TypicalValues { get; set; }

    protected IList<TEnum> _reorderedValues;

    protected IList<TEnum> ReorderedValues { 
        get { return _reorderedValues.Any() ? _reorderedValues : TypicalValues; } 
        set { _reorderedValues = value; }
    } 

    static EnumComparer() {
        if (!typeof(TEnum).IsEnum) 
        {
            throw new ArgumentException("T must be an enumerated type");
        }

        TypicalValues = new List<TEnum>();
        foreach (TEnum value in Enum.GetValues(typeof(TEnum))) {
            TypicalValues.Add(value);
        };            
    }

    public EnumComparer(IList<TEnum> reorderedValues = null) {
        if (_reorderedValues == null ) {
            _reorderedValues = new List<TEnum>();

            return;
        }

        _reorderedValues = reorderedValues;
    }

    public void Add(TEnum value) {
        if (_reorderedValues.Contains(value))
            return;

        _reorderedValues.Add(value);
    }

    public int Compare(TEnum x, TEnum y) {
        var xIndex = ReorderedValues.IndexOf(x);
        var yIndex = ReorderedValues.IndexOf(y);

        // no such enums in our order list:
        // so this enum values must be in the end
        //   and must be ordered between themselves by default

        if (xIndex == -1) {
            if (yIndex == -1) {
                xIndex = TypicalValues.IndexOf(x);
                yIndex = TypicalValues.IndexOf(y);
                return xIndex.CompareTo(yIndex);                
            }

           return -1;
        }

        if (yIndex == -1) {
            return -1; //
        }

        return xIndex.CompareTo(yIndex);
    }

    public void Clear() {
        _reorderedValues = new List<TEnum>();
    }

    private IEnumerable<TEnum> GetEnumerable() {
        return Enumerable.Concat(
            ReorderedValues,
            TypicalValues.Where(v => !ReorderedValues.Contains(v))
        );
    }

    public IEnumerator<TEnum> GetEnumerator() {
        return GetEnumerable().GetEnumerator();            
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerable().GetEnumerator();            
    }
}

So, well, let's make sorting more faster. We need to override default OrderBy method for our enums:

public static class LinqEnumExtensions
{
    public static IEnumerable<TSource> OrderBy<TSource, TEnum>(this IEnumerable<TSource> source, Func<TSource, TEnum> selector, EnumComparer<TEnum> enumComparer) where TEnum : struct, IConvertible
    {
        foreach (var enumValue in enumComparer)
        {
            foreach (var sourceElement in source.Where(item => selector(item).Equals(enumValue)))
            {
                yield return sourceElement;
            }
        }
    }
}

Yeah, that's lazy. You can google how yield works. Well, let's test speed. Simple benchmark: http://pastebin.com/P8qaU20Y. Result for n = 1000000;

Enumerable orderBy, elementAt: 00:00:04.5485845
       Own orderBy, elementAt: 00:00:00.0040010
Enumerable orderBy, full sort: 00:00:04.6685977
       Own orderBy, full sort: 00:00:00.4540575

We see, that our own orderBy by is more lazy that standart order by (yeah, it doesn't need to sort everything). And faster even for fullsort.

Problems in this code: it doesn't support ThenBy(). If you need this, you can write your own linq extension that returns IOrderedEnumerable There are a blog post series by Jon Skeet which goes into LINQ to Objects in some depth, providing a complete alternative implementation. The basis of IOrderedEnumerable is covered in part 26a and 26b, with more details and optimization in 26c and 26d.

Answer 3

Instead of using an IComparer, you could also use a SelectMany approach, which should have better performance for large message lists, if you have a fixed number of message types.

var messageTypeOrder = new [] {
    MessageType.Boo,
    MessageType.Bar,
    MessageType.Foo,
    MessageType.Doo,
};

List<Message> tempList = messageTypeOrder
    .SelectMany(type => messageList.Where(m => m.MessageType == type))
    .ToList();

Answer 4

You may avoid writing a completely new type just to implement IComparable. Use the Comparer class instead:

IComparer<Message> comparer = Comparer.Create<Message>((message) =>
    {
    // lambda that compares things
    });
tempList.Sort(comparer);

Answer 5

You can build a mapping dictionary dynamically from the Enum values with LINQ like this:

  var mappingDIctionary = new List<string>((string[])Enum.GetNames(typeof(Hexside)))
                    .OrderBy(label => label )
                    .Select((i,n) => new {Index=i, Label=n}).ToList();

Now any new values added to the Enum n future will automatically get properly mapped.

Also, if someone decides to renumber, refactor, or reorder the enumeration, everything is handled automatically.

Update: As pointed out below, Alphabetical ordering was not called for; rather a semi- alphabetical ordering, so essentially random. Although not an answer to this particular question, this technique might be useful to future visitors, so I will leave it standing.

Answer 6

No need to have the mapping. This should give you the list and order based on the enum. You don't have to modify anything even when you change the enum's order or and new items...

var result = (from x in tempList
              join y in Enum.GetValues(typeof(MessageType)).Cast<MessageType>()
              on x equals y
              orderby y
              select y).ToList();

Answer 7

If you are about to get this working with Entity Framework (EF), you would have to spread out your enum in your OrderBy as such:

messageList.OrderBy(m => 
    m.MessageType == MessageType.Boo ? 0 :
    m.MessageType == MessageType.Bar ? 1 :
    m.MessageType == MessageType.Foo ? 2 :
    m.MessageType == MessageType.Doo ? 3 : 4
);

This creates a sub select with CASE WHEN, then ORDER BY on that temporary column.