7

I'm making an interval collection extension of the famous C# library C5. The IInterval interface defines an interval with comparable endpoints (irrelevant members removed):

public interface IInterval<T> where T : IComparable<T>
{
    T Low { get; }
    T High { get; }
}

This works well in general, since interval endpoints can be anything comparable like integers, dates, or even strings.

However, it is sometimes favorable to be able to calculate the duration of an interval. The interval [3:5) has a duration of 2, and the interval [1PM, 9PM) has a duration of 8 hours. This is not possible with comparables, since it only gives us the order of elements, not their distance, e.g. it is difficult to give the distance between two strings. The endpoint type basically has to be interval-scaled values.

Is there an interface like IComparable<T>, that allows me to compare endpoints in general, but also do stuff like subtracting two endpoints to get a duration, and adding a duration to a low endpoint to get the high endpoint that could be used for an inheriting interface, IDurationInterval<T> : IInterval<T> for instance?

Or more concise: is there an interface for interval-scaled values?

Mikkel R. Lund
  • 2,336
  • 1
  • 31
  • 44

1 Answers1

4

No such interface exists. Some languages, like Scala, have abstractions over these kinds of operations, but .NET has none. Also, I've found that the .NET library designers are fairly conservative when it comes to adding levels of abstraction: it seems they tend to prefer simple and concrete over complex and abstract. They've never added this abstraction presumably because there's never been a pressing need for it in any of the .NET Framework's libraries. Also, it's an abstraction that can cause a lot of overhead if used improperly.

However, nothing in .NET's type system precludes such an interface. It would need two type parameters instead of one: one for the implementing type, and one of the result type. The most basic interface might look like this:

interface IAlgebraic<T, R> {
  T Add(R value)
  R Subtract(T value)
}

Unfortunately, there's no way to add this interface to existing types, like Int32 and DateTime. For those types, you'd need a corollary to IComparable<T>'s Comparer<T>.

interface IAlgebraicOps<T, R> {
  T Add(T x, R y)
  R Subtract(T x, T y)
}
Nimrand
  • 1,748
  • 2
  • 16
  • 29
  • This is also my best idea so far. My worries are that this would add too much of an overhead, but it might just make enough sense to do it. You could probably make an interface like `IDurationInterval` with the methods `T Add(R difference)`, `T Subtract(R difference)` and `R Difference(T other)`. This, however, still has its downsides, as you still wouldn't be able to find the middle value of an interval. But I do like the overall idea! – Mikkel R. Lund Jul 20 '15 at 00:32
  • The overhead of making an virtual method call via an interface is only large when compared to a simple add processor instruction that can be used for simple data types like ints. Unless you're expecting to do millions of calculations a second, I doubt you'd notice the difference. – Nimrand Jul 20 '15 at 00:47
  • The mention about the midpoint brings up another good point. While you can abstract over mathematical operations like add and subtract, it's difficult to know where to stop. Scala's generic interface, Numeric, has operations for comparison, add, subtract, multiply, aboslute, one, and zero. Int, Long, Float, and Double can support all these, but only the first 3 make sense for DateTime. In reality, there's a hierarchy of interfaces that could be made. At its base is Comparable. There is an interface support add, subtract, and similar operations. – Nimrand Jul 20 '15 at 00:56
  • Adding to that, it's actually possible to calculate the mid point using this interface, provided that R supports a division operation (through a second interface, e.g., IDivisible). To calculate the midpoint, you'd simply use interval.Low.Add(interval.High.Subtract(interval.Low).Divide(2)). If you prefer, I can elaborate on this in my answer, but your original question didn't include this capability. – Nimrand Jul 20 '15 at 01:07
  • You are totally right; it is a matter of where you want to stop. Though, I think you could get far with the basic operations I listed above. To get back to the concern on the performance: if you need to divide for instance a `DateTime`, you would have to wrap it in an interface for division, giving you another degree of indirection. My fear is that those things quickly add up. I have seen the midpoint used for binary searches in `DateTime`s, so it is not unimaginable, but maybe not very useful in a general library... – Mikkel R. Lund Jul 20 '15 at 01:44
  • 1
    Abstract Algebra has actually already analyzed and delineated the possible abstractions to a great deal of detail. But, I think for most practical purposes, an interface hierarchy of IComparable > IAddSubtract > INumeric (for multiplication, zero, one, and absolute) > IDivisible (for division support) captures just about anything could need (barring better names). – Nimrand Jul 20 '15 at 01:55
  • I don't know if I would fear things "quickly adding up". You're talking about a linear increase in overhead that is quite minuscule in the grand scheme of things. The time complexity of the algorithms involved would not be affected. For example, searching a collection of 65,536 elements requires at most 16 midpoint calculations. That's 16 * 3 = 48 virtual interface calls. That's nothing. – Nimrand Jul 20 '15 at 02:01
  • That said, I still don't quite follow exactly what you're hoping to accomplish by using Intervals and collections. You've defined an Interval as basically being a range of a given set of values (such as Ints, DateTimes, etc.). How does it relate to collections? I can think of many ways in which these might be used together, but I can't tell which one you're driving at. Context is important when considering performance. How do you expect your library to be used, and what are the performance requirements? – Nimrand Jul 20 '15 at 02:04
  • The library contains interval collections, which are basically collections of intervals, that allow you to quickly retrieve or count all intervals in the collection overlapping a point/interval. This could for instance be used in a calendar to find all event happing today. The details of the intervals can be abstracted away for many operations on the intervals themselves - not the collections. So operations like `Overlaps` or `Contains` are implemented in a static extension class, so users can use it on their own implementations of `IInterval`. But other algorithms could need the duration. – Mikkel R. Lund Jul 20 '15 at 02:17
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/83698/discussion-between-nimrand-and-lund-mikkel). – Nimrand Jul 20 '15 at 02:20
  • Re: _"Unfortunately, there's no way to add this interface to existing types"_. This is certainly true. Of course this problem [could be solved with another layer of indirection](http://stackoverflow.com/questions/288623/level-of-indirection-solves-every-problem): Where type `T` does not implement that interface, write a wrapper type `TProxy` for it that *does* implement the interface. Add an implicit type cast operator to `TProxy` from `T` and you're almost there. – stakx - no longer contributing Jul 20 '15 at 08:00
  • 1
    I starting working on the interface, when it suddenly hit me, that the endpoints must be interval-scaled values: https://en.wikipedia.org/wiki/Level_of_measurement#Interval_scale. I've updated the question accordingly. – Mikkel R. Lund Aug 05 '15 at 05:57