tree_model.h

转到此文件的文档。

#ifndef XGBOOST_TREE_MODEL_H_
#define XGBOOST_TREE_MODEL_H_

#include <dmlc/io.h>
#include <dmlc/parameter.h>
#include <xgboost/base.h>
#include <xgboost/data.h>
#include <xgboost/feature_map.h>
#include <xgboost/linalg.h> // for VectorView
#include <xgboost/logging.h>
#include <xgboost/model.h>
#include <xgboost/multi_target_tree_model.h> // for MultiTargetTree

#include <algorithm>
#include <cstring>
#include <limits>
#include <memory> // for make_unique
#include <stack>
#include <string>
#include <vector>

namespace xgboost {
class Json;

// FIXME(trivialfis): Once binary IO is gone, make this parameter internal as it should
// not be configured by users.
struct TreeParam : public dmlc::Parameter<TreeParam> {
 int deprecated_num_roots{1};
 /* \brief number of nodes in the tree */int num_nodes{1};
 /* \brief number of deleted nodes */int num_deleted{0};
 int deprecated_max_depth{0};
 /* \brief number of features in the model */bst_feature_t num_feature{0};
 /* \brief Size of leaf vector */bst_target_t size_leaf_vector{1};
 int reserved[31];
 TreeParam() {
 // assert compact alignment
 static_assert(sizeof(TreeParam) == (31 + 6) * sizeof(int), "TreeParam: 64位对齐");
 std::memset(reserved, 0, sizeof(reserved));
 }

 // Swap byte order for all fields. Useful for transporting models between machines with different
 // endianness (big endian vs little endian)
 [[nodiscard]] TreeParam ByteSwap() const {
 TreeParam x = *this;
 dmlc::ByteSwap(&x.deprecated_num_roots, sizeof(x.deprecated_num_roots), 1);
 dmlc::ByteSwap(&x.num_nodes, sizeof(x.num_nodes), 1);
 dmlc::ByteSwap(&x.num_deleted, sizeof(x.num_deleted), 1);
 dmlc::ByteSwap(&x.deprecated_max_depth, sizeof(x.deprecated_max_depth), 1);
 dmlc::ByteSwap(&x.num_feature, sizeof(x.num_feature), 1);
 dmlc::ByteSwap(&x.size_leaf_vector, sizeof(x.size_leaf_vector), 1);
 dmlc::ByteSwap(x.reserved, sizeof(x.reserved[0]), sizeof(x.reserved) / sizeof(x.reserved[0]));
 return x;
 }

 // declare the parameters
 DMLC_DECLARE_PARAMETER(TreeParam) {
 // only declare the parameters that can be set by the user.
 // other arguments are set by the algorithm.
 DMLC_DECLARE_FIELD(num_nodes).set_lower_bound(1).set_default(1);
 DMLC_DECLARE_FIELD(num_feature)
 .set_default(0)
 .describe("树构建中使用的特征数量。");
 DMLC_DECLARE_FIELD(num_deleted).set_default(0);
 DMLC_DECLARE_FIELD(size_leaf_vector)
 .set_lower_bound(0)
 .set_default(1)
 .describe("叶子向量的大小，为向量树保留");
 }

 bool operator==(const TreeParam& b) const {
 return num_nodes == b.num_nodes && num_deleted == b.num_deleted &&
 num_feature == b.num_feature && size_leaf_vector == b.size_leaf_vector;
 }
};

struct RTreeNodeStat {
 /* \brief loss reduction of this node */bst_float loss_chg;
 /* \brief sum of hessian */bst_float sum_hess;
 /* \brief base weight */bst_float base_weight;
 /* \brief number of child node that are leaves */int leaf_child_cnt {0};

 RTreeNodeStat() = default;
 RTreeNodeStat(float loss_chg, float sum_hess, float weight)
 loss_chg{loss_chg}, sum_hess{sum_hess}, base_weight{weight} {}
 bool operator==(const RTreeNodeStat& b) const {
 return loss_chg == b.loss_chg && sum_hess == b.sum_hess &&
 base_weight == b.base_weight && leaf_child_cnt == b.leaf_child_cnt;
 }
 // Swap byte order for all fields. Useful for transporting models between machines with different
 // endianness (big endian vs little endian)
 [[nodiscard]] RTreeNodeStat ByteSwap() const {
 RTreeNodeStat x = *this;
 dmlc::ByteSwap(&x.loss_chg, sizeof(x.loss_chg), 1);
 dmlc::ByteSwap(&x.sum_hess, sizeof(x.sum_hess), 1);
 dmlc::ByteSwap(&x.base_weight, sizeof(x.base_weight), 1);
 dmlc::ByteSwap(&x.leaf_child_cnt, sizeof(x.leaf_child_cnt), 1);
 return x;
 }
};

/* \brief A unique pointer that can be copied. */template <typename T>
class CopyUniquePtr {
 std::unique_ptr<T> ptr_{nullptr};

 public
 CopyUniquePtr() = default;
 CopyUniquePtr(CopyUniquePtr const& that) {
 ptr_.reset(nullptr);
 if (that.ptr_) {
 ptr_ = std::make_unique<T>(*that);
 }
 }
 /* \brief get pointer */[[nodiscard]] XGBOOST_DEVICE T* get() const noexcept { return ptr_.get(); } // NOLINT

 /* \brief dereference */T& operator*() { return *ptr_; }
 /* \brief member access */T* operator->() noexcept { return this->get(); }

 /* \brief const dereference */T const& operator*() const { return *ptr_; }
 /* \brief const member access */T const* operator->() const noexcept { return this->get(); }

 /* \brief check if pointer is valid */explicit operator bool() const { return static_cast<bool>(ptr_); }
 /* \brief check if pointer is not valid */bool operator!() const { return !ptr_; }
 /* \brief reset pointer */void reset(T* ptr) { ptr_.reset(ptr); } // NOLINT
};

/* \brief data structure for regression tree */class RegTree : public Model {
 public
 using SplitCondT = bst_float;
 // invalid node idstatic constexpr bst_node_t kInvalidNodeId{MultiTargetTree::InvalidNodeId()};
 // marker for deleted nodestatic constexpr uint32_t kDeletedNodeMarker = std::numeric_limits<uint32_t>::max();
 // root node idstatic constexpr bst_node_t kRoot{0};

 /* \brief regression tree node */class Node {
 public
 XGBOOST_DEVICE Node() {
 // assert compact alignment
 static_assert(sizeof(Node) == 4 * sizeof(int) + sizeof(Info),
 "Node: 64 bit align");
 }
 Node(int32_t cleft, int32_t cright, int32_t parent,
 uint32_t split_ind, float split_cond, bool default_left)
 parent_{parent}, cleft_{cleft}, cright_{cright} {
 this->SetParent(parent_);
 this->SetSplit(split_ind, split_cond, default_left);
 }

 /** \brief get left child * \return left child index */[[nodiscard]] XGBOOST_DEVICE int LeftChild() const { return this->cleft_; }
 /** \brief get right child * \return right child index */[[nodiscard]] XGBOOST_DEVICE int RightChild() const { return this->cright_; }
 /** \brief get default child when feature is missing * \return default child index */[[nodiscard]] XGBOOST_DEVICE int DefaultChild() const {
 return this->DefaultLeft() ? this->LeftChild() : this->RightChild();
 }
 /** \brief get split feature index * \return split feature index */[[nodiscard]] XGBOOST_DEVICE bst_feature_t SplitIndex() const {
 static_assert(!std::is_signed_v<bst_feature_t>);
 return sindex_ & ((1U << 31) - 1U);
 }
 /** \brief check if it's default left branch * \return whether it's default left branch */[[nodiscard]] XGBOOST_DEVICE bool DefaultLeft() const { return (sindex_ >> 31) != 0; }
 /** \brief whether the node is leaf * \return whether is leaf */[[nodiscard]] XGBOOST_DEVICE bool IsLeaf() const { return cleft_ == kInvalidNodeId; }
 /** \brief get leaf value of leaf node * \return leaf value */[[nodiscard]] XGBOOST_DEVICE float LeafValue() const { return (this->info_).leaf_value; }
 /** \brief get split condition * \return split condition */[[nodiscard]] XGBOOST_DEVICE SplitCondT SplitCond() const { return (this->info_).split_cond; }
 /** \brief get parent of the node * \return parent index */[[nodiscard]] XGBOOST_DEVICE int Parent() const { return parent_ & ((1U << 31) - 1); }
 /** \brief whether this node is left child * \return whether it is left child */[[nodiscard]] XGBOOST_DEVICE bool IsLeftChild() const { return (parent_ & (1U << 31)) != 0; }
 /** \brief whether node is deleted * \return whether node is deleted */[[nodiscard]] XGBOOST_DEVICE bool IsDeleted() const { return sindex_ == kDeletedNodeMarker; }
 /** \brief check if node is root * \return whether is root */[[nodiscard]] XGBOOST_DEVICE bool IsRoot() const { return parent_ == kInvalidNodeId; }
 /** * \param nid node id * \brief set left child */XGBOOST_DEVICE void SetLeftChild(int nid) {
 this->cleft_ = nid;
 }
 /** * \param nid node id * \brief set right child */XGBOOST_DEVICE void SetRightChild(int nid) {
 this->cright_ = nid;
 }
 /** * \brief set split condition * \param split_index feature index to split * \param split_cond split condition * \param default_left the default direction when feature is missing */XGBOOST_DEVICE void SetSplit(unsigned split_index, SplitCondT split_cond,
 bool default_left = false) {
 if (default_left) split_index |= (1U << 31);
 this->sindex_ = split_index;
 (this->info_).split_cond = split_cond;
 }
 /** * \brief set the node to be leaf * \param value the value of the leaf */XGBOOST_DEVICE void SetLeaf(bst_float value, int right = kInvalidNodeId) {
 (this->info_).leaf_value = value;
 this->cleft_ = kInvalidNodeId;
 this->cright_ = right;
 }
 /** \brief mark that this node is deleted */XGBOOST_DEVICE void MarkDelete() {
 this->sindex_ = kDeletedNodeMarker;
 }
 /** \brief reuse this node */XGBOOST_DEVICE void Reuse() {
 this->sindex_ = 0;
 }
 // set parent
 /* \brief set parent of the node */XGBOOST_DEVICE void SetParent(int pidx, bool is_left_child = true) {
 if (is_left_child) pidx |= (1U << 31);
 this->parent_ = pidx;
 }
 bool operator==(const Node& b) const {
 return parent_ == b.parent_ && cleft_ == b.cleft_ &&
 cright_ == b.cright_ && sindex_ == b.sindex_ &&
 info_.leaf_value == b.info_.leaf_value;
 }

 [[nodiscard]] Node ByteSwap() const {
 Node x = *this;
 dmlc::ByteSwap(&x.parent_, sizeof(x.parent_), 1);
 dmlc::ByteSwap(&x.cleft_, sizeof(x.cleft_), 1);
 dmlc::ByteSwap(&x.cright_, sizeof(x.cright_), 1);
 dmlc::ByteSwap(&x.sindex_, sizeof(x.sindex_), 1);
 dmlc::ByteSwap(&x.info_, sizeof(x.info_), 1);
 return x;
 }

 private
 /* \brief node information, union of leaf value and split condition. */union Info{
 bst_float leaf_value;
 SplitCondT split_cond;
 };
 // pointer to parent, highest bit is used to
 // indicate whether it's a left child or not
 int32_t parent_{kInvalidNodeId};
 // pointer to left, right
 int32_t cleft_{kInvalidNodeId}, cright_{kInvalidNodeId};
 // split feature index, left split or right split depends on the highest bit
 uint32_t sindex_{0};
 // extra info
 Info info_;
 };

 /** \brief Change node to a leaf node. * \param rid node index * \param value new leaf value */void ChangeToLeaf(int rid, bst_float value) {
 CHECK(nodes_[nodes_[rid].LeftChild() ].IsLeaf());
 CHECK(nodes_[nodes_[rid].RightChild()].IsLeaf());
 this->DeleteNode(nodes_[rid].LeftChild());
 this->DeleteNode(nodes_[rid].RightChild());
 nodes_[rid].SetLeaf(value);
 }
 /** \brief collapse a node to a leaf node, delete all children * \param rid node index * \param value new leaf value */void CollapseToLeaf(int rid, bst_float value) {
 if (nodes_[rid].IsLeaf()) return;
 if (!nodes_[nodes_[rid].LeftChild() ].IsLeaf()) {
 CollapseToLeaf(nodes_[rid].LeftChild(), 0.0f);
 }
 if (!nodes_[nodes_[rid].RightChild() ].IsLeaf()) {
 CollapseToLeaf(nodes_[rid].RightChild(), 0.0f);
 }
 this->ChangeToLeaf(rid, value);
 }

 /* \brief constructor */RegTree() {
 param_.Init(Args{});
 nodes_.resize(param_.num_nodes);
 stats_.resize(param_.num_nodes);
 split_types_.resize(param_.num_nodes, FeatureType::kNumerical);
 split_categories_segments_.resize(param_.num_nodes);
 for (int i = 0; i < param_.num_nodes; i++) {
 nodes_[i].SetLeaf(0.0f);
 nodes_[i].SetParent(kInvalidNodeId);
 }
 }
 /* \brief constructor with size and feature support */explicit RegTree(bst_target_t n_targets, bst_feature_t n_features) : RegTree{} {
 param_.num_feature = n_features;
 param_.size_leaf_vector = n_targets;
 if (n_targets > 1) {
 this->p_mt_tree_.reset(new MultiTargetTree{&param_});
 }
 }

 /* \brief reference to node */Node& operator[](int nid) {
 return nodes_[nid];
 }
 /* \brief const reference to node */const Node& operator[](int nid) const {
 return nodes_[nid];
 }

 /* \brief get all nodes */[[nodiscard]] const std::vector<Node>& GetNodes() const { return nodes_; }

 /* \brief get all stats */[[nodiscard]] const std::vector<RTreeNodeStat>& GetStats() const { return stats_; }

 /* \brief reference to node statistics */RTreeNodeStat& Stat(int nid) {
 return stats_[nid];
 }
 /* \brief const reference to node statistics */[[nodiscard]] const RTreeNodeStat& Stat(int nid) const {
 return stats_[nid];
 }

 /** \brief 从二进制流加载模型 * \param fi 输入流 */void Load(dmlc::Stream* fi);
 /** \brief 将模型保存到二进制流 * \param fo 输出流 */void Save(dmlc::Stream* fo) const;

 /** \brief 从 JSON 对象加载模型。 * \param in JSON 对象。 */void LoadModel(Json const& in) override;
 /** \brief 将模型保存到 JSON 对象。 * \param out JSON 对象。 */void SaveModel(Json* out) const override;

 /** \brief 测试两棵树是否相等。 */bool operator==(const RegTree& b) const {
 return nodes_ == b.nodes_ && stats_ == b.stats_ &&
 deleted_nodes_ == b.deleted_nodes_ && param_ == b.param_;
 }
 /* \brief 遍历此树中的所有节点。
 *
 * \param func 一个接受节点索引的函数，当迭代应停止时返回 false，否则返回 true。
 * stop, otherwise returns true.
 */
 template <typename Func> void WalkTree(Func func) const {
 std::stack<bst_node_t> nodes;
 nodes.push(kRoot);
 auto &self = *this;
 while (!nodes.empty()) {
 auto nidx = nodes.top();
 nodes.pop();
 if (!func(nidx)) {
 return;
 }
 auto left = self.LeftChild(nidx);
 auto right = self.RightChild(nidx);
 if (left != RegTree::kInvalidNodeId) {
 nodes.push(left);
 }
 if (right != RegTree::kInvalidNodeId) {
 nodes.push(right);
 }
 }
 }
 /** \brief 测试两棵树是否相等。 */[[nodiscard]] bool Equal(const RegTree& b) const;

 /** \brief 将叶子节点展开为分支节点 * \param nid 要展开的节点 id * \param split_index 分裂的特征索引 * \param split_value 分裂条件 * \param default_left 默认方向 * \param base_weight 节点的基权重 * \param left_leaf_weight 左子节点的叶子权重 * \param right_leaf_weight 右子节点的叶子权重 * \param loss_change 此分裂引起的训练损失变化 * \param sum_hess 当前节点的 hessian 之和 * \param left_sum 左子节点的 hessian 之和 * \param right_sum 右子节点的 hessian 之和 */void ExpandNode(bst_node_t nid, unsigned split_index, bst_float split_value,
 bool default_left, bst_float base_weight,
 bst_float left_leaf_weight, bst_float right_leaf_weight,
 bst_float loss_change, float sum_hess, float left_sum,
 float right_sum,
 bst_node_t leaf_right_child = kInvalidNodeId);
 /** \brief 将多目标叶子节点展开为分支节点 * \param nidx 要展开的节点 id * \param split_index 分裂的特征索引 * \param split_cond 分裂条件 * \param default_left 默认方向 * \param base_weight 节点的基权重 * \param left_weight 左子节点的叶子权重 * \param right_weight 右子节点的叶子权重 */void ExpandNode(bst_node_t nidx, bst_feature_t split_index, float split_cond, bool default_left,
 linalg::VectorView<float const> base_weight,
 linalg::VectorView<float const> left_weight,
 linalg::VectorView<float const> right_weight);

 /** \brief 通过类别分裂展开叶子节点 * \param nid 要展开的节点 id * \param split_index 分裂的特征索引 * \param split_cat 左分支中的类别列表 * \param default_left 默认方向 * \param base_weight 节点的基权重 * \param left_leaf_weight 左子节点的叶子权重 * \param right_leaf_weight 右子节点的叶子权重 * \param loss_change 此分裂引起的训练损失变化 * \param sum_hess 当前节点的 hessian 之和 * \param left_sum 左子节点的 hessian 之和 * \param right_sum 右子节点的 hessian 之和 */void ExpandCategorical(bst_node_t nid, bst_feature_t split_index,
 common::Span<const uint32_t> split_cat, bool default_left,
 bst_float base_weight, bst_float left_leaf_weight,
 bst_float right_leaf_weight, bst_float loss_change, float sum_hess,
 float left_sum, float right_sum);
 /** \brief 检查树是否包含类别分裂 */[[nodiscard]] bool HasCategoricalSplit() const { return !split_categories_.empty(); }
 /** \brief 检查是否是多目标树 */[[nodiscard]] bool IsMultiTarget() const { return static_cast<bool>(p_mt_tree_); }
 /** \brief 树输出的目标数量。 */[[nodiscard]] bst_target_t NumTargets() const { return param_.size_leaf_vector; }
 /** \brief 如果是多目标树，获取 MultiTargetTree 对象 */[[nodiscard]] auto GetMultiTargetTree() const {
 CHECK(IsMultiTarget());
 return p_mt_tree_.get();
 }
 /** \brief 此树中使用的特征数量 */[[nodiscard]] bst_feature_t NumFeatures() const noexcept { return param_.num_feature; }
 /** \brief 树中的节点数量 */[[nodiscard]] bst_node_t NumNodes() const noexcept { return param_.num_nodes; }
 /** \brief 树中的有效节点数量 */[[nodiscard]] bst_node_t NumValidNodes() const noexcept {
 return param_.num_nodes - param_.num_deleted;
 }
 /** \brief 树中的额外节点数量 */[[nodiscard]] bst_node_t NumExtraNodes() const noexcept {
 return param_.num_nodes - 1 - param_.num_deleted;
 }
 /* \brief 计算树中的叶子节点数量。 */
 [[nodiscard]] bst_node_t GetNumLeaves() const;
 /** \brief 计算树中的分裂节点数量。 */[[nodiscard]] bst_node_t GetNumSplitNodes() const;

 /** \brief 获取节点的深度 * \param nid 节点 id * \return 节点的深度 */[[nodiscard]] std::int32_t GetDepth(bst_node_t nid) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->Depth(nid);
 }
 int depth = 0;
 while (!nodes_[nid].IsRoot()) {
 ++depth;
 nid = nodes_[nid].Parent();
 }
 return depth;
 }
 /** \brief 设置节点的叶子向量。 * \param nidx 节点索引 * \param weight 叶子值 */void SetLeaf(bst_node_t nidx, linalg::VectorView<float const> weight) {
 CHECK(IsMultiTarget());
 return this->p_mt_tree_->SetLeaf(nidx, weight);
 }

 /** \brief 获取节点的最大深度 * \param nid 节点 id * \return 节点的最大深度 */[[nodiscard]] int MaxDepth(int nid) const {
 if (nodes_[nid].IsLeaf()) return 0;
 return std::max(MaxDepth(nodes_[nid].LeftChild()) + 1, MaxDepth(nodes_[nid].RightChild()) + 1);
 }

 /** \brief 获取树的最大深度 */int MaxDepth() { return MaxDepth(0); }

 /** \brief 一个帮助使用特征向量的结构 * \note 这是一个临时的辅助结构，请谨慎使用 */struct FVec {
 /** * \brief 初始化特征向量 * \param size 特征向量的大小 */void Init(size_t size);
 /** * \brief 使用数据实例填充特征向量 * \param inst 数据实例 */void Fill(SparsePage::Inst const& inst);

 /** * \brief 清空特征向量 */void Drop();
 /** * \brief 获取特征向量的大小 */[[nodiscard]] size_t Size() const;
 [[nodiscard]] bst_float GetFvalue(size_t i) const;
 [[nodiscard]] bool IsMissing(size_t i) const;
 [[nodiscard]] bool HasMissing() const;
 void HasMissing(bool has_missing) { this->has_missing_ = has_missing; }

 [[nodiscard]] common::Span<float> Data() { return data_; }

 private
 std::vector<float> data_;
 bool has_missing_;
 };

 void CalculateContributionsApprox(const RegTree::FVec& feat,
 std::vector<float>* mean_values,
 bst_float* out_contribs) const;
 [[nodiscard]] std::string DumpModel(const FeatureMap& fmap, bool with_stats,
 std::string format) const;
 [[nodiscard]] FeatureType NodeSplitType(bst_node_t nidx) const { return split_types_.at(nidx); }
 [[nodiscard]] std::vector<FeatureType> const& GetSplitTypes() const {
 return split_types_;
 }
 [[nodiscard]] common::Span<uint32_t const> GetSplitCategories() const {
 return split_categories_;
 }
 [[nodiscard]] common::Span<uint32_t const> NodeCats(bst_node_t nidx) const {
 auto node_ptr = GetCategoriesMatrix().node_ptr;
 auto categories = GetCategoriesMatrix().categories;
 auto segment = node_ptr[nidx];
 auto node_cats = categories.subspan(segment.beg, segment.size);
 return node_cats;
 }
 [[nodiscard]] auto const& GetSplitCategoriesPtr() const { return split_categories_segments_; }

 struct CategoricalSplitMatrix {
 struct Segment {
 std::size_t beg{0};
 std::size_t size{0};
 };
 common::Span<FeatureType const> split_type;
 common::Span<uint32_t const> categories;
 common::Span<Segment const> node_ptr;
 };

 [[nodiscard]] CategoricalSplitMatrix GetCategoriesMatrix() const {
 CategoricalSplitMatrix view;
 view.split_type = common::Span<FeatureType const>(this->GetSplitTypes());
 view.categories = this->GetSplitCategories();
 view.node_ptr = common::Span<CategoricalSplitMatrix::Segment const>(split_categories_segments_);
 return view;
 }

 [[nodiscard]] bst_feature_t SplitIndex(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->SplitIndex(nidx);
 }
 return (*this)[nidx].SplitIndex();
 }
 [[nodiscard]] float SplitCond(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->SplitCond(nidx);
 }
 return (*this)[nidx].SplitCond();
 }
 [[nodiscard]] bool DefaultLeft(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->DefaultLeft(nidx);
 }
 return (*this)[nidx].DefaultLeft();
 }
 [[nodiscard]] bst_node_t DefaultChild(bst_node_t nidx) const {
 return this->DefaultLeft(nidx) ? this->LeftChild(nidx) : this->RightChild(nidx);
 }
 [[nodiscard]] bool IsRoot(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return nidx == kRoot;
 }
 return (*this)[nidx].IsRoot();
 }
 [[nodiscard]] bool IsLeaf(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->IsLeaf(nidx);
 }
 return (*this)[nidx].IsLeaf();
 }
 [[nodiscard]] bst_node_t Parent(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->Parent(nidx);
 }
 return (*this)[nidx].Parent();
 }
 [[nodiscard]] bst_node_t LeftChild(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->LeftChild(nidx);
 }
 return (*this)[nidx].LeftChild();
 }
 [[nodiscard]] bst_node_t RightChild(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->RightChild(nidx);
 }
 return (*this)[nidx].RightChild();
 }
 [[nodiscard]] bool IsLeftChild(bst_node_t nidx) const {
 if (IsMultiTarget()) {
 CHECK_NE(nidx, kRoot);
 auto p = this->p_mt_tree_->Parent(nidx);
 return nidx == this->p_mt_tree_->LeftChild(p);
 }
 return (*this)[nidx].IsLeftChild();
 }
 [[nodiscard]] bst_node_t Size() const {
 if (IsMultiTarget()) {
 return this->p_mt_tree_->Size();
 }
 return this->nodes_.size();
 }

 private
 template <bool typed>
 void LoadCategoricalSplit(Json const& in);
 void SaveCategoricalSplit(Json* p_out) const;
 TreeParam param_;
 // vector of nodes
 std::vector<Node> nodes_;
 // free node space, used during training process
 std::vector<int> deleted_nodes_;
 // stats of nodes
 std::vector<RTreeNodeStat> stats_;
 std::vector<FeatureType> split_types_;

 // Categories for each internal node.
 std::vector<uint32_t> split_categories_;
 // Ptr to split categories of each node.
 std::vector<CategoricalSplitMatrix::Segment> split_categories_segments_;
 // ptr to multi-target tree with vector leaf.
 CopyUniquePtr<MultiTargetTree> p_mt_tree_;
 // allocate a new node,
 // !!!!!! NOTE: may cause BUG here, nodes.resize
 bst_node_t AllocNode() {
 if (param_.num_deleted != 0) {
 int nid = deleted_nodes_.back();
 deleted_nodes_.pop_back();
 nodes_[nid].Reuse();
 --param_.num_deleted;
 return nid;
 }
 int nd = param_.num_nodes++;
 CHECK_LT(param_.num_nodes, std::numeric_limits<int>::max())
 << "number of nodes in the tree exceed 2^31";
 nodes_.resize(param_.num_nodes);
 stats_.resize(param_.num_nodes);
 split_types_.resize(param_.num_nodes, FeatureType::kNumerical);
 split_categories_segments_.resize(param_.num_nodes);
 return nd;
 }
 // delete a tree node, keep the parent field to allow trace back
 void DeleteNode(int nid) {
 CHECK_GE(nid, 1);
 auto pid = (*this)[nid].Parent();
 if (nid == (*this)[pid].LeftChild()) {
 (*this)[pid].SetLeftChild(kInvalidNodeId);
 } else {
 (*this)[pid].SetRightChild(kInvalidNodeId);
 }

 deleted_nodes_.push_back(nid);
 nodes_[nid].MarkDelete();
 ++param_.num_deleted;
 }
};

inline void RegTree::FVec::Init(size_t size) {
 data_.resize(size);
 std::fill(data_.begin(), data_.end(), std::numeric_limits<float>::quiet_NaN());
 has_missing_ = true;
}

inline void RegTree::FVec::Fill(SparsePage::Inst const& inst) {
 auto p_data = inst.data();
 auto p_out = data_.data();

 for (std::size_t i = 0, n = inst.size(); i < n; ++i) {
 auto const& entry = p_data[i];
 p_out[entry.index] = entry.fvalue;
 }
 has_missing_ = data_.size() != inst.size();
}

inline void RegTree::FVec::Drop() { this->Init(this->Size()); }

inline size_t RegTree::FVec::Size() const {
 return data_.size();
}

inline float RegTree::FVec::GetFvalue(size_t i) const {
 return data_[i];
}

inline bool RegTree::FVec::IsMissing(size_t i) const { return std::isnan(data_[i]); }

inline bool RegTree::FVec::HasMissing() const { return has_missing_; }

// Multi-target tree not yet implemented error
inline StringView MTNotImplemented() {
 return " support for multi-target tree is not yet implemented.";
}
} // namespace xgboost
#endif // XGBOOST_TREE_MODEL_H_