#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <functional>
#include <deque>

int answer = -1; // to store the final result of CPS'd versions

/* ----------------------------------------- */
/* Binary tree data structure */

class node {
public:
  int value;
  node* left;
  node* right;

  node(int value)
    : value(value), left(nullptr), right(nullptr) { }
  node(int value, node* left, node* right)
    : value(value), left(left), right(right) { }
};

/* ----------------------------------------- */
/* Cilk program */

namespace cilk {

  auto sum(node* n) -> int {
    if (n == nullptr) {
      return 0;
    } else {
      auto s0 = /* spawn */ sum(n->left);
      auto s1 =             sum(n->right);
      /* sync; */
      return s0 + s1 + n->value;
    }
  }
  
} // end namespace

/* ----------------------------------------- */
/* Convert to continuation-passing style */

namespace cps {

  auto sum(node* n, std::function<void(int)> k) -> void {
    if (n == nullptr) {
      k(0);
    } else {
      sum(n->left, [&] (int s0) { // K1
	  sum(n->right, [&] (int s1) { // K2
	      k(s0 + s1 + n->value);
	  });
      });
    }
  }

  auto sum(node* n) -> void {
    sum(n, [&] (int s) { // K3
      answer = s; });
  }
  
} // end namespace

/* ----------------------------------------- */
/* Defunctionalize */

using kont_tag = enum kont_enum { K1, K2, K3, K4, K5 };

class kont {
public:
  kont_tag tag;
  union {
    struct {
      node* n;
      kont* k;
    } k1;
    struct {
      int s0;
      node* n;
      kont* k;
    } k2;
  } u;

  kont(kont_tag tag, node* n, kont* k) // K1
    : tag(tag) { u.k1.n = n; u.k1.k = k; }
  kont(kont_tag tag, int s0, node* n, kont* k) // K2
    : tag(tag) { u.k2.s0 = s0; u.k2.n = n; u.k2.k = k; }
  kont(kont_tag tag) // K3
    : tag(tag) { }
};

namespace defunc {

  auto apply(kont* k, int s) -> void;
  
  auto sum(node* n, kont* k) -> void {
    if (n == nullptr) {
      apply(k, 0);
    } else {
      sum(n->left, new kont(K1, n, k));
    }
  }

  auto apply(kont* k, int s) -> void {
    if (k->tag == K1) {
      sum(k->u.k1.n->right, new kont(K2, s, k->u.k1.n, k->u.k1.k));
    } else if (k->tag == K2) {
      apply(k->u.k2.k, k->u.k2.s0 + s + k->u.k2.n->value);
    } else if (k->tag == K3) {
      answer = s;
    }
  }

  auto sum(node* n) {
    sum(n, new kont(K3));
  }
  
} // end namespace

/* ----------------------------------------- */
/* Tail-call elimination of apply */

namespace tailcallelimapply {

  auto apply(kont* k, int s) -> void;
  
  auto sum(node* n, kont* k) -> void {
    if (n == nullptr) {
      apply(k, 0);
    } else {
      sum(n->left, new kont(K1, n, k));
    }
  }

  auto apply(kont* k, int s) -> void {
    while (true) {
      if (k->tag == K1) {
	sum(k->u.k1.n->right, new kont(K2, s, k->u.k1.n, k->u.k1.k));
	return;
      } else if (k->tag == K2) {
	s = k->u.k2.s0 + s + k->u.k2.n->value;
	k = k->u.k2.k;
      } else if (k->tag == K3) {
	answer = s;
	return;
      }
    }
  }

  auto sum(node* n) -> void {
    sum(n, new kont(K3));
  }
  
} // end namespace

/* ----------------------------------------- */
/* Inline apply */

namespace inlineapply {
  
  auto sum(node* n, kont* k) -> void {
    if (n == nullptr) {
      int s = 0;
      while (true) {
	if (k->tag == K1) {
	  sum(k->u.k1.n->right, new kont(K2, s, k->u.k1.n, k->u.k1.k));
	  return;
	} else if (k->tag == K2) {
	  s = k->u.k2.s0 + s + k->u.k2.n->value;
	  k = k->u.k2.k;
	} else if (k->tag == K3) {
	  answer = s;
	  return;
	}
      }
    } else {
      sum(n->left, new kont(K1, n, k));
    }
  }

  auto sum(node* n) -> void {
    sum(n, new kont(K3));
  }

} // end namespace

/* ----------------------------------------- */
/* Tail-call elimination of sum */

namespace tailcallelimsum {
  
  auto sum(node* n, kont* k) -> void {
    while (true) {
      if (n == nullptr) {
	int s = 0;
	while (true) {
	  if (k->tag == K1) {
	    n = k->u.k1.n->right;
	    k = new kont(K2, s, k->u.k1.n, k->u.k1.k);
	    break;
	  } else if (k->tag == K2) {
	    s = k->u.k2.s0 + s + k->u.k2.n->value;
	    k = k->u.k2.k;
	  } else if (k->tag == K3) {
	    answer = s;
	    return;
	  }
	}
      } else {
	k = new kont(K1, n, k);
	n = n->left;
      }
    }
  }

  auto sum(node* n) {
    sum(n, new kont(K3));
  }

} // end namespace

/* ----------------------------------------- */
/* Replace linked stack by deque */

class vkont {
public:
  kont_tag tag;
  union {
    struct {
      node* n;
    } k1;
    struct {
      int s0;
      node* n;
    } k2;
  } u;

  vkont(kont_tag tag, node* n) // K1
    : tag(tag) { u.k1.n = n; }
  vkont(kont_tag tag, int s0, node* n) // K2
    : tag(tag) { u.k2.s0 = s0; u.k2.n = n; }
  vkont(kont_tag tag) // K3
    : tag(tag) { }
};

namespace usedeque {
  
  auto sum(node* n, std::deque<vkont>& k) -> void {
    while (true) {
      if (n == nullptr) {
	int s = 0;
	while (true) {
	  auto& f = k.back();
	  if (f.tag == K1) {
	    n = f.u.k1.n->right;
	    f = vkont(K2, s, f.u.k1.n);
	    break;
	  } else if (f.tag == K2) {
	    s = f.u.k2.s0 + s + f.u.k2.n->value;
	    k.pop_back();
	  } else if (f.tag == K3) {
	    answer = s;
	    return;
	  }
	}
      } else {
	k.push_back(vkont(K1, n));
	n = n->left;
      }
    }
  }

  auto sum(node* n) -> void {
    std::deque<vkont> k({vkont(K3)});
    sum(n, k);
  }
  
} // end namespace

/* ----------------------------------------- */
/* Task scheduler */

class task {
public:
  int in;
  std::function<void()> body;

  task(std::function<void()> body)
    : body(body), in(1) { }
};

namespace scheduler {

  std::deque<task*> ready;

  auto join(task* t) -> void {
    auto in = --t->in;
    if (in == 0) {
      ready.push_back(t);
    }
  }

  auto release(task* t) -> void {
    join(t);
  }
  
  auto fork(task* t, task* k) -> void {
    k->in++;
    release(t);    
  }

  auto loop() -> void {
    while (! ready.empty()) {
      auto t = ready.back();
      ready.pop_back();
      t->body();
      delete t;
    }
  }

  auto launch(task* t) -> void {
    release(t);
    loop();
  }
  
} // end namespace

/* ----------------------------------------- */
/* Task-parallel sum */

namespace taskpar {

  using namespace scheduler;

  auto sum(node* n, std::function<void(int)> k) -> void {
    if (n == nullptr) {
      k(0);
    } else {
      auto s = new int[2];
      auto tj = new task([=] {	k(s[0] + s[1] + n->value); });
      fork(new task([=] {
	sum(n->right,  [=] (int s1) { // K5
	    s[1] = s1;
	    join(tj); }); }),
      tj);
      fork(new task([=] {
	sum(n->left, [=] (int s0) { // K4
	    s[0] = s0;
	    join(tj); }); }),
      tj);
      release(tj);
    }
  }

  auto sum(node* n) -> void {
    scheduler::launch(new task([&] { sum(n, [&] (int sf) { answer = sf; }); }));
  }
  
} // end namespace

/* ----------------------------------------- */
/* Defunctionalized task-parallel sum */

class tpkont {
public:
  kont_tag tag;
  union {
    struct {
      int* s;
      task* tj;
    } k4ork5;
  } u;

  tpkont(kont_tag tag, int* s, task* tj) // K4 or K5
    : tag(tag) { u.k4ork5.s = s; u.k4ork5.tj = tj; }
  tpkont(kont_tag tag) // K3
    : tag(tag) { }
};

namespace taskpardefunc {

  using namespace scheduler;

  auto apply(tpkont* k, int s) -> void;
  
  auto sum(node* n, tpkont* k) -> void {
    if (n == nullptr) {
      apply(k, 0);
    } else {
      auto s = new int[2];
      auto tj = new task([=] {	apply(k, s[0] + s[1] + n->value); });
      fork(new task([=] { sum(n->right, new tpkont(K5, s, tj)); }), tj);
      fork(new task([=] { sum(n->left,  new tpkont(K4, s, tj)); }), tj);
      release(tj);
    }
  }

  auto apply(tpkont* k, int s) -> void {
    if (k->tag == K4 || k->tag == K5) {
      auto i = (k->tag == K4) ? 0 : 1;
      k->u.k4ork5.s[i] = s;
      join(k->u.k4ork5.tj);
    } else if (k->tag == K3) {
      answer = s;
    }
  }

  auto sum(node* n) -> void {
    scheduler::launch(new task([&] { sum(n, new tpkont(K3)); }));
  }
  
} // end namespace

/* ----------------------------------------- */
/* Heartbeat task-parallel sum */

class hbkont {
public:
  kont_tag tag;
  union {
    struct {
      node* n;
      hbkont* k;
    } k1;
    struct {
      int s0;
      node* n;
      hbkont* k;
    } k2;
    struct {
      int* s;
      task* tj;
    } k4ork5;
  } u;

  hbkont(kont_tag tag, node* n, hbkont* k) // K1
    : tag(tag) { u.k1.n = n; u.k1.k = k; }
  hbkont(kont_tag tag, int s0, node* n, hbkont* k) // K2
    : tag(tag) { u.k2.s0 = s0; u.k2.n = n; u.k2.k = k; }
  hbkont(kont_tag tag, int* s, task* tj) // K4 or K5
    : tag(tag) { u.k4ork5.s = s; u.k4ork5.tj = tj; }
  hbkont(kont_tag tag) // K3
    : tag(tag) { }
};

namespace heartbeat {

  using namespace scheduler;

  int counter = 0;

  constexpr
  int H = 3; // heartbeat rate

  auto heartbeat() -> bool {
    if (++counter >= H) {
      counter = 0;
      return true;
    }
    return false;
  }

  auto sum(node* n, hbkont* k) -> void;

  auto next(hbkont* k) -> hbkont*& {
    if (k->tag == K1) {
      return k->u.k1.k;
    } else if (k->tag == K2) {
      return k->u.k2.k;
    } else {
      assert(false);
    }
  }

  auto find_oldest(hbkont* k, std::function<bool(hbkont*)> p) -> hbkont* {
    hbkont* kr = nullptr;
    while (k->tag == K1 || k->tag == K2) {
      kr = p(k) ? k : kr;
      k = next(k);
    }
    return kr;
  }

  auto replace(hbkont* k, hbkont* kt, hbkont* kn) -> hbkont* {
    auto kr = &k;
    while ((*kr) != kt) {
      kr = &next(*kr);
    }
    *kr = kn;
    return k;
  }

  auto try_promote(hbkont* k) -> hbkont* {
    auto kt = find_oldest(k, [=] (hbkont* k) { return k->tag == K1; });
    if (kt == nullptr) {
      return k;
    }
    auto n = kt->u.k1.n;
    auto kj = kt->u.k1.k;
    auto s = new int[2];
    auto tj = new task([=] { sum(nullptr, new hbkont(K2, s[0] + s[1], n, kj)); });
    fork(new task([=] { sum(n->right, new hbkont(K5, s, tj)); }), tj);
    return replace(k, kt, new hbkont(K4, s, tj));
  }
  
  auto sum(node* n, hbkont* k) -> void {
    while (true) {
      k = heartbeat() ? try_promote(k) : k; // promotion-ready program point
      if (n == nullptr) {
	int s = 0;
	while (true) {
	  k = heartbeat() ? try_promote(k) : k; // promotion-ready program point
	  if (k->tag == K1) {
	    n = k->u.k1.n->right;
	    k = new hbkont(K2, s, k->u.k1.n, k->u.k1.k);
	    break;
	  } else if (k->tag == K2) {
	    s = k->u.k2.s0 + s + k->u.k2.n->value;
	    k = k->u.k2.k;
	  } else if (k->tag == K3) {
	    answer = s;
	    return;
	  } else if (k->tag == K4 || k->tag == K5) {
	    auto i = (k->tag == K4) ? 0 : 1;
	    k->u.k4ork5.s[i] = s;
	    join(k->u.k4ork5.tj);
	    return;
	  }
	}
      } else {
	k = new hbkont(K1, n, k);
	n = n->left;
      }
    }
  }

  auto sum(node* n) -> void {
    scheduler::launch(new task([&] { sum(n, new hbkont(K3)); }));
  }
  
} // end namespace

/* ----------------------------------------- */
/* Heartbeat task-parallel sum */

class tpalrts_prml_node {
public:
  tpalrts_prml_node* prev;
  tpalrts_prml_node* next;
};

class tpalrts_prml {
public:
  tpalrts_prml_node* front = nullptr;
  tpalrts_prml_node* back = nullptr;
  tpalrts_prml() { }
  tpalrts_prml(tpalrts_prml_node* front, tpalrts_prml_node* back)
    : front(front), back(back) { }
};

class vhbkont {
public:
  kont_tag tag;
  union {
    struct {
      tpalrts_prml_node prml_node;
      node* n;
    } k1;
    struct {
      int s0;
      node* n;
    } k2;
    struct {
      int* s;
      task* tj;
      std::deque<vhbkont>* kp;
    } k4ork5;
  } u;

  vhbkont(kont_tag tag, node* n, tpalrts_prml_node* prev) // K1
    : tag(tag) { u.k1.n = n; u.k1.prml_node.prev = prev; u.k1.prml_node.next = nullptr; }
  vhbkont(kont_tag tag, int s0, node* n) // K2
    : tag(tag) { u.k2.s0 = s0; u.k2.n = n; }
  vhbkont(kont_tag tag, int* s, task* tj, std::deque<vhbkont>* kp) // K4
    : tag(tag) { u.k4ork5.s = s; u.k4ork5.tj = tj; u.k4ork5.kp = kp; }
  vhbkont(kont_tag tag, int* s, task* tj) // K5
    : tag(tag) { u.k4ork5.s = s; u.k4ork5.tj = tj; u.k4ork5.kp = nullptr; }
  vhbkont(kont_tag tag) // K3
    : tag(tag) { }
};

namespace vheartbeat {

  using namespace scheduler;

  int counter = 0;

  constexpr
  int H = 3; // heartbeat rate

  auto heartbeat() -> bool {
    if (++counter >= H) {
      counter = 0;
      return true;
    }
    return false;
  }

  auto tpalrts_prmlist_push_back(tpalrts_prml prml, tpalrts_prml_node* t) -> tpalrts_prml {
    if (prml.back != nullptr) {
      prml.back->next = t;
    }
    prml.back = t;
    if (prml.front == nullptr) {
      prml.front = prml.back;
    }
    return prml;
  }

  auto tpalrts_prmlist_pop_back(tpalrts_prml prml) -> tpalrts_prml {
    auto next = prml.back;
    assert(next != nullptr);
    auto prev = next->prev;
    if (prev == nullptr) {
      prml.front = nullptr;
    } else {
      prev->next = nullptr;
      next->prev = nullptr;
    }
    prml.back = prev;
    return prml;
  }

  auto tpalrts_prmlist_pop_front(tpalrts_prml prml) -> tpalrts_prml {
    auto prev = prml.front;
    assert(prev != nullptr);
    auto next = prev->next;
    if (next == nullptr) {
      prml.back = nullptr;
    } else {
      next->prev = nullptr;
      prev->next = nullptr;
    }
    prml.front = next;
    return prml;
  }

  auto enclosing_frame_pointer_of(tpalrts_prml_node* n) -> vhbkont* {
    auto r = vhbkont(K1, nullptr, (tpalrts_prml_node*)nullptr);
    auto d = (char*)(&r.u.k1.prml_node)-(char*)(&r);
    auto p = (char*)n;
    auto h = p - d;
    return (vhbkont*)h;
  }
  
  auto sum(node* n, std::deque<vhbkont>& k, tpalrts_prml prml) -> void;
  
  auto try_promote(tpalrts_prml prml) -> tpalrts_prml {
    if (prml.front == nullptr) {
      return prml;
    }
    auto f_fr = enclosing_frame_pointer_of(prml.front);
    assert(f_fr->tag == K1);
    auto n = f_fr->u.k1.n;
    auto s = new int[2];
    auto kp = new std::deque<vhbkont>;
    auto tj = new task([=] {
      std::deque<vhbkont> kj;
      kp->swap(kj);
      *f_fr = vhbkont(K2, s[0] + s[1], n);
      delete kp;
      delete [] s;	    
      sum(nullptr, kj, tpalrts_prml());
    });
    fork(new task([=] {
      std::deque<vhbkont> k2({vhbkont(K5, s, tj)});
      sum(n->right, k2, tpalrts_prml());
    }), tj);
    prml = tpalrts_prmlist_pop_front(prml);
    *f_fr = vhbkont(K4, s, tj, kp);
    return prml;
  }

  auto sum(node* n, std::deque<vhbkont>& k, tpalrts_prml prml) -> void {
    while (true) {
      if (heartbeat()) { // promotion-ready program point
	prml = try_promote(prml);
      }
      if (n == nullptr) {
	int s = 0;
	while (true) {
	  if (heartbeat()) { // promotion-ready program point
	    prml = try_promote(prml);
	  }
	  auto& f = k.back();
	  if (f.tag == K1) {
	    prml = tpalrts_prmlist_pop_back(prml);
	    n = f.u.k1.n->right;
	    f = vhbkont(K2, s, f.u.k1.n);
	    break;
	  } else if (f.tag == K2) {
	    s = f.u.k2.s0 + s + f.u.k2.n->value;
	    k.pop_back();
	  } else if (f.tag == K3) {
	    answer = s;
	    return;
	  } else if (f.tag == K4 || f.tag == K5) {
	    auto i = (f.tag == K4) ? 0 : 1;
	    f.u.k4ork5.s[i] = s;
	    auto tj = f.u.k4ork5.tj;
	    if (f.tag == K4) {
	      f.u.k4ork5.kp->swap(k);
	    }
	    join(tj);
	    return;
	  } 
	}
      } else {
	k.push_back(vhbkont(K1, n, prml.back));
	prml = tpalrts_prmlist_push_back(prml, &(k.back().u.k1.prml_node));
	n = n->left;
      }
    }
  }

  auto sum(node* n) -> void {
    scheduler::launch(new task([&] {
      std::deque<vhbkont> k({vhbkont(K3)});
      sum(n, k, tpalrts_prml());
    }));
  }

} // end namespace

/* ----------------------------------------- */
/* Driver */

int main() {

  auto algos = std::deque<std::function<void(node*)>>(
    {
      [&] (node* n) { cps::sum(n); },
      [&] (node* n) { defunc::sum(n); },
      [&] (node* n) { tailcallelimapply::sum(n); },
      [&] (node* n) { inlineapply::sum(n); },
      [&] (node* n) { tailcallelimsum::sum(n); },
      [&] (node* n) { usedeque::sum(n); },
      [&] (node* n) { taskpar::sum(n); },
      [&] (node* n) { taskpardefunc::sum(n); },
      [&] (node* n) { heartbeat::sum(n); },
      [&] (node* n) { vheartbeat::sum(n); },
    });

  auto ns = std::deque<node*>(
    { 
      nullptr,
      new node(123),
      new node(1, new node(2), nullptr),
      new node(1, nullptr, new node(2)),  
      new node(1, new node(200), new node(3)), 
      new node(1, new node(2), new node(3, new node(4), new node(5))),
      new node(1, new node(3, new node(4), new node(5)), new node(2)),
    });

  for (auto n : ns) {
    auto ref = cilk::sum(n);
    for (auto& a : algos) {
      answer = -1;
      a(n);
      if (ref != answer) {
	std::cerr << "wrong answer: " << answer << ", should be: " << ref << std::endl;
	exit(0);
      }
    }
  }
  return 0;
}