statistics: implement rectangle selection in scatter plot

Allow the user to select regions of the scatter plot using
a rectangular selection. When shift is pressed, do an
incremental selection.

Unfortunately, the list-selection code is so slow that this
becomes unusable for a large number of selected dives.

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

16 files changed, 207 insertions, 36 deletions

diff --git a/stats/barseries.cpp b/stats/barseries.cpp
index ad956c454..58c6511a6 100644
--- a/stats/barseries.cpp
+++ b/stats/barseries.cpp
@@ -406,12 +406,15 @@ void BarSeries::unhighlight()
 	highlighted = Index();
 }
 
-void BarSeries::selectItemsUnderMouse(const QPointF &pos, bool)
+bool BarSeries::selectItemsUnderMouse(const QPointF &pos, bool)
 {
 	Index index = getItemUnderMouse(pos);
-	if (index.bar < 0)
-		return setSelection({}, nullptr);
+	if (index.bar < 0) {
+		setSelection({}, nullptr);
+		return false;
+	}
 
 	const std::vector<dive *> &dives = items[index.bar].subitems[index.subitem].dives;
 	setSelection(dives, dives.empty() ? nullptr : dives.front());
+	return true;
 }
diff --git a/stats/barseries.h b/stats/barseries.h
index 190efe19d..5d592d4fa 100644
--- a/stats/barseries.h
+++ b/stats/barseries.h
@@ -69,7 +69,7 @@ public:
 	void updatePositions() override;
 	bool hover(QPointF pos) override;
 	void unhighlight() override;
-	void selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
+	bool selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
 
 private:
 	BarSeries(StatsView &view, StatsAxis *xAxis, StatsAxis *yAxis,
diff --git a/stats/boxseries.cpp b/stats/boxseries.cpp
index 3d2de0e82..5362aa7af 100644
--- a/stats/boxseries.cpp
+++ b/stats/boxseries.cpp
@@ -143,12 +143,15 @@ void BoxSeries::unhighlight()
 	highlighted = -1;
 }
 
-void BoxSeries::selectItemsUnderMouse(const QPointF &pos, bool)
+bool BoxSeries::selectItemsUnderMouse(const QPointF &pos, bool)
 {
 	int index = getItemUnderMouse(pos);
-	if (index < 0)
-		return setSelection({}, nullptr);
+	if (index < 0) {
+		setSelection({}, nullptr);
+		return false;
+	}
 
 	const std::vector<dive *> &dives = items[index]->q.dives;
 	setSelection(dives, dives.empty() ? nullptr : dives.front());
+	return true;
 }
diff --git a/stats/boxseries.h b/stats/boxseries.h
index d4ec09ac8..2285e11c5 100644
--- a/stats/boxseries.h
+++ b/stats/boxseries.h
@@ -23,7 +23,7 @@ public:
 	void updatePositions() override;
 	bool hover(QPointF pos) override;
 	void unhighlight() override;
-	void selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
+	bool selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
 
 	// Note: this expects that all items are added with increasing pos
 	// and that no bar is inside another bar, i.e. lowerBound and upperBound
diff --git a/stats/chartitem.cpp b/stats/chartitem.cpp
index 93f374e14..acd303928 100644
--- a/stats/chartitem.cpp
+++ b/stats/chartitem.cpp
@@ -196,6 +196,12 @@ bool ChartScatterItem::contains(QPointF point) const
 	return squareDist(point, rect.center()) <= (scatterItemDiameter / 2.0) * (scatterItemDiameter / 2.0);
 }
 
+// For rectangular selections, we are more crude: simply check whether the center is in the selection.
+bool ChartScatterItem::inRect(const QRectF &selection) const
+{
+	return selection.contains(rect.center());
+}
+
 void ChartScatterItem::setHighlight(Highlight highlightIn)
 {
 	if (highlight == highlightIn)
@@ -301,13 +307,21 @@ void ChartPieItem::resize(QSizeF size)
 	img->fill(Qt::transparent);
 }
 
-ChartLineItem::ChartLineItem(StatsView &v, ChartZValue z, QColor color, double width) : HideableChartItem(v, z),
+ChartLineItemBase::ChartLineItemBase(StatsView &v, ChartZValue z, QColor color, double width) : HideableChartItem(v, z),
 	color(color), width(width), positionDirty(false), materialDirty(false)
 {
 }
 
-ChartLineItem::~ChartLineItem()
+ChartLineItemBase::~ChartLineItemBase()
+{
+}
+
+void ChartLineItemBase::setLine(QPointF fromIn, QPointF toIn)
 {
+	from = fromIn;
+	to = toIn;
+	positionDirty = true;
+	markDirty();
 }
 
 // Helper function to set points
@@ -347,12 +361,37 @@ void ChartLineItem::render()
 	positionDirty = materialDirty = false;
 }
 
-void ChartLineItem::setLine(QPointF fromIn, QPointF toIn)
+void ChartRectLineItem::render()
 {
-	from = fromIn;
-	to = toIn;
-	positionDirty = true;
-	markDirty();
+	if (!node) {
+		geometry.reset(new QSGGeometry(QSGGeometry::defaultAttributes_Point2D(), 4));
+		geometry->setDrawingMode(QSGGeometry::DrawLineLoop);
+		material.reset(new QSGFlatColorMaterial);
+		createNode();
+		node->setGeometry(geometry.get());
+		node->setMaterial(material.get());
+		view.addQSGNode(node.get(), zValue);
+		positionDirty = materialDirty = true;
+	}
+	updateVisible();
+
+	if (positionDirty) {
+		// Attention: width is a geometry property and therefore handled by position dirty!
+		geometry->setLineWidth(static_cast<float>(width));
+		auto vertices = geometry->vertexDataAsPoint2D();
+		setPoint(vertices[0], from);
+		setPoint(vertices[1], QPointF(from.x(), to.y()));
+		setPoint(vertices[2], to);
+		setPoint(vertices[3], QPointF(to.x(), from.y()));
+		node->markDirty(QSGNode::DirtyGeometry);
+	}
+
+	if (materialDirty) {
+		material->setColor(color);
+		node->markDirty(QSGNode::DirtyMaterial);
+	}
+
+	positionDirty = materialDirty = false;
 }
 
 ChartBarItem::ChartBarItem(StatsView &v, ChartZValue z, double borderWidth, bool horizontal) : HideableChartItem(v, z),
diff --git a/stats/chartitem.h b/stats/chartitem.h
index c700cb421..038054c39 100644
--- a/stats/chartitem.h
+++ b/stats/chartitem.h
@@ -112,23 +112,35 @@ private:
 	double borderWidth;
 };
 
-class ChartLineItem : public HideableChartItem<HideableQSGNode<QSGGeometryNode>> {
+// Common data for line and rect items. Both are represented by two points.
+class ChartLineItemBase : public HideableChartItem<HideableQSGNode<QSGGeometryNode>> {
 public:
-	ChartLineItem(StatsView &v, ChartZValue z, QColor color, double width);
-	~ChartLineItem();
+	ChartLineItemBase(StatsView &v, ChartZValue z, QColor color, double width);
+	~ChartLineItemBase();
 	void setLine(QPointF from, QPointF to);
-	void render() override;		// Only call on render thread!
-private:
+protected:
 	QPointF from, to;
 	QColor color;
 	double width;
-	bool horizontal;
 	bool positionDirty;
 	bool materialDirty;
 	std::unique_ptr<QSGFlatColorMaterial> material;
 	std::unique_ptr<QSGGeometry> geometry;
 };
 
+class ChartLineItem : public ChartLineItemBase {
+public:
+	using ChartLineItemBase::ChartLineItemBase;
+	void render() override;		// Only call on render thread!
+};
+
+// A simple rectangle without fill. Specified by any two opposing vertices.
+class ChartRectLineItem : public ChartLineItemBase {
+public:
+	using ChartLineItemBase::ChartLineItemBase;
+	void render() override;		// Only call on render thread!
+};
+
 // A bar in a bar chart: a rectangle bordered by lines.
 class ChartBarItem : public HideableChartProxyItem<QSGRectangleNode> {
 public:
@@ -185,6 +197,7 @@ public:
 	void render() override;			// Only call on render thread!
 	QRectF getRect() const;
 	bool contains(QPointF point) const;
+	bool inRect(const QRectF &rect) const;
 private:
 	QSGTexture *getTexture() const;
 	QRectF rect;
diff --git a/stats/pieseries.cpp b/stats/pieseries.cpp
index 9f55d41d2..61579df74 100644
--- a/stats/pieseries.cpp
+++ b/stats/pieseries.cpp
@@ -265,12 +265,15 @@ void PieSeries::unhighlight()
 	highlighted = -1;
 }
 
-void PieSeries::selectItemsUnderMouse(const QPointF &pos, bool)
+bool PieSeries::selectItemsUnderMouse(const QPointF &pos, bool)
 {
 	int index = getItemUnderMouse(pos);
-	if (index < 0)
-		return setSelection({}, nullptr);
+	if (index < 0) {
+		setSelection({}, nullptr);
+		return false;
+	}
 
 	const std::vector<dive *> &dives = items[index].dives;
 	setSelection(dives, dives.empty() ? nullptr : dives.front());
+	return true;
 }
diff --git a/stats/pieseries.h b/stats/pieseries.h
index d41469029..05372e84f 100644
--- a/stats/pieseries.h
+++ b/stats/pieseries.h
@@ -28,7 +28,7 @@ public:
 	void updatePositions() override;
 	bool hover(QPointF pos) override;
 	void unhighlight() override;
-	void selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
+	bool selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
 
 	std::vector<QString> binNames();
 
diff --git a/stats/scatterseries.cpp b/stats/scatterseries.cpp
index fe9889d33..63fdaae1b 100644
--- a/stats/scatterseries.cpp
+++ b/stats/scatterseries.cpp
@@ -78,7 +78,25 @@ std::vector<int> ScatterSeries::getItemsUnderMouse(const QPointF &point) const
 	return res;
 }
 
-void ScatterSeries::selectItemsUnderMouse(const QPointF &point, bool shiftPressed)
+std::vector<int> ScatterSeries::getItemsInRect(const QRectF &rect) const
+{
+	std::vector<int> res;
+
+	auto low = std::lower_bound(items.begin(), items.end(), rect.left(),
+				    [] (const Item &item, double x) { return item.item->getRect().right() < x; });
+	auto high = std::upper_bound(low, items.end(), rect.right(),
+				    [] (double x, const Item &item) { return x < item.item->getRect().left(); });
+	// Hopefully that narrows it down enough. For discrete scatter plots, we could also partition
+	// by equal x and do a binary search in these partitions. But that's probably not worth it.
+	res.reserve(high - low);
+	for (auto it = low; it < high; ++it) {
+		if (it->item->inRect(rect))
+			res.push_back(it - items.begin());
+	}
+	return res;
+}
+
+bool ScatterSeries::selectItemsUnderMouse(const QPointF &point, bool shiftPressed)
 {
 	std::vector<struct dive *> selected;
 	std::vector<int> indices = getItemsUnderMouse(point);
@@ -87,6 +105,7 @@ void ScatterSeries::selectItemsUnderMouse(const QPointF &point, bool shiftPresse
 		// When shift is pressed, add the items under the mouse to the selection
 		// or, if all items under the mouse are selected, remove them.
 		selected = getDiveSelection();
+		selected.reserve(indices.size() + selected.size());
 		bool allSelected = std::all_of(indices.begin(), indices.end(),
 					       [this] (int idx) { return items[idx].d->selected; });
 		if (allSelected) {
@@ -108,11 +127,39 @@ void ScatterSeries::selectItemsUnderMouse(const QPointF &point, bool shiftPresse
 			}
 		}
 	} else {
+		selected.reserve(indices.size());
 		for(int idx: indices)
 			selected.push_back(items[idx].d);
 	}
 
 	setSelection(selected, selected.empty() ? nullptr : selected.front());
+	return !indices.empty();
+}
+
+bool ScatterSeries::supportsLassoSelection() const
+{
+	return true;
+}
+
+void ScatterSeries::selectItemsInRect(const QRectF &rect, bool shiftPressed, const std::vector<dive *> &oldSelection)
+{
+	std::vector<struct dive *> selected;
+	std::vector<int> indices = getItemsInRect(rect);
+	selected.reserve(oldSelection.size() + indices.size());
+
+	if (shiftPressed) {
+		selected = oldSelection;
+		// Ouch - this primitive merging of the selections grows with O(n^2). Fix this.
+		for (int idx: indices) {
+			if (std::find(selected.begin(), selected.end(), items[idx].d) == selected.end())
+				selected.push_back(items[idx].d);
+		}
+	} else {
+		for (int idx: indices)
+			selected.push_back(items[idx].d);
+	}
+
+	setSelection(selected, selected.empty() ? nullptr : selected.front());
 }
 
 static QString dataInfo(const StatsVariable &var, const dive *d)
diff --git a/stats/scatterseries.h b/stats/scatterseries.h
index 35526dfc0..1b8db0337 100644
--- a/stats/scatterseries.h
+++ b/stats/scatterseries.h
@@ -27,11 +27,14 @@ public:
 
 	// Note: this expects that all items are added with increasing pos!
 	void append(dive *d, double pos, double value);
-	void selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
+	bool selectItemsUnderMouse(const QPointF &point, bool shiftPressed) override;
+	bool supportsLassoSelection() const override;
+	void selectItemsInRect(const QRectF &rect, bool shiftPressed, const std::vector<dive *> &oldSelection) override;
 
 private:
 	// Get items under mouse.
 	std::vector<int> getItemsUnderMouse(const QPointF &f) const;
+	std::vector<int> getItemsInRect(const QRectF &f) const;
 
 	struct Item {
 		ChartItemPtr<ChartScatterItem> item;
diff --git a/stats/statscolors.h b/stats/statscolors.h
index d8198911c..178cf8b00 100644
--- a/stats/statscolors.h
+++ b/stats/statscolors.h
@@ -24,6 +24,7 @@ inline const QColor quartileMarkerColor(Qt::red);
 inline const QColor regressionItemColor(Qt::red);
 inline const QColor meanMarkerColor(Qt::green);
 inline const QColor medianMarkerColor(Qt::red);
+inline const QColor selectionLassoColor(Qt::black);
 
 QColor binColor(int bin, int numBins);
 QColor labelColor(int bin, size_t numBins);
diff --git a/stats/statsseries.cpp b/stats/statsseries.cpp
index 18fc0a3ff..0885f14de 100644
--- a/stats/statsseries.cpp
+++ b/stats/statsseries.cpp
@@ -20,3 +20,12 @@ QPointF StatsSeries::toScreen(QPointF p)
 void StatsSeries::divesSelected(const QVector<dive *> &)
 {
 }
+
+bool StatsSeries::supportsLassoSelection() const
+{
+	return false;
+}
+
+void StatsSeries::selectItemsInRect(const QRectF &, bool, const std::vector<dive *> &)
+{
+}
diff --git a/stats/statsseries.h b/stats/statsseries.h
index cee2ec0a8..bc7cd2c57 100644
--- a/stats/statsseries.h
+++ b/stats/statsseries.h
@@ -4,11 +4,13 @@
 #ifndef STATS_SERIES_H
 #define STATS_SERIES_H
 
+#include <vector>
 #include <QPointF>
 
 class StatsAxis;
 class StatsView;
 struct dive;
+class QRectF;
 
 class StatsSeries {
 public:
@@ -17,7 +19,11 @@ public:
 	virtual void updatePositions() = 0;	// Called if chart geometry changes.
 	virtual bool hover(QPointF pos) = 0;	// Called on mouse movement. Return true if an item of this series is highlighted.
 	virtual void unhighlight() = 0;		// Unhighlight any highlighted item.
-	virtual void selectItemsUnderMouse(const QPointF &pos, bool shiftPressed) = 0;
+	// Returns true if an item was under the mouse.
+	virtual bool selectItemsUnderMouse(const QPointF &pos, bool shiftPressed) = 0;
+	virtual bool supportsLassoSelection() const;
+	// Needs only be defined if supportsLassoSelection() returns true.
+	virtual void selectItemsInRect(const QRectF &rect, bool shiftPressed, const std::vector<dive *> &oldSelection);
 	virtual void divesSelected(const QVector<dive *> &dives);
 
 protected:
diff --git a/stats/statsview.cpp b/stats/statsview.cpp
index 9ee0f0e44..88f394550 100644
--- a/stats/statsview.cpp
+++ b/stats/statsview.cpp
@@ -18,6 +18,7 @@
 #include "zvalues.h"
 #include "core/divefilter.h"
 #include "core/subsurface-qt/divelistnotifier.h"
+#include "core/selection.h"
 #include "core/trip.h"
 
 #include <cmath>
@@ -30,6 +31,7 @@
 // Constants that control the graph layouts
 static const double sceneBorder = 5.0;			// Border between scene edges and statitistics view
 static const double titleBorder = 2.0;			// Border between title and chart
+static const double selectionLassoWidth = 2.0;		// Border between title and chart
 
 StatsView::StatsView(QQuickItem *parent) : QQuickItem(parent),
 	backgroundDirty(true),
@@ -37,6 +39,7 @@ StatsView::StatsView(QQuickItem *parent) : QQuickItem(parent),
 	xAxis(nullptr),
 	yAxis(nullptr),
 	draggedItem(nullptr),
+	shiftSelection(false),
 	rootNode(nullptr)
 {
 	setFlag(ItemHasContents, true);
@@ -82,8 +85,25 @@ void StatsView::mousePressEvent(QMouseEvent *event)
 	}
 
 	bool shiftPressed = event->modifiers() & Qt::ShiftModifier;
+	bool itemSelected = false;
 	for (auto &series: series)
-		series->selectItemsUnderMouse(pos, shiftPressed);
+		itemSelected |= series->selectItemsUnderMouse(pos, shiftPressed);
+
+	// The user clicked in "empty" space. If there is a series supporting lasso-select,
+	// got into lasso mode. For now, we only support a rectangular lasso.
+	if (!itemSelected && std::any_of(series.begin(), series.end(),
+					 [] (const std::unique_ptr<StatsSeries> &s)
+					 { return s->supportsLassoSelection(); })) {
+		if (selectionRect)
+			deleteChartItem(selectionRect); // Ooops. Already a selection in place.
+		dragStartMouse = pos;
+		selectionRect = createChartItem<ChartRectLineItem>(ChartZValue::Selection, selectionLassoColor, selectionLassoWidth);
+		shiftSelection = shiftPressed;
+		oldSelection = shiftPressed ? getDiveSelection() : std::vector<dive *>();
+		grabMouse();
+		setKeepMouseGrab(true); // don't allow Qt to steal the grab
+		update();
+	}
 }
 
 void StatsView::mouseReleaseEvent(QMouseEvent *)
@@ -92,6 +112,12 @@ void StatsView::mouseReleaseEvent(QMouseEvent *)
 		draggedItem = nullptr;
 		ungrabMouse();
 	}
+
+	if (selectionRect) {
+		deleteChartItem(selectionRect);
+		ungrabMouse();
+		update();
+	}
 }
 
 // Define a hideable dummy QSG node that is used as a parent node to make
@@ -358,14 +384,26 @@ void StatsView::divesSelected(const QVector<dive *> &dives)
 
 void StatsView::mouseMoveEvent(QMouseEvent *event)
 {
-	if (!draggedItem)
-		return;
+	if (draggedItem) {
+		QSizeF sceneSize = size();
+		if (sceneSize.width() <= 1.0 || sceneSize.height() <= 1.0)
+			return;
+		draggedItem->setPos(event->pos() - dragStartMouse + dragStartItem);
+		update();
+	}
 
-	QSizeF sceneSize = size();
-	if (sceneSize.width() <= 1.0 || sceneSize.height() <= 1.0)
-		return;
-	draggedItem->setPos(event->pos() - dragStartMouse + dragStartItem);
-	update();
+	if (selectionRect) {
+		QPointF p1 = event->pos();
+		QPointF p2 = dragStartMouse;
+		selectionRect->setLine(p1, p2);
+		QRectF rect(std::min(p1.x(), p2.x()), std::min(p1.y(), p2.y()),
+			    fabs(p2.x() - p1.x()), fabs(p2.y() - p1.y()));
+		for (auto &series: series) {
+			if (series->supportsLassoSelection())
+				series->selectItemsInRect(rect, shiftSelection, oldSelection);
+		}
+		update();
+	}
 }
 
 void StatsView::hoverEnterEvent(QHoverEvent *)
@@ -446,6 +484,7 @@ void StatsView::reset()
 	regressionItem.reset();
 	meanMarker.reset();
 	medianMarker.reset();
+	selectionRect.reset();
 
 	// Mark clean and dirty chart items for deletion
 	cleanItems.splice(deletedItems);
diff --git a/stats/statsview.h b/stats/statsview.h
index 87dcdad29..279889104 100644
--- a/stats/statsview.h
+++ b/stats/statsview.h
@@ -19,6 +19,7 @@ struct StatsVariable;
 class StatsSeries;
 class CategoryAxis;
 class ChartItem;
+class ChartRectLineItem;
 class ChartTextItem;
 class CountAxis;
 class HistogramAxis;
@@ -142,7 +143,10 @@ private:
 	ChartItemPtr<Legend> legend;
 	Legend *draggedItem;
 	ChartItemPtr<RegressionItem> regressionItem;
+	ChartItemPtr<ChartRectLineItem> selectionRect;
 	QPointF dragStartMouse, dragStartItem;
+	bool shiftSelection;
+	std::vector<dive *> oldSelection;
 
 	void hoverEnterEvent(QHoverEvent *event) override;
 	void hoverMoveEvent(QHoverEvent *event) override;
diff --git a/stats/zvalues.h b/stats/zvalues.h
index 58222f5ab..dc84bdd99 100644
--- a/stats/zvalues.h
+++ b/stats/zvalues.h
@@ -11,6 +11,7 @@ enum class ChartZValue {
 	Axes,
 	SeriesLabels,
 	ChartFeatures,	// quartile markers and regression lines
+	Selection,
 	InformationBox,
 	Legend,
 	Count