Is there a list that is sorted automatically in .NET?

Question

I have a collection of Layers where they have names and colors. What I want to do is to sort these first based on colors, then based on their names:

class Layer
{
    public string Name {get; set;}
    public LayerColor Color {get; set;}
}

enum LayerColor
{
    Red,
    Blue,
    Green
}

Like:

(red) layer2
(red) layer7
(blue) layer0
(blue) layer3
...

I was looking at SortedList but that acts like a Dictionary so doesn't allow for duplicate items.

Also I am using an API where I get the list of Layers by creation order, so I need to get the full list of Layers to sort them the way I want.

Eventually the list of Layers will be binded to a WPF UI where the users will have the ability to add new Layers, so that's why I wanted the internal list to always be sorted as the performance is not important (the number of Layers are less than a thousand).

In the end the Layers I sorted will be accessed via something like this:

class Image
{
    public MySortedList<Layer> Layers {get; set;}
}

What's the best way to do this?

Solution 1

Did you search for it? Generic SortedList and SortedList.

So I missed the duplicate part which make it a little bit harder I agree. But here is how I would solve it:

var sortedList = new SortedList<LayerColor, SortedList<Layer, Layer>>();
var redSortedList = new SortedList<Layer, Layer>();
// Add all layers associated with the color red
sortedList.Add(LayerColor.Red, redSortedList);

Will that work for you. Also, I would prefer to use linq but if you really want a sorted list my solution will most likely work.

Last try:) :

public class YourClass
{
    private List<Layer> _layers;
    public List<Layer> Layers
    {
        get
        {
            _layers = _layers.OrderBy(y => y.LayerColor).ThenBy(y => y.Name).ToList();
            return _layers;
        }
        set
        {
            _layers = value;
        }
    }
}

Note that I'm writing directly in browser without testing it in VS (sitting on OS X), but you probably get the point.

Solution 2

A little late to the party, but up for posterity's sake.

in order to optimise separation of concerns, I wrote a wrapper class which keeps a list sorted (and allows duplicates), as below:

public class OrderedList<T> : IList<T>, ICollection<T>, IList, ICollection, IReadOnlyList<T>, IReadOnlyCollection<T>, IEnumerable<T>, IEnumerable
{
    #region Fields
    readonly List<T> _list;
    readonly IComparer<T> _comparer;
    #endregion

    #region Constructors
    OrderedList(List<T> list, IComparer<T> comparer)
    {
        _list = list;
        _comparer = comparer;
    }
    public OrderedList() 
        : this(new List<T>(), Comparer<T>.Default)
    {
    }
    public OrderedList(IComparer<T> comparer)
        : this(new List<T>(), comparer)
    {
    }
    public OrderedList(IEnumerable<T> collection)
        : this(collection, Comparer<T>.Default)
    {
    }

    public OrderedList(IEnumerable<T> collection, IComparer<T> comparer)
        : this(new List<T>(collection), comparer)
    {
        _list.Sort(comparer);
    }

    public OrderedList(int capacity)
        : this(new List<T>(capacity), Comparer<T>.Default)
    {
    }
    public OrderedList(int capacity, IComparer<T> comparer)
        : this(new List<T>(capacity), comparer)
    {
    }
    //yet to be implemented
    //public void OrderedList(Comparison<T> comparison);

    #endregion

    #region Properties
    public int Capacity { get { return _list.Capacity; } set { _list.Capacity = value; } }
    public int Count { get { return _list.Count; } }
    object IList.this[int index] { get { return _list[index]; } set { _list[index] = (T)value; } }
    public T this[int index] { get { return _list[index]; } set { _list[index] = value; } }
    //public bool IsSynchronized { get { return false; } }
    bool ICollection.IsSynchronized { get { return false; } }
    //public object SyncRoot { get { return _list; } }
    object ICollection.SyncRoot { get { return _list; } } //? should return this 
    bool IList.IsFixedSize { get { return false; } }
    bool IList.IsReadOnly { get { return false; } }
    bool ICollection<T>.IsReadOnly { get { return false; } }
    #endregion

    #region Methods
    void ICollection<T>.Add(T item)
    {
        Add(item);
    }
    /// <summary>
    /// Adds a new item to the appropriate index of the SortedList
    /// </summary>
    /// <param name="item">The item to be removed</param>
    /// <returns>The index at which the item was inserted</returns>
    public int Add(T item)
    {
        int index = BinarySearch(item);
        if (index < 0)
        {
            index = ~index;
        }
        _list.Insert(index, item);
        return index;
    }
    int IList.Add(object item)
    {
        return Add((T)item);
    }
    //NOT performance tested against other ways algorithms yet
    public void AddRange(IEnumerable<T> collection)
    {
        var insertList = new List<T>(collection);
        if (insertList.Count == 0) 
        {
            return;
        }
        if (_list.Count == 0) 
        { 
            _list.AddRange(collection);
            _list.Sort(_comparer);
            return;
        }
        //if we insert backwards, index we are inserting at does not keep incrementing
        insertList.Sort(_comparer);
        int searchLength = _list.Count;
        for (int i=insertList.Count-1;i>=0;i--)
        {
            T item = insertList[i];
            int insertIndex = BinarySearch(0, searchLength, item);
            if (insertIndex < 0)
            {
                insertIndex = ~insertIndex;
            }
            else
            {
                while (--insertIndex>=0 && _list[insertIndex].Equals(item)) { }
                insertIndex++;
            }
            if (insertIndex<=0)
            {
                _list.InsertRange(0, insertList.GetRange(0, i+1 ));
                break;
            }
            searchLength = insertIndex-1;
            item = _list[searchLength];
            int endInsert = i;
            while (--i>=0 && _comparer.Compare(insertList[i], item) > 0) { }
            i++;
            _list.InsertRange(insertIndex, insertList.GetRange(i, endInsert - i +1));
        }
    }
    public int BinarySearch(T item)
    {
        return _list.BinarySearch(item, _comparer);
    }
    public int BinarySearch(int index, int count, T item)
    {
        return _list.BinarySearch(index,count,item, _comparer);
    }
    public ReadOnlyCollection<T> AsReadOnly()
    {
        return _list.AsReadOnly();
    }
    public void Clear() { _list.Clear(); }
    public bool Contains(T item) { return BinarySearch(item) >= 0; }
    bool IList.Contains(object item)
    {
        return Contains((T)item);
    }
    public List<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter) { return _list.ConvertAll(converter); }
    public void CopyTo(T[] array) { _list.CopyTo(array); }
    public void CopyTo(T[] array, int arrayIndex) { _list.CopyTo(array,arrayIndex); }
    void ICollection.CopyTo(Array array, int arrayIndex) { _list.CopyTo((T[])array, arrayIndex); }
    public void CopyTo(int index, T[] array, int arrayIndex, int count) { _list.CopyTo(index, array, arrayIndex, count); }
    public void ForEach(Action<T> action)
    {
        foreach (T item in _list)
        {
            action(item);
        }
    }

    IEnumerator IEnumerable.GetEnumerator() { return _list.GetEnumerator(); }
    public IEnumerator<T> GetEnumerator() { return _list.GetEnumerator(); }
    public List<T> GetRange(int index, int count) { return _list.GetRange(index,count); }

    public bool Remove(T item) 
    {
        int index = BinarySearch(item);
        if (index < 0)
        {
            return false;
        }
        _list.RemoveAt(index);
        return true;
    }
    void IList.Remove(object item)
    {
        Remove((T)item);
    }

    public void RemoveAt(int index) { _list.RemoveAt(index); }
    public void RemoveRange(int index, int count) { _list.RemoveRange(index, count); }
    public T[] ToArray() { return _list.ToArray(); }
    public void TrimExcess() { _list.TrimExcess(); }
    /// <summary>
    /// Find the first index of the given item
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public int IndexOf(T item)
    {
        int index = BinarySearch(item);
        if (index < 0) return -1;
        while(--index >= 0 && _list[index].Equals(item)){}
        return index+1;
    }

    int IList.IndexOf(object item)
    {
        return IndexOf((T)item);
    }
    /// <summary>
    /// Find the last index of the given item
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public int LastIndexOf(T item)
    {
        int index = BinarySearch(item);
        if (index < 0) return -1;
        while (++index < _list.Count && _list[index].Equals(item)) { }
        return index-1;
    }

    /// <summary>
    /// Return all values within bounds specified
    /// </summary>
    /// <param name="min">Minimum Bound</param>
    /// <param name="max">Maximum Bound</param>
    /// <returns>subset of list with values within or equal to bounds specified</returns>
    public T[] WithinRange(T min, T max)
    {
        if (_comparer.Compare(min,max) > 0)
        {
            throw new ArgumentException("min must be <= max");
        }
        int minSearchLength;
        int maxIndex = _list.BinarySearch(max, _comparer);
        if (maxIndex >= 0)
        {
            minSearchLength = maxIndex + 1;
            while (++maxIndex < _list.Count && _comparer.Compare(max, _list[maxIndex]) == 0) { }
            --maxIndex;
        }
        else
        {
            minSearchLength = ~maxIndex;
            if (minSearchLength <= 0)
            {
                return new T[0];
            }
            maxIndex = minSearchLength - 1;
        }

        int minIndex = _list.BinarySearch(0, minSearchLength, min, _comparer);
        if (minIndex >= 0)
        {
            while (--minIndex >= 0 && _comparer.Compare(max, _list[minIndex]) == 0) { }
            ++minIndex;
        }
        else
        {
            minIndex = ~minIndex;
            if (minIndex > maxIndex)
            {
                return new T[0];
            }
        }
        int length = maxIndex - minIndex + 1;
        var returnVar = new T[length];
        _list.CopyTo(minIndex, returnVar, 0, length);
        return returnVar;

    }
    #endregion

    #region NotImplemented
    const string _insertExceptionMsg = "SortedList detemines position to insert automatically - use add method without an index";
    void IList.Insert(int index, object item)
    {
        throw new NotImplementedException(_insertExceptionMsg);
    }
    void IList<T>.Insert(int index, T item)
    {
        throw new NotImplementedException(_insertExceptionMsg);
    }
    #endregion
}

Tests written are not extensive (or pretty) but are included in case anyone wanted to expand on them

[TestClass]
public class TestOrderedList
{
    [TestMethod]
    public void TestIntegerList()
    {
        var startList = new List<int>(new int[] { 5, 2, 1, 4, 5, 5, 2 });
        var olist = new OrderedList<int>(startList);
        startList = startList.OrderBy(l => l).ToList();
        CollectionAssert.AreEqual(startList, olist);
        Assert.AreEqual(0, olist.Add(0));
        int nextInc = olist.Max() + 1;
        Assert.AreEqual(olist.Count, olist.Add(nextInc));
        CollectionAssert.AreEqual(startList.Concat(new int[] { 0, nextInc }).OrderBy(l => l).ToList(), olist);
        Assert.IsTrue(olist.Remove(0));
        Assert.IsFalse(olist.Remove(0));
        Assert.IsTrue(olist.Remove(nextInc));
        CollectionAssert.AreEqual(startList, olist);

        var addList = new List<int>(new int[] { 5, -1, 2, 2, -1, 3, 2 });
        olist.AddRange(addList);
        addList = startList.Concat(addList).OrderBy(l => l).ToList();
        CollectionAssert.AreEqual(addList, olist);
        olist.Remove(-1);
        addList.Remove(-1);
        CollectionAssert.AreEqual(addList, olist);
        olist.Remove(2);
        addList.Remove(2);
        CollectionAssert.AreEqual(addList, olist);

        olist = new OrderedList<int>();
        int[] seed = new int[] { -2, -2 };
        olist.AddRange(seed);
        CollectionAssert.AreEqual(seed, olist);
        olist.AddRange(new int[] { });
        olist.AddRange(new int[] { -2 });
        CollectionAssert.AreEqual(seed.Concat(new int[] { -2 }).ToList(), olist);
        olist.AddRange(new int[] { -3 });
        CollectionAssert.AreEqual((new int[] { -3, -2 }).Concat(seed).ToList(), olist);
    }

    [TestMethod]
    public void TestIndexOf()
    {
        var test = new OrderedList<int>(new[] { 0, -1, -2 });
        Assert.AreEqual(0, test.IndexOf(-2));
        Assert.AreEqual(2, test.IndexOf(0));
        test.Add(-2);
        Assert.AreEqual(0, test.IndexOf(-2));
        Assert.AreEqual(1, test.LastIndexOf(-2));
        test.Add(0);
        Assert.AreEqual(3, test.IndexOf(0));
        Assert.AreEqual(4, test.LastIndexOf(0));
    }

    [TestMethod]
    public void TestRangeFinding()
    {
        var test = new OrderedList<int> { 2 };
        CollectionAssert.AreEqual(new[] { 2 }, test.WithinRange(0, 6));
        CollectionAssert.AreEqual(new[] { 2 }, test.WithinRange(0, 2));
        CollectionAssert.AreEqual(new[] { 2 }, test.WithinRange(2, 4));
        CollectionAssert.AreEqual(new int[0], test.WithinRange(-6, 0));
        CollectionAssert.AreEqual(new int[0], test.WithinRange(6, 8));

        test = new OrderedList<int>();
        CollectionAssert.AreEqual(new int[0], test.WithinRange(6, 8));

        test = new OrderedList<int>{ -4, -2, 0 ,4, 6, 6 };
        CollectionAssert.AreEqual(new[] { 0, 4 }, test.WithinRange(0, 4));
        CollectionAssert.AreEqual(new[] { 0, 4 }, test.WithinRange(-1, 5));
        CollectionAssert.AreEqual(new[] { 6, 6 }, test.WithinRange(6, 8));
        CollectionAssert.AreEqual(new[] { 6, 6 }, test.WithinRange(5, 8));
        CollectionAssert.AreEqual(new[] { -4, -2 }, test.WithinRange(-5, -1));
        CollectionAssert.AreEqual(new[] { -4, }, test.WithinRange(-4, -3));
        CollectionAssert.AreEqual(new int[0], test.WithinRange(-6, -5));

        Assert.ThrowsException<ArgumentException>(() => test.WithinRange(6, 4));

    }
}

Solution 3

You could use the regular List<T>, but call the Sort() method prior to displaying the list, and after new values are added. That should give you the functionality that you need. The performance will be good enough for this application.

Of course, you will have to define your own comparison for it to use, but that shouldn't be too much trouble.

If you don't have any hooks into the add event that can be used to sort the list, then you can wrap the list in a custom collection class as @Justin recommends.

Solution 4

If the sort is only for display purposes, let WPF handle it:

ICollectionView view = CollectionViewSource.GetDefaultView(Layers);
view.SortDescriptions.Add(new SortDescription("Color", ListSortDirection.Ascending);
view.SortDescriptions.Add(new SortDescription("Name", ListSortDirection.Ascending);

then just bind Layers to your UI ItemsControl.

Solution 5

using System.Linq, do:

from layer in layers
        orderby layer.Color, layer.Name
        select layer

View more solutions