RangeSet for .NET

Update 4/13 - Added support for single value ranges.

What data structure do you use when you need to efficiently check if a number is within a large set of ranges?

If you require that the ranges do not overlap, then it is simple to keep a balanced binary tree of the ranges. Finding if a number is within one of those ranges should only take O(log n) to find. Below is an implementation of a RangedSet that uses a standard .NET SortedSet to store the ranges.

IRangeSet Interface

public interface IRangeSet<in T> where T : IComparable

{

    void AddRange(T min, T max);

    bool Contains(T findValue);

}

Implementation

public class RangeSet<T> : IRangeSet<T> where T : IComparable

{

    private readonly SortedSet<RangeInfo> _set;

    public RangeSet()

    {

        var comparer = new Comparer();

        _set = new SortedSet<RangeInfo>(comparer);

    }

    public void AddRange(T min, T max)

    {

        var comparison = min.CompareTo(max);

        if (comparison > 0)

            throw new ArgumentException("Min must be less than Max");

        _set.Add(new RangeInfo

        {

            Min = min,

            Max = max

        });

    }

    public bool Contains(T findValue)

    {

        return _set.Contains(new RangeInfo

        {

            FindValue = findValue,

            IsFind = true

        });

    }

    private struct RangeInfo

    {

        public bool IsFind;

        public T FindValue;

        public T Min;

        public T Max;

    }

    private class Comparer : IComparer<RangeInfo>

    {

        public int Compare(RangeInfo x, RangeInfo y)

        {

            if (x.IsFind)

                return IsInRange(y, x.FindValue);

            if (y.IsFind)

                return IsInRange(x, y.FindValue) * -1;

            var xMaxComparedToYMin = x.Max.CompareTo(y.Min);

            var xMinComparedToYMax = x.Min.CompareTo(y.Max);

            if (xMaxComparedToYMin != 0 && xMinComparedToYMax != 0)

            {

                var xMaxGreaterThanYMin = xMaxComparedToYMin > 0;

                var xMinLessThanYMax = xMinComparedToYMax < 0;

                if (xMaxGreaterThanYMin ^ xMinLessThanYMax)

                    return xMaxGreaterThanYMin ? 1 : -1;

            }

            throw new InvalidOperationException("Cannot have overlapping ranges");

        }

        private static int IsInRange(RangeInfo rangeInfo, T find)

        {

            var isGreaterThanMin = find.CompareTo(rangeInfo.Min) >= 0;

            var isLessThanMax = find.CompareTo(rangeInfo.Max) <= 0;

            if (isGreaterThanMin && isLessThanMax)

                return 0;

            return isGreaterThanMin ? 1 : -1;

        }

    }

}

Unit Tests

public class RangeSetTests

{

    [Theory]

    [InlineData(2, 2, 3, 6, 1, false)]

    [InlineData(2, 2, 3, 6, 2, true)]

    [InlineData(2, 2, 3, 6, 3, true)]

    [InlineData(2, 3, 5, 6, 1, false)]

    [InlineData(2, 3, 5, 6, 2, true)]

    [InlineData(2, 3, 5, 6, 3, true)]

    [InlineData(2, 3, 5, 6, 4, false)]

    [InlineData(2, 3, 5, 6, 5, true)]

    [InlineData(2, 3, 5, 6, 6, true)]

    [InlineData(2, 3, 5, 6, 7, false)]

    public void FindInRange(int r1Min, int r1Max, int r2Min, int r2Max, int f, bool r)

    {

        var set = new RangeSet<int>();

        set.AddRange(r1Min, r1Max);

        set.AddRange(r2Min, r2Max);

        var result = set.Contains(f);

        Assert.Equal(r, result);

    }

    [Theory]

    [InlineData(1, 2)]

    [InlineData(1, 3)]

    [InlineData(1, 5)]

    [InlineData(1, 6)]

    [InlineData(2, 4)]

    [InlineData(2, 5)]

    [InlineData(2, 6)]

    [InlineData(3, 4)]

    [InlineData(3, 5)]

    [InlineData(3, 6)]

    [InlineData(4, 5)]

    [InlineData(4, 6)]

    [InlineData(5, 6)]

    public void NoOverlappingRanges(int min, int max)

    {

        var set = new RangeSet<int>();

        set.AddRange(2, 5);

        Assert.Throws<InvalidOperationException>(() => set.AddRange(min, max));

    }

    [Theory]

    [InlineData(1, 0)]

    [InlineData(2, 1)]

    [InlineData(3, 1)]

    public void MinMustBeLess(int min, int max)

    {

        var set = new RangeSet<int>();

        Assert.Throws<ArgumentException>(() => set.AddRange(min, max));

    }

}

Enjoy,
Tom