Если вы хотите перебрать все значения, которые перекрывают диапазоны поиска, вам не нужен бинарный поиск.
Сначала общепринятая тема:
use warnings;
use strict;
use Carp;
Прежде всего, убедитесь, что у нас есть параметры target и search и что для каждого диапазона начальная точка не превышает его конечную точку. В противном случае мы отказываемся продолжить.
sub binary_range_search {
my %arg = @_;
my @errors;
my $target = $arg{target} || push @errors => "no target";
my $search = $arg{search} || push @errors => "no search";
for (@$target) {
my($start,$end) = @$_;
push @errors => "Target start ($start) is greater than end ($end)"
if $start > $end;
}
for (@$search) {
my($start,$end) = @{$_}{qw/ start end /};
push @errors => "Search start ($start) is greater than end ($end)"
if $start > $end;
}
croak "Invalid use of binary_range_search:\n",
map " - $_\n", @errors
if @errors;
Сам итератор является замыканием, которое поддерживает следующее состояние:
my $i;
my($ta,$tb);
my($sa,$sb);
my $si = 0;
, где
$i если определено следующее значение из текущего диапазона перекрытия $ta и $tb - начальная и конечная точки для текущего целевого диапазона $sa и $sb аналогичны приведенным выше, но для текущего диапазона поиска $si является индексом в @$search и определяет текущий диапазон поиска
Мы будем присваивать и возвращать итератор $it. Объявление и инициализация разделены, поэтому итератор может вызывать себя при необходимости.
my $it;
$it = sub {
Мы закончили, если больше не осталось целевых диапазонов или если не было диапазонов поиска для начала.
return unless @$target && @$search;
Когда определено $i, это означает, что мы нашли перекрытие и повторяем, увеличивая $i, пока оно не станет больше конечной точки текущего целевого диапазона или текущего диапазона поиска.
if (defined $i) {
# iterating within a target range
if ($i > $tb || $i > $sb) {
++$si;
undef $i;
return $it->();
}
else {
return $i++;
}
}
В противном случае нам нужно определить, перекрывает ли следующий целевой диапазон какой-либо диапазон поиска. Однако, если $i не определено и мы уже рассмотрели все диапазоны поиска, мы отбрасываем текущий целевой диапазон и начинаем заново.
else {
# does the next target range overlap?
if ($si >= @$search) {
shift @$target;
$si = 0;
return $it->();
}
Здесь мы извлекаем начальную и конечную точки как текущего целевого диапазона (всегда перед @$target), так и текущего диапазона поиска (индексируется $si).
($ta,$tb) = @{ $target->[0] };
($sa,$sb) = @{ $search->[$si] }{qw/ start end /};
Теперь проверка на перекрытие проста. Для непересекающихся диапазонов поиска мы игнорируем и движемся дальше. В противном случае мы находим крайнюю левую точку в перекрытии и итерируем оттуда.
if ($sb < $ta || $sa > $tb) {
# disjoint
++$si;
undef $i;
return $it->();
}
elsif ($sa >= $ta) {
$i = $sa;
return $i++;
}
elsif ($ta >= $sa) {
$i = $ta;
return $i++;
}
}
};
Наконец, мы возвращаем итератор:
$it;
}
Для примера, похожего на тот, что в вашем вопросе
my $it = binary_range_search(
target => [ [1, 200], [50, 300] ],
search => [ { start => 1, end => 1000 },
{ start => 500, end => 1500 },
{ start => 40, end => 60 },
{ start => 250, end => 260 } ],
);
while (defined(my $value = $it->())) {
print "got $value\n";
}
Выход с внутренними точками исключен
got 1
[...]
got 200
got 40
[...]
got 60
got 50
[...]
got 300
got 50
[...]
got 60
got 250
[...]
got 260