From 29158da41e7943ea8019efdbff70c994fb1c73e9 Mon Sep 17 00:00:00 2001
From: Alex Auvolat <alex.auvolat@ens.fr>
Date: Sun, 1 Feb 2015 18:07:20 +0100
Subject: Begin work on worker thread

---
 problem.cpp | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 problem.hpp |  18 ++++++++
 ui.cpp      |  11 +++++
 ui.hpp      |   1 +
 4 files changed, 170 insertions(+), 3 deletions(-)

diff --git a/problem.cpp b/problem.cpp
index e56b0b3..3169751 100644
--- a/problem.cpp
+++ b/problem.cpp
@@ -1,5 +1,8 @@
+#include <deque>
+
 #include "problem.hpp"
 
+
 using namespace std;
 
 // ===================================== //
@@ -42,16 +45,150 @@ solution solution::direct_sol(const hilare_a &pos_a, const hilare_a &pos_b) {
 	return solution(sol);
 }
 
+bool solution::intersects(const problem &p) const {
+	for (auto& x: movement) {
+		if (x.intersects(p)) return true;
+	}
+	return false;
+}
+
 // =============================== //
 // IMPLEMENTATION FOR CLASS SOLVER //
 // =============================== //
 
-solver::solver() {
-	// nothing ?
+solver::solver() : _worker(&solver::run, this) {
+	_running = false;
+	_done = false;
+	_please_stop = false;
+}
+
+void solver::start(const problem &p) {
+	_p = p;
+
+	if (_running) {
+		_please_stop = true;
+		_worker.wait();
+	}
+
+	_please_stop = false;
+	_done = false;
+	_running = true;
+	_worker.launch();
+}
+
+void solver::run() {
+	problem p = _p;		// copy problem
+
+	solver_internal d;
+	d.initialize(p);
+	{
+		sf::Lock l(_d_lock);
+		_d = d;
+	}
+
+	while (!_please_stop) {
+		solution s = d.try_find_solution();
+		if (s.movement.size() > 0) {
+			_s = s;
+			_done = true;
+			break;
+		}
+
+		if (!_please_stop) break;
+
+		d.step(p);
+
+		// Write local results to guys outside
+		{
+			sf::Lock l(_d_lock);
+			_d = d;
+		}
+	}
+	_running = false;
+}
+
+bool solver::finished() {
+	return _done;
+}
+
+solution solver::get_solution() {
+	if (_done) return _s;
+	return solution();
 }
 
 solver_internal solver::peek_internal() {
-	return _d;
+	solver_internal x;
+	{	
+		sf::Lock l(_d_lock);
+		x = _d;
+	}
+	return x;
+}
+
+void solver_internal::initialize(const problem &p) {
+	paths.clear();
+	pts.clear();
+
+	pts.push_back(p.begin_pos);
+	pts.push_back(p.end_pos);
+
+	solution ts = solution::direct_sol(p.begin_pos, p.end_pos);
+	if (!ts.intersects(p)) {
+		paths[0][1] = ts;
+	}
+}
+
+solution solver_internal::try_find_solution() {
+	// Simple graph search algorithm
+
+	vector<int> par(pts.size(), -1);
+	deque<int> q;
+
+	par[0] = 0;
+	q.push_back(0);
+	while (!q.empty()) {
+		int x = q.front();
+		q.pop_front();
+
+		if (paths.find(x) != paths.end()) {
+			auto pp = paths.find(x)->second;
+
+			for (auto& kv: pp) {
+				int y = kv.first;
+				if (par[y] == -1) {
+					par[y] = x;
+					q.push_back(y);
+				}
+			}
+		}
+	}
+
+	if (par[1] != -1) {
+		vector<hilare_a_mvt> sol;
+
+		int b = 1;
+		while (b != 0) {
+			int a = par[b];
+
+			auto& x = paths[a][b];
+
+			sol.insert(sol.begin(), x.movement.begin(), x.movement.end());
+
+			b = a;
+		}
+
+		return solution(sol);
+	}
+
+	return solution();	// not found
+}
+
+void solver_internal::step(const problem &p) {
+	// take new random point
+	// try to connect to all existing points
+
+	// TODO
+	sf::sleep(sf::milliseconds(10));	// no CPU hog
 }
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/problem.hpp b/problem.hpp
index 685e1df..8851fa2 100644
--- a/problem.hpp
+++ b/problem.hpp
@@ -2,6 +2,7 @@
 
 #include <vector>
 #include <map>
+#include <SFML/System.hpp>
 
 #include "geom.hpp"
 
@@ -87,18 +88,35 @@ struct solver_internal {
 	// represents a graph of randomly chosen positions and simple solutions between them
 	std::vector<hilare_a> pts;
 	std::map<int, std::map<int, solution> > paths;
+
+	void initialize(const problem &p);
+	solution try_find_solution();
+	void step(const problem &p);
 };
 
 class solver {
 	// mutex-protected asynchronous structure
 
 	private:
+
+	sf::Mutex _d_lock;
 	solver_internal _d;
+	problem _p;
+
+	bool _please_stop;
+	bool _running;
+	bool _done;
+	solution _s;
+	
+	sf::Thread _worker;
 
 	public:
 	solver();
 
 	void start(const problem &p);
+
+	void run();	// worker thread
+
 	bool finished();
 	solution get_solution();
 
diff --git a/ui.cpp b/ui.cpp
index 1f61f03..a2ec620 100644
--- a/ui.cpp
+++ b/ui.cpp
@@ -11,6 +11,7 @@
 		- e : select end pos
 		- a : add obstacle
 		- d : delete obstacle under mouse pointer
+		- g : start solving
 	Select modes : no other keys
 */
 
@@ -25,6 +26,8 @@ UI::UI(hilare_a_param *p) : _sel_obs(vec(0,0), 0) {
 	_view.zoom = 1;
 
 	_mode = M_NORMAL;
+
+	_got_sol = true;
 }
 
 void UI::run() {
@@ -55,6 +58,9 @@ void UI::run() {
 					_view.zoom *= 1.1;
 				} else if (k == 'o') {
 					_view.zoom /= 1.1;
+				} else if (k == 'g') {
+					_solver.start(_p);
+					_got_sol = false;
 				}
 			}
 
@@ -63,6 +69,11 @@ void UI::run() {
 			if (_mode == M_SEL_BEGIN || _mode == M_SEL_END) handle_sel_pos(ev);
 		}
 
+		if (!_got_sol && _solver.finished()) {
+			_s = _solver.get_solution();
+			_got_sol = true;
+		}
+
 		_win.clear(sf::Color::Black);
 
 		render_internal();
diff --git a/ui.hpp b/ui.hpp
index 8496b58..07383fd 100644
--- a/ui.hpp
+++ b/ui.hpp
@@ -28,6 +28,7 @@ class UI {
 	problem _p;
 	solution _s;
 	solver _solver;
+	bool _got_sol;
 
 	struct {
 		double x0, y0, zoom;
-- 
cgit v1.2.3