summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorJonas Suhr Christensen <jsc@umbraculum.org>2012-05-03 17:14:23 +0200
committerJonas Suhr Christensen <jsc@umbraculum.org>2012-05-03 17:14:23 +0200
commite2cf2ab253d32147e079a817f692f5c87b635c7e (patch)
tree65e3b0bdac4b525bb8a1cf0c8f9868ca6fcc00af /src
parente3c0c95f2ad3d25411c007ce4ffdb25084a1bc0d (diff)
Added breadth first search tour
Diffstat (limited to 'src')
-rw-r--r--src/tasktree.cc29
-rw-r--r--src/tasktree.h4
2 files changed, 32 insertions, 1 deletions
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();