#!/usr/bin/perl

use strict;
use warnings;

my (@x, @y);
while (<>) {
	unless (/[^\d\.\s-]/) {
		my @f = split;
		push @x, $f[0];
		foreach my $i (1..$#f) {
			push @{ $y[$i-1] }, $f[$i];
		}
	}
}

my ($maxima, $minima) = peak_find($y[0]);

foreach my $index (@$maxima) {
	print "$x[$index]\t$y[0][$index]\n";
}
print "\n";
print "\n";
foreach my $index (@$minima) {
	print "$x[$index]\t$y[0][$index]\n";
}
print "\n";

# Function that first finds all local maxima and minima in the data
# (the algorithm comes from http://www.perlmonks.org/index.pl?node_id=448913)
# then weeds them out so that only one maximum and minimum remains for each pulse.
sub peak_find {
	#my $xa = shift;
	my $ya = shift;

	my $period = autocorr_firstpeak($ya);
	
	my (@maxima, @minima);

	push @maxima, undef;
	push @minima, undef;	
	foreach my $i (1..$#$ya) {
		if ( $ya->[$i] > $ya->[$i-1] ) {
			$maxima[ -1 ] = $i;
		} elsif ( $maxima[ -1 ] ) {
			$maxima[ @maxima ] = undef;
		}
		if ( $ya->[$i] < $ya->[$i-1] ) {
			$minima[ -1 ] = $i;
		} elsif ( $minima[ -1 ] ) {
			$minima[ @minima ] = undef;
		}
	}
	pop @maxima unless $maxima[ -1 ];
	pop @minima unless $minima[ -1 ];
	
	# At this point, @maxima and @minima contain 
	# all local maxima and minima of the data, respectively
	
	my %max_hash = map {$_ => $ya->[$_]} @maxima;
	my %min_hash = map {$_ => $ya->[$_]} @minima;	
	
	my @sorted_max = sort { $max_hash{$b} <=> $max_hash{$a} } keys %max_hash;
	my @sorted_min = sort { $min_hash{$a} <=> $min_hash{$b} } keys %min_hash;
	
	my %filtered_max_hash; 
	my %filtered_min_hash;
	
	my $factor = 0.7; 
	foreach my $index (@sorted_max) {
		if (exists $max_hash{$index}) {
			$filtered_max_hash{$index} = $max_hash{$index};
			foreach my $shift (0..int($period*$factor)) {
				delete $max_hash{$index + $shift} 
					unless exists $filtered_max_hash{$index + $shift};
				delete $max_hash{$index - $shift} 
					unless exists $filtered_max_hash{$index - $shift};
			}
		}
	}
	foreach my $index (@sorted_min) {
		if (exists $min_hash{$index}) {
			$filtered_min_hash{$index} = $min_hash{$index};
			foreach my $shift (0..int($period*$factor)) {
				delete $min_hash{$index + $shift} 
					unless exists $filtered_min_hash{$index + $shift};
				delete $min_hash{$index - $shift} 
					unless exists $filtered_min_hash{$index - $shift};
			}
		}
	}
	
	
	my @filtered_maxima = sort { $a <=> $b } keys %max_hash;
	my @filtered_minima = sort { $a <=> $b } keys %min_hash;
	
	return \@filtered_maxima, \@filtered_minima;
}

# Returns the first peak of the autocorrelation function -
# this corresponds to the highest frequency of periodicity in the data.
sub autocorr_firstpeak {
	my $xa = shift;
	
	my @a;
	my ($min, $max, $index);
	my $which = 1; # 1=min, 0=max; 

	$a[0] = 0;
	for my $x (@$xa) {
		$a[0] += $x**2;
	}
	
	for my $i (1..$#$xa) {
		$a[$i] = 0;
		for my $j (0..$#$xa) {
			$a[$i] += $xa->[$j]*$xa->[$j-$i];
		}
		if ($which) {
			if ($a[$i] < $a[$i-1]) {
				$min = $a[$i];
			} else {
				$which = 0;
			}
		} else {
			if ($a[$i] > $a[$i-1]) {
				$max = $a[$i];
			} else {
				$index = $i-1;
				last;
			}
		}
	}
	return $index;
}