perl - 如何扩展二进制搜索迭代器以使用多个目标

Question

我有一个函数，binary_range_search，它是这样调用的:

my $brs_iterator = binary_range_search(
    target => $range,                   # eg. [1, 200]
    search => $ranges                   # eg. [ {start => 1,   end => 1000},
);                                      #       {start => 500, end => 1500} ]

brs_iterator->() 将遍历 $range 重叠的所有 @$ranges。

我想扩展 binary_range_search 以便能够以多个范围作为目标来调用它，例如:

target => $target_ranges # eg. [ [1, 200], [50, 300], ... ]
search => $search_ranges # as above

因此，当对 $range->[0] 的搜索用完时，它应该继续搜索 $range->[1]，依此类推。这是有问题的函数，其原始形式:

sub binary_range_search {
    my %options = @_;
    my $range    = $options{target}  || return;
    my $ranges   = $options{search}  || return;

    my ( $low, $high ) = ( 0, @{$ranges} - 1 );

    while ( $low <= $high ) {

        my $try = int( ( $low + $high ) / 2 );

        $low  = $try + 1, next if $ranges->[$try]{end}   < $range->[0];
        $high = $try - 1, next if $ranges->[$try]{start} > $range->[1];

        my ( $down, $up ) = ($try) x 2;

        my %seen = ();

        my $brs_iterator = sub {

            if (    $ranges->[ $up + 1 ]{end}       >= $range->[0]
                    and $ranges->[ $up + 1 ]{start} <= $range->[1]
                    and !exists $seen{ $up + 1 } )
            {
                $seen{ $up + 1 } = undef;
                return $ranges->[ ++$up ];
            }
            elsif ( $ranges->[ $down - 1 ]{end}       >= $range->[0]
                    and $ranges->[ $down + 1 ]{start} <= $range->[1]
                    and !exists $seen{ $down - 1 }
                    and $down > 0 )
            {
                $seen{ $down - 1 } = undef;
                return $ranges->[ --$down ];
            }
            elsif ( !exists $seen{$try} ) {
                $seen{$try} = undef;
              return $ranges->[$try];
            }
            else {
                return;
            }

        };
        return $brs_iterator;
    }
    return sub { };
}

这是一个标准的二分搜索策略，直到它找到一个重叠的范围。然后它向右移动，耗尽它，向左移动，耗尽它，最后放弃。理想情况下，我想它应该 shift 下一个目标范围，然后重新搜索(也许通过递归？)。我的问题是，我不确定如何使用迭代器构造使其工作。

Answer 1

我只是将您的迭代器生成包装在一个 for 循环中，并构建了一个迭代器函数数组。

根据上下文，我要么返回一个主迭代器，要么返回一个迭代器函数列表。我不确定你想要什么。

use strict;
use warnings;


my $t = [ [1,200], [400,900] ];
my @r = (
    { start =>   1, end =>  100 },
    { start =>   2, end =>  500 },
    { start => 204, end =>  500 },
    { start => 208, end =>  500 },
    { start => 215, end => 1000 },
    { start => 150, end => 1000 },
    { start => 500, end => 1100 },
);

# Get a master iterator that will process each iterator in turn.
my $brs_iterator = binary_range_search(
    targets => $t,  
    search => \@r,
);

# Get an array of iterators
my @brs_iterator = binary_range_search(
    targets => $t,  
    search => \@r,
);



sub binary_range_search {
    my %options = @_;
    my $targets = $options{targets}  || return;
    my $ranges  = $options{search}  || return;


    my @iterators;

    TARGET:
    for my $target ( @$targets ) {

        my ( $low, $high ) = ( 0, $#{$ranges} );

        RANGE_CHECK:
        while ( $low <= $high ) {

            my $try = int( ( $low + $high ) / 2 );

            # Remove non-overlapping ranges
            $low  = $try + 1, next RANGE_CHECK 
                if $ranges->[$try]{end}   < $target->[0];

            $high = $try - 1, next RANGE_CHECK 
                if $ranges->[$try]{start} > $target->[1];

            my ( $down, $up ) = ($try) x 2;

            my %seen = ();

            my $brs_iterator = sub {

                if (    exists $ranges->[$up + 1]
                        and $ranges->[ $up + 1 ]{end}   >= $target->[0]
                        and $ranges->[ $up + 1 ]{start} <= $target->[1]
                        and !exists $seen{ $up + 1 } )
                {
                    $seen{ $up + 1 } = undef;
                    return $ranges->[ ++$up ];
                }
                elsif ( $ranges->[ $down - 1 ]{end}       >= $target->[0]
                        and $ranges->[ $down + 1 ]{start} <= $target->[1]
                        and !exists $seen{ $down - 1 }
                        and $down > 0 )
                {
                    $seen{ $down - 1 } = undef;
                    return $ranges->[ --$down ];
                }
                elsif ( !exists $seen{$try} ) {
                    $seen{$try} = undef;
                  return $ranges->[$try];
                }
                else {
                    return;
                }

            };
            push @iterators, $brs_iterator;
            next TARGET;
        }

    }

    # In scalar context return master iterator that iterates over the list of range iterators.
    # In list context returns a list of range iterators.
    return wantarray 
         ? @iterators 
         : sub { 
             while( @iterators ) {
                 if( my $range = $iterators[0]() ) {
                     return $range;
                 }
                 shift @iterators;
             }
             return;
        }; 
}