/*-----------------------------------------------------------------
 *	$Id: x2sys_cross.c,v 1.82 2009/09/09 23:27:05 guru Exp $
 *
 *      Copyright (c) 1999-2009 by P. Wessel
 *      See LICENSE.TXT file for copying and redistribution conditions.
 *
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; version 2 of the License.
 *
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *
 *      Contact info: www.soest.hawaii.edu/pwessel
 *--------------------------------------------------------------------*/
/* x2sys_cross will calculate crossovers generated by the
 * intersections of two tracks.  Optionally, it will also evaluate
 * the interpolated datafields at the crossover locations.
 *
 * Author:	Paul Wessel
 * Date:	15-JUN-2004
 * Version:	1.0, based on the spirit of the old xsystem code,
 *		but with a smarter algorithm based on the book
 *		"Algorithms in C" by R. Sedgewick.
 *		31-MAR-2006: Changed -O to -L to avoid clash with GMT.
 *
 */

#include "x2sys.h"

struct PAIR {				/* Used with -Kkombinations.lis option */
	char *id1, *id2;
};

int main (int argc, char **argv)
{
	char **trk_name;			/* Name of tracks */
	char line[BUFSIZ];			/* Input buffer */
	char *header_format;			/* Pointer to header format */
	char t_or_i;				/* t = time, i = dummy node time */
	char *fp_combo = CNULL;			/* File pointer to combinations list */
	char name1[80], name2[80];		/* Name of two files to be examined */
	char *TAG = CNULL;			/* System TAG name for these kinds of data */

	GMT_LONG n_rec[2];				/* Number of data records for both files */
	int half_window_width = 3;		/* Number of points on either side in the interpolation */
	int window_width;			/* Max number of points to use in the interpolation */
	int n_tracks = 0;				/* Total number of data sets to compare */
	int nx;					/* Number of crossovers found for this pair */
	int *col_number = VNULL;		/* Array with the column numbers of the data fields */
	int n_output;				/* Number of columns on output */
	int n_pairs = 0;			/* Number of acceptable combinations */
	int n_bin_header;
	int A, B, i, j, col, k, start, n_bad;	/* Misc. counters and local variables */
	int end, first, n_ok, n_alloc = 1;
	int n_data_col, left[2], t_left;
	GMT_LONG n_left, right[2], t_right, n_right;
	int n_duplicates, n_errors;

	size_t col_alloc = 0, add_chunk, not_used = 0;

	BOOLEAN xover_locations_only = FALSE;	/* TRUE if only x,y (and possible indices) to be output */
	BOOLEAN internal = TRUE;		/* FALSE if only external xovers are needed */
	BOOLEAN external = TRUE;		/* FALSE if only internal xovers are needed */
	BOOLEAN error = FALSE;			/* TRUE for invalid arguments */
	BOOLEAN do_project = FALSE;		/* TRUE if we must mapproject first */
	BOOLEAN got_time = FALSE;		/* TRUE if there is a time column */
	BOOLEAN xover_mode = FALSE;		/* Backwards compatibility with xover */
	BOOLEAN speed_check = FALSE;		/* TRUE if speed must be checked */
	BOOLEAN heading_check = FALSE;		/* TRUE if speed must be checked before headings are calculated */
	BOOLEAN first_header = TRUE;		/* TRUE for very first crossover */
	BOOLEAN first_crossover;		/* TRUE for first crossover between two data sets */
	BOOLEAN combinations = FALSE;		/* TRUE if a combination list has been given with -K */
	BOOLEAN two_values = FALSE;		/* TRUE if we want the two track values rather than crossover and mean returned */
	BOOLEAN t_given = FALSE;		/* TRUE when -T aoption is set */
	BOOLEAN same = FALSE;			/* TRUE when the two cruises we compare have the same name */
	BOOLEAN has_time[2];			/* TRUE for each cruises that actually has a time column */
	BOOLEAN *duplicate;			/* Array, TRUE for any cruise that is already listed */
	BOOLEAN *ok = VNULL;
	BOOLEAN cmdline_files = FALSE;		/* TRUE if files where given directly on the command line */

	double dt;				/* Time between crossover and previous node */
	double dist_x[2];			/* Distance(s) along track at the crossover point */
	double time_x[2];			/* Time(s) along track at the crossover point */
	double deld, delt;			/* Differences in dist and time across xpoint */
	double speed[2];			/* speed across the xpoint ( = deld/delt) */
	double **data[2];			/* Data matrices for the two data sets to be checked */
	double *xdata[2];			/* Data vectors with estimated values at crossover points */
	double *dist[2];			/* Data vectors with along-track distances */
	double *time[2];			/* Data vectors with along-track times (or dummy node indices) */
	double *t = VNULL, *y = VNULL;		/* Interpolation y(t) arrays */
	double *out;				/* Output record array */
	double west, east, south, north;	/* Used when projecting data before xover calculations */
	double X2SYS_NaN;			/* Value to write out when result is NaN */
	double heading_speed = 0.0;		/* Ignore heading calculation on segments that implies speed lower than this */
	double lower_speed = 0.0;		/* Ignore crossovers on segments that implies speed lower than this */
	double upper_speed = DBL_MAX;		/* Ignore crossovers on segments that implies speed higher than this */
	double xx, yy;				/* Temporary projection variables */
	double dist_scale;			/* Scale to give selected distance units */
	double vel_scale;			/* Scale to give selected velocity units */


	struct X2SYS_INFO *s;				/* Data format information  */
	struct GMT_XSEGMENT *ylist_A, *ylist_B;		/* y-indices sorted in increasing order */
	struct GMT_XOVER XC;				/* Structure with resulting crossovers */
	struct X2SYS_FILE_INFO data_set[2];		/* File information */
	struct X2SYS_BIX Bix;
	struct PAIR *pair = NULL;			/* Used with -Kkombinations.lis option */

	PFI out_record;			/* Pointer to function that writes the crossover record */
	PFD azimuth_func;
	FILE *fp;

	BOOLEAN combo_ok (char *name_1, char *name_2, struct PAIR *pair, int n_pairs);


/*----------------------------------END OF VARIBLE DECLARATIONS-----------------------------------------------*/

	argc = GMT_begin (argc, argv);
	for (i = strlen(argv[0]); i >= 0 && argv[0][i] != '/'; i--);
	X2SYS_program = &argv[0][i+1];	/* Name without full path */

	gmtdefs.interpolant = 0;	/* Linear interpolation default here */
	dist[0] = dist[1] = NULL;
	
	for (i = 1; i < argc; i++) {
		if (argv[i][0] == '-') {
			switch (argv[i][1]) {

				/* Common parameters */

				case 'R':
				case 'J':
				case 'V':
				case 'b':
				case '\0':
					error += GMT_parse_common_options (argv[i], &west, &east, &south, &north);
					break;

				/* Supplemental parameters */

				case 'I':
					switch (argv[i][2]) {
						case 'l':
						case 'L':
							gmtdefs.interpolant = 0;
							break;
						case 'a':
						case 'A':
							gmtdefs.interpolant = 1;
							break;
						case 'c':
						case 'C':
							gmtdefs.interpolant = 2;
							break;
						default:	/* Use GMT defaults */
							break;
					}
					break;
				case 'K':	/* Get list of approved filepair combinations to check */
					fp_combo = &argv[i][2];
					combinations = TRUE;
					break;
				case 'L':	/* Compatibility with old xover mode */
					xover_mode = TRUE;
					break;
				case 'S':	/* Speed checks */
					switch (argv[i][2]) {
						case 'L':
						case 'l':	/* Lower cutoff speed */
							lower_speed = atof (&argv[i][3]);
							speed_check = TRUE;
							break;
						case 'U':
						case 'u':	/* Upper cutoff speed */
							upper_speed = atof (&argv[i][3]);
							speed_check = TRUE;
							break;
						case 'H':
						case 'h':	/* Heading calculation cutoff speed */
							heading_speed = atof (&argv[i][3]);
							heading_check = TRUE;
							break;
						default:
							fprintf (stderr, "%s: Syntax Error: -S<l|h|u><speed>\n", GMT_program);
							error++;
							break;
					}
					break;
				case 'T':
					TAG = &argv[i][2];
					t_given = TRUE;
					break;
				case 'W':	/* Get new window half-width as number of points */
					half_window_width = atoi (&argv[i][2]);
					break;
				case 'Q':	/* Specify internal or external only */
					if (argv[i][2] == 'e') internal = FALSE;
					if (argv[i][2] == 'i') external = FALSE;
					break;
				case '2':	/* Return z1, z1 rather than (z1-z1) and 0.5 * (z1 + z2) */
					two_values = TRUE;
					break;
				default:
					error = TRUE;
					break;
			}
		}
	}

	if (argc == 1 || error || GMT_give_synopsis_and_exit) {
		fprintf (stderr, "%s %s - calculate crossovers\n\n", GMT_program, X2SYS_VERSION);
		fprintf (stderr, "usage: x2sys_cross <files> -T<TAG> [-Il|a|c] [%s] [-K<combi.lis>] [-L]\n", GMT_J_OPT);
		fprintf (stderr, "	[-Qe|i] [%s] [-Sl|h|u<speed>] [-V] [-W<size>] [%s] [-2]\n\n", GMT_Rgeo_OPT, GMT_bo_OPT);

		fprintf (stderr, "	Output is x y t1 t2 d1 d2 az1 az2 v1 v2 xval1 xmean1 xval2 xmean2 ...\n");
		fprintf (stderr, "	If time is not selected (or present) we use record numbers as proxies i1 i2\n");
		if (GMT_give_synopsis_and_exit) exit (EXIT_FAILURE);

		fprintf (stderr, "	<files> is one or more datafiles, or give =<files.lis> for a file with a list of datafiles\n");
		fprintf (stderr, "	-T <TAG> is the system tag for the data set.\n");
		fprintf (stderr, "\n\tOPTIONS:\n");
		fprintf (stderr, "	-I sets the interpolation mode.  Choose among:\n");
		fprintf (stderr, "	   l Linear interpolation [Default]\n");
		fprintf (stderr, "	   a Akima spline interpolation\n");
		fprintf (stderr, "	   c Acubic spline interpolation\n");
		GMT_explain_option ('J');
		fprintf (stderr,"	-K Gives list of file pairs that are ok to compare [Default is all combinations]\n");
		fprintf (stderr,"	-L Output data using old XOVER format [Default is X2SYS format]\n");
		fprintf (stderr,"	-Q Append e for external crossovers\n");
		fprintf (stderr,"	   Append i for internal crossovers [Default is all crossovers]\n");
		GMT_explain_option ('R');
		fprintf (stderr, "	-S Sets limits on lower and upper speeds (units determined by -Ns):\n");
		fprintf (stderr, "	   -Sl sets lower speed [Default is 0]\n");
		fprintf (stderr, "	   -Sh no headings should be computed if velocity drops below this value [0]\n");
		fprintf (stderr, "	   -Su sets upper speed [Default is Infinity]\n");
		GMT_explain_option ('V');
		fprintf (stderr,"	-W sets maximum points on either side of xover to use in interpolation [Default is 3]\n");
		fprintf (stderr,"	-2 Return z-values for each track [Default is crossover and mean value]\n");
		GMT_explain_option ('o');
		exit (EXIT_FAILURE);
	}

	if (!t_given) {
		fprintf (stderr, "%s: ERROR: Must specify -T\n", GMT_program);
		exit (EXIT_FAILURE);
	}
	if (!(internal || external)) {
		fprintf (stderr, "%s: Error: Only one of -Qe -Qi can be specified!\n", GMT_program);
		exit (EXIT_FAILURE);
	}
	if (half_window_width < 1) {
		fprintf (stderr, "%s: Error -W: window must be at least 1\n", GMT_program);
		exit (EXIT_FAILURE);
	}
	if (lower_speed > upper_speed) {
		fprintf (stderr, "%s: Error -S: lower speed cutoff higher than upper cutoff!\n", GMT_program);
		exit (EXIT_FAILURE);
	}

	x2sys_err_fail (x2sys_set_system (TAG, &s, &Bix, &GMT_io), TAG);
	if (!s->geographic) GMT_io.in_col_type[0] = GMT_io.in_col_type[1] = GMT_io.out_col_type[0] = GMT_io.out_col_type[1] = GMT_IS_UNKNOWN;

	if (s->x_col == -1 || s->y_col == -1) {
		fprintf (stderr, "%s: ERROR: lon,lat or x,y are not among data columns!\n", GMT_program);
		exit (EXIT_FAILURE);
	}
	
	if ((n_tracks = x2sys_get_tracknames (argc, argv, &trk_name, &cmdline_files)) == 0) {
		fprintf (stderr, "%s: Error: Must give at least one data set!\n", GMT_program);
		exit (EXIT_FAILURE);		
	}
	if (gmtdefs.verbose) fprintf (stderr, "%s: Files found: %d\n", GMT_program, n_tracks);

	duplicate = (BOOLEAN *)GMT_memory (VNULL, (size_t)n_tracks, sizeof (BOOLEAN), GMT_program);

	if (gmtdefs.verbose) fprintf (stderr, "%s: Checking for duplicates : ", GMT_program);
	/* Make sure there are no duplicates */
	for (A = n_duplicates = 0; A < n_tracks; A++) {	/* Loop over all files */
		if (duplicate[A]) continue;
		for (B = A + 1; B < n_tracks; B++) {
			if (duplicate[B]) continue;
			same = !strcmp (trk_name[A], trk_name[B]);
			if (same) {
				fprintf (stderr, "%s: File %s repeated on command line - skipped\n", GMT_program, trk_name[A]);
				duplicate[B] = TRUE;
				n_duplicates++;
			}
		}
	}
	if (gmtdefs.verbose) fprintf (stderr, "%d found\n", n_duplicates);
	
	if (combinations) {	/* Read list of acceptable trk_name combinations */

		if (gmtdefs.verbose) fprintf (stderr, "%s: Explicit combinations found: ", GMT_program);
		if ((fp = fopen (fp_combo, "r")) == NULL) {
			fprintf (stderr, "%s: Error: Could not open combinations file %s!\n", GMT_program, fp_combo);
			exit (EXIT_FAILURE);
		}

		n_alloc = add_chunk = GMT_CHUNK;
		pair = (struct PAIR *) GMT_memory (VNULL, (size_t)n_alloc, sizeof (struct PAIR), GMT_program);

		while (fgets (line, BUFSIZ, fp)) {

			if (line[0] == '#' || line[0] == '\n') continue;	/* Skip comments and blanks */
			GMT_chop (line);	/* Get rid of CR, LF stuff */

			if (sscanf (line, "%s %s", name1, name2) != 2) {
				fprintf (stderr, "%s: Error: Error decoding combinations file for pair %d!\n", GMT_program, n_pairs);
				exit (EXIT_FAILURE);
			}
			pair[n_pairs].id1 = strdup (name1);
			pair[n_pairs].id2 = strdup (name2);
			n_pairs++;
			if (n_pairs == n_alloc) {
				add_chunk *= 2;
				n_alloc += add_chunk;
				pair = (struct PAIR *) GMT_memory ((void *)pair, (size_t)n_alloc, sizeof (struct PAIR), GMT_program);
			}
		}
		fclose (fp);

		if (!n_pairs) {
			fprintf (stderr, "%s: Error: No combinations found in file %s!\n", GMT_program, fp_combo);
			exit (EXIT_FAILURE);
		}
		pair = (struct PAIR *) GMT_memory ((void *)pair, (size_t)n_pairs, sizeof (struct PAIR), GMT_program);
		if (gmtdefs.verbose) fprintf (stderr, "%d\n", n_pairs);
	}

	if (xover_mode && !GMT_io.binary[1]) {	/* Backwards compatibility */
		out_record = (PFI) x2sys_xover_output;
		header_format = x2sys_xover_header;
		X2SYS_NaN = (double) GMTMGG_NODATA;
		first_header = FALSE;	/* No special header */
	}
	else {
		out_record = (PFI) GMT_output;
		header_format = x2sys_header;
		X2SYS_NaN = GMT_d_NaN;
	}

	if (gmtdefs.interpolant == 0) half_window_width = 1;
	window_width = 2 * half_window_width;
	n_data_col = x2sys_n_data_cols (s);
	got_time = (s->t_col >= 0);
	if (!got_time) speed_check = FALSE;	/* Cannot check speed if there is no time */

	n_output = 10 + 2 * n_data_col;
	n_bin_header = (n_output - 1) * ((GMT_io.single_precision[1]) ? sizeof (float) : sizeof (double));
	GMT_io.out_col_type[0] = (!strcmp (s->info[s->x_col].name, "lon")) ? GMT_IS_LON : GMT_IS_FLOAT;
	GMT_io.out_col_type[1] = (!strcmp (s->info[s->x_col].name, "lat")) ? GMT_IS_LAT : GMT_IS_FLOAT;
	GMT_io.out_col_type[2] = GMT_io.out_col_type[3] = (got_time) ? GMT_IS_ABSTIME : GMT_IS_FLOAT;
	for (i = 0; i < n_data_col+2; i++) GMT_io.out_col_type[4+2*i] = GMT_io.out_col_type[5+2*i] = GMT_IS_FLOAT;

	if (n_data_col == 0){
		xover_locations_only = TRUE;
	}
	else {	/* Set the actual column numbers with data fields */
		t = (double *) GMT_memory (VNULL, (size_t)window_width, sizeof (double), GMT_program);
		y = (double *) GMT_memory (VNULL, (size_t)window_width, sizeof (double), GMT_program);
		col_number = (int *) GMT_memory (VNULL, (size_t)n_data_col, sizeof (int), GMT_program);
		ok = (BOOLEAN *) GMT_memory (VNULL, (size_t)n_data_col, sizeof (BOOLEAN), GMT_program);
		for (col = k = 0; col < s->n_out_columns; col++) {
			if (col == s->x_col || col == s->y_col || col == s->t_col) continue;
			col_number[k++] = col;
		}
		col_alloc = n_data_col * sizeof (int);
		if (s->t_col < 0 && gmtdefs.verbose) fprintf (stderr, "%s: No time column, use dummy times\n", GMT_program);
	}

	out = (double *) GMT_memory (VNULL, (size_t)n_output, sizeof (double), GMT_program);
	xdata[0] = (double *) GMT_memory (VNULL, (size_t)s->n_out_columns, sizeof (double), GMT_program);
	xdata[1] = (double *) GMT_memory (VNULL, (size_t)s->n_out_columns, sizeof (double), GMT_program);

	if (project_info.region_supplied && project_info.projection != GMT_NO_PROJ) {
		do_project = TRUE;
		s->geographic = FALSE;	/* Since we then have x,y projected coordinates, not lon,lat */
		s->dist_flag = 0;
		GMT_err_fail (GMT_map_setup (west, east, south, north), "");
	}

	switch (s->dist_flag) {
		case 0:	/* Cartesian */
			azimuth_func = GMT_az_backaz_cartesian;
			s->unit[X2SYS_DIST_SELECTION][0] = s->unit[X2SYS_SPEED_SELECTION][0] = 0;	/* For Cartesian there is no default unit */
			break;
		case 1:	/* Flat earth */
			azimuth_func = GMT_az_backaz_flatearth;
			break;
		case 2:	/* Great circle */
			azimuth_func = GMT_az_backaz_sphere;
			break;
		default:	/* Geodesic */
			azimuth_func = GMT_az_backaz_geodesic;
			break;
	}
		
	MGD77_Set_Unit (s->unit[X2SYS_DIST_SELECTION], &dist_scale, -1);	/* Gets scale which multiplies meters to chosen distance unit */
	MGD77_Set_Unit (s->unit[X2SYS_SPEED_SELECTION], &vel_scale, -1);	/* Sets output scale for distances using in velocities */
	switch (s->unit[X2SYS_SPEED_SELECTION][0]) {
		case 'c':
			vel_scale = 1.0;
			break;
		case 'e':
			vel_scale /= dist_scale;			/* Must counteract any distance scaling to get meters. dt is in sec so we get  m/s */
			break;
		case 'k':
			vel_scale *= (3600.0 / dist_scale);		/* Must counteract any distance scaling to get km. dt is in sec so 3600 gives  km/hr */
			break;
		case 'm':
			vel_scale *= (3600.0 / dist_scale);		/* Must counteract any distance scaling to get miles. dt is in sec so 3600 gives  miles/hr */
			break;
		case 'n':
			vel_scale *= (3600.0 / dist_scale);		/* Must counteract any distance scaling to get miles. dt is in sec so 3600 gives  miles/hr */
			break;
		default:	/*Cartesian */
			break;
	}
	
	for (A = 0; A < n_tracks; A++) {	/* Loop over all files */
		if (duplicate[A]) continue;

		if (s->x_col < 0 || s->x_col < 0) {
			fprintf (stderr, "%s: Error: x and/or y column not found for track %s!\n", GMT_program, trk_name[A]);
			exit (EXIT_FAILURE);
		}

		x2sys_err_fail ((s->read_file) (trk_name[A], &data[0], s, &data_set[0], &GMT_io, &n_rec[0]), trk_name[A]);

		has_time[0] = FALSE;
		if (got_time) {	/* Check to make sure we do in fact have time */
			for (i = n_bad = 0; i < n_rec[0]; i++) n_bad += GMT_is_dnan (data[0][s->t_col][i]);
			if (n_bad < n_rec[0]) has_time[0] = TRUE;
		}

		if (do_project) {	/* Convert all the coordinates */
			for (i = 0; i < n_rec[0]; i++) {
				GMT_geo_to_xy (data[0][s->x_col][i], data[0][s->y_col][i], &xx, &yy);
				data[0][s->x_col][i] = xx;
				data[0][s->y_col][i] = yy;
			}
		}

		GMT_err_fail (GMT_distances (data[0][s->x_col], data[0][s->y_col], n_rec[0], dist_scale, s->dist_flag, &dist[0]), "");

		time[0] = (has_time[0]) ? data[0][s->t_col] : x2sys_dummytimes (n_rec[0]) ;

		GMT_init_track (data[0][s->y_col], n_rec[0], &ylist_A);

		for (B = A; B < n_tracks; B++) {
			if (duplicate[B]) continue;

			same = !strcmp (trk_name[A], trk_name[B]);
			if (same && !(A == B)) {
				fprintf (stderr, "%s: File %s repeated on command line - skipped\n", GMT_program, trk_name[A]);
				continue;
			}
			if (!internal &&  same) continue;	/* Only do external errors */
			if (!external && !same) continue;	/* Only do internal errors */

			if (combinations && !combo_ok (trk_name[A], trk_name[B], pair, n_pairs)) continue;	/* Do not want this combo */
			
			if (gmtdefs.verbose) fprintf (stderr, "%s: Processing %s - %s : ", GMT_program, trk_name[A], trk_name[B]);

			if (same) {	/* Just set pointers */
				data[1] = data[0];
				dist[1] = dist[0];
				time[1] = time[0];
				has_time[1] = has_time[0];
				n_rec[1] = n_rec[0];
				ylist_B = ylist_A;
				data_set[1] = data_set[0];
			}
			else {	/* Must read a second file */

				x2sys_err_fail ((s->read_file) (trk_name[B], &data[1], s, &data_set[1], &GMT_io, &n_rec[1]), trk_name[B]);

				has_time[1] = FALSE;
				if (got_time) {	/* Check to make sure we do in fact have time */
					for (i = n_bad = 0; i < n_rec[1]; i++) n_bad += GMT_is_dnan (data[1][s->t_col][i]);
					if (n_bad < n_rec[1]) has_time[1] = TRUE;
				}
				
				if (do_project) {	/* Convert all the coordinates */
					for (i = 0; i < n_rec[0]; i++) {
						GMT_geo_to_xy (data[1][s->x_col][i], data[1][s->y_col][i], &xx, &yy);
						data[1][s->x_col][i] = xx;
						data[1][s->y_col][i] = yy;
					}
				}

				GMT_err_fail (GMT_distances (data[1][s->x_col], data[1][s->y_col], n_rec[1], dist_scale, s->dist_flag, &dist[1]), "");

				time[1] = (has_time[1]) ? data[1][s->t_col] : x2sys_dummytimes (n_rec[1]);

				GMT_init_track (data[1][s->y_col], n_rec[1], &ylist_B);
			}

			/* Calculate all possible crossover locations */

			nx = GMT_crossover (data[0][s->x_col], data[0][s->y_col], data_set[0].ms_rec, ylist_A, n_rec[0], data[1][s->x_col], data[1][s->y_col], data_set[1].ms_rec, ylist_B, n_rec[1], (A == B), &XC);

			if (nx && xover_locations_only) {	/* Report crossover locations only */
				if (!GMT_io.binary[1]) fprintf (GMT_stdout, "> %s - %s\n", trk_name[A], trk_name[B]);
				for (i = 0; i < nx; i++) {
					out[0] = XC.x[i];
					out[1] = XC.y[i];
					if (s->geographic) GMT_lon_range_adjust (s->geodetic, &out[0]);
					GMT_output (GMT_stdout, 2, out);
				}
				GMT_x_free (&XC);
			}
			else if (nx) {	/* Got crossovers, now estimate crossover values */

				first_crossover = TRUE;

				for (i = 0; i < nx; i++) {	/* For each potential crossover */

					memset ((void *)ok, 0, col_alloc);
					n_ok = 0;

					for (k = 0; k < 2; k++) {	/* For each of the two data sets involved */

						/* Get node number to each side of crossover location */

				/*	--o----------o--------o------X-------o-------o----------o-- ----> time
							      ^      ^       ^
							    left   xover   right			*/

						left[k]  = (GMT_LONG) floor (XC.xnode[k][i]);
						right[k] = (GMT_LONG) ceil  (XC.xnode[k][i]);
						
						if (left[k] == right[k]) {	/* Crosses exactly on a node; move left or right so interpolation will work */
							if (left[k] > 0)
								left[k]--;	/* Move back so cross occurs at right[k] */
							else
								right[k]++;	/* Move forward so cross occurs at left[k] */
						}

						deld = dist[k][right[k]] - dist[k][left[k]];
						delt = time[k][right[k]] - time[k][left[k]];

						/* Check if speed is outside accepted domain */

						speed[k] = (delt == 0.0) ? GMT_d_NaN : vel_scale * (deld / delt);
						if (speed_check && !GMT_is_dnan (speed[k]) && (speed[k] < lower_speed || speed[k] > upper_speed)) continue;

						/* Linearly estimate the crossover times and distances */

						dt = XC.xnode[k][i] - left[k];
						time_x[k] = time[k][left[k]];
						dist_x[k] = dist[k][left[k]];
						if (dt > 0.0) {
							time_x[k] += dt * delt;
							dist_x[k] += dt * deld;
						}


						for (j = 0; j < n_data_col; j++) {	/* Evaluate each field at the crossover */

							col = col_number[j];

							start = t_right = left[k];
							end = t_left = right[k];
							n_left = n_right = 0;

							xdata[k][col] = GMT_d_NaN;	/* In case of nuthin' */

							/* First find the required <window> points to the left of the xover */

							while (start >= 0 && n_left < half_window_width) {
								if (!GMT_is_dnan (data[k][col][start])) {
									n_left++;
									if (t_left > left[k]) t_left = start;
									y[half_window_width-n_left] = data[k][col][start];
									t[half_window_width-n_left] = time[k][start];
								}
								start--;
							}

							if (!n_left) continue;
							if (got_time && ((time_x[k] - time[k][t_left]) > Bix.time_gap)) continue;
							if (!got_time && ((dist_x[k] - dist[k][t_left]) > Bix.dist_gap)) continue;

							/* Ok, that worked.  Now for the right side: */

							while (end < n_rec[k] && n_right < half_window_width) {
								if (!GMT_is_dnan (data[k][col][end])) {
									y[half_window_width+n_right] = data[k][col][end];
									t[half_window_width+n_right] = time[k][end];
									n_right++;
									if (t_right < right[k]) t_right = end;
								}
								end++;
							}

							if (!n_right) continue;
							if (got_time && ((time[k][t_right] - time_x[k]) > Bix.time_gap)) continue;
							if (!got_time && ((dist[k][t_right] - dist_x[k]) > Bix.dist_gap)) continue;

							/* Ok, got enough data to interpolate at xover */

							first = half_window_width - n_left;
							n_errors = GMT_intpol (&t[first], &y[first], (n_left + n_right), (GMT_LONG)1, &time_x[k], &xdata[k][col], gmtdefs.interpolant);
							if (n_errors == 0) {	/* OK */
								ok[j]++;
								n_ok++;
							}
						}
					}

					/* Only output crossover if there are any data there */

					if (n_ok == 0) continue;
					for (j = n_ok = 0; j < n_data_col; j++) if (ok[j] == 2) n_ok++;
					if (n_ok == 0) continue;

					/* OK, got something to report */

					/* Load the out array */

					out[0] = XC.x[i];	/* Crossover location */
					out[1] = XC.y[i];

					for (k = 0; k < 2; k++) {	/* Get times, distances, headings, and velocities */

						/* Get time */

						out[2+k] = (got_time && !has_time[k]) ? X2SYS_NaN : time_x[k];

						/* Get cumulative distance at crossover */

						out[k+4] = dist_x[k];

						/* Estimate heading there */

						j = k + 6;
						out[j] = (!GMT_is_dnan (speed[k]) && (!heading_check || speed[k] > heading_speed)) ? (*azimuth_func) (data[k][s->x_col][right[k]], data[k][s->y_col][right[k]], data[k][s->x_col][left[k]], data[k][s->y_col][left[k]], FALSE) : X2SYS_NaN;

						/* Estimate velocities there */

						j = k + 8;
						out[j] = (has_time[k]) ? speed[k] : X2SYS_NaN;
					}

					/* Calculate crossover and mean value */

					for (k = 0, j = 10; k < n_data_col; k++) {
						if (two_values) {
							col = col_number[k];
							out[j++] = xdata[0][col];
							out[j++] = xdata[1][col];
						}
						else {
							if (ok[k] == 2) {
								col = col_number[k];
								out[j++] = xdata[0][col] - xdata[1][col];
								out[j++] = 0.5 * (xdata[0][col] + xdata[1][col]);
							}
							else {
								out[j] = out[j+1] = X2SYS_NaN;
								j += 2;
							}
						}
					}

					if (first_header) {	/* Write the header record */
						t_or_i = (got_time) ? 't' : 'i';
						fprintf (GMT_stdout, "# Tag: %s\n", TAG);
						fprintf (GMT_stdout, "# Command: %s", GMT_program);
						if (cmdline_files) fprintf (GMT_stdout, " [tracks]");
						for (k = 1; k < argc; k++) if (argv[k][0] == '-') fprintf (GMT_stdout, " %s", argv[k]);
						fprintf (GMT_stdout, "\n");
						fprintf (GMT_stdout, "# %s\t%s", s->info[s->out_order[s->x_col]].name, s->info[s->out_order[s->y_col]].name);
						fprintf (GMT_stdout, "\t%c_1\t%c_2\tdist_1\tdist_2\thead_1\thead_2\tvel_1\tvel_2", t_or_i, t_or_i);
						for (j = 0; j < n_data_col; j++) {
							col = col_number[j];
							if (two_values)
								fprintf (GMT_stdout, "\t%s_1\t%s_2", s->info[s->out_order[col]].name, s->info[s->out_order[col]].name);
							else
								fprintf (GMT_stdout, "\t%s_X\t%s_M", s->info[s->out_order[col]].name, s->info[s->out_order[col]].name);
						}
						fputc ('\n', GMT_stdout);
						first_header = FALSE;
					}

					if (first_crossover) {
						if (GMT_io.binary[1]) {	/* Segment record has x = NaN as flag */
							(*out_record) (GMT_stdout, 1, &GMT_d_NaN);
							sprintf (line, header_format, trk_name[A], data_set[0].year, trk_name[B], data_set[1].year);
							not_used = fwrite ((void *)line, sizeof (char), (size_t)n_bin_header, GMT_stdout);
						}
						else {
							if (header_format == x2sys_header) {
								char info[BUFSIZ], start[2][GMT_TEXT_LEN], stop[2][GMT_TEXT_LEN];
								memset ((void *)info, 0, BUFSIZ);
								for (k = 0; k < 2; k++) {
									if (has_time[k]) {	/* Find first and last record times */
										for (j = 0; j < n_rec[k] && GMT_is_dnan (time[k][j]); j++);	/* Find first non-NaN time */
										GMT_ascii_format_one (start[k], time[k][j], GMT_IS_ABSTIME);
										for (j = n_rec[k]-1; j > 0 && GMT_is_dnan (time[k][j]); j--);	/* Find last non-NaN time */
										GMT_ascii_format_one (stop[k], time[k][j], GMT_IS_ABSTIME);
									}
									else {
										(void)strcpy (start[k], "NaN");
										(void)strcpy (stop[k], "NaN");
									}
								}
								sprintf (info, "%s/%s/%g %s/%s/%g", start[0], stop[0], dist[0][n_rec[0]-1], start[1], stop[1], dist[1][n_rec[1]-1]);
								fprintf (GMT_stdout, header_format, trk_name[A], data_set[0].year, trk_name[B], data_set[1].year, info);
							}
							else
								fprintf (GMT_stdout, header_format, trk_name[A], data_set[0].year, trk_name[B], data_set[1].year);
						}
						first_crossover = FALSE;
					}

					if (s->geographic) GMT_lon_range_adjust (s->geodetic, &out[0]);
					(*out_record) (GMT_stdout, n_output, out);
				}

				GMT_x_free (&XC);
			}

			if (!same) {	/* Must free up memory for B */
				x2sys_free_data (data[1], s->n_out_columns, &data_set[1]);
				GMT_free ((void *)dist[1]);
				if (!got_time) GMT_free ((void *)time[1]);
				GMT_free ((void *)ylist_B);
			}
			if (gmtdefs.verbose) fprintf (stderr, "%d\n", nx);
		}

		/* Must free up memory for A */

		x2sys_free_data (data[0], s->n_out_columns, &data_set[0]);
		GMT_free ((void *)dist[0]);
		if (!got_time) GMT_free ((void *)time[0]);
		GMT_free ((void *)ylist_A);
	}

	/* Free up other arrays */

	GMT_free ((void *)xdata[0]);
	GMT_free ((void *)xdata[1]);
	GMT_free ((void *)out);
	GMT_free ((void *)duplicate);
	if (n_data_col) {
		GMT_free ((void *)t);
		GMT_free ((void *)y);
		GMT_free ((void *)col_number);
		GMT_free ((void *)ok);
	}
	x2sys_free_list (trk_name, n_tracks);

	x2sys_end (s);
	GMT_end (argc, argv);

	exit (EXIT_SUCCESS);
}

BOOLEAN combo_ok (char *name_1, char *name_2, struct PAIR *pair, int n_pairs)
{
	int i;

	/* Return TRUE if this particular combination is found in the list of pairs */

	for (i = 0; i < n_pairs; i++) {
		if (!(strcmp (name_1, pair[i].id1) || strcmp (name_2, pair[i].id2))) return (TRUE);
		if (!(strcmp (name_2, pair[i].id1) || strcmp (name_1, pair[i].id2))) return (TRUE);
	}
	return (FALSE);
}
