CODEWITHSUNDEEP
arraysperlintervals
Mastodon
Mastodon

Reputation: 151

How to obtain the complement intervals from an array of intervals?

The easiest way to explain my question is with an example.

I have an array in Perl with a set of intervals, and I need to obtain the complementary intervals, in other words, the anti-image of that set. From:

@ary1 = qw(23-44 85-127 168-209)

Printed intervals: 23-44, 85-127, 168-209.

Transform it to:

...-22, 45-84, 128-167, 210-...

Upvotes: 0

Views: 145

Answers (4)

emazep
emazep

Reputation: 479

To be pedantic, none of the offered solutions works if the given set contains -Inf or +Inf, eg: ('...-22', '45-84', '128-167', '210-...').

Provided that the intervals are sorted and don't overlap and the data always conform to the given syntax, here is a solution which works also in the aforementioned case (which is very similar to the one offered by @Borodin):

use strict;
use warnings;

my @data = ('...-22', '45-84', '128-167', '210-...');

use constant {
    SEP     => '-'  ,
    NEG_INF => '...',
    POS_INF => '...'
};

my ($first, $prev_upper) = split SEP, shift @data;
my @res = $first eq NEG_INF
    ? () : join SEP, NEG_INF, $first - 1;

for (@data) {
    my ($lower, $upper) = split SEP;
    push @res, join SEP, $prev_upper + 1, $lower - 1;
    $prev_upper = $upper
}
push @res, join SEP, $prev_upper + 1, POS_INF
    unless $prev_upper eq POS_INF;

print join ' ', @res; # 23-44 85-127 168-209

Upvotes: 0

Borodin
Borodin

Reputation: 126722

You may prefer this solution, which works similarly to the answer from @Choroba.

I have displayed the resultant @pairs array using both Data::Dump, which shows you the contents of the array in case you need to process it further, and print, which outputs text that matches your requirement in the question.

use strict;
use warnings;

my @input = qw/ 23-44 85-127 168-209 /;

my $begin;
my @pairs;

for (@input) {
  next unless /(\d+)-(\d+)/;
  push @pairs, [ $begin // '...', $1-1 ];
  $begin = $2+1;
}
push @pairs, [ $begin, '...' ];



use Data::Dump;
dd \@pairs;

print join(', ', map join('-', @$_), @pairs), "\n";

output

[["...", 22], [45, 84], [128, 167], [210, "..."]]
...-22, 45-84, 128-167, 210-...

Upvotes: 0

choroba
choroba

Reputation: 241858

If the intervals are already sorted and don't overlap:

#!/usr/bin/perl
use warnings;
use strict;

use List::MoreUtils qw{ natatime };

my @ary1 = qw(23-44 85-127 168-209);

my $diff = 1;
my $pair = natatime 2, '...', 
                       map({ map { $diff *= -1; $_ + $diff }
                                 split /-/
                           } @ary1),
                       '...';
my @compl;
while (my ($from, $to) = $pair->()) {
    push @compl, "$from-$to";
}

print "@compl\n";

Output

...-22 45-84 128-167 210-...

Upvotes: 4

toolic
toolic

Reputation: 62037

Set::IntSpan

use warnings;
use strict;
use Set::IntSpan;

my @ary1 = qw(23-44 85-127 168-209);
my $spec = join ',', @ary1;
my $set  = Set::IntSpan->new($spec);
my $list = $set->holes();
print "$list\n";

__END__

45-84,128-167

Upvotes: 3

Related Questions