29

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?

2
  • As you can see there are many answers to your question, but the question you should ask your self is why do you want to sort it. Of course I can understand why, but do you need performance or just a nice looking way to sort it? Sorry, missed that you said that performance is not important. Apr 19, 2011 at 20:12
  • Yes it's only for display purposes for a WPF UI.
    – Joan Venge
    Apr 19, 2011 at 20:17

8 Answers 8

24

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

    }
}
3
  • any updated or additions to this class? I like it and want to adopt it, however, there are some comment that suggest you wern't finished and/or were going to optimize this?
    – MoonKnight
    Jul 18, 2016 at 13:40
  • 1
    Looks as if you can just set values inside the list with orderedList[5] = 3; and then the sorting will no longer be valid. Apr 3, 2018 at 13:16
  • C# language should be implementing this by now. I'm surprised that there is no option in the libs for a sorted list or ordered list where duplicates are allowed. You can use a sorted dictionary but what about cases where you don't need key-value pairs? Jul 22, 2020 at 8:02
12

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.

6
  • 3
    I don't think GenericSortedList allows dupes does it?
    – Justin
    Apr 19, 2011 at 19:57
  • The "duplicate items" requirement makes this a bit trickier than usual. Apr 19, 2011 at 19:58
  • Of course he can use them, you just have to be a little bit creative. An update is coming. Apr 19, 2011 at 20:00
  • Thanks but if I do this then I have to handle the proper binding for WPF, right? Currently my hierarchy is flat so it's easy to bind.
    – Joan Venge
    Apr 19, 2011 at 20:10
  • 1
    Missed the part about performance, I'll update with how I would solve it if that is not a problem. Apr 19, 2011 at 20:15
2

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.

2

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.

2
  • Thanks, would this work for TreeViews too? I have a GridViewColumn but not sure where to put this.
    – Joan Venge
    Apr 19, 2011 at 20:07
  • Also can you please show this to me in xaml? I am trying to look it up but so far not much luck.
    – Joan Venge
    Apr 19, 2011 at 20:42
1

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

4
  • Is it better to inherit from Collection or List or IList?
    – Joan Venge
    Apr 19, 2011 at 20:08
  • @Joan: I would implement ICollection<T> or IList<T> (the latter if you need indexed access)
    – digEmAll
    Apr 19, 2011 at 20:12
  • Thanks digEmAll. I will probably do that or use Julien's WPF sorting method if I can get it working.
    – Joan Venge
    Apr 19, 2011 at 20:15
  • @digEmAll, ninjad by a day. It depends on what kind of access you need.
    – Justin
    Apr 21, 2011 at 18:43
1

using System.Linq, do:

from layer in layers
        orderby layer.Color, layer.Name
        select layer
4
  • I hope he is asking for the sorted list because he wants optimal performance when asking for the objects, and in that case I'm not sure linq will help since you have to sort them afterwars... but otherwise this is what I would suggest :) Apr 19, 2011 at 20:05
  • Thanks, how does orderby knows how to sort based on Color enum? Do I have to define it somewhere?
    – Joan Venge
    Apr 19, 2011 at 20:06
  • no you do not need to define, it will use the int value of color; with red = 0 and green = 2 Apr 19, 2011 at 20:14
  • Thanks, that's interesting too.
    – Joan Venge
    Apr 19, 2011 at 20:31
-2

Start by implementing the IComparable interface in Layer and declaring a CompareTo method. Then use a SortedList collection to store your object.

 public class Layer : IComparable {

    public int CompareTo(object obj) {
          //return -1 if this is before obj, 0 is same, 1 is after.
    }

 }
1
  • That's a partial solution, but somehow you have to identify a unique key. Apr 19, 2011 at 20:49
-3

You can use arraylist and do below linq query to sort them

ArrayList myList = new ArrayList();
            Layer obj1 = new Layer();
            obj1.Color = LayerColor.Red;
            obj1.Name = "Layer1";
            myList.Add(obj1);

            Layer obj2 = new Layer();
            obj2.Color = LayerColor.Green;
            obj2.Name = "Layer2";
            myList.Add(obj2);

            Layer obj3 = new Layer();
            obj3.Color = LayerColor.Blue;
            obj3.Name = "Layer3";
            myList.Add(obj3);

            Layer obj4 = new Layer();
            obj4.Color = LayerColor.Green;
            obj4.Name = "Layer4";
            myList.Add(obj4);


            var mySortedList = myList.OfType<Layer>().OrderBy(l => l.Color)
                         .ThenBy(l => l.Name);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.