louds_tree.h

#pragma once
 
#include <pixie/bitvector.h>
 
#include <cstdint>
#include <span>
 
namespace pixie {

struct LoudsNode {
  size_t number;
  size_t pos;
 
  LoudsNode(size_t node_number, size_t louds_pos)
      : number(node_number), pos(louds_pos) {}
};

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

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

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

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

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

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

  LoudsNode child(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(const LoudsNode& node) const {
    size_t zeros = node.pos + 1 - node.number;
    return LoudsNode(zeros, bv.select(zeros + 1));
  }

  LoudsNode parent(const LoudsNode& node) const {
    if (node.number == 0) {
      return root();
    }
    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(const LoudsNode& node) const {
    size_t zero_pos = bv.select0(node.number);
    return bv[zero_pos + 1];
  }

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