Changeset 90 in tspsg-svn for trunk/src

Timestamp:

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

Author:

laleppa

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).

Location:

trunk/src

Files:

• os.h (modified) (2 diffs)
• tspsolver.cpp (modified) (4 diffs)
• tspsolver.h (modified) (4 diffs)

trunk/src/os.h

@@ -77 +77 @@
         #define OS "Cygwin"ARCH
         #define OSID quint8(4)
-#elif defined Q_OS_DARWIN
-        #define OS "Darwin OS"ARCH
-        #define OSID quint8(5)
 #elif defined Q_OS_DGUX
         #define OS "DG/UX"ARCH
-        #define OSID quint8(6)
+        #define OSID quint8(5)
 #elif defined Q_OS_DYNIX
         #define OS "DYNIX/ptx"ARCH
-        #define OSID quint8(7)
+        #define OSID quint8(6)
 #elif defined Q_OS_FREEBSD
         #define OS "FreeBSD"ARCH
-        #define OSID quint8(8)
+        #define OSID quint8(7)
 #elif defined Q_OS_HPUX
         #define OS "HP-UX"ARCH
-        #define OSID quint8(9)
+        #define OSID quint8(8)
 #elif defined Q_OS_HURD
         #define OS "GNU Hurd"ARCH
-        #define OSID quint8(10)
+        #define OSID quint8(9)
 #elif defined Q_OS_IRIX
         #define OS "SGI Irix"ARCH
-        #define OSID quint8(11)
+        #define OSID quint8(10)
 #elif defined Q_OS_LINUX
         #define OS "Linux"ARCH
-        #define OSID quint8(12)
+        #define OSID quint8(11)
 #elif defined Q_OS_LYNX
         #define OS "LynxOS"ARCH
+        #define OSID quint8(12)
+#elif defined Q_OS_MAC
+        #define OS "Mac OS (Darwin)"ARCH
         #define OSID quint8(13)
 #elif defined Q_OS_MSDOS
@@ -122 +122 @@
         #define OS "HP Tru64 UNIX"ARCH
         #define OSID quint8(19)
-#elif defined Q_OS_QNX6
-        #define OS "QNX RTP 6.1"ARCH
+#elif defined Q_OS_QNX
+        #define OS "QNX Neutrino"ARCH
         #define OSID quint8(20)
-#elif defined Q_OS_QNX
-        #define OS "QNX"ARCH
-        #define OSID quint8(21)
 #elif defined Q_OS_RELIANT
         #define OS "Reliant UNIX"ARCH
-        #define OSID quint8(22)
+        #define OSID quint8(21)
 #elif defined Q_OS_SCO
         #define OS "SCO OpenServer 5"ARCH
-        #define OSID quint8(23)
+        #define OSID quint8(22)
 #elif defined Q_OS_SOLARIS
         #define OS "Sun Solaris"ARCH
+        #define OSID quint8(23)
+#elif defined Q_OS_SYMBIAN
+        #define OS "Symbian"ARCH
         #define OSID quint8(24)
 #elif defined Q_OS_ULTRIX

trunk/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;
+                        }
+                }
+        }
 }
 

trunk/src/tspsolver.h

@@ -63 +63 @@
         SCandidate candidate; //!< A candiadate for branching in the current matrix
         QList<SCandidate> alts; //!< A list of alternative branching candidates
+        SStep *pNode; //!< Pointer to the parent step
         SStep *plNode; //!< Pointer to the left branch step
         SStep *prNode; //!< Pointer to the right branch step
@@ -69 +70 @@
         SStep() {
                 price = -1;
-                plNode = prNode = NULL;
+                pNode = plNode = prNode = NULL;
         }
 };
@@ -76 +77 @@
  * \brief This class solves Travelling Salesman Problem task.
  * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
- *
- * \todo TODO: Deletion of solution tree on destroy and cleanup.
  */
 class CTSPSolver
@@ -100 +99 @@
         double align(TMatrix &matrix);
         void cleanup();
-        void deleteNode(SStep *&node);
+        void deleteTree(SStep *&root);
         QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
         double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;