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