A collection of ranges

Question

Imagine a scenario where, using xml, the user is able to specify ranges in a flexible manner, using any combination of "gte", "gt", "lte", "lt" or "eq".

Here are some examples

<rangeElement gte="0" lt="5" ... />
<rangeElement gt="3" lte="7" ... />
<rangeElement eq="5" ... />
<rangeElement gt="10.5" ... />

Now what I need is two classes, Range and RangeCollection, that can deal with these.

The Range class might look something like this:

public class Range
{
   public LowerBoundInclusive { get; set; }
   public LowerBoundExclusive { get; set; }
   public UpperBoundInclusive { get; set; }
   public UpperBoundExclusive { get; set; }
   public object Data { get; set; }

   public Range(XElement xmlElement)
   {
      ....
   }
}

The RangeCollection class should have some basic way of sorting its ranges, detecting overlaps and returning a corresponding range given a value.

I've had a play with this but things quickly get fiendishly complex. Has anyone else seen a implementation of this, or want to give it a shot?

BTW. I know there are similar threads that tackle ranges but they do not adequately deal with the difference between "less-than-or-equal" and "less-than".

Answer 1

What you need is interval tree. It is not hard to find implementation in C# and modify it to make it suitable to your needs. I don't see any problems with "<=" or just "<" relations.