Skip to content

Instantly share code, notes, and snippets.

@Erkaman
Created August 9, 2019 22:44
Show Gist options
  • Save Erkaman/c79746b72f3316dd262cd6bf5821c003 to your computer and use it in GitHub Desktop.
Save Erkaman/c79746b72f3316dd262cd6bf5821c003 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <thread>
#include <chrono>
#include <functional>
#include <atomic>
struct Node {
public:
char data;
std::vector<Node*> children;
Node(char data_): data(data_) {}
};
std::atomic<int> atomicCounter{ 0 };
std::function<void()> makeThreadFunc(int sleep, Node* node) {
return [sleep, node]() {
// we NEED the sleep for a proper breadth first traversal.
std::this_thread::sleep_for(std::chrono::milliseconds(sleep * 10));
printf("%c\n", node->data);
for (size_t ii = 0; ii < node->children.size(); ++ii) {
std::thread(makeThreadFunc(atomicCounter++, node->children[ii])).detach();
}
};
}
void sleepyBreadthFirstTraversal(Node* root)
{
std::thread(makeThreadFunc(atomicCounter++, root)).detach();
// wait out until all threads finished.
// should be a thread::join, but Im lazy ¯\_(ツ)_/¯
std::this_thread::sleep_for(std::chrono::milliseconds(10000));
}
void traverseQueue(Node* root) {
std::queue<Node*> queue;
queue.push(root);
while (!queue.empty()) {
Node* node = queue.front(); queue.pop();
printf("%c\n", node->data);
for (size_t ii = 0; ii < node->children.size(); ++ii) {
queue.push(node->children[ii]);
}
}
}
int main() {
Node* a = new Node('a');
Node* b = new Node('b');
Node* c = new Node('c');
Node* d = new Node('d');
Node* e = new Node('e');
Node* f = new Node('f');
Node* g = new Node('g');
Node* h = new Node('h');
Node* i = new Node('i');
Node* j = new Node('j');
Node* k = new Node('k');
Node* l = new Node('l');
a->children.push_back(b);
a->children.push_back(c);
a->children.push_back(d);
b->children.push_back(e);
b->children.push_back(f);
d->children.push_back(g);
d->children.push_back(h);
e->children.push_back(i);
e->children.push_back(j);
g->children.push_back(k);
g->children.push_back(l);
traverseQueue(a);
printf("\n\n");
sleepyBreadthFirstTraversal(a);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment