perl - How to extend a binary search iterator to consume multiple targets -

-

i have function, binary_range_search, called so:

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

brs_iterator->() iterate on @$ranges on $range overlaps.

i extend binary_range_search able call multiple ranges target, eg:

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

so, when search on $range->[0] exhausted, should move on $range->[1], , on. here function in question, in original form:

sub binary_range_search {     %options = @_;     $range    = $options{target}  || return;     $ranges   = $options{search}  || return;      ( $low, $high ) = ( 0, @{$ranges} - 1 );      while ( $low <= $high ) {          $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];          ( $down, $up ) = ($try) x 2;          %seen = ();          $brs_iterator = sub {              if (    $ranges->[ $up + 1 ]{end}       >= $range->[0]                     , $ranges->[ $up + 1 ]{start} <= $range->[1]                     , !exists $seen{ $up + 1 } )             {                 $seen{ $up + 1 } = undef;                 return $ranges->[ ++$up ];             }             elsif ( $ranges->[ $down - 1 ]{end}       >= $range->[0]                     , $ranges->[ $down + 1 ]{start} <= $range->[1]                     , !exists $seen{ $down - 1 }                     , $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 { }; }

it's standard binary search strategy, until finds overlapping range. moves on right, exhausts it, moves on left, exhausts it, , gives up. ideally, should maybe shift next target range, , redo search, suppose (perhaps via recursion?). problem is, not sure how make work iterator construction.

i wrapped iterator generation in loop, , built array of iterator functions.

depending on context, either return master iterator or list of iterator functions. wasn't sure wanted.

use strict; use warnings;   $t = [ [1,200], [400,900] ]; @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 }, );  # master iterator process each iterator in turn. $brs_iterator = binary_range_search(     targets => $t,       search => \@r, );  # array of iterators @brs_iterator = binary_range_search(     targets => $t,       search => \@r, );    sub binary_range_search {     %options = @_;     $targets = $options{targets}  || return;     $ranges  = $options{search}  || return;       @iterators;      target:     $target ( @$targets ) {          ( $low, $high ) = ( 0, $#{$ranges} );          range_check:         while ( $low <= $high ) {              $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];              ( $down, $up ) = ($try) x 2;              %seen = ();              $brs_iterator = sub {                  if (    exists $ranges->[$up + 1]                         , $ranges->[ $up + 1 ]{end}   >= $target->[0]                         , $ranges->[ $up + 1 ]{start} <= $target->[1]                         , !exists $seen{ $up + 1 } )                 {                     $seen{ $up + 1 } = undef;                     return $ranges->[ ++$up ];                 }                 elsif ( $ranges->[ $down - 1 ]{end}       >= $target->[0]                         , $ranges->[ $down + 1 ]{start} <= $target->[1]                         , !exists $seen{ $down - 1 }                         , $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 iterates on list of range iterators.     # in list context returns list of range iterators.     return wantarray           ? @iterators           : sub {               while( @iterators ) {                  if( $range = $iterators[0]() ) {                      return $range;                  }                  shift @iterators;              }              return;         };  }

Comments

Post a Comment

Popular posts from this blog

ruby - When to use an ORM (Sequel, Datamapper, AR, etc.) vs. pure SQL for querying -

-
a colleague of mine designing sql queries 1 below produce reports, displayed in excel files through external data query. @ present, reporting processes on db required (no crud operations). i trying convince him better use ruby orm in order able display data in rails/sinatra app. despite obvious advantages in displaying data, advantages there him in learning use orm sequel or datamapper? the sql queries writing quite complex, , being relatively new sql, complains time-consuming , confusing. possible write extremely complex queries orm? , if so, suitable(i have heard sequel legacy dbs)? , advantages of learning ruby , using orm versus sticking plain sql, in making complex database queries? i'm datamapper maintainer, , think complex reporting should use sql. while think someday we'll have dsl provides power , conciseness of sql, i've seen far requires write more ruby code sql complex queries. rather maintain 5 line sql query 10-15 lines of ruby code desc...
Read more

php - PHPDoc: @return void necessary? -

-
is necessary this: /** * ... * * @return void */ i have quite few methods don't have return value, , seems redundant put in comment. considered bad form leave out? if makes clear documentation, leave in, isn't strictly necessary. it's entirely subjective decision. personally, leave out. edit stand corrected. after little googling, wikipedia page says: @return [type description] tag should not used constructors or methods defined void return type. the phpdoc.org website says: @return datatype description @return datatype1|datatype2 description the @return tag used document return value of functions or methods. @returns alias @return support tag formats of other automatic documentors the datatype should valid php type (int, string, bool, etc), class name type of object returned, or "mixed". if want explicitly show multiple possible return types, list them pipe-delimited without spaces (e.g. "@retur...
Read more

c++ - Convert big endian to little endian when reading from a binary file -

-
this question has answer here: how convert between big-endian , little-endian values in c++? 28 answers i've been looking around how convert big-endian little-endians. didn't find solve problem. seem there's many way can conversion. anyway following code works ok in big-endian system. how should write conversion function work on little-endian system well? this homework, since systems @ school running big-endian system. it's got curious , wanted make work on home computer also #include <iostream> #include <fstream> using namespace std; int main() { ifstream file; file.open("file.bin", ios::in | ios::binary); if(!file) cerr << "not able read" << endl; else { cout << "opened" << endl; int i_var; double d_var; while(!file.eof()) {...
Read more