From e2cf2ab253d32147e079a817f692f5c87b635c7e Mon Sep 17 00:00:00 2001
From: Jonas Suhr Christensen <jsc@umbraculum.org>
Date: Thu, 3 May 2012 17:14:23 +0200
Subject: Added breadth first search tour

---
 src/tasktree.cc | 29 +++++++++++++++++++++++++++++
 src/tasktree.h  |  4 +++-
 2 files changed, 32 insertions(+), 1 deletion(-)

diff --git a/src/tasktree.cc b/src/tasktree.cc
index 3a72046..0a9ad46 100644
--- a/src/tasktree.cc
+++ b/src/tasktree.cc
@@ -177,6 +177,35 @@ task_t TaskTree::getData(taskid_t id)
   return t;
 }
 
+// bfs search from id in tree
+TaskIdList TaskTree::bfs(taskid_t id) 
+  throw (std::exception) {
+
+  TaskIdList lst;
+  lst.push_back(id);
+  
+  std::list<node_t*> queue;
+  node_t* current = id2node.at(id);
+  while(true) {
+    NodeList children = current->children;
+    for(NodeList::iterator it = children.begin(); it != children.end(); it++) {
+      node_t* child = *it;
+      queue.push_back(child);
+      lst.push_back(child->id);
+    }
+    
+    if(!queue.empty()) {
+      current = queue.front();
+      queue.pop_front();
+    }
+    else {
+      break;
+    }
+  }
+
+  return lst;
+}
+
 TaskIdList TaskTree::ancestorList(taskid_t id)
   throw (std::exception) {
   
diff --git a/src/tasktree.h b/src/tasktree.h
index 6623b0f..aeeddfc 100644
--- a/src/tasktree.h
+++ b/src/tasktree.h
@@ -55,7 +55,9 @@ public:
   TaskIdList move(taskid_t id, taskid_t newParentId) throw (std::exception);
   TaskIdList updateData(taskid_t id, task_t t) throw (std::exception);
   task_t getData(taskid_t id) throw (std::exception);
-  
+
+  TaskIdList bfs(taskid_t id) throw (std::exception);
+
   TaskIdList ancestorList(taskid_t id) throw (std::exception);
 
   void toStdOut();
-- 
cgit v1.2.3