Better algorithm to merge gps locations & locations names from webservice

This no longer abuses the dive merging code (which would leave stray
"dives" behind if a gps fix couldn't be merged with any of the dives) and
instead parses the gps fixes into a second table and then walks that table
and tries to find matching dives.

The code tries to be reasonably smart about this. If we have
auto-generated GPS fixes at regular intervals, we look for a fix that is
during a dive (that's likely when the boat where the phone is staying dry
is more or less above the diver having fun). And if we have named entries
(so the user typed in a location name) we try to match them in order to
the dives that happened "that day" (where "that day" is about 6h before
and after the timestamp of the gps fix).

This commit also renames dive_has_location() to dive_has_gps_location() as
the difference between if(!dive->location) and if(dives_has_location) is a
bit too subtle...

Signed-off-by: Dirk Hohndel <dirk@hohndel.org>

7 files changed, 119 insertions, 8 deletions

diff --git a/dive.c b/dive.c
index d86c7de2a..a0cb60ba6 100644
--- a/dive.c
+++ b/dive.c
@@ -1519,3 +1519,38 @@ struct dive *merge_dives(struct dive *a, struct dive *b, int offset, gboolean pr
 	fixup_dive(res);
 	return res;
 }
+
+struct dive *find_dive_including(timestamp_t when)
+{
+	int i;
+	struct dive *dive;
+
+	/* binary search, anyone? Too lazy for now;
+	 * also we always use the duration from the first divecomputer
+	 *     could this ever be a problem? */
+	for_each_dive(i, dive) {
+		if (dive->when <= when && when <= dive->when + dive->dc.duration.seconds)
+			return dive;
+	}
+	return NULL;
+}
+
+gboolean dive_within_time_range(struct dive *dive, timestamp_t when, timestamp_t offset)
+{
+	return when - offset <= dive->when && dive->when + dive->dc.duration.seconds <= when + offset;
+}
+
+/* find the n-th dive that is part of a group of dives within the offset around 'when'.
+ *  How is that for a vague definition of what this function should do... */
+struct dive *find_dive_n_near(timestamp_t when, int n, timestamp_t offset)
+{
+	int i, j = 0;
+	struct dive *dive;
+
+	for_each_dive(i, dive) {
+		if (dive_within_time_range(dive, when, offset))
+			if (++j == n)
+				return dive;
+	}
+	return NULL;
+}
diff --git a/dive.h b/dive.h
index 2f4dcbd9e..e719f2289 100644
--- a/dive.h
+++ b/dive.h
@@ -321,11 +321,19 @@ struct dive {
 	struct divecomputer dc;
 };
 
-static inline int dive_has_location(struct dive *dive)
+static inline int dive_has_gps_location(struct dive *dive)
 {
 	return dive->latitude.udeg || dive->longitude.udeg;
 }
 
+static inline void copy_gps_location(struct dive *from, struct dive *to)
+{
+	if (from && to) {
+		to->latitude.udeg = from->latitude.udeg;
+		to->longitude.udeg = from->longitude.udeg;
+	}
+}
+
 /* Pa = N/m^2 - so we determine the weight (in N) of the mass of 10m
  * of water (and use standard salt water at 1.03kg per liter if we don't know salinity)
  * and add that to the surface pressure (or to 1013 if that's unknown) */
@@ -433,6 +441,13 @@ extern struct dive_table dive_table;
 extern int selected_dive;
 #define current_dive (get_dive(selected_dive))
 
+static inline struct dive *get_gps_location(int nr, struct dive_table *table)
+{
+	if (nr >= table->nr || nr < 0)
+		return NULL;
+	return table->dives[nr];
+}
+
 static inline struct dive *get_dive(int nr)
 {
 	if (nr >= dive_table.nr || nr < 0)
@@ -450,6 +465,9 @@ static inline struct dive *get_dive(int nr)
 #define for_each_dive(_i,_x) \
 	for ((_i) = 0; ((_x) = get_dive(_i)) != NULL; (_i)++)
 
+#define for_each_gps_location(_i,_x) \
+	for ((_i) = 0; ((_x) = get_gps_location(_i, &gps_location_table)) != NULL; (_i)++)
+
 static inline struct dive *get_dive_by_diveid(int diveid, int deviceid)
 {
 	int i;
@@ -464,6 +482,9 @@ static inline struct dive *get_dive_by_diveid(int diveid, int deviceid)
 	}
 	return NULL;
 }
+extern struct dive *find_dive_including(timestamp_t when);
+extern gboolean dive_within_time_range(struct dive *dive, timestamp_t when, timestamp_t offset);
+struct dive *find_dive_n_near(timestamp_t when, int n, timestamp_t offset);
 
 /* Check if two dive computer entries are the exact same dive (-1=no/0=maybe/1=yes) */
 extern int match_one_dc(struct divecomputer *a, struct divecomputer *b);
@@ -504,6 +525,7 @@ extern void record_dive(struct dive *dive);
 extern struct sample *prepare_sample(struct divecomputer *dc);
 extern void finish_sample(struct divecomputer *dc);
 
+extern void sort_table(struct dive_table *table);
 extern void report_dives(gboolean imported, gboolean prefer_imported);
 extern struct dive *fixup_dive(struct dive *dive);
 extern struct dive *merge_dives(struct dive *a, struct dive *b, int offset, gboolean prefer_downloaded);
diff --git a/divelist.c b/divelist.c
index 882ba3bc6..5a942c13f 100644
--- a/divelist.c
+++ b/divelist.c
@@ -875,7 +875,7 @@ GdkPixbuf *get_gps_icon(void)
 
 static GdkPixbuf *get_gps_icon_for_dive(struct dive *dive)
 {
-	if (dive_has_location(dive))
+	if (dive_has_gps_location(dive))
 		return get_gps_icon();
 	else
 		return NULL;
@@ -1608,7 +1608,7 @@ gboolean icon_click_cb(GtkWidget *w, GdkEventButton *event, gpointer data)
 			gtk_tree_model_get_iter(MODEL(dive_list), &iter, path);
 			gtk_tree_model_get(MODEL(dive_list), &iter, DIVE_INDEX, &idx, -1);
 			dive = get_dive(idx);
-			if (dive && dive_has_location(dive))
+			if (dive && dive_has_gps_location(dive))
 				show_gps_location(dive, NULL);
 		}
 		if (path)
@@ -2435,7 +2435,7 @@ static void popup_divelist_menu(GtkTreeView *tree_view, GtkTreeModel *model, int
 		}
 #if HAVE_OSM_GPS_MAP
 		/* Only offer to show on map if it has a location. */
-		if (dive_has_location(dive)) {
+		if (dive_has_gps_location(dive)) {
 			menuitem = gtk_menu_item_new_with_label(_("Show in map"));
 			g_signal_connect(menuitem, "activate", G_CALLBACK(show_gps_location_cb), dive);
 			gtk_menu_shell_append(GTK_MENU_SHELL(menu), menuitem);
diff --git a/gps.c b/gps.c
index 31be2bbc5..15ee65830 100644
--- a/gps.c
+++ b/gps.c
@@ -242,7 +242,7 @@ void show_gps_locations()
 		map = init_map();
 
 	for_each_dive(idx, dive) {
-		if (dive_has_location(dive)) {
+		if (dive_has_gps_location(dive)) {
 			add_gps_point(map, dive->latitude.udeg / 1000000.0,
 				dive->longitude.udeg / 1000000.0);
 		}
diff --git a/info.c b/info.c
index 65ad8b128..2916c0eaf 100644
--- a/info.c
+++ b/info.c
@@ -675,7 +675,7 @@ static void dive_info_widget(GtkWidget *box, struct dive *dive, struct dive_info
 
 	info->location = text_entry(box, _("Location"), location_list, dive->location);
 
-	if (dive_has_location(dive))
+	if (dive_has_gps_location(dive))
 		print_gps_coordinates(gps_text, sizeof(gps_text), dive->latitude.udeg / 1000000.0,
 								  dive->longitude.udeg / 1000000.0);
 	hbox = gtk_hbox_new(FALSE, 2);
diff --git a/main.c b/main.c
index 4cacb0375..170481035 100644
--- a/main.c
+++ b/main.c
@@ -50,6 +50,11 @@ static int sortfn(const void *_a, const void *_b)
 	return 0;
 }
 
+void sort_table(struct dive_table *table)
+{
+	qsort(table->dives, table->nr, sizeof(struct dive *), sortfn);
+}
+
 const char *weekday(int wday)
 {
 	static const char wday_array[7][7] = {
@@ -157,7 +162,7 @@ void report_dives(gboolean is_imported, gboolean prefer_imported)
 	/* This does the right thing for -1: NULL */
 	last = get_dive(preexisting-1);
 
-	qsort(dive_table.dives, dive_table.nr, sizeof(struct dive *), sortfn);
+	sort_table(&dive_table);
 
 	for (i = 1; i < dive_table.nr; i++) {
 		struct dive **pp = &dive_table.dives[i-1];
diff --git a/webservice.c b/webservice.c
index 9dde771e8..fec2ccf2d 100644
--- a/webservice.c
+++ b/webservice.c
@@ -4,6 +4,7 @@
 #include <libxml/tree.h>
 #include <libxml/parser.h>
 #include "dive.h"
+#include "divelist.h"
 #include "display-gtk.h"
 
 struct dive_table gps_location_table;
@@ -144,6 +145,52 @@ static void download_dialog_delete(GtkWidget *w, gpointer data)
 	download_dialog_release_xml(state);
 }
 
+static gboolean is_automatic_fix(struct dive *gpsfix)
+{
+	if (gpsfix && gpsfix->location && !strcmp(gpsfix->location, "automatic fix"))
+		return TRUE;
+	return FALSE;
+}
+
+#define SAME_GROUP 6 * 3600   // six hours
+
+static void merge_locations_into_dives(void)
+{
+	int i, nr = 0;
+	struct dive *gpsfix, *last_named_fix = NULL, *dive;
+
+	sort_table(&gps_location_table);
+
+	for_each_gps_location(i, gpsfix) {
+		if (is_automatic_fix(gpsfix)) {
+			dive = find_dive_including(gpsfix->when);
+			if (dive && !dive_has_gps_location(dive))
+				copy_gps_location(gpsfix, dive);
+		} else {
+			if (last_named_fix && dive_within_time_range(last_named_fix, gpsfix->when, SAME_GROUP)) {
+				nr++;
+			} else {
+				nr = 1;
+				last_named_fix = gpsfix;
+			}
+			dive = find_dive_n_near(gpsfix->when, nr, SAME_GROUP);
+			if (dive) {
+				if (!dive_has_gps_location(dive))
+					copy_gps_location(gpsfix, dive);
+				if (!dive->location)
+					dive->location = strdup(gpsfix->location);
+			} else {
+				struct tm tm;
+				utc_mkdate(gpsfix->when, &tm);
+				printf("didn't find dive matching gps fix named %s @ %04d-%02d-%02d %02d:%02d:%02d\n",
+					gpsfix->location,
+					tm.tm_year+1900, tm.tm_mon+1, tm.tm_mday,
+					tm.tm_hour, tm.tm_min, tm.tm_sec);
+			}
+		}
+	}
+}
+
 void webservice_download_dialog(void)
 {
 	const guint pad = 6;
@@ -207,7 +254,9 @@ void webservice_download_dialog(void)
 		/* apply download */
 		parse_xml_buffer(_("Webservice"), state.xmldata, state.xmldata_len, &gps_location_table, NULL);
 		/* now merge the data in the gps_location table into the dive_table */
-		// TBD
+		merge_locations_into_dives();
+		mark_divelist_changed(TRUE);
+		dive_list_update_dives();
 		/* store last entered uid in config */
 		subsurface_set_conf("webservice_uid", gtk_entry_get_text(GTK_ENTRY(uid)));
 	}