node.h

#ifndef UTS_NODE_H
#define UTS_NODE_H

#include <cstdint>
#include <array>
#include <vector>

#include "picosha2.h"

namespace uts {
using node_state = std::array<uint8_t, 20>;

/**
 * Node of an unballanced binomial tree (https://www.cs.unc.edu/~olivier/LCPC06.pdf).
 * To build up the tree recursivly call spawn_child_nodes on each node until leaves are reached.
 * The tree is not built up directly in memory, but rather by the recursive calls.
 */
class node {
  // The state is used to allow a deterministic tree construction using sha256 hashes.
  node_state state_;

  // Set this to a positive number for the root node to start the tree with a specific size
  int root_children_;

  // general branching factors
  double q_;
  int b_;

  // Private constructor for children
  node(node_state state, double q, int b) : state_{state}, root_children_{-1}, q_{q}, b_{b} {}

  std::array<uint8_t, 20> generate_child_state(uint32_t index);
  double get_state_random();

 public:
  node(int seed, int root_children, double q, int b) : state_({{}}), root_children_{root_children}, q_{q}, b_{b} {
    for (int i = 0; i < 16; i++) {
      state_[i] = 0;
    }
    state_[16] = static_cast<uint8_t>(0xFF & (seed >> 24));
    state_[17] = static_cast<uint8_t>(0xFF & (seed >> 16));
    state_[18] = static_cast<uint8_t>(0xFF & (seed >> 8));
    state_[19] = static_cast<uint8_t>(0xFF & (seed >> 0));

    picosha2::hash256_one_by_one hasher;
    hasher.process(state_.begin(), state_.end());
    hasher.finish();
    hasher.get_hash_bytes(state_.begin(), state_.end());
  }

  std::vector<node> spawn_child_nodes() {
    double state_random = get_state_random();
    int num_children;
    if (root_children_ > 0) {
      num_children = root_children_; // Root always spawns children
    } else if (state_random < q_) {
      num_children = b_;
    } else {
      num_children = 0;
    }

    std::vector<node> result;
    for (int i = 0; i < num_children; i++) {
      result.push_back(node(generate_child_state(i), q_, b_));
    }

    return result;
  }
};
}

#endif //UTS_NODE_H