C#: Generic sorted container that can return the sorted position of a newly added object?

Question

I need a generic container that keeps its elements sorted and can be asked where (at which position) it would insert a new element, without actually inserting it.

Does such a container exist in the .NET libraries? The best illustration is an example (container sorts characters by ASCII value, let's assume unicode does not exist):

sortedContainer.Add('d');
sortedContainer.Add('b');
sortedContainer.Add('g');

//container contains elements ordered like 'b' 'd' 'g'
//index  -------------------------------->  0   1   2

sortedContainer.GetSortedIndex('a'); //returns 0
sortedContainer.GetSortedIndex('b'); //returns 0

sortedContainer.GetSortedIndex('c'); //returns 1
sortedContainer.GetSortedIndex('d'); //returns 1

sortedContainer.GetSortedIndex('e'); //returns 2
sortedContainer.GetSortedIndex('f'); //returns 2
sortedContainer.GetSortedIndex('g'); //returns 2

sortedContainer.GetSortedIndex('h'); //returns 3
[...]

The search for the position should take advantage of the fact that the elements are sorted.

Answer 1

If you sort a List<T> and then use List<T>.BinarySearch it will give you the index of the entry if it exists, or the bitwise complement of the index of where it would be inserted if you inserted then sorted. From that, you should easily be able to build your method.

Sample code matching your example, but not the results - if you look at your sample, you've only got 3 entries, so it doesn't make sense for 'h' to return 4 or 'g' to return 3. I hope that's your example which is slightly off, rather than me misunderstanding the problem :) Note that the sorting isn't automatic - you'd have to sort the list explicitly before calling GetSortedIndex.

using System;
using System.Collections.Generic;

static class Test
{
    static int GetSortedIndex<T>(this List<T> list, T entry)
    {
        int index = list.BinarySearch(entry);
        return index >= 0 ? index : ~index;
    }

    static void Main()
    {
        List<char> container = new List<char> { 'b', 'd', 'g' };
        Console.WriteLine(container.GetSortedIndex('a'));
        Console.WriteLine(container.GetSortedIndex('b'));
        Console.WriteLine(container.GetSortedIndex('c'));
        Console.WriteLine(container.GetSortedIndex('d'));
        Console.WriteLine(container.GetSortedIndex('e'));
        Console.WriteLine(container.GetSortedIndex('f'));
        Console.WriteLine(container.GetSortedIndex('g'));
        Console.WriteLine(container.GetSortedIndex('h'));
    }
}

Answer 2

The closest class to what you are looking for is SortedList<TKey,TValue>. This class will maintain a sorted list order.

However there is no method by which you can get the to be added index of a new value. You can however write an extension method that will give you the new index

public int GetSortedIndex<TKey,TValue>(this SortedList<TKey,TValue> list, TKey key) {
  var comp = list.Comparer;
  for ( var i = 0; i < list.Count; i++ ) {
    if ( comp.Compare(key, list.GetKey(i)) < 0 ) {
      return i;
    }
  }
  return list.Count;
}

Answer 3

Sounded like a fun test, so I gave it a shot. Probably not the most elegant, and not the most efficient either, but this should work:

 public class SortedContainer<T> : IList<T> where T : IComparable<T>
    {
        private List<T> internalList = new List<T>();

        public int IndexOf(T item)
        {
            return internalList.IndexOf(item);
        }

        public void Insert(int index, T item)
        {
            internalList.Insert(index, item);
        }

        public void RemoveAt(int index)
        {
            internalList.RemoveAt(index);
        }

        public T this[int index]
        {
            get
            {
                return internalList[index];
            }
            set
            {
                internalList[index] = value;
            }
        }

        public void Add(T item)
        {
            internalList.Add(item);
            this.Sort();
        }

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

        public bool Contains(T item)
        {
            return internalList.Contains(item);
        }

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

        public int Count
        {
            get { return internalList.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(T item)
        {
            bool result = internalList.Remove(item);
            this.Sort();
            return result;
        }



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

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return internalList.GetEnumerator();
        }

        private void Sort()
        {
            internalList.Sort();
        }

        private List<T> GetCopy()
        {
            return internalList.ToList();
        }

        public int GetSortedIndex(T item)
        {
            List<T> copy = GetCopy();
            copy.Add(item);
            copy.Sort();
            return copy.IndexOf(item);
        }

    }

Basically, implement IList, and keep an internatl List. Every time the Add method is called, you call sort on the internal list. Then, when you want to get the sorted index without actually adding, it creates a copy of that list, inserts the item into the copy, then sorts the copy. It then returns the index of that item where it is in the copy. The internal list at this point has not been affected. I tested it and it works.

Again, probably not the most efficient.