LocateRange_snippit.cs

    (int, int) LocateRange<TKey, TValue> (SortedList<TKey, TValue> list, Func<Tkey, bool> beforeRange, Func<Tkey, bool> inRange, Func<Tkey, bool> afterRange)
    {
        //
        // searches list for the range of items that meet the specified criteria
        // returns (-1, -1) if nothing found or the indices if it is
        //
        // example searching a string keyed list by items that start with some value:
        //
        // given:
        //
        //     var list = SortedList<string, ...>
        //     string term
        //
        // call:
        //
        //     let (var startIndex, var endIndex) = LocateRange(
        //         list,
        //         item => string.Compare(term, item) < 0 && !item.StartsWith(term),
        //         item => item.StartsWith(term),
        //         item => string.Compare(term, item) > 0
        //         );
        //
        
        var comparer = list.Comparer;
        var length = list.Count;
        
        // Implementation: joint binary search.
        (int, int) SearchFirst(int i, int j, bool foundFirst, bool foundLast)
        {
            bool IsFirstFound(int index) => isInRange(list.Keys[index]) && (index < 1 || !isInRange(list.Keys[index - 1]));
            bool CutLeft(int index) => beforeRange(list.Keys[index]) || IsFirstFound(index);

            foundFirst = foundFirst || IsFirstFound(i);
            if (i > j) return (-1, -1);
            if (foundFirst && foundLast) return (i, j);

            if (!foundFirst) 
            {
                i++;
                var testIndex = i + ((j - i) >> 1);
                if (CutLeft(testIndex)) i = testIndex; 
            }

            (int, int) SearchLast(int i, int j, bool foundFirst, bool foundLast)
            {
                bool IsLastFound(int index) => isInRange(list.Keys[index]) && (index > length - 2 || !isInRange(list.Keys[index + 1]));
                bool CutRight(int index) => afterRange(list.Keys[index]) || IsLastFound(index);

                foundLast = foundLast || IsLastFound(j);
                
                if (!foundLast)
                {
                    j--;
                    var testIndex = j - ((j - i) >> 1);
                    if (CutRight(testIndex)) j = testIndex;
                }

                return SearchFirst(i, j, foundFirst, foundLast);
            }
            return SearchLast(i, j, foundFirst, foundLast);
        }

        return SearchFirst(0, length - 1, false, false);
    }