How to access BinarySearch() method in IList to List initialization without breaking program to interface rule

Question

I have a code snippet and I am not able to take the advantage of program to interface instead of implementation. In below scenario, I am not able to perform binary search on "listOne". Is there any other way other than IList<int> to List<int> initialization?.

IList<int> listOne = new List<int>();
List<int> listTwo = new List<int>();

// some code goes here.

// Below statement invalid.
//int itemFoundIndex = listOne.BinarySearch(5);

int itemFoundIndex = listTwo.BinarySearch(5);

Update:

In design point of view when we have this kind of situation, Do we need to worry about program to interface or not? Asked this question mocking and unit tests point of view as well.

Answer 1

This is a thorny issue with .NET collections. The hierarchies are not designed well. I think it is reasonable to assume that not each IList derived class can implement BinarySearch efficiently. The BCL should contain an interface ISupportsBinarySearch and an extension method that uses that interface if available and implements it's own binary search if not.

The Enumerable.Count extension method does just that. It delegates to ICollection.Count if available.

Given that the BCL does not have this feature that I just proposed you need to do some work yourself. Write yourself an extension method that does binary search on any IList. In that method runtime test whether the passed-in IList is in fact a List. If that is the case delegate to the List.BinarySearch method.

Answer 2

Because the Refrence Source is available I looked in to how Array.BinarySearch does it's work. It is not a complex method so I wrote my own extension method that tries the built in searches first but if it can't find them it then does its own Binary Search on the IList.

public static class ExtensionMethods
{
    [Pure]
    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
    public static int BinarySearch<T>(IList<T> list, T value)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        Contract.Ensures((Contract.Result<int>() >= 0) && Contract.Result<int>() <= (list.Count > 0 ? list.Count - 1 : 0) || (Contract.Result<int>() < 0 && ~Contract.Result<int>() <= list.Count));
        Contract.EndContractBlock();
        return BinarySearch(list, 0, list.Count, value, null);
    }

    [Pure]
    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
    public static int BinarySearch<T>(IList<T> list, T value, IComparer<T> comparer)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        Contract.EndContractBlock();
        return BinarySearch(list, 0, list.Count, value, comparer);
    }

    [Pure]
    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
    public static int BinarySearch<T>(IList<T> list, int index, int length, T value, IComparer<T> comparer)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        Contract.EndContractBlock();

        //Try one of the existing implementations of BinarySearch before we do our own.
        var asListT = list as List<T>;
        if (asListT != null)
            return BinarySearch(list, index, length, value, comparer);

        var asTypedArray = list as T[];
        if (asTypedArray != null)
            Array.BinarySearch<T>(asTypedArray, index, length, value, comparer);

        var asUntypedArray = list as Array;
        if (asUntypedArray != null)
        {
            if (comparer != null)
            {
                IComparer nonGenericComparer = comparer as IComparer ?? new ComparerWrapper<T>(comparer);
                return Array.BinarySearch(asUntypedArray, index, length, value, nonGenericComparer);
            }
            else
            {
                return Array.BinarySearch(asUntypedArray, index, length, value, null);
            }
        }

        if (index < 0 || length < 0)
            throw new ArgumentOutOfRangeException((index < 0 ? "index" : "length"), "argument is less than 0.");
        if (list.Count - index < length)
            throw new ArgumentException("index and length do not specify a valid range in the list.");



        if (comparer == null) 
            comparer = Comparer<T>.Default;


        int lo = index;
        int hi = index + length - 1;
        while (lo <= hi)
        {
            // i might overflow if lo and hi are both large positive numbers. 
            int i = GetMedian(lo, hi);

            int c;
            try
            {
                c = comparer.Compare(list[i], value);
            }
            catch (Exception e)
            {
                throw new InvalidOperationException("Comparer failed", e);
            }
            if (c == 0) return i;
            if (c < 0)
            {
                lo = i + 1;
            }
            else
            {
                hi = i - 1;
            }
        }
        return ~lo;
    }

    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
    private static int GetMedian(int low, int hi)
    {
        // Note both may be negative, if we are dealing with arrays w/ negative lower bounds.
        Contract.Requires(low <= hi);
        Contract.Assert(hi - low >= 0, "Length overflow!");
        return low + ((hi - low) >> 1);
    }
}

class ComparerWrapper<T> : IComparer
{
    private readonly IComparer<T> _comparer;

    public ComparerWrapper(IComparer<T> comparer)
    {
        _comparer = comparer;
    }

    public int Compare(object x, object y)
    {
        return _comparer.Compare((T)x, (T)y);
    }
}