jeudi 21 février 2019

comparison of 2 ranges that may or may not have bounds

The problem is quite simple, yet it is very hard to come up with a solution that is not hundreds of lines of sphagetti else-ifs.

There are 2 ranges that may or may not have bounds, if there are bounds they may be inclusive or not.

pseudocode:

struct bound
{
    float val
    bool inclusive
}

struct range
{
    optional<bound> lower_bound
    optional<bound> upper_bound
}

For example, <3, 5] (numbers >3 and <= 5) would be range: { lower_bound: {3, false}, upper_bound: {5, true} } and [8, (numbers >= 8) would be range: { lower_bound: { 8, true }, upper_bound: null }

Given 2 ranges, decide on relation of the first range to the second (identical, subset, superset, intersect, disjoint) (example ranges above are disjoint since no value can be both <= 5 and >= 8)

enum relation { identical, subset, superset, intersect, disjoint }

relation_first_to_second(range first, range second): relation
{
     // ???
}

The problem is that when writing the function care must be taken to handle all possible corner cases, I have made a sample chart that showcases these cases (- means there is no bound). We can assume that ranges are always valid themselves, in others words we can assume that (if they exist) A is always less or equal to B and X is always less or equal to Y (but we can not assume relation between: A/X A/Y B/X B/Y).

lower upper   lower upper   relation first to second
  -     -       -     -      identical
  -     -       -     Y      superset
  -     -       X     -      superset
  -     -       X     Y      superset
  -     B       -     -      subset
  -     B       -     Y      B=Y: identical, B<Y: subset, B>Y superset
  -     B       X     -      B<X: disjoint, B>=X: intersect
  -     B       X     Y      B<X: disjoint, X<=B<=Y: intersect, B>Y: superset
  A     -       -     -      subset
  A     -       -     Y      A<=Y: intersect, A>Y: disjoint
  A     -       X     -      A=X: identical, A<X: superset, A>X: subset
  A     -       X     Y      A>Y: disjoint, X<=A<=Y: intersect, A<X: superset
  A     B       -     -      subset
  A     B       -     Y      Y<A: disjoint, A<=Y<=B: intersect, Y>B: subset
  A     B       X     -      X<A: subset, A<=X<=B: intersect, X>B: disjoint
  A     B       X     Y      this will be complex to check...

Note that this chart does not take inclusive into consideration.


If you have a better idea of implementing ranges themselves - you are welcome, just don't assume that <=3 is the same as <4 and don't rely on the fact that unbound range can use minimum/maximum value of integer (the actual problem domain is more generic). I can't think of any better representation than a type that consists of 2 bounds (each storing value and whether it's inclusive) that may or may not exist.


I'm looking for a code (any language or pseudocode) as short as possible that implements relation_first_to_second function. This is not a code golf, but I think "shortest code solution is best answer" is very relevant for this question.

Aucun commentaire:

Enregistrer un commentaire