Wednesday, June 12, 2013

C#: Inserting duplicates into sorted List

I wanted to have a sorted list, with the ability to have items duplicate, built in sorted collections doesn’t allow duplicate values, so I used a List, and for effeciancy, I maintained the items sorted in it while insertion, instead of calling the sort method with each insertion
To insert in the list sorted, I used the binary search method, to find the first item less then or equal to the inserted item

Suppose we have a sorted list “list”, and we want to insert item i keeping it sorted


    List<int> list= new List<int>();

    int index = list.BinarySearch(i);
    if (index < 0)
       list.Insert(~index, i);
    else
       list.Insert(index, i);

Another way of having sorted list with duplicates is to use a normal sorted list and a custom comparer

    public class DuplicateKeyComparer<TKey>:IComparer<TKey> where TKey : IComparable
    {
        public int Compare(TKey x, TKey y)
        {
            int result = x.CompareTo(y);

            if (result == 0)
                return 1;   // Handle equality as being greater
            return result;
        }
    }



Only draw back of this method is that we can't find elements or remove, we can only iterate over them, as using the above comparer would always return 1 and won't match any elements.