From 40d8482d24cad4d998240f79e9d6a6745cb845c1 Mon Sep 17 00:00:00 2001
From: "Christopher L. Conway" <christopherleeconway@gmail.com>
Date: Wed, 27 Oct 2010 22:53:03 +0000
Subject: [PATCH] Slightly more efficient version of getType

---
 src/expr/node_manager.cpp | 21 ++++++++-------------
 1 file changed, 8 insertions(+), 13 deletions(-)

diff --git a/src/expr/node_manager.cpp b/src/expr/node_manager.cpp
index c1456050d..b0592ba2f 100644
--- a/src/expr/node_manager.cpp
+++ b/src/expr/node_manager.cpp
@@ -31,7 +31,7 @@
 #include "util/tls.h"
 
 #include <algorithm>
-#include <list>
+#include <stack>
 #include <ext/hash_set>
 
 using namespace std;
@@ -427,15 +427,12 @@ TypeNode NodeManager::getType(TNode n, bool check)
   if(!hasType || needsCheck) {
     // TypeNode oldType = typeNode;
 
-    list<TNode> worklist;
-    worklist.push_back(n);
+    stack<TNode> worklist;
+    worklist.push(n);
 
-    /* Iterate and compute the children bottom up.  This iteration is
-       very inefficient: it would be better to top-sort the Nodes so
-       that the leaves are always computed first. */
+    /* Iterate and compute the children bottom up. */
     while( !worklist.empty() ) {
-      TNode m = worklist.front();
-      worklist.pop_front();
+      TNode m = worklist.top();
 
       bool readyToCompute = true;
       TNode::iterator it = m.begin();
@@ -445,17 +442,15 @@ TypeNode NodeManager::getType(TNode n, bool check)
         if( !hasAttribute(*it, TypeAttr()) 
             || (check && !getAttribute(*it, TypeCheckedAttr())) ) {
           readyToCompute = false;
-          worklist.push_back(*it);
+          worklist.push(*it);
         }
       }
 
       if( readyToCompute ) {
         /* All the children have types, time to compute */
         computeType(m,check);
-      } else {
-        /* Wait until the children have been computed. */
-        worklist.push_back(m);
-      }
+        worklist.pop();
+      } 
     }
 
     /* Retrieve the type computed in the loop */
-- 
2.30.2