louds.h

#pragma once
 
#include <pixie/rank_select/support.h>
#include <pixie/tree.h>
 
#include <cstdint>
#include <span>
 
namespace pixie {

using LoudsNode = TreeNode;

class LoudsTree : public TreeBase<LoudsTree> {
 private:
  RankSelectSupport<> bv;
 
 public:
  explicit LoudsTree(std::span<const uint64_t> louds, size_t tree_size)
      : bv(louds, 2 * tree_size - 1) {}

  LoudsNode root_impl() const { return LoudsNode(0, 0); }

  size_t size_impl() const { return (bv.size() + 1) / 2; }

  bool is_leaf_impl(const LoudsNode& node) const {
    return (node.pos + 1 == bv.size()) or bv[node.pos + 1];
  }

  bool is_root_impl(const LoudsNode& node) const { return node.number == 0; }

  size_t degree_impl(const LoudsNode& node) const {
    if (is_leaf_impl(node)) {
      return 0;
    }
    return bv.select(node.number + 2) - node.pos - 1;
  }

  LoudsNode child_impl(const LoudsNode& node, size_t i) const {
    size_t zeros = node.pos + i + 1 - node.number;
    return LoudsNode(zeros, bv.select(zeros + 1));
  }

  LoudsNode first_child_impl(const LoudsNode& node) const {
    size_t zeros = node.pos + 1 - node.number;
    return LoudsNode(zeros, bv.select(zeros + 1));
  }

  LoudsNode parent_impl(const LoudsNode& node) const {
    if (node.number == 0) {
      return root_impl();
    }
    size_t zero_pos = bv.select0(node.number);
    size_t parent_number = zero_pos - node.number;
    return LoudsNode(parent_number, bv.select(parent_number + 1));
  }

  bool is_last_child_impl(const LoudsNode& node) const {
    size_t zero_pos = bv.select0(node.number);
    return bv[zero_pos + 1];
  }

  LoudsNode next_sibling_impl(const LoudsNode& node) const {
    size_t sibling_number = node.number + 1;
    return LoudsNode(sibling_number, bv.select(sibling_number + 1));
  }
};
 
}  // namespace pixie