#!/usr/local/bin/perl
#
# Script to merge multiple data files according to time.
# John Graybeal 21 June 2004  MBARI

# Interpolate columns of data according to time in one of the columns, or a fixed time 
# interval.
# Assumptions:
#   The first column is assumed to be the time (the key).
#	The first column is a simple float, double, or int.  
#	The first data row starts with a number, and all rows following that contain data.
#	The first file is assumed to be the one to interpolate to if we aren't going "allWays".
#	The first file may contain just time (no values), if it is used to drive the interpolation.
#	Time is assumed to be epoch days since 1970.  But the algorithm could work for any 'key' under 
#   the following circumstances: 
#   - key values are sorted in every file, so that they never decrease 
#     (they may stay the same, but interpolation of data files with repeated keys yet 
#      different values Will Be Bad.)
#   - The test for valid time is changed appropriately.
#	Linear interpolation is used.
#	Missing values are not handled appropriately, whether they are blank or have a missing value constant.
#
# Syntax is:
#   merge.pl [options] file1 file2 ... fileN
#   untested	-secsOffset	(seconds) offset between each interpolation; 0=use file(s) [0]
#	untested	-timeStart (epoch seconds since 1970.0) time to start interpolation; 0=first time [999999]
#	untested	-timeEnd (epoch seconds since 1970.0) time to stop interpolation; [999999]
#	tested  	-allWays   Conduct multi-way merge (interpolate to all provided time sources) [0]
#	not done	-useNearest   Match nearest item rather than using interpolation [0]
#	untested	-itemSeparator	string which separates data items in file [\t]
#	part-tested		-extrapValue	value to use when no interpolation possible; null, nearest, or string [nearest]
#
#
use Getopt::Long;
use IO;

my $debug = 5;

my $timeStart = 999999;
my $timeEnd = 999999;
my $secsOffset = 0;
my $allWays = 0;
my $useNearest = 0;
# PerlMystery: Extra tabs get inserted when tab is itemSeparator, but not with comma (?)
my $itemSeparator = ",";
my $extrapValue = "nearest";

my $fileNum = 0;
my @line = ();  # contains the current line for all the files
my @time = ();  # contains the current time values for all the files
my @prevTime = (); # contains the previous time values for all the files

my $index = 0;
my $nArgs = $#ARGV + 1;
my $nFiles = 0;  # should equal $nArgs if all is well, but keeping separate count is a good idea
my $fileNum = 0;

my @fileDone;  # indicate whether each input file has gotten to the end

my @matchList;  # list of all files which matched time on this cycle

# Get run-line parameters
if ($ARGV) {die "\nUsage: $0 [options] file1 file2 [-h for options]...\n\n" ;}

GetOptions ('timeStart=f' => \$timeStart, 'timeEnd=f' => \$timeEnd, 'secsOffset=f' => \$secsOffset, 
			'allWays' => \$allWays, 'itemSeparator=s' => \$itemSeparator, 
            'useNearest' => \$useNearest, 'extrapValue=s' => \$extrapValue );
         
if ($debug) {
	print "******************************************************\n";
	print "Options: \n";
	print "	timeStart = $timeStart\n";
	print "	timeEnd = $timeEnd\n";
	print "	secsOffset = $secsOffset\n";
	print "	allWays = $allWays\n";
	print "	useNearest = $useNearest\n";
	print "	itemSeparator = '$itemSeparator'\n";
	print "	extrapValue = $extrapValue\n";
}

my $nextIntervalTime = $timeStart;

# Open up all the files and make sure all is well
FILEOPEN: 
for my $argIndex (0 .. $nArgs-1) {
	if ($debug) {print "Loop $argIndex for file $fileNum: Arg is '$ARGV[$argIndex]'\n"};
	
	# PerlMystery: For some reasond, adding an option make Perl think there's an extra
	# empty argument at the end of the list of arguments.  This ignores the blank arg.
	last if (!$ARGV[$argIndex]);
	
#	get file name to process
	$fileName[$fileNum] = $ARGV[$argIndex];
# 	Position each file at first data line
	if ($debug) {print "File $fileNum: Opening file $fileName[$fileNum]... "};
	$inFiles[$fileNum] = IO::File->new("$fileName[$fileNum]")  or die "Can't open data file: $!";
	
# 	Read past comment lines in each file (looking for number in first column)
	if ($debug > 3) {print "Positioning file... ";}
#	while (<$inFiles[$fileNum]>) {
	$gotTime = 0;
	do {
		$line[$fileNum] = readline($inFiles[$fileNum]);
		$lineNum[$fileNum] = $. ;
		if ($debug>3) {print "Pos/Line $lineNum[$fileNum]: $line[$fileNum]"};
		
		if (eof) {
#			$atEnd = true;
			warn "Didn't find good data (leading digit) in file $fileName[$fileNum] (read $lineNum[$fileNum] lines).\n";
			close ($inFiles[$fileNum]);
			next FILEOPEN;
		}
		if ($line[$fileNum] =~ /^\d/) {
			# get rid of the lf/cr
			chomp $line[$fileNum];
			if ($debug) {print "Positioned to data at line $lineNum[$fileNum] of file $fileName[$fileNum].\n";}
			
			if ($debug) {print "Verifying file $fileName....\n "};
#		 	Get time from first line of each data file (confirming file is parseable)
#			Split out the time and the associated data (if any)
			($time[$fileNum], @dataTemp) = split($itemSeparator, $line[$fileNum]);
#			Determine how many data items there are
			$nItems[$fileNum] = $#dataTemp + 1;
			if ($nItems[$fileNum] == 0) {
				# get rid of spurious stuff like EOL, blanks, etc.
				@dataString[$fileNum] = "";
			} else {
#				Save a string with all the data from this file.  We'll have to parse out the data when we need it.
				@dataString[$fileNum] = join($itemSeparator, @dataTemp);
				if ($debug>2) {
					print "Split row $lineNum[$fileNum]: At time $time[$fileNum], we have $nItems[$fileNum] items: @dataString[$fileNum]\n";
				}
			}
			# Verify time looks OK (crude verification, but good for now).
			if (($time[$fileNum] > 20000.) || ($time[$fileNum] < 40000.)) {
				if ($debug >2) {
					print "File verified. File index is $fileNum.\n";
				}
				print "# File $fileName[$fileNum] ready at line $lineNum[$fileNum].\n";
				$gotTime = 1;
				# initialize boolean array elements for first time
				$fileDone[$fileNum] = 0;
				# increment to get ready for next one
				$nFiles++; 
				$fileNum++;
			} else {
				warn "Couldn't get a good time from file $fileName[$fileNum]arg $argIndex (should be days since 1970).\n";
				close $inFiles[$fileNum];
			}
		} 
	} until ($gotTime);
}

my $timeKey; # this holds the next time key for interpolation
# initialize it with some useful value
$timeKey = ($secsOffset ? $timeStart : $time[0]); 

if ($debug) {
	print "Time key is initialized to $timeKey\n";
}

my $nFilesDone = 0;  # count of the number of files we've gone all the way through
my $allFilesDone = 0;

# At this point we should have nFiles input files (inFiles), each one positioned to the first data line
# @time array should contain the start time for each file
# $nItems array should contain the number of data items in each file

# while there are still keys (time intervals) left to process... 
while (workLeft($allWays, $secsOffset, $timeKey, $timeEnd, $allFilesDone, $fileDone[0])) {


# 	find earliest time
	if (!$allWays) {
		if ($secsOffset) {
			$timeKey = $nextIntervalTIme;
			$matchList = -1;
		} else {
			# time is in the first file
			$timeKey = $time[0];
			$matchList = 0;
		}
	} else {
		# we have to figure out which is the next time
		# this has the (dubious) side benefit of catching errors of "no files left" variety
		# (because there is no good time to replace $nextIntervalTime of 999999)
		($timeKey, $matchTemp) = minTime ($nextIntervalTime, @time);
		@matchList = split(",", $matchTemp);
	}
	
	chomp($timeKey);
	if ($debug) {
		print "Earliest time index: $timeKey (found in file(s) $matchTemp (-1=interval)).\n";
	}

#  match time key with correct data from other files (at first, this is extrap by def'n)

	# In the case that we are not doing "all ways" interpolation, other files may have times which 
	# are earlier than our target time. For each file where this is the case, read from the data file 
	# until a later time is found
	if (!$allWays) {
	
#		first file is just a data file if secsOffset is true (>0) (since we aren't doing this all ways)
		$fileStart = ($secsOffset ? 0 : 1);
		
		my $timeFound;
		
#		Search over all the files
		for my $fileIndex ($fileStart .. $nFiles-1) {
			
			if ($time[$fileIndex] >= $timeKey) {
				$timeFound = 1;
				if ($debug) {
					print "Already at useful time.\n";
				}
			} else {

				if ($debug > 4) {print "Searching file $fileIndex for matching time..\n"};
	
				$timeFound = 0;
				do { # until we find a time that is greater than the timeKey
					$line[$fileIndex] = readline($inFiles[$fileIndex]);
					$lineNum[$fileIndex] = $. ;
					if ($line[$fileIndex] == undef) {
						# file is done
						$fileDone[$fileIndex] = 1;
						$nFilesDone++;
						$allFilesDone = tf($nFilesDone == $nFiles);						
						print "Got to end of file # $fileIndex, for a total of $nFilesDone (out of $nFiles). AllFilesDone=$allFilesDone.\n";
						last;
					}
					if ($debug > 3) {print "Pos: File/Line $fileIndex/$lineNum[$fileIndex]: $line[$fileIndex]"};
					# save previous values for later interpolation
					$prevTime[$fileIndex] = $time[$fileIndex];
					@prevDataString[$fileIndex] = @dataString[$fileIndex];
					
	#				Split out the time and the associated data (if any)
					($time[$fileIndex], @dataTemp) = split($itemSeparator, $line[$fileIndex]);
	#				We could test whether there are the same number of data items as on the first line:
	# (but we won't)	warn if ($nItems[$fileIndex] != $#dataTemp + 1), "Number of data items changed.");
					
	#				Save a string with all the data from this file/line. (Better way to do this in Perl?) 
	#				We'll have to parse out the data when we need it.  
					@dataString[$fileIndex] = join($itemSeparator, @dataTemp);
					
	#				Did we get to the desired place?
					if ($time[$fileIndex] >= $timeKey) {
						$timeFound = 1;
						if ($debug) {
							print "Found useful time.\n";
						}
					}
				} until $timeFound;
				
			}  # pre-test to see if we're already there
		} # for all files which might have first time
	} # only do this is we are not doing all ways interpolation

	if ($debug > 2) {print "nFiles: fileDone array = $nFiles: $fileDone[0], $fileDone[1]!\n"};

# Now we should be able to interpolate all the values to this given time ($timeKey)	
	my $resultLine = $timeKey; # initialize resultLine to include the time
	if ($debug > 2) {print "Initialized result line to: $resultLine\$\n"};
	
	for my $fileIndex (0.. $nFiles-1) {
		if ($fileDone[$fileIndex]) {
			if ($debug > 4) {print "$fileDone[$fileIndex]: File $fileIndex finished, must extrapolate.."};
			# this file has been fully read already, handle extrapolated value (time must be earlier than the timeKey)
			# nearest value for extrapolation is the current value 
			# extrapolate for whole line
			$resultVal = extrapVal ($extrapValue, $nItems[$fileIndex], $dataString[$fileIndex]);
			if ($debug > 4) {print "using $extrapValue, $dataString[$fileIndex].."};
			if ($debug > 4) {print "returns $resultVal.."};
			$resultLine = join ($itemSeparator, $resultLine, $resultVal);
		} else {
			# file is still open, we should have a solution
			if ($debug > 4) {print "File $fileIndex open.."};
			if ($time[$fileIndex] >= $timeKey) {
				if ($debug > 4) {print "Time greater than index.."};
				if (!defined ($prevTime[$fileIndex])) {
					if ($debug > 4) {print "prevTime not defined.."};
					# possible extrapolation situation, no previous value
					if ($time[$fileIndex] == $timeKey) {
						if ($debug > 4) {print "Miracle, times match.."};
						# it's OK, use present value!
						$resultLine = join ($itemSeparator, $resultLine, @dataString[$fileIndex]);
					} else {
						if ($debug > 4) {print "No prevTime, have to extrapolate.."};
						# have to extrapolate
						# nearest value for extrapolation is the current value 
						# extrapolate for whole line
						$resultVal = extrapVal ($extrapValue, $nItems[$fileIndex], $dataString[$fileIndex]);
						if ($debug > 4) {print "using $extrapValue, $dataString[$fileIndex].."};
						if ($debug > 4) {print "returns $resultVal.."};
						$resultLine = join ($itemSeparator, $resultLine, $resultVal);
					}
				} elsif ($prevTime[$fileIndex] < $timeKey) {
					if ($debug > 4) {print "prevTime < timeKey.."};

					# We can perform an interpolation here
					if ($time[$fileIndex] == $timeKey) {
						if ($debug > 4) {print "Times match, use exact string.."};
						# Times match -- just use the string as is
						$resultLine = join ($itemSeparator, $resultLine, @dataString[$fileIndex]);
						chomp($resultLine);  # (couldn't get rid of EOL when it's first read in, so do it here)
					} else {
						# really interpolate.  First get the time ratio.
						if ($debug > 4) {print "Doing real interpolation.."};
						$deltaRatio = ($timeKey - $prevTime[$fileIndex]) / ($time[$fileIndex] - $prevTime[$fileIndex]);
						if ($debug > 4) {
							print "BeforeTime, AfterTime, Desired Time, deltaRatio: ";
							print "$prevTime[$fileIndex], $time[$fileIndex], $timeKey, $deltaRatio\n";
						}
						# iterate over all the data values
						my @prevValues = split ($itemSeparator, @prevDataString[$fileIndex]);
						my $prevItemsCnt = scalar(@prevValues);
						my @values = split ($itemSeparator, @dataString[$fileIndex]);
						my $itemsCnt = scalar(@values);
						my $expectCount = $nItems[$fileIndex];
						if (($prevItemsCnt != $expectCount) || ($itemsCnt != $expectCount)) {
							print "Alert! Unexpected number of values.  Expected $expectCount, but ";
							print "previous line had $prevItemsCnt and this line has $itemsCnt.\n";
							die "Sorry, must abort, data will be compromised.\n";
						}
						my @resultVal;
						for $valIndex (0 .. $nItems[$fileIndex]-1) {
							$resultVal[$valIndex] = interpVal ($prevValues[$valIndex], $values[$valIndex], $deltaRatio);
						}
						$resultLine = join ($itemSeparator, $resultLine, @resultVal);
					}
				} else {
					# previous time equals or exceeds time key, why did we read ahead?
					print "prevTime, timeKey: $prevTime[$fileIndex] , $timeKey\n";
					die "Previous time matched or exceeded timeKey, not clear why we read next line. Programmer error.\n";
				} # handled all possible cases for previous time
				if ($debug > 2) {print "\nNow result line is $resultLine\$\n"};

			} else {
				# current time is earlier than time key, shouldn't be the case 
				# either the file was done (handled earlier) or we should have read more input (also above)
				print "time, timeKey: $time[$fileIndex] , $timeKey\n";
				die "File time earlier than timeKey, should have handled elsewhere. Programmer error.\n";
			} # handled all possible time orders for this time vs timeKey
		} # handled all possible cases of file done
	} # end looping over all the files
	
	# print the output line
	print "$resultLine\n";


	# read a line from the lucky file(s) that provided the timeKey for this round
	@matchArray = split(",", $matchTemp);
	foreach $whichFile (@matchArray) {
		if ($debug > 4) {print "Matchlist: <$matchList>  whichFile: <$whichFile>\n"};
		if ($whichFile >= 0) {
			$line[$whichFile] = readline($inFiles[$whichFile]);
			$lineNum[$whichFile] = $. ;
			if ($line[$whichFile] != undef) {
				if ($debug > 3) {print "Reading from last timeKey source (file #$whichFile): Line $lineNum[$whichFile]: $line[$whichFile]";}
				# save previous values for later interpolation
				$prevTime[$whichFile] = $time[$whichFile];
				@prevDataString[$whichFile] = @dataString[$whichFile];
	#			Split out the time and the associated data (if any)
				($time[$whichFile], @dataTemp) = split($itemSeparator, $line[$whichFile]);
	#			We could test whether there are the same number of data items as on the first line:
	# (but we won't)	warn if ($nItems[$whichFile] != $#dataTemp + 1), "Number of data items changed.");
					
	#			Save a string with all the data from this file/line. (Better way to do this in Perl?) 
	#			We'll have to parse out the data when we need it.  
				$dataString[$whichFile] = join($itemSeparator, @dataTemp);
				chomp($dataString[$whichFile]);
			} else {
				# file is done
				$fileDone[$whichFile] = 1;
				$nFilesDone++;
				$allFilesDone = tf(($nFilesDone) == ($nFiles));
				if ($debug >= 3) {print "Got to end of file #$whichFile, for a total of $nFilesDone file(s) completed ((out of $nFiles). AllFilesDone=$allFilesDone.\n";}
			}
		} else {
			# the interval time must need updating
			$nextIntervalTime += ($secsOffset / (3600 * 24));
		}
	} 
} # keep going until no more keys left to process


# this method accepts as inputs tRatio, v0, and v1
sub interpVal  {

# given prev time t0, new time t1, and match time t, correspoding value v at time t is found as 
# a function of the corresponding values v0 and v1:
#   v = v0 + (v1-v0) * (t-t0)/(t1-t0)
# the latter multiplier can be precalculated as tRatio

	my ($v0, $v1, $tRatio) = @_;
	return ($v0 + $tRatio * ($v1 - $v0));
}

# this method accepts as inputs extrapValue, nearestValue
sub extrapVal {

	my ($valueForExtrapolation, $nItems, $lineToInsert) = @_;
	my $retLine;
	
	if ($valueForExtrapolation = "nearest") {
		$retLine = $lineToInsert;
	} elsif ($valueForExtrapolation = "null") {
		$retLine = join($itemSeparator, "" x $nItems) ;
	} else {
		$retLine = join($itemSeparator, $valueForExtrapolation x $nItems) ;
	}
	return $retLine;
}

# get the minimum time from the array passed in
# return minimum time and which index held it (-1 = secsOffset, 0 = first file)
sub minTime {
    my (@numbers) = @_;
    my $nNums = scalar(@numbers);

#	This initialization relies on the calling routine to set the $numbers[0] to 
#   a high number of it is not valid.
	my ($min);
    $min = $numbers[0];
    my $whichIsMin = -1;

    for my $i (1..$nNums-1) {
    	if (!$fileDone[$i-1]) {
			if ($numbers[$i] < $min) {
				$min = $numbers[$i];
				$whichIsMin = $i-1;
			} elsif ($numbers[$i] == $min) {
				$whichIsMin = join (",", $whichIsMin, $i-1);
			}
		}
    }
    if ($debug > 4) {print "minTime thinks matches are at $whichIsMin\n"};
    return ($min, $whichIsMin);
}

# Theoretically this isn't needed, but it makes troubleshooting SO much easier...
sub tf {
	my ($testVal) = @_;
	return ( $testVal ? 1 : 0 );
}

# this method determines whether we're done yet
sub workLeft {
	my ($allWays, $secsOffset, $timeKey, $timeEnd, $allFilesAreDone, $file0Done) = @_;
	if ($debug>3) {print "workLeft args (all/secs/tmKey/tmEnd/allDone/f0Done): $split(@_)\n"};
	
#	debug variables
	$notsO = tf(!$secsOffset);
	$notF0Done = tf(!$file0Done);
	if ($debug > 3) {
		$dStr = ($notF0Done ? "notF0Done true <" : "notF0Done false<");
		print ($dStr, "$notF0Done>\n");
	}
	$notAllFilesDone = tf(!$allFilesAreDone);
	if ($debug > 3) {
		$dStr = ($notAllFilesDone ? "notAllFilesDone true <" : "notAllFilesDone false<");
		print ($dStr, "$notAllFilesDone>\n");
	}
	$notAllWays = tf(!$allWays);

#	more if: moreSecs or (!fileDone[1] & !secsOffset) or moreFiles & allWays 

#	See if we are past the end time (time end overrides everything and is always initialized large
	$moreOffsets = tf($timeKey < $timeEnd);
	if ($debug > 4) {print "moreOffset =>  $timeKey < $timeEnd\n"};

#	See if there is more data in the first file that must be read
	$moreFile0 = tf(!$secsOffset && !$file0Done);
	if ($debug > 4) {print "moreFile0 => $notsO && $notF0Done ($secsOffset, $file0Done)\n"};
	
#	See if all the files have been read that need to be
#	Don't have to check secsOffset because it has no effect when all files are done
	$moreFileN = tf($allWays && !$allFilesAreDone);
	if ($debug > 4) {print "moreFileN => $allWays && $notAllFilesDone ($secsOffset,$allWays,$allFilesAreDone)\n"};

	$workToDo = tf($moreOffsets && ($moreFile0 || $moreFileN));
	if ($debug > 3) {print "Returning workToDo of $workToDo, based on: $moreOffsets && ($moreFile0 || $moreFileN)\n"};
	return $workToDo;
}