Changeset 3e46075789 in tspsg for src/tspsolver.cpp

Timestamp:

Feb 17, 2010, 5:54:05 PM (15 years ago)

Author:

Oleksii Serdiuk

Branches:

0.1.3.145-beta1-symbian, 0.1.4.170-beta2-bb10, appveyor, imgbot, master, readme

Children:

8203c075d5

Parents:

e4ae9e95f7

Message:

• Reimplemented solution tree deletion to be non-recursive function. Should use less memory.
• Updated os.h with the fresh list of OSs, supported by Qt (​http://doc.trolltech.com/4.6/qtglobal.html).

File:

• src/tspsolver.cpp (modified) (4 diffs)

src/tspsolver.cpp

@@ -123 +123 @@
                 // Route with (nRow,nCol) path
                 right = new SStep();
+                right->pNode = step;
                 right->matrix = step->matrix;
                 for (int k = 0; k < nCities; k++) {
@@ -137 +138 @@
                 // Route without (nRow,nCol) path
                 left = new SStep();
+                left->pNode = step;
                 left->matrix = step->matrix;
                 left->matrix[nRow][nCol] = INFINITY;
@@ -183 +185 @@
 {
         if (root != NULL)
-                deleteNode(root);
+                deleteTree(root);
 }
 
@@ -215 +217 @@
         mayNotBeOptimal = false;
         if (root != NULL)
-                deleteNode(root);
+                deleteTree(root);
         QApplication::restoreOverrideCursor();
 }
 
-void CTSPSolver::deleteNode(SStep *&node)
-{
-//static int x;
-//      x++;
-//qDebug() << ">>>" << x;
-        if (node->plNode != NULL)
-                deleteNode(node->plNode);
-        if (node->prNode != NULL)
-                deleteNode(node->prNode);
-        delete node;
-        node = NULL;
-//qDebug() << "<<<" << x;
-//      x--;
+void CTSPSolver::deleteTree(SStep *&root)
+{
+        if (root == NULL)
+                return;
+SStep *step = root;
+SStep *parent;
+        forever {
+                if (step->plNode != NULL) {
+                        // We have left child node - going inside it
+                        step = step->plNode;
+                        step->pNode->plNode = NULL;
+                        continue;
+                } else if (step->prNode != NULL) {
+                        // We have right child node - going inside it
+                        step = step->prNode;
+                        step->pNode->prNode = NULL;
+                        continue;
+                } else {
+                        // We have no child nodes. Deleting current one.
+                        parent = step->pNode;
+                        delete step;
+                        if (parent != NULL) {
+                                // Going back to the parent node.
+                                step = parent;
+                        } else {
+                                // We came back to the root node. Finishing.
+                                root = NULL;
+                                break;
+                        }
+                }
+        }
 }