#!/usr/bin/perl
use strict;
use warnings;
use List::Util 'first';
sub gen_merger {
my ($list, $fetch, $compare, $finish) = @_;
my @item = map $fetch->($_), @$list;
my $done;
return sub {
return $finish if $done;
my $idx = first {$item[$_] ne $finish} 0 .. $#item;
my $next = $item[$idx];
for ($idx + 1 .. $#item) {
next if $item[$_] eq $finish;
my $result = $compare->($next, $item[$_]);
if ($result == 1) {
$next = $item[$_];
$idx = $_;
}
}
$item[$idx] = $fetch->($list->[$idx]);
$done = 1 if ! first {$_ ne $finish} @item;
return $next;
};
}
sub gen_sum_iter {
my ($num, $list) = @_;
my $idx = 0;
return sub {
return undef if $idx > $#$list;
return $num + $list->[$idx++];
};
};
my @list1 = (1 .. 5);
my @list2 = (1 .. 5);
my $finish = 'A val that is guaranteed not to be present in any list';
my @merge_list = map gen_sum_iter($_, \@list2), @list1; # Map over smaller list if possible
my $fetch = sub {my $sum = $_[0]->(); return defined $sum ? $sum : $finish;};
my $compare = sub {$_[0] <=> $_[1]};
my $next = gen_merger(\@merge_list, $fetch, $compare, $finish);
while (1) {
my $item = $next->();
last if defined $item && $item eq $finish;
print "$item\n";
}
####
#!/usr/bin/perl
use constant VAL => 0;
use constant IDX => 1;
use constant SUM => 2;
use strict;
use warnings;
my @list1 = (1 .. 5);
my @list2 = (1 .. 5);
my @merge_list = map {[$_, 0, $_ + $list2[0]]} @list1; # Map over smaller list if known
while (@merge_list) {
my ($min, $index) = ($merge_list[0][SUM], 0);
for (1 .. $#merge_list) {
($min, $index) = ($merge_list[$_][SUM], $_) if $merge_list[$_][SUM] < $min;
}
print "$min\n";
$merge_list[$index][IDX]++;
if ($merge_list[$index][IDX] > $#list2) {
splice(@merge_list, $index, 1);
}
else {
$merge_list[$index][SUM] = $merge_list[$index][VAL] + $list2[$merge_list[$index][IDX]];
}
}
##
##
#!/usr/bin/perl
use strict;
use warnings;
my @list1 = 1 .. 5;
my @list2 = 1 .. 5;
my @merge_list = ((0) x scalar @list1); # use smaller of 2 lists
while (1) {
my ($min, $idx);
for (my $i = 0; $i < @merge_list; ++$i) {
next if $merge_list[$i] > $#list2;
my $sum = $list1[$i] + $list2[$merge_list[$i]];
($min, $idx) = ($sum, $i) if ! defined $min || $sum < $min;
}
last if ! defined $min;
print "$min\n";
$merge_list[$idx]++;
}