Alternative for SortedSet<T> in Portable Class Library?

Question

Are there any alternatives in PCL for SortedSet<T>? Or must I implement my own?

I need an indexed list of non-duplicated strings that I can search through within a PCL that supports .NET 4.0. My current workaround is to rely on a List<T> object, call its Sort method and use BinarySearch method. It works, but I was hoping I could do better.

Answer 1

There are no "Sorted" collections in that PCL profile. So, you'd either have to call the Sort method on another collection to get it sorted or write your own sorted collection. If all you need is a collection, you could use a simple binary search/insertion to sort items as they are added to the collection. An example using a backing List<T> might look like this:

public class SortedCollection<T> : ICollection<T>
{
    private readonly List<T> collection = new List<T>();
    // TODO: initializable:
    private readonly IComparer<T> comparer = Comparer<T>.Default;

    public void Add(T item)
    {
        if (Count == 0)
        {
            collection.Add(item);
            return;
        }
        int minimum = 0;
        int maximum = collection.Count - 1;

        while (minimum <= maximum)
        {
            int midPoint = (minimum + maximum) / 2;
            int comparison = comparer.Compare(collection[midPoint], item);
            if (comparison == 0)
            {
                return; // already in the list, do nothing
            }
            if (comparison < 0)
            {
                minimum = midPoint + 1;
            }
            else
            {
                maximum = midPoint - 1;
            }
        }
        collection.Insert(minimum, item);
    }

    public bool Contains(T item)
    {
        // TODO: potential optimization
        return collection.Contains(item);
    }

    public bool Remove(T item)
    {
        // TODO: potential optimization
        return collection.Remove(item);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return collection.GetEnumerator();
    }

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

    public void Clear()
    {
        collection.Clear();
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        collection.CopyTo(array, arrayIndex);
    }

    public int Count { get { return collection.Count; } }
    public bool IsReadOnly { get { return false; } }
}

I've done the minimum to get a sorted collection that is functional. You can optimize so that Contains and Remove recognize the list is sorted and do a O(log n) search instead of a an O(n)...

There are other algorithms that might be faster; but without much more to go on, I chose a simple and well understood algorithm.