use Stream;
package Stream;

sub nmerge {
    my @streams = @_;
    my @nonEmptyStreams = grep !$_->is_empty, @streams;

    return @nonEmptyStreams[0] if scalar @nonEmptyStreams < 2;

    my @heads = map $_->head, @nonEmptyStreams;

    # now figure out what the smallest head value is
    # first initialize the minimal value for min
    my $min = shift @heads;
    for (@heads) {
	if ($min > $_) {
	    $min = $_;
	}
    }
    Stream->new(
		$min,
		sub { &nmerge( map { $_->head == $min ?
				    $_->tail :
				    $_ }
				@nonEmptyStreams) });
}

# Merge two streams of numbers in ascending order, discarding duplicates
sub merge3 {
  my ($s1, $s2, $s3) = @_;
  return &merge($s2, $s3) if $s1->is_empty;
  return &merge($s1, $s3) if $s2->is_empty;
  return &merge($s1, $s2) if $s3->is_empty;
  my $h1 = $s1->head;
  my $h2 = $s2->head;
  my $h3 = $s3->head;
  if ($h1 > $h2) {
    Stream->new($h2, sub { &merge($s1, $s2->tail) });
  } elsif ($h1 < $h2) {
    Stream->new($h1, sub { &merge($s1->tail, $s2) });
  } else {			# heads are equal
    Stream->new($h1, sub { &merge($s1->tail, $s2->tail) });
  }
}

sub nmerge2 {
    my @streams = @_;
    my $min;
    my @minstreams;
    my @unminstreams;
    my $headstream;

    1 while (($headstream = shift @_) && exists($headstream->{e}));
    return Stream->empty unless $headstream;
    $min = $headstream->{h}; @minstreams = ($headstream);

    foreach $s (@_) {
      next if exists($s->{e});
      my $h;
      if (($h = $s->{h}) < $min) {
	$min = $h;
	push @unminstreams, @minstreams;
	@minstreams = ($s);
      } elsif ($h == $min) {
	push @minstreams, $s;
      } else {
	push @unminstreams, $s;
      }
    }

    Stream->new($min, sub { &nmerge2(@unminstreams, 
				     map {$_->tail} @minstreams) 
			      }
		);
}

sub h1 {
  my $hamming;
  $hamming  = 
      Stream->new(1, 
	  sub { &merge($hamming->scale(2),
		       &merge($hamming->scale(3),
			      $hamming->scale(5)
			      ))
		  }
          );
}

sub h2 {
  my $hamming;
  $hamming  = 
      Stream->new(1, 
	  sub { &nmerge($hamming->scale(2),
			$hamming->scale(3),
			$hamming->scale(5)
			)
		  }
          );
}

sub h3 {
  my $hamming;
  $hamming  = 
      Stream->new(1, 
	  sub { &nmerge2($hamming->scale(2),
			 $hamming->scale(3),
			 $hamming->scale(5)
			 )
		  }
          );
}

package main;
use Benchmark;

# &Stream::h3->show;


timethese(10, {
    orig => sub { &Stream::h1->take(1000) },
    hsu  => sub { &Stream::h2->take(1000) },
    mjd  => sub { &Stream::h3->take(1000) },
  }
);