Index: src/tspsolver.cpp
===================================================================
--- src/tspsolver.cpp	(revision e2abfd326fbc0376081d9298a0ae92600057d629)
+++ src/tspsolver.cpp	(revision b574c383b7908655a2d893f213a82f3f46c316d4)
@@ -24,8 +24,41 @@
 #include "tspsolver.h"
 
-//! Class constructor
-CTSPSolver::CTSPSolver()
-	: nCities(0), root(NULL)
-{
+//! \internal \brief A short for maximum double, used internally in the solution algorithm.
+#define MAX_DOUBLE std::numeric_limits<double>::max()
+
+/*!
+ * \brief Returns CTSPSolver's version ID.
+ * \return A string: <b>\$Id$</b>.
+ */
+QString CTSPSolver::getVersionId()
+{
+	return QString("$Id$");
+}
+
+/*!
+ * \brief Constructs CTSPSolver object.
+ * \param parent A parent object.
+ */
+CTSPSolver::CTSPSolver(QObject *parent)
+	: QObject(parent), nCities(0), root(NULL) {}
+
+/*!
+ * \brief Cleans up the object and frees up memory used by the solution tree.
+ * \param processEvents If set to \c true then \link QCoreApplication::processEvents() QApplication::processEvents(QEventLoop::ExcludeUserInputEvents)\endlink will be called from time to time while cleaning up.
+ * \warning After call to this function a solution tree returned by the solve() function is no longer valid.
+ * \note It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.
+ *
+ * \sa solve()
+ */
+void CTSPSolver::cleanup(bool processEvents)
+{
+	if (!processEvents)
+		QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
+	route.clear();
+	mayNotBeOptimal = false;
+	if (root != NULL)
+		deleteTree(root, processEvents);
+	if (!processEvents)
+		QApplication::restoreOverrideCursor();
 }
 
@@ -51,17 +84,8 @@
 
 /*!
- * \brief Returns CTSPSolver's version ID.
- * \return A string: <b>\$Id$</b>.
- */
-QString CTSPSolver::getVersionId()
-{
-	return QString("$Id$");
-}
-
-/*!
- * \brief Returns whether or not the solution is definitely optimal.
- * \return \c true if solution is definitely optimal, otherwise \c false.
- *
- *  The solution may need some further interations to determine whether it is optimal.
+ * \brief Indicates whether or not the solution is definitely optimal.
+ * \return \c true if the solution is definitely optimal, otherwise \c false.
+ *
+ *  The solution may need some further iterations to determine whether or not it is optimal.
  *  In such cases this function returns \c false.
  */
@@ -75,29 +99,29 @@
  * \param numCities Number of cities in the task.
  * \param task The matrix of city-to-city travel costs.
- * \param parent The parent widget for displaying messages and dialogs.
  * \return Pointer to the root of the solution tree.
  *
  * \todo TODO: Comment the algorithm.
  */
-SStep *CTSPSolver::solve(int numCities, TMatrix task, QWidget *parent)
+SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
 {
 	if (numCities <= 1)
 		return NULL;
+
+QMutexLocker locker(&mutex);
 	cleanup();
+	canceled = false;
+	locker.unlock();
+
 	nCities = numCities;
-QProgressDialog pd(parent);
-QProgressBar *pb = new QProgressBar(&pd);
-	pb->setAlignment(Qt::AlignCenter);
-	pb->setFormat(tr("%v of %m parts found"));
-	pd.setBar(pb);
-	pd.setMaximum(nCities);
-	pd.setMinimumDuration(1000);
-	pd.setLabelText(tr("Calculating optimal route..."));
-	pd.setWindowTitle(tr("Solution Progress"));
-	pd.setWindowModality(Qt::ApplicationModal);
-	pd.setValue(0);
 
 SStep *step = new SStep();
 	step->matrix = task;
+	// We need to distinguish the values forbidden by the user
+	// from the values forbidden by the algorithm.
+	// So we replace user's infinities by the maximum available double value.
+	normalize(step->matrix);
+#ifdef DEBUG
+	qDebug() << step->matrix;
+#endif // DEBUG
 	step->price = align(step->matrix);
 	root = step;
@@ -108,16 +132,27 @@
 double check = INFINITY;
 	while (this->route.size() < nCities) {
-//		forbidden.clear();
 		step->alts = findCandidate(step->matrix,nRow,nCol);
+
 		while (hasSubCycles(nRow,nCol)) {
-//			forbidden[nRow] = nCol;
+#ifdef DEBUG
+			qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
+#endif // DEBUG
 			step->matrix[nRow][nCol] = INFINITY;
 			step->price += align(step->matrix);
 			step->alts = findCandidate(step->matrix,nRow,nCol);
 		}
-		if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
+
+#ifdef DEBUG
+		qDebug() /*<< step->matrix*/ << "Selected: (" << nRow << ";" << nCol << ")";
+		qDebug() << "Alternate:" << step->alts;
+		qDebug() << "Step price:" << step->price << endl;
+#endif // DEBUG
+
+		locker.relock();
+		if ((nRow == -1) || (nCol == -1) || canceled) {
 			cleanup();
-			break;
-		}
+			return NULL;
+		}
+		locker.unlock();
 
 		// Route with (nRow,nCol) path
@@ -132,5 +167,5 @@
 		}
 		right->price = step->price + align(right->matrix);
-		// Forbid selected route to exclude its reuse in next steps.
+		// Forbid the selected route to exclude its reuse in next steps.
 		right->matrix[nCol][nRow] = INFINITY;
 		right->matrix[nRow][nCol] = INFINITY;
@@ -148,9 +183,12 @@
 		step->prNode = right;
 
+		// This matrix is not used anymore. Restoring infinities back.
+		denormalize(step->matrix);
+
 		if (right->price <= left->price) {
 			// Route with (nRow,nCol) path is cheaper
 			step = right;
 			this->route[nRow] = nCol;
-			pd.setValue(this->route.size());
+			emit routePartFound(this->route.size());
 			if (firstStep) {
 				check = left->price;
@@ -168,16 +206,27 @@
 	}
 
-	if (!root && !pd.wasCanceled()) {
-		pd.reset();
-		QMessageBox(QMessageBox::Warning,tr("Solution Result"),tr("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
-	}
-
-	qApp->processEvents();
-
-	if (root) {
-		route = this->route;
-		mayNotBeOptimal = (check < step->price);
-	}
+	route = this->route;
+	mayNotBeOptimal = (check < step->price);
+
 	return root;
+}
+
+/*!
+ * \brief Indicates whether or not the solution process was canceled.
+ * \return \c true if the solution process was canceled, otherwise \c false.
+ */
+bool CTSPSolver::wasCanceled() const
+{
+QMutexLocker locker(&mutex);
+	return canceled;
+}
+
+/*!
+ * \brief Cancels the solution process.
+ */
+void CTSPSolver::cancel()
+{
+QMutexLocker locker(&mutex);
+	canceled = true;
 }
 
@@ -198,5 +247,6 @@
 		if (min > 0) {
 			r += min;
-			subRow(matrix,k,min);
+			if (min < MAX_DOUBLE)
+				subRow(matrix,k,min);
 		}
 	}
@@ -205,5 +255,6 @@
 		if (min > 0) {
 			r += min;
-			subCol(matrix,k,min);
+			if (min < MAX_DOUBLE)
+				subCol(matrix,k,min);
 		}
 	}
@@ -211,15 +262,5 @@
 }
 
-void CTSPSolver::cleanup()
-{
-	QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
-	route.clear();
-	mayNotBeOptimal = false;
-	if (root != NULL)
-		deleteTree(root);
-	QApplication::restoreOverrideCursor();
-}
-
-void CTSPSolver::deleteTree(SStep *&root)
+void CTSPSolver::deleteTree(SStep *&root, bool processEvents)
 {
 	if (root == NULL)
@@ -228,4 +269,6 @@
 SStep *parent;
 	forever {
+		if (processEvents)
+			QApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
 		if (step->plNode != NULL) {
 			// We have left child node - going inside it
@@ -252,4 +295,12 @@
 		}
 	}
+}
+
+void CTSPSolver::denormalize(TMatrix &matrix) const
+{
+	for (int r = 0; r < nCities; r++)
+		for (int c = 0; c < nCities; c++)
+			if ((r != c) && (matrix.at(r).at(c) == MAX_DOUBLE))
+				matrix[r][c] = INFINITY;
 }
 
@@ -287,5 +338,5 @@
 		if ((k != exr) && (min > matrix.at(k).at(nCol)))
 			min = matrix.at(k).at(nCol);
-	return min == INFINITY ? 0 : min;
+	return (min == INFINITY) ? 0 : min;
 }
 
@@ -293,8 +344,9 @@
 {
 double min = INFINITY;
-	for (int k = 0; k < nCities; k++)
+	for (int k = 0; k < nCities; k++) {
 		if (((k != exc)) && (min > matrix.at(nRow).at(k)))
 			min = matrix.at(nRow).at(k);
-	return min == INFINITY ? 0 : min;
+	}
+	return (min == INFINITY) ? 0 : min;
 }
 
@@ -313,4 +365,12 @@
 }
 
+void CTSPSolver::normalize(TMatrix &matrix) const
+{
+	for (int r = 0; r < nCities; r++)
+		for (int c = 0; c < nCities; c++)
+			if ((r != c) && (matrix.at(r).at(c) == INFINITY))
+				matrix[r][c] = MAX_DOUBLE;
+}
+
 void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
 {
@@ -327,11 +387,19 @@
 }
 
+#ifdef DEBUG
 QDebug operator<<(QDebug dbg, const TMatrix &matrix)
 {
 	for (int r = 0; r < matrix.count(); r++) {
 		for (int c = 0; c < matrix.at(r).count(); c++)
-			dbg.space() << matrix.at(r).at(c);
+			dbg.space() << QString::number(matrix.at(r).at(c)).leftJustified(5);
 		dbg << endl;
 	}
 	return dbg;
 }
+
+QDebug operator<<(QDebug dbg, const SCandidate &cand)
+{
+	dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";
+	return dbg;
+}
+#endif // DEBUG
