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

C#: Application without a window or taskbar item (background app) that can still use Console.WriteLine() -

-
i'm trying create application adheres following: no taskbar no console or form window can utilize console.writeline() . (i.e. if executes app command prompt write console.) the problem if create windows form (or wpf) application can have there no taskbar, console or window show up, console.writeline() nothing. if create console app, writes console, can't figure out how hide (and if did hide it, write command prompt window?)... how do this? just create standard console application. callers responsibility hide window caused program (from how run c# console application console hidden ): system.diagnostics.processstartinfo start = new system.diagnostics.processstartinfo(); start.filename = dir + @"\myprocesstostart.exe"; start.windowstyle = system.diagnostics.processwindowstyle.hidden;
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

openssl - Load PKCS#8 binary key into Ruby -

-
i'm trying load particular private key encoded in binary der format ( pkcs#8 ) ruby. however, openssl::pkey won't recognize it. can make work doing console work , transforming pem so: openssl pkcs8 -inform der -in file.key -passin pass:xxxxxxxx >private_key.pem after this, key can correctly read. however, since whole process done in memory instead of writing , reading files. so question is: possible load private keys binary encoded der format ruby/openssl? thank time, fernando yes, can indirectly load pkcs#8 der-encoded private keys using ruby openssl. openssl::pkey::rsa.new handle pem-formatted pkcs#8, easy read binary der , convert pem-formatted string , load string. for example, these der-encoded private keys: $ openssl genrsa | openssl pkcs8 -topk8 -outform der \ -nocrypt -out pkcs8.key $ openssl genrsa | openssl pkcs8 -topk8 -outform der \ -v2 des3 -passout pass:secret -out pkcs8_des3.key you can this: require 'open...
Read more