Search code examples
raku

Is there an elegant way in Raku to see if two ranges overlap?


Is there an elegant way to see if two ranges have any overlap?

For instance, if

my $r = 1..10;
my $r1 = 2..5;
my $r2 = 7..15;

then $r1 ~~ $r is True. But $r ~~ $r1, $r2 ~~ $r, $r ~~ $r2 are all False.

Is there an elegant way to do this, and optionally even determine the overlap?

I can do (e.g.) $r ∩ $r1, but that creates a Set instead of a Range, and isn't feasible for huge ranges.

The following does the trick, but if there is a more elegant, built-in way, I'd prefer that.

sub infix:<∩>(Range $r1, Range $r2)
{
    my ($min1, $max1) = $r1.int-bounds;
    my ($min2, $max2) = $r2.int-bounds;
    return Nil if $max1 < $min2 || $max2 < $min1;
    return max($min1,$min2) .. min($max1,$max2);
}

my $r = 1..10;
my $r1 = 2..5;
my $r2 = 7..15;

say $r ∩ $r1;   # 2..5
say $r ∩ $r2;   # 7..10
say $r1 ∩ $r2;  # Nil

Solution

  • Here's how this works with my Math::Interval module:

    use Math::Interval;
    
    my $i0 = (1..10).Interval;
    my $i1 = (2..5).Interval;
    my $i2 = (7..15).Interval;
    
    ## smartmatch ~~ does the same as for Range ("x is contained by y")
    say $i1 ~~ $i0;  # True
    say $i0 ~~ $i1;  # False
    say $i2 ~~ $i0;  # False 
    say $i0 ~~ $i2;  # False
    
    # cmp returns Nil on overlap (ie overlaps are not ordered)
    say $i1 cmp $i0;  # Nil 
    say $i0 cmp $i1;  # Nil 
    say $i2 cmp $i0;  # Nil 
    say $i1 cmp $i2;  # Less    NB. this is $i1 vs $i2!
    
    #  ∩ [also (&)] gives the intersect as an Interval (ie a subset of Range)
    say $i1  ∩  $i0;  # 2..5 
    say $i0  ∩  $i1;  # 2..5 
    say $i2  ∩  $i0;  # 7..10 
    say $i1  ∩  $i2;  # Set()   NB. this is $i1 vs $i2!
    
    say ($i1  ∩  $i0) ~~ Range;  # True
    

    There are a couple of wrinkles here, but I believe that substantially this provides what you need and you will accept this Answer.

    • its provided via a raku module you have to install with zef install Math::Interval
    • you need to use the .Interval coercion methid to convert a standard raku Range to an Interval (which is a subset of Range so can then be used interchangeably)
    • the intersect operation returns an Interval (which is a subset of Range) so will do what you need, except when there is no overlap ... in that case it gives back ∅ (aka the null Set())

    I am open to changing this in the module, perhaps we need to specify what is meant by the null Range, eg. Nil..Nil ? I have made an issue for this here, all f/back welcome!