Set of real numbers

class Iv {
    has $.range handles <min max excludes-min excludes-max minmax ACCEPTS>;
    method empty {
	$.min after $.max or $.min === $.max && ($.excludes-min || $.excludes-max)
    }
    multi method Bool() { not self.empty };
    method length() { $.max - $.min }
    method gist() {
	($.excludes-min ?? '(' !! '[') ~
	$.min ~ ',' ~ $.max ~
	($.excludes-max ?? ')' !! ']');
    }
}

class IvSet {
    has Iv @.intervals;

    sub canon (@i) {
	my @new = consolidate(|@i).grep(*.so);
	@new.sort(*.range.min);
    }

    method new(@ranges) {
	my @iv = canon @ranges.map: { Iv.new(:range($_)) }
	self.bless(:intervals(@iv));
    }

    method complement {
	my @new;
	my @old = @!intervals;
	if not @old {
	    return iv -Inf..Inf;
	}
	my $pre;
	push @old, Inf^..Inf unless @old[*-1].max === Inf;
	if @old[0].min === -Inf {
	    $pre = @old.shift;
	}
	else {
	    $pre = -Inf..^-Inf;
	}
	while @old {
	    my $old = @old.shift;
	    my $excludes-min = !$pre.excludes-max;
	    my $excludes-max = !$old.excludes-min;
	    push @new, Range.new($pre.max,$old.min,:$excludes-min,:$excludes-max);
	    $pre = $old;
	}
	IvSet.new(@new);
    }

    method ACCEPTS(IvSet:D $me: $candidate) {
	so $.intervals.any.ACCEPTS($candidate);
    }
    method empty { so $.intervals.all.empty }
    multi method Bool() { not self.empty };

    method length() { [+] $.intervals».length }
    method gist() { join ' ', $.intervals».gist }
}

sub iv(**@ranges) { IvSet.new(@ranges) }

multi infix:<∩> (Iv $a, Iv $b) {
    if $a.min ~~ $b or $a.max ~~ $b or $b.min ~~ $a or $b.max ~~ $a {
	my $min = $a.range.min max $b.range.min;
	my $max = $a.range.max min $b.range.max;
	my $excludes-min = not $min ~~ $a & $b;
	my $excludes-max = not $max ~~ $a & $b;
	Iv.new(:range(Range.new($min,$max,:$excludes-min, :$excludes-max)));
    }
}
multi infix:<∪> (Iv $a, Iv $b) {
    my $min = $a.range.min min $b.range.min;
    my $max = $a.range.max max $b.range.max;
    my $excludes-min = not $min ~~ $a | $b;
    my $excludes-max = not $max ~~ $a | $b;
    Iv.new(:range(Range.new($min,$max,:$excludes-min, :$excludes-max)));
}

multi infix:<∩> (IvSet $ars, IvSet $brs) {
    my @overlap;
    for $ars.intervals -> $a {
	for $brs.intervals -> $b {
	    if $a.min ~~ $b or $a.max ~~ $b or $b.min ~~ $a or $b.max ~~ $a {
		my $min = $a.range.min max $b.range.min;
		my $max = $a.range.max min $b.range.max;
		my $excludes-min = not $min ~~ $a & $b;
		my $excludes-max = not $max ~~ $a & $b;
		push @overlap, Range.new($min,$max,:$excludes-min, :$excludes-max);
	    }
	}
    }
    IvSet.new(@overlap)
}

multi infix:<∪> (IvSet $a, IvSet $b) {
    iv |$a.intervals».range, |$b.intervals».range;
}

multi consolidate() { () }
multi consolidate($this is copy, *@those) {
    gather {
        for consolidate |@those -> $that {
            if $this ∩ $that { $this ∪= $that }
            else             { take $that }
        }
        take $this;
    }
}

multi infix:<−> (IvSet $a, IvSet $b) { $a ∩ $b.complement }

multi prefix:<−> (IvSet $a) { $a.complement; }

constant ℝ = iv -Inf..Inf;

my $s1 = iv(0^..1) ∪ iv(0..^2);
my $s2 = iv(0..^2) ∩ iv(1^..2);
my $s3 = iv(0..^3) − iv(0^..^1);
my $s4 = iv(0..^3) − iv(0..1) ;

say "\t\t\t\t0\t1\t2";
say "(0, 1] ∪ [0, 2) -> $s1.gist()\t", 0 ~~ $s1,"\t", 1 ~~ $s1,"\t", 2 ~~ $s1;
say "[0, 2) ∩ (1, 2] -> $s2.gist()\t", 0 ~~ $s2,"\t", 1 ~~ $s2,"\t", 2 ~~ $s2;
say "[0, 3) − (0, 1) -> $s3.gist()\t", 0 ~~ $s3,"\t", 1 ~~ $s3,"\t", 2 ~~ $s3;
say "[0, 3) − [0, 1] -> $s4.gist()\t", 0 ~~ $s4,"\t", 1 ~~ $s4,"\t", 2 ~~ $s4;

say '';

say "ℝ is not empty: ", !ℝ.empty;
say "[0,3] − ℝ is empty: ", not iv(0..3) − ℝ;

my $A = iv(0..10) ∩
   iv |(0..10).map({ $_ - 1/6 .. $_ + 1/6 }).cache;

my $B = iv 0..sqrt(1/6),
      |(1..99).map({ sqrt($_-1/6) .. sqrt($_ + 1/6) }), sqrt(100-1/6)..10;

say 'A − A is empty: ', not $A − $A;

say '';

my $C = $A − $B;
say "A − B =";
say "  ",.gist for $C.intervals;
say "Length A − B = ", $C.length;

Output:

                                0       1       2
(0, 1] ∪ [0, 2) -> [0,2)        True    True    False
[0, 2) ∩ (1, 2] -> (1,2)        False   False   False
[0, 3) − (0, 1) -> [0,0] [1,3)  True    True    True
[0, 3) − [0, 1] -> (1,3)        False   False   True

ℝ is not empty: True
[0,3] − ℝ is empty: True
A − A is empty: True

A − B =
  [0.833333,0.912870929175277)
  (1.08012344973464,1.166667]
  [1.833333,1.95789002074512)
  (2.04124145231932,2.166667]
  (2.85773803324704,2.97209241668783)
  (3.02765035409749,3.13581462037113)
  [3.833333,3.85140666943045)
  (3.89444048184931,3.97911212877111)
  (4.02077936060494,4.10284454169706)
  (4.14326763155202,4.166667]
  [4.833333,4.88193950529227)
  (4.91596040125088,4.98330546257535)
  (5.01663898109747,5.08265022732563)
  (5.11533641774094,5.166667]
  (5.84522597225006,5.90197706987526)
  (5.93014895821906,5.98609499868932)
  (6.01387285088957,6.06904715201104)
  (6.09644705272396,6.15088069574865)
  [6.833333,6.84348838921594)
  (6.8677992593455,6.91616464041548)
  (6.94022093788567,6.98808509774554)
  (7.01189465598754,7.05927286151579)
  (7.08284312029193,7.12974987873581)
  (7.15308791129165,7.166667]
  [7.833333,7.86341740805697)
  (7.88458411500991,7.92674796706274)
  (7.94774601171091,7.98957654280459)
  (8.01040989379861,8.05191488612077)
  (8.07258735887489,8.11377429642539)
  (8.13428956127495,8.166667]
  (8.8411914732499,8.87881373457813)
  (8.89756521002609,8.93495010245347)
  (8.95358401237553,8.99073597284078)
  (9.00925450115972,9.04617783007461)
  (9.06458309392477,9.10128196098403)
  (9.1195760135363,9.15605446321358)
  [9.833333,9.84039294608367)
  (9.85731538841416,9.89107341663853)
  (9.9079092984679,9.94149552800449)
  (9.9582461641931,9.99166319154791)
Length A − B = 2.07586484118467

Last updated