Modeling and computing intersection between continuous intervals

Question

I created the class ContinuousDimensionInterval, to model an interval of a continuous dimension interval, presented below.

namespace Minotaur.Math.Dimensions {
    using System;

    public sealed class ContinuousDimensionInterval: IDimensionInterval {

        public int DimensionIndex { get; }
        public readonly DimensionBound Start;
        public readonly DimensionBound End;

        public ContinuousDimensionInterval(
            int dimensionIndex,
            DimensionBound start, 
            DimensionBound end
            ) {
            if (dimensionIndex < 0)
                throw new ArgumentOutOfRangeException(nameof(dimensionIndex) + " must be >= 0.");

            DimensionIndex = dimensionIndex;
            Start = start;
            End = end;
        }

        public bool Contains(float value) {
            if (float.IsNaN(value))
                throw new ArgumentOutOfRangeException(nameof(value));

            if (value > Start.Value && value < End.Value)
                return true;
            if (Start.IsInclusive && value == Start.Value)
                return true;
            if (End.IsInclusive && value == End.Value)
                return true;

            return false;
        }
    }
}

I felt the need to create a struct, DimensionBound, to represent the bounds of an interval, since they may be inclusive or exclusive.

namespace Minotaur.Math.Dimensions {
    using System;

    public readonly struct DimensionBound {
        public readonly float Value;
        public readonly bool IsInclusive;

        public DimensionBound(float value, bool isInclusive) {
            if (float.IsNaN(value))
                throw new ArgumentOutOfRangeException(nameof(value) + " can't be NaN.");

            Value = value;
            IsInclusive = isInclusive;
        }
    }
}

I'd like to receive some feedback on the implementation of both classes.

1. Should I disallow the construction of DimensionBound with value=infinity and inclusive=true?
2. Is my decision to make DimensionBound a struct reasonable? It feels struct-like to me...
3. Should DimensionBound implement IEquatable<DimensionBound>?
4. Am I over-engineering the whole thing by creating a class to represent the bounds of an interval?

Here an example of how the class is used:

private static bool IntersectsContinuous(ContinuousDimensionInterval lhs, ContinuousDimensionInterval rhs) {
    // @Improve performance?
    // @Verify correctness
    var aStart= lhs.Start;
    var aEnd = lhs.End;

    var bStart = rhs.Start;
    var bEnd = rhs.End;

    if (aStart.Value > bEnd.Value)
        return false;
    if (aStart.Value == bEnd.Value)
        return aStart.IsInclusive && bEnd.IsInclusive;

    if (bStart.Value > aEnd.Value)
        return false;
    if (bStart.Value == aEnd.Value)
        return bStart.IsInclusive && aEnd.IsInclusive;

    return true;
}

Answer 1

Review

• You are constrained to float which makes your class only usable for a limited number of scenarios. I would like to be able to work with int, double, DateTime, MyCustomEntity, ..
• You should not need to care about special cases as unbounded or NaN. NaN should be filtered out beforehand, since it is unusable for comparison. Unbounded and bounded values should be compared by using the built-in interface IComparable.
• Intersection of continuous data when 2 edges match requires both edges to be IsInclusive in your specification. I would argue that only one of them should require this flag. Adjacent items that meet each other form an intersection ( [source required] ).
• Your struct is immutable, which is proper design. Whether or not to make a class instead, depends on how you would like to use this. I tend to prefer class more than struct. Note that a struct has an inherent default value, while a reference type is null by default. How would you distinguish a default value from a value that happens to have the same value? This is one reason to go with a class, unless you cope with this issue by using a Nullable<T> and accepting the overhead it provides.
• It is good practice to override GetHashCode() and Equals().

---

Suggestions

1201ProgramAlarm's answer suggests to use IComparable on DimensionBound, but I would use it on the generic type parameter.

public class DimensionBound<T> where T : IComparable<T>
{
    public readonly T Value;
    public readonly bool IsInclusive;

    public DimensionBound(T value, bool isInclusive)
    {
        Value = value;
        IsInclusive = isInclusive;
    }
}

The interval could then be refactored to compare the values. Note that I would provide a convenience constructor accepting an inclusive start and exclusive end (which is considered common practice when dealing with continuous data).

I would also favour instance methods over the static comparison. Furthermore, I would argue the purpose of the dimension in this class. I would remove it and call the class Interval. You can always create an additional class or use a tuple (int, Interval) to include the dimension.

public sealed class Interval<T> where T : IComparable<T>
{
    public readonly DimensionBound<T> Start;
    public readonly DimensionBound<T> End;

    public Interval(T start, T end)
        : this(ew DimensionBound<T>(start, true), new DimensionBound<T>(end, false))
    {
    }

    public Interval(DimensionBound<T> start, DimensionBound<T> end)
    {
        Start = start;
        End = end;
    }

    public bool Contains(T value)
    {
        // method body ..
    }

    public bool Intersects(Interval<T> other)
    {
        // method body ..
    }
}

If we don't change your specification and require both edges to be inclusive when 2 intervals meet, we could implement Intersects (Contains is similar) as follows (comments added for code review purposes only):

public bool Intersects(Interval<T> other)
{
    // compare start to other end
    var compareToStart = Start.Value.CompareTo(other.End.Value);

    // no intersection possible; instance starts after other is finished
    if (compareToStart == 1) return false;

    // both intervals meet but at least one of the bounds is exclusive, so no intersection
    if (compareToStart == 0 && !(Start.IsInclusive && other.End.IsInclusive)) return false;

    // compare end to other start
    var compareToEnd = End.Value.CompareTo(other.Start.Value);

    // no intersection possible; instance finishes before other is started
    if (compareToEnd == -1) return false;

    // both intervals meet but at least one of the bounds is exclusive, so no intersection
    if (compareToEnd == 0 && !(End.IsInclusive && other.Start.IsInclusive)) return false;

    return true;
}

This works with float, or any other IComparable<T>.

Assert.IsTrue(new Interval<float>(0, 1).Intersects(new Interval<float>(0.5f, 1.5f));

Answer 2

The ContinuousDimensionInterval constructor should validate that it has valid bounds, i.e. Start <= End (and if they are equal, at least one of them should be inclusive). This is more likely to be a programming or logic error than an attempt to create an empty interval (which may be something you want to more explicitly support by providing a SetEmpty member).

DimensionBound should have some sort of comparison operations defined for it. The full IComparable interface, not just IEquatable. This would also make validating the Start and End bounds of ContinuousDimensionInterval easier.

As for your specific questions:

1. Does it make sense that an interval will be unbounded (either positive or negative infinity)? I don't see a reason to restrict them to finite bounds.
2. A struct in C# is a value type, not a reference type, so it will always be copied when being passed around. There are other restrictions as well. Only you can decide if they are acceptable for you. (My personal preference would be to lean towards making it a class.)
3. As I mentioned above, you should implement the full IComparable interface for DimensionBound.
4. Nope. Small classes that do one thing are the building blocks to larger, more complicated objects.