#ifndef TASKFLOW_HPP_

#define TASKFLOW_HPP_

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <mutex>

#include <deque>

#include <vector>

#include <algorithm>

#include <thread>

#include <future>

#include <functional>

#include <unordered_map>

#include <unordered_set>

#include <sstream>

#include <list>

#include <forward_list>

#include <numeric>

#include <iomanip>

#include <cassert>

namespace tf {

template <typename... ArgsT>

inline void throw_re(const char* fname, const size_t line, ArgsT&&... args) {

}

#define TF_THROW(...) throw_re(__FILE__, __LINE__, __VA_ARGS__);

template <typename... T>

struct dependent_false {

static constexpr bool value = false;

};

template <typename T, typename = void>

struct is_iterator {

static constexpr bool value = false;

};

template <typename T>

struct is_iterator<T, std::enable_if_t<!std::is_same_v<typename std::iterator_traits<T>::value_type, void>>> {

static constexpr bool value = true;

};

template <typename T>

inline constexpr bool is_iterator_v = is_iterator<T>::value;

template <typename T, typename = void>

struct is_iterable : std::false_type {

};

template <typename T>

struct is_iterable<T, std::void_t<decltype(std::declval<T>().begin()),

decltype(std::declval<T>().end())>>

: std::true_type {

};

template <typename T>

inline constexpr bool is_iterable_v = is_iterable<T>::value;

template <typename T>

struct MoveOnCopy {

};

template <typename T>

MoveOnCopy(T&&) -> MoveOnCopy<T>;

class Threadpool {

};

inline Threadpool::Threadpool(unsigned N) {

spawn(N);

}

inline Threadpool::~Threadpool() {

shutdown();

}

inline size_t Threadpool::num_tasks() const {

return _task_queue.size();

}

inline size_t Threadpool::num_workers() const {

return _threads.size();

}

inline bool Threadpool::is_worker() const {

std::scoped_lock<std::mutex> lock(_mutex);

return _worker_ids.find(std::this_thread::get_id()) != _worker_ids.end();

}

inline void Threadpool::spawn(unsigned N) {

}

template <typename C>

auto Threadpool::silent_async(C&& c, Signal sig) {

}

template<typename C>

auto Threadpool::async(C&& c, Signal sig) {

}

inline void Threadpool::shutdown() {

}

template <typename F>

class BasicTaskflow {

};

template <typename F>

template <typename C>

BasicTaskflow<F>::Node::Node(C&& c) : _work {std::forward<C>(c)} {

}

template <typename F>

void BasicTaskflow<F>::Node::precede(Node& v) {

_successors.push_back(&v);

v._dependents++;

}

template <typename F>

size_t BasicTaskflow<F>::Node::num_successors() const {

return _successors.size();

}

template <typename F>

size_t BasicTaskflow<F>::Node::dependents() const {

return _dependents.load();

}

template <typename F>

const std::string& BasicTaskflow<F>::Node::name() const {

return _name;

}

template <typename F>

BasicTaskflow<F>::Topology::Topology(std::forward_list<Node>&& t) :

nodes(std::move(t)) {

std::promise<void> promise;

future = promise.get_future().share();

target._work = [p=MoveOnCopy{std::move(promise)}] () mutable { p.get().set_value(); };

source.precede(target);

// Build the super source and super target.

for(auto& task : nodes) {

if(task.dependents() == 0) {

source.precede(task);

}

if(task.num_successors() == 0) {

task.precede(target);

}

}

}

template <typename F>

BasicTaskflow<F>::Task::Task(const Task& rhs) : _node {rhs._node} {

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::precede(Task tgt) {

_node->precede(*(tgt._node));

return *this;

}

template <typename F>

template <typename... Bs>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::broadcast(Bs&&... tgts) {

(_node->precede(*(tgts._node)), ...);

return *this;

}

template <typename F>

template <typename S>

void BasicTaskflow<F>::Task::_broadcast(S& tgts) {

for(auto& to : tgts) {

_node->precede(*(to._node));

}

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::broadcast(std::vector<Task>& tgts) {

_broadcast(tgts);

return *this;

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::broadcast(std::initializer_list<Task> tgts) {

_broadcast(tgts);

return *this;

}

template <typename F>

template <typename... Bs>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::gather(Bs&&... tgts) {

(tgts.precede(*this), ...);

return *this;

}

template <typename F>

template <typename S>

void BasicTaskflow<F>::Task::_gather(S& tgts) {

for(auto& from : tgts) {

from._node->precede(*_node);

}

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::gather(std::vector<Task>& tgts) {

_gather(tgts);

return *this;

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::gather(std::initializer_list<Task> tgts) {

_gather(tgts);

return *this;

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::operator = (const Task& rhs) {

_node = rhs._node;

return *this;

}

template <typename F>

BasicTaskflow<F>::Task::Task(Task&& rhs) : _node{rhs._node} {

rhs._node = nullptr;

}

template <typename F>

template <typename C>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::work(C&& c) {

_node->_work = std::forward<C>(c);

return *this;

}

template <typename F>

typename BasicTaskflow<F>::Task& BasicTaskflow<F>::Task::name(const std::string& name) {

_node->_name = name;

return *this;

}

template <typename F>

const std::string& BasicTaskflow<F>::Task::name() const {

return _node->_name;

}

template <typename F>

size_t BasicTaskflow<F>::Task::num_dependents() const {

return _node->_dependents;

}

template <typename F>

size_t BasicTaskflow<F>::Task::num_successors() const {

return _node->_successors.size();

}

template <typename F>

BasicTaskflow<F>::Task::Task(Node* t) : _node {t} {

}

template <typename F>

BasicTaskflow<F>::BasicTaskflow() : _threadpool{std::thread::hardware_concurrency()} {

}

template <typename F>

BasicTaskflow<F>::BasicTaskflow(unsigned N) : _threadpool{N} {

}

template <typename F>

BasicTaskflow<F>::~BasicTaskflow() {

wait_for_topologies();

}

template <typename F>

void BasicTaskflow<F>::num_workers(size_t W) {

_threadpool.shutdown();

_threadpool.spawn(W);

}

template <typename F>

size_t BasicTaskflow<F>::num_nodes() const {

//return _nodes.size();

return std::distance(_nodes.begin(), _nodes.end());

}

template <typename F>

size_t BasicTaskflow<F>::num_workers() const {

return _threadpool.num_workers();

}

template <typename F>

size_t BasicTaskflow<F>::num_topologies() const {

return _topologies.size();

}

template <typename F>

auto BasicTaskflow<F>::precede(Task from, Task to) {

from._node->precede(*(to._node));

}

template <typename F>

template <typename L>

void BasicTaskflow<F>::_linearize(L& keys) {

std::adjacent_find(

keys.begin(), keys.end(),

[] (auto& from, auto& to) {

from._node->precede(*(to._node));

return false;

}

);

}

template <typename F>

auto BasicTaskflow<F>::linearize(std::vector<Task>& keys) {

_linearize(keys);

}

template <typename F>

auto BasicTaskflow<F>::linearize(std::initializer_list<Task> keys) {

_linearize(keys);

}

template <typename F>

auto BasicTaskflow<F>::broadcast(Task from, std::vector<Task>& keys) {

from.broadcast(keys);

}

template <typename F>

auto BasicTaskflow<F>::broadcast(Task from, std::initializer_list<Task> keys) {

from.broadcast(keys);

}

template <typename F>

auto BasicTaskflow<F>::gather(std::vector<Task>& keys, Task to) {

to.gather(keys);

}

template <typename F>

auto BasicTaskflow<F>::gather(std::initializer_list<Task> keys, Task to) {

to.gather(keys);

}

template <typename F>

auto BasicTaskflow<F>::silent_dispatch() {

if(_nodes.empty()) return;

auto& topology = _topologies.emplace_front(std::move(_nodes));

// Start the taskflow

_schedule(topology.source);

}

template <typename F>

auto BasicTaskflow<F>::dispatch() {

if(_nodes.empty()) {

return std::async(std::launch::deferred, [](){}).share();

}

auto& topology = _topologies.emplace_front(std::move(_nodes));

// Start the taskflow

_schedule(topology.source);

return topology.future;

}

template <typename F>

auto BasicTaskflow<F>::wait_for_all() {

if(!_nodes.empty()) {

silent_dispatch();

}

wait_for_topologies();

}

template <typename F>

void BasicTaskflow<F>::wait_for_topologies() {

for(auto& t: _topologies){

t.future.get();

}

_topologies.clear();

}

template <typename F>

auto BasicTaskflow<F>::placeholder() {

auto& node = _nodes.emplace_front();

return Task(&node);

}

template <typename F>

template <typename C>

auto BasicTaskflow<F>::silent_emplace(C&& c) {

auto& node = _nodes.emplace_front(std::forward<C>(c));

return Task(&node);

}

template <typename F>

template <typename... C, std::enable_if_t<(sizeof...(C)>1), void>*>

auto BasicTaskflow<F>::silent_emplace(C&&... cs) {

return std::make_tuple(silent_emplace(std::forward<C>(cs))...);

}

template <typename F>

template <typename C>

auto BasicTaskflow<F>::emplace(C&& c) {

using R = std::invoke_result_t<C>;

std::promise<R> p;

auto fu = p.get_future();

auto& node = _nodes.emplace_front([p=MoveOnCopy(std::move(p)), c=std::forward<C>(c)] () mutable {

if constexpr(std::is_same_v<void, R>) {

c();

p.get().set_value();

}

else {

p.get().set_value(c());

}

});

return std::make_pair(Task(&node), std::move(fu));

}

template <typename F>

template <typename... C, std::enable_if_t<(sizeof...(C)>1), void>*>

auto BasicTaskflow<F>::emplace(C&&... cs) {

return std::make_tuple(emplace(std::forward<C>(cs))...);

}

template <typename F>

template <typename I, typename C>

auto BasicTaskflow<F>::parallel_for(I beg, I end, C&& c, size_t g) {

using category = typename std::iterator_traits<I>::iterator_category;

if(g == 0) {

auto d = std::distance(beg, end);

auto w = std::max(size_t{1}, num_workers());

g = (d + w - 1) / w;

}

auto source = placeholder();

auto target = placeholder();

while(beg != end) {

auto e = beg;

// Case 1: random access iterator

if constexpr(std::is_same_v<category, std::random_access_iterator_tag>) {

size_t r = std::distance(beg, end);

std::advance(e, std::min(r, g));

}

// Case 2: non-random access iterator

else {

for(size_t i=0; i<g && e != end; ++e, ++i);

}

// Create a task

auto task = silent_emplace([beg, e, c] () mutable {

std::for_each(beg, e, c);

});

source.precede(task);

task.precede(target);

// adjust the pointer

beg = e;

}

return std::make_pair(source, target);

}

template <typename F>

template <typename T, typename C, std::enable_if_t<is_iterable_v<T>, void>*>

auto BasicTaskflow<F>::parallel_for(T& t, C&& c, size_t group) {

return parallel_for(t.begin(), t.end(), std::forward<C>(c), group);

}

template <typename F>

template <typename I, typename T, typename B>

auto BasicTaskflow<F>::reduce(I beg, I end, T& result, B&& op/*, size_t g*/) {

using category = typename std::iterator_traits<I>::iterator_category;

// Evenly partition

//if(g == 0) {

size_t d = std::distance(beg, end);

size_t w = std::max(size_t{1}, num_workers());

size_t g = std::max((d + w - 1) / w, size_t{2});

//}

auto source = placeholder();

auto target = placeholder();