[ACCEPTED]-Is there a list that is sorted automatically in .NET?-sorting

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

in order to optimise separation of 5 concerns, I wrote a wrapper class which 4 keeps a list sorted (and allows duplicates), as 3 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 2 pretty) but are included in case anyone 1 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));

    }
}

Did you search for it? Generic SortedList and SortedList.

So I missed 9 the duplicate part which make it a little 8 bit harder I agree. But here is how I would 7 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 6 would prefer to use linq but if you really 5 want a sorted list my solution will most 4 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 3 directly in browser without testing it in 2 VS (sitting on OS X), but you probably get 1 the point.

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

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

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

If the sort is only for display purposes, let 2 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 1 ItemsControl.

You're on the right track. I would create 5 a custom collection class that inherits 4 from Collection. In this custom collection 3 you can override on the on insert/on delete 2 methods and sort your collection as items 1 are added/removed from it.

using System.Linq, do:

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

0