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?

Answer 1

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));      } }