Import: pass a dive table to process_imported_dives()

Dives were directly imported into the global dive table and then
merged in process_imported_dives(). Make this interface more flexible,
by passing an independent dive table.

The dive table of the to-be-imported dives will be sorted and merged.
Then each dive is inserted in a one-by-one manner to into the global
dive table.

This actually introduces (at least) two functional changes:
1) If a new dive spans two old dives, it will only be merged to the
   first dive. But this seems like a pathological case, which is of
   dubious value anyway.
2) Dives unrelated to the import will not be merged. The old code
   would happily merge dives that were not even close to the
   newly imported dives. A surprising behavior.

Signed-off-by: Berthold Stoeger <bstoeger@mail.tuwien.ac.at>

9 files changed, 203 insertions, 111 deletions

diff --git a/core/divelist.c b/core/divelist.c
index 94adc92dc..41ebc4364 100644
--- a/core/divelist.c
+++ b/core/divelist.c
@@ -16,7 +16,7 @@
  * void update_cylinder_related_info(struct dive *dive)
  * void dump_trip_list(void)
  * void insert_trip(dive_trip_t **dive_trip_p)
- * void remove_dive_from_trip(struct dive *dive)
+ * void remove_dive_from_trip(struct dive *dive, bool was_autogen)
  * void add_dive_to_trip(struct dive *dive, dive_trip_t *trip)
  * dive_trip_t *create_and_hookup_trip_from_dive(struct dive *dive)
  * void autogroup_dives(void)
@@ -30,6 +30,7 @@
  * void remove_autogen_trips()
  * void sort_table(struct dive_table *table)
  * bool is_trip_before_after(const struct dive *dive, bool before)
+ * void delete_dive_from_table(struct dive_table *table, int idx)
  */
 #include <unistd.h>
 #include <stdio.h>
@@ -917,21 +918,29 @@ void autogroup_dives(void)
 #endif
 }
 
+/* Remove a dive from a dive table. This assumes that the
+ * dive was already removed from any trip and deselected.
+ * It simply shrinks the table and frees the trip */
+void delete_dive_from_table(struct dive_table *table, int idx)
+{
+	int i;
+	free_dive(table->dives[idx]);
+	for (i = idx; i < table->nr - 1; i++)
+		table->dives[i] = table->dives[i + 1];
+	table->dives[--table->nr] = NULL;
+}
+
 /* this implements the mechanics of removing the dive from the table,
  * but doesn't deal with updating dive trips, etc */
 void delete_single_dive(int idx)
 {
-	int i;
 	struct dive *dive = get_dive(idx);
 	if (!dive)
 		return; /* this should never happen */
 	remove_dive_from_trip(dive, false);
 	if (dive->selected)
 		deselect_dive(idx);
-	for (i = idx; i < dive_table.nr - 1; i++)
-		dive_table.dives[i] = dive_table.dives[i + 1];
-	dive_table.dives[--dive_table.nr] = NULL;
-	free_dive(dive);
+	delete_dive_from_table(&dive_table, idx);
 }
 
 struct dive **grow_dive_table(struct dive_table *table)
@@ -1219,16 +1228,16 @@ void remove_autogen_trips()
  * what the numbers should be - in which case you need to do
  * a manual re-numbering.
  */
-static void try_to_renumber(struct dive *last, int preexisting)
+static void try_to_renumber(int preexisting)
 {
 	int i, nr;
+	struct dive *last = get_dive(preexisting - 1);
 
 	/*
-	 * If the new dives aren't all strictly at the end,
-	 * we're going to expect the user to do a manual
-	 * renumbering.
+	 * If there was a last dive, but it didn't have
+	 * a number, give up.
 	 */
-	if (preexisting && get_dive(preexisting - 1) != last)
+	if (last && !last->number)
 		return;
 
 	/*
@@ -1266,40 +1275,18 @@ void process_loaded_dives()
 	sort_table(&dive_table);
 }
 
-void process_imported_dives(bool prefer_imported)
+/*
+ * Merge subsequent dives in a table, if mergeable. This assumes
+ * that the dives are neither selected, not part of a trip, as
+ * is the case of freshly imported dives.
+ */
+static void merge_imported_dives(struct dive_table *table)
 {
 	int i;
-	int preexisting = dive_table.preexisting;
-	struct dive *last;
-
-	/* If no dives were imported, don't bother doing anything */
-	if (preexisting >= dive_table.nr)
-		return;
-
-	/* check if we need a nickname for the divecomputer for newly downloaded dives;
-	 * since we know they all came from the same divecomputer we just check for the
-	 * first one */
-	if (dive_table.dives[preexisting]->downloaded)
-		set_dc_nickname(dive_table.dives[preexisting]);
-	else
-		/* they aren't downloaded, so record / check all new ones */
-		for (i = preexisting; i < dive_table.nr; i++)
-			set_dc_nickname(dive_table.dives[i]);
-
-	for (i = preexisting; i < dive_table.nr; i++)
-		dive_table.dives[i]->downloaded = true;
-
-	/* This does the right thing for -1: NULL */
-	last = get_dive(preexisting - 1);
-
-	sort_table(&dive_table);
-
-	for (i = 1; i < dive_table.nr; i++) {
-		struct dive **pp = &dive_table.dives[i - 1];
-		struct dive *prev = pp[0];
-		struct dive *dive = pp[1];
+	for (i = 1; i < table->nr; i++) {
+		struct dive *prev = table->dives[i - 1];
+		struct dive *dive = table->dives[i];
 		struct dive *merged;
-		int id;
 
 		/* only try to merge overlapping dives - or if one of the dives has
 		 * zero duration (that might be a gps marker from the webservice) */
@@ -1307,33 +1294,138 @@ void process_imported_dives(bool prefer_imported)
 		    dive_endtime(prev) < dive->when)
 			continue;
 
-		merged = try_to_merge(prev, dive, prefer_imported);
+		merged = try_to_merge(prev, dive, false);
 		if (!merged)
 			continue;
 
-		// remember the earlier dive's id
-		id = prev->id;
-
-		/* careful - we might free the dive that last points to. Oops... */
-		if (last == prev || last == dive)
-			last = merged;
+		/* Overwrite the first of the two dives and remove the second */
+		free_dive(prev);
+		table->dives[i - 1] = merged;
+		delete_dive_from_table(table, i);
 
 		/* Redo the new 'i'th dive */
 		i--;
-		add_single_dive(i, merged);
-		delete_single_dive(i + 1);
-		delete_single_dive(i + 1);
-		// keep the id or the first dive for the merged dive
-		merged->id = id;
 	}
+}
+
+/*
+ * Try to merge a new dive into the dive at position idx. Return
+ * true on success. On success, the dive to add and the old dive
+ * will be deleted. On failure, they are untouched.
+ * If "prefer_imported" is true, use data of the new dive.
+ */
+static bool try_to_merge_into(struct dive *dive_to_add, int idx, bool prefer_imported)
+{
+	struct dive *old_dive = dive_table.dives[idx];
+	struct dive_trip *trip = old_dive->divetrip;
+	struct dive *merged = try_to_merge(old_dive, dive_to_add, prefer_imported);
+	if (!merged)
+		return false;
+
+	merged->id = old_dive->id;
+	merged->selected = old_dive->selected;
+	dive_table.dives[idx] = merged;
+	if (trip) {
+		remove_dive_from_trip(old_dive, false);
+		add_dive_to_trip(merged, trip);
+	}
+	free_dive(old_dive);
+	free_dive(dive_to_add);
+
+	return true;
+}
+
+/*
+ * Add imported dive to global dive table. Overlapping dives will
+ * be merged if possible. If prefer_imported is true, data of the
+ * new dives are prioritized in such a case.
+ * Note: the dives in import_table are consumed! On return import_table
+ * has size 0.
+ */
+void process_imported_dives(struct dive_table *import_table, bool prefer_imported)
+{
+	int i, j;
+	struct dive *old_dive, *merged;
+	int preexisting;
+	bool sequence_changed = false;
+
+	/* If no dives were imported, don't bother doing anything */
+	if (!import_table->nr)
+		return;
+
+	/* check if we need a nickname for the divecomputer for newly downloaded dives;
+	 * since we know they all came from the same divecomputer we just check for the
+	 * first one */
+	if (import_table->dives[0]->downloaded)
+		set_dc_nickname(import_table->dives[0]);
+	else
+		/* they aren't downloaded, so record / check all new ones */
+		for (i = 0; i < import_table->nr; i++)
+			set_dc_nickname(import_table->dives[i]);
+
+	/* Sort the table of dives to be imported and combine mergable dives */
+	sort_table(import_table);
+	merge_imported_dives(import_table);
+
+	for (i = 0; i < import_table->nr; i++)
+		import_table->dives[i]->downloaded = true;
+
+	/* Merge newly imported dives into the dive table.
+	 * Since both lists (old and new) are sorted, we can step
+	 * through them concurrently and locate the insertions points.
+	 * Once found, check if the new dive can be merged in the
+	 * previous or next dive.
+	 * Note that this doesn't consider pathological cases such as:
+	 *  - New dive "connects" two old dives (turn three into one).
+	 *  - New dive can not be merged into adjacent but some further dive.
+	 */
+	j = 0; /* Index in old dives */
+	preexisting = dive_table.nr; /* Remember old size for renumbering */
+	for (i = 0; i < import_table->nr; i++) {
+		struct dive *dive_to_add = import_table->dives[i];
+
+		/* Find insertion point. */
+		while (j < dive_table.nr && dive_table.dives[j]->when < dive_to_add->when)
+			j++;
+
+		/* Try to merge into previous dive. */
+		if (j > 0 && dive_endtime(dive_table.dives[j - 1]) > dive_to_add->when) {
+			if (try_to_merge_into(dive_to_add, j - 1, prefer_imported))
+				continue;
+		}
+
+		/* That didn't merge into the previous dive. If we're
+		 * at the end of the dive table, quit the loop and add
+		 * all new dives at the end. */
+		if (j >= dive_table.nr)
+			break;
+
+		/* Try to merge into next dive. */
+		if (dive_endtime(dive_to_add) > dive_table.dives[j]->when) {
+			if (try_to_merge_into(dive_to_add, j, prefer_imported))
+				continue;
+		}
+
+		/* We couldnt merge dives, add at the given position. */
+		add_single_dive(j, dive_to_add);
+		j++;
+		sequence_changed = true;
+	}
+
+	/* If there are still dives to add, add them at the end of the dive table. */
+	for ( ; i <  import_table->nr; i++)
+		add_single_dive(dive_table.nr, import_table->dives[i]);
 
 	/* make sure no dives are still marked as downloaded */
-	for (i = 1; i < dive_table.nr; i++)
+	for (i = 0; i < dive_table.nr; i++)
 		dive_table.dives[i]->downloaded = false;
 
-	/* If there are dives in the table, are they numbered */
-	if (!last || last->number)
-		try_to_renumber(last, preexisting);
+	/* we took care of all dives, clean up the import table */
+	import_table->nr = 0;
+
+	/* If the sequence wasn't changed, renumber */
+	if (!sequence_changed)
+		try_to_renumber(preexisting);
 
 	mark_divelist_changed(true);
 }
diff --git a/core/divelist.h b/core/divelist.h
index af47d0f23..885dbe67f 100644
--- a/core/divelist.h
+++ b/core/divelist.h
@@ -19,7 +19,7 @@ extern int init_decompression(struct deco_state *ds, struct dive *dive);
 
 /* divelist core logic functions */
 extern void process_loaded_dives();
-extern void process_imported_dives(bool prefer_imported);
+extern void process_imported_dives(struct dive_table *import_table, bool prefer_imported);
 extern char *get_dive_gas_string(struct dive *dive);
 
 struct dive **grow_dive_table(struct dive_table *table);
@@ -43,6 +43,7 @@ extern struct dive *last_selected_dive();
 extern bool is_trip_before_after(const struct dive *dive, bool before);
 extern void set_dive_nr_for_current_dive();
 extern timestamp_t get_surface_interval(timestamp_t when);
+extern void delete_dive_from_table(struct dive_table *table, int idx);
 
 int get_min_datafile_version();
 void reset_min_datafile_version();
diff --git a/desktop-widgets/divelogimportdialog.cpp b/desktop-widgets/divelogimportdialog.cpp
index 5df477349..874c33adc 100644
--- a/desktop-widgets/divelogimportdialog.cpp
+++ b/desktop-widgets/divelogimportdialog.cpp
@@ -896,14 +896,15 @@ int DiveLogImportDialog::parseTxtHeader(QString fileName, char **params, int pnr
 
 void DiveLogImportDialog::on_buttonBox_accepted()
 {
+	struct dive_table table = { 0 };
 	QStringList r = resultModel->result();
 	if (ui->knownImports->currentText() != "Manual import") {
 		for (int i = 0; i < fileNames.size(); ++i) {
 			if (ui->knownImports->currentText() == "Seabear CSV") {
-				parse_seabear_log(qPrintable(fileNames[i]), &dive_table);
+				parse_seabear_log(qPrintable(fileNames[i]), &table);
 			} else if (ui->knownImports->currentText() == "Poseidon MkVI") {
 				QPair<QString, QString> pair = poseidonFileNames(fileNames[i]);
-				parse_txt_file(qPrintable(pair.second), qPrintable(pair.first), &dive_table);
+				parse_txt_file(qPrintable(pair.second), qPrintable(pair.first), &table);
 			} else {
 				char *params[49];
 				int pnr = 0;
@@ -920,7 +921,7 @@ void DiveLogImportDialog::on_buttonBox_accepted()
 				pnr = setup_csv_params(r, params, pnr);
 				parse_csv_file(qPrintable(fileNames[i]), params, pnr - 1,
 						specialCSV.contains(ui->knownImports->currentIndex()) ? qPrintable(CSVApps[ui->knownImports->currentIndex()].name) : "csv",
-						&dive_table);
+						&table);
 			}
 		}
 	} else {
@@ -984,7 +985,7 @@ void DiveLogImportDialog::on_buttonBox_accepted()
 				params[pnr++] = intdup(r.indexOf(tr("Rating")));
 				params[pnr++] = NULL;
 
-				parse_manual_file(qPrintable(fileNames[i]), params, pnr - 1, &dive_table);
+				parse_manual_file(qPrintable(fileNames[i]), params, pnr - 1, &table);
 			} else {
 				char *params[51];
 				int pnr = 0;
@@ -1001,12 +1002,12 @@ void DiveLogImportDialog::on_buttonBox_accepted()
 				pnr = setup_csv_params(r, params, pnr);
 				parse_csv_file(qPrintable(fileNames[i]), params, pnr - 1,
 						specialCSV.contains(ui->knownImports->currentIndex()) ? qPrintable(CSVApps[ui->knownImports->currentIndex()].name) : "csv",
-						&dive_table);
+						&table);
 			}
 		}
 	}
 
-	process_imported_dives(false);
+	process_imported_dives(&table, false);
 	MainWindow::instance()->refreshDisplay();
 }
 
diff --git a/desktop-widgets/downloadfromdivecomputer.cpp b/desktop-widgets/downloadfromdivecomputer.cpp
index 561ff2998..46cb0418b 100644
--- a/desktop-widgets/downloadfromdivecomputer.cpp
+++ b/desktop-widgets/downloadfromdivecomputer.cpp
@@ -487,34 +487,30 @@ void DownloadFromDCWidget::on_cancel_clicked()
 
 void DownloadFromDCWidget::on_ok_clicked()
 {
-	struct dive *dive;
-
 	if (currentState != DONE && currentState != ERROR)
 		return;
 
-	// record all the dives in the 'real' dive_table
-	for (int i = 0; i < downloadTable.nr; i++) {
+	// delete non-selected dives
+	int total = downloadTable.nr;
+	int j = 0;
+	for (int i = 0; i < total; i++) {
 		if (diveImportedModel->data(diveImportedModel->index(i, 0), Qt::CheckStateRole) == Qt::Checked)
-			record_dive(downloadTable.dives[i]);
+			j++;
 		else
-			clear_dive(downloadTable.dives[i]);
-		downloadTable.dives[i] = NULL;
+			delete_dive_from_table(&downloadTable, j);
 	}
-	downloadTable.nr = 0;
 
-	int uniqId, idx;
-	// remember the last downloaded dive (on most dive computers this will be the chronologically
-	// first new dive) and select it again after processing all the dives
 	MainWindow::instance()->dive_list()->unselectDives();
 
-	dive = get_dive(dive_table.nr - 1);
-	if (dive != NULL) {
-		uniqId = get_dive(dive_table.nr - 1)->id;
-		process_imported_dives(preferDownloaded());
+	if (downloadTable.nr > 0) {
+		// remember the last downloaded dive (on most dive computers this will be the chronologically
+		// first new dive) and select it again after processing all the dives
+		int uniqId = downloadTable.dives[downloadTable.nr - 1]->id;
+		process_imported_dives(&downloadTable, preferDownloaded());
 		// after process_imported_dives does any merging or resorting needed, we need
 		// to recreate the model for the dive list so we can select the newest dive
 		MainWindow::instance()->recreateDiveList();
-		idx = get_idx_by_uniq_id(uniqId);
+		int idx = get_idx_by_uniq_id(uniqId);
 		// this shouldn't be necessary - but there are reports that somehow existing dives stay selected
 		// (but not visible as selected)
 		MainWindow::instance()->dive_list()->unselectDives();
diff --git a/desktop-widgets/mainwindow.cpp b/desktop-widgets/mainwindow.cpp
index e37c7a7bd..9049b741b 100644
--- a/desktop-widgets/mainwindow.cpp
+++ b/desktop-widgets/mainwindow.cpp
@@ -1733,12 +1733,13 @@ void MainWindow::importFiles(const QStringList fileNames)
 		return;
 
 	QByteArray fileNamePtr;
+	struct dive_table table = { 0 };
 
 	for (int i = 0; i < fileNames.size(); ++i) {
 		fileNamePtr = QFile::encodeName(fileNames.at(i));
-		parse_file(fileNamePtr.data(), &dive_table);
+		parse_file(fileNamePtr.data(), &table);
 	}
-	process_imported_dives(false);
+	process_imported_dives(&table, false);
 	refreshDisplay();
 }
 
diff --git a/desktop-widgets/subsurfacewebservices.cpp b/desktop-widgets/subsurfacewebservices.cpp
index a7586c128..693463bf1 100644
--- a/desktop-widgets/subsurfacewebservices.cpp
+++ b/desktop-widgets/subsurfacewebservices.cpp
@@ -767,8 +767,9 @@ void DivelogsDeWebServices::buttonClicked(QAbstractButton *button)
 			break;
 		}
 		/* parse file and import dives */
-		parse_file(QFile::encodeName(zipFile.fileName()), &dive_table);
-		process_imported_dives(false);
+		struct dive_table table = { 0 };
+		parse_file(QFile::encodeName(zipFile.fileName()), &table);
+		process_imported_dives(&table, false);
 		MainWindow::instance()->refreshDisplay();
 
 		/* store last entered user/pass in config */
diff --git a/qt-models/diveimportedmodel.cpp b/qt-models/diveimportedmodel.cpp
index 48d9a1dcd..ebe803244 100644
--- a/qt-models/diveimportedmodel.cpp
+++ b/qt-models/diveimportedmodel.cpp
@@ -163,21 +163,17 @@ void DiveImportedModel::recordDives()
 		// nothing to do, just exit
 		return;
 
-	// walk the table of imported dives and record the ones that the user picked
-	// clearing out the table as we go
-	for (int i = 0; i < rowCount(); i++) {
-		struct dive *d = diveTable->dives[i];
-		if (d && checkStates[i]) {
-			record_dive(d);
-		} else {
-			// we should free the dives that weren't recorded
-			clear_dive(d);
-			free(d);
-		}
-		diveTable->dives[i] = NULL;
+	// delete non-selected dives
+	int total = diveTable->nr;
+	int j = 0;
+	for (int i = 0; i < total; i++) {
+		if (checkStates[i])
+			j++;
+		else
+			delete_dive_from_table(&downloadTable, j);
 	}
-	diveTable->nr = 0;
-	process_imported_dives(true);
+
+	process_imported_dives(diveTable, true);
 	if (autogroup)
 		autogroup_dives();
 }
diff --git a/tests/testmerge.cpp b/tests/testmerge.cpp
index 50bfd6e50..a99fd65e7 100644
--- a/tests/testmerge.cpp
+++ b/tests/testmerge.cpp
@@ -21,10 +21,11 @@ void TestMerge::testMergeEmpty()
 	/*
 	 * check that we correctly merge mixed cylinder dives
 	 */
-	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47.xml", &dive_table), 0);
-	process_imported_dives(false);
-	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test48.xml", &dive_table), 0);
-	process_imported_dives(false);
+	struct dive_table table = { 0 };
+	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47.xml", &table), 0);
+	process_imported_dives(&table, false);
+	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test48.xml", &table), 0);
+	process_imported_dives(&table, false);
 	QCOMPARE(save_dives("./testmerge47+48.ssrf"), 0);
 	QFile org(SUBSURFACE_TEST_DATA "/dives/test47+48.xml");
 	org.open(QFile::ReadOnly);
@@ -44,10 +45,11 @@ void TestMerge::testMergeBackwards()
 	/*
 	 * check that we correctly merge mixed cylinder dives
 	 */
-	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test48.xml", &dive_table), 0);
-	process_imported_dives(false);
-	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47.xml", &dive_table), 0);
-	process_imported_dives(false);
+	struct dive_table table = { 0 };
+	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test48.xml", &table), 0);
+	process_imported_dives(&table, false);
+	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47.xml", &table), 0);
+	process_imported_dives(&table, false);
 	QCOMPARE(save_dives("./testmerge47+48.ssrf"), 0);
 	QFile org(SUBSURFACE_TEST_DATA "/dives/test47+48.xml");
 	org.open(QFile::ReadOnly);
diff --git a/tests/testrenumber.cpp b/tests/testrenumber.cpp
index 54d689004..bd9ddf0ca 100644
--- a/tests/testrenumber.cpp
+++ b/tests/testrenumber.cpp
@@ -14,8 +14,9 @@ void TestRenumber::setup()
 
 void TestRenumber::testMerge()
 {
-	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47b.xml", &dive_table), 0);
-	process_imported_dives(false);
+	struct dive_table table = { 0 };
+	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47b.xml", &table), 0);
+	process_imported_dives(&table, false);
 	QCOMPARE(dive_table.nr, 1);
 	QCOMPARE(unsaved_changes(), 1);
 	mark_divelist_changed(false);
@@ -24,8 +25,9 @@ void TestRenumber::testMerge()
 
 void TestRenumber::testMergeAndAppend()
 {
-	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47c.xml", &dive_table), 0);
-	process_imported_dives(false);
+	struct dive_table table = { 0 };
+	QCOMPARE(parse_file(SUBSURFACE_TEST_DATA "/dives/test47c.xml", &table), 0);
+	process_imported_dives(&table, false);
 	QCOMPARE(dive_table.nr, 2);
 	QCOMPARE(unsaved_changes(), 1);
 	struct dive *d = get_dive(1);