text: /*
  * Copyright (C) 2021. Huawei Technologies Co., Ltd.
  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * */
  /*!
   * Copyright 2017-2018 by Contributors
   * \file updater_quantile_hist.h
   * \brief use quantized feature values to construct a tree
   * \author Philip Cho, Tianqi Chen, Egor Smirnov
   */
  #ifndef XGBOOST_TREE_UPDATER_QUANTILE_HIST_H_
  #define XGBOOST_TREE_UPDATER_QUANTILE_HIST_H_
  
  #include <dmlc/timer.h>
  #include <rabit/rabit.h>
  #include <xgboost/tree_updater.h>
  
  #include <memory>
  #include <vector>
  #include <string>
  #include <queue>
  #include <iomanip>
  #include <unordered_map>
  #include <utility>
  
  #include "xgboost/data.h"
  #include "xgboost/json.h"
  #include "constraints.h"
  #include "./param.h"
  #include "./split_evaluator.h"
  #include "../common/random.h"
  #include "../common/timer.h"
  #include "../common/hist_util.h"
  #include "../common/row_set.h"
  #include "../common/column_matrix.h"
  
  namespace xgboost {
  
  /*!
   * \brief A C-style array with in-stack allocation. As long as the array is smaller than MaxStackSize, it will be allocated inside the stack. Otherwise, it will be heap-allocated.
   */
  template<typename T, size_t MaxStackSize>
  class MemStackAllocator {
   public:
    explicit MemStackAllocator(size_t required_size): required_size_(required_size) {
    }
  
    T* Get() {
      if (!ptr_) {
        if (MaxStackSize >= required_size_) {
          ptr_ = stack_mem_;
        } else {
          ptr_ =  reinterpret_cast<T*>(malloc(required_size_ * sizeof(T)));
          do_free_ = true;
        }
      }
  
      return ptr_;
    }
  
    ~MemStackAllocator() {
      if (do_free_) free(ptr_);
    }
  
  
   private:
    T* ptr_ = nullptr;
    bool do_free_ = false;
    size_t required_size_;
    T stack_mem_[MaxStackSize];
  };
  
  namespace tree {
  
  using xgboost::common::GHistIndexMatrix;
  using xgboost::common::GHistIndexBlockMatrix;
  using xgboost::common::GHistIndexRow;
  using xgboost::common::HistCollection;
  using xgboost::common::RowSetCollection;
  using xgboost::common::GHistRow;
  using xgboost::common::GHistBuilder;
  using xgboost::common::ColumnMatrix;
  using xgboost::common::Column;
  
  /*! \brief construct a tree using quantized feature values */
  class QuantileHistMaker: public TreeUpdater {
   public:
    QuantileHistMaker() = default;
    void Configure(const Args& args) override;
  
    void Update(HostDeviceVector<GradientPair>* gpair,
                DMatrix* dmat,
                const std::vector<RegTree*>& trees, int iter,
                float* p_last_round_best_loss) override;
  
    bool UpdatePredictionCache(const DMatrix* data,
                               HostDeviceVector<bst_float>* out_preds, int iter) override;
  
    void LoadConfig(Json const& in) override {
      auto const& config = get<Object const>(in);
      FromJson(config.at("train_param"), &this->param_);
    }
    void SaveConfig(Json* p_out) const override {
      auto& out = *p_out;
      out["train_param"] = ToJson(param_);
    }
  
    char const* Name() const override {
      return "grow_quantile_histmaker";
    }
  
   protected:
    // training parameter
    TrainParam param_;
    // quantized data matrix
    GHistIndexMatrix gmat_;
    // (optional) data matrix with feature grouping
    GHistIndexBlockMatrix gmatb_;
    // column accessor
    ColumnMatrix column_matrix_;
    DMatrix const* p_last_dmat_ {nullptr};
    bool is_gmat_initialized_ {false};
  
    // data structure
    struct NodeEntry {
      /*! \brief statics for node entry */
      GradStats stats;
      /*! \brief loss of this node, without split */
      bst_float root_gain;
      /*! \brief weight calculated related to current data */
      float weight;
      /*! \brief current best solution */
      SplitEntry best;
      // constructor
      explicit NodeEntry(const TrainParam& param)
          : root_gain(0.0f), weight(0.0f) {}
    };
    // actual builder that runs the algorithm
  
    struct Builder {
     public:
      // constructor
      explicit Builder(const TrainParam& param,
                       std::unique_ptr<TreeUpdater> pruner,
                       std::unique_ptr<SplitEvaluator> spliteval,
                       FeatureInteractionConstraintHost int_constraints_,
                       DMatrix const* fmat)
        : param_(param), pruner_(std::move(pruner)),
          spliteval_(std::move(spliteval)),
          interaction_constraints_{std::move(int_constraints_)},
          p_last_tree_(nullptr), p_last_fmat_(fmat),
          last_iter_sampling(-1) {
        builder_monitor_.Init("Quantile::Builder");
      }
      // update one tree, growing
      virtual void Update(const GHistIndexMatrix& gmat,
                          const GHistIndexBlockMatrix& gmatb,
                          const ColumnMatrix& column_matrix,
                          HostDeviceVector<GradientPair>* gpair,
                          DMatrix* p_fmat,
                          RegTree* p_tree,
                          int iter,
                          float* p_last_round_best_loss);
  
      inline void BuildHist(const std::vector<GradientPair>& gpair,
                            const RowSetCollection::Elem row_indices,
                            const GHistIndexMatrix& gmat,
                            const GHistIndexBlockMatrix& gmatb,
                            GHistRow hist) {
        if (param_.enable_feature_grouping > 0) {
          hist_builder_.BuildBlockHist(gpair, row_indices, gmatb, hist);
        } else {
          hist_builder_.BuildHist(gpair, row_indices, gmat, hist, data_layout_ != kSparseData);
        }
      }
  
      inline void SubtractionTrick(GHistRow self, GHistRow sibling, GHistRow parent) {
        builder_monitor_.Start("SubtractionTrick");
        hist_builder_.SubtractionTrick(self, sibling, parent);
        builder_monitor_.Stop("SubtractionTrick");
      }
  
      bool UpdatePredictionCache(const DMatrix* data,
                                 HostDeviceVector<bst_float>* p_out_preds);
  
     protected:
      /* tree growing policies */
      struct ExpandEntry {
        static const int kRootNid  = 0;
        static const int kEmptyNid = -1;
        int nid;
        int sibling_nid;
        int depth;
        bst_float loss_chg;
        unsigned timestamp;
        ExpandEntry(int nid, int sibling_nid, int depth, bst_float loss_chg, unsigned tstmp):
          nid(nid), sibling_nid(sibling_nid), depth(depth), loss_chg(loss_chg), timestamp(tstmp) {}
  
        bool IsValid(TrainParam const& param, int32_t num_leaves) const {
          bool ret = loss_chg <= kRtEps ||
                     (param.max_depth > 0 && this->depth == param.max_depth) ||
                     (param.max_leaves > 0 && num_leaves == param.max_leaves);
          return ret;
        }
      };
  
      // initialize temp data structure
      virtual void InitData(const GHistIndexMatrix& gmat,
                    const std::vector<GradientPair>& gpair,
                    const DMatrix& fmat,
                    const RegTree& tree, int iter = 0);
  
      void EvaluateSplits(const std::vector<ExpandEntry>& nodes_set,
                          const GHistIndexMatrix& gmat,
                          const HistCollection& hist,
                          const RegTree& tree,
                          int _iter = 0);
  
      void ApplySplit(std::vector<ExpandEntry> nodes,
                          const GHistIndexMatrix& gmat,
                          const ColumnMatrix& column_matrix,
                          const HistCollection& hist,
                          RegTree* p_tree);
  
      template <typename BinIdxType>
      void PartitionKernel(const size_t node_in_set, const size_t nid, common::Range1d range,
                           const int32_t split_cond,
                           const ColumnMatrix& column_matrix, const RegTree& tree);
  
      void AddSplitsToRowSet(const std::vector<ExpandEntry>& nodes, RegTree* p_tree);
  
  
      void FindSplitConditions(const std::vector<ExpandEntry>& nodes, const RegTree& tree,
                               const GHistIndexMatrix& gmat, std::vector<int32_t>* split_conditions);
  
      void InitNewNode(int nid,
                       const GHistIndexMatrix& gmat,
                       const std::vector<GradientPair>& gpair,
                       const DMatrix& fmat,
                       const RegTree& tree);
  
      // Enumerate the split values of specific feature
      // Returns the sum of gradients corresponding to the data points that contains a non-missing
      // value for the particular feature fid.
      template <int d_step>
      GradStats EnumerateSplit(const GHistIndexMatrix &gmat, const GHistRow &hist,
                               const NodeEntry &snode, SplitEntry *p_best,
                               bst_uint fid, bst_uint nodeID, int proc_grid_idx) const;
  
      // if sum of statistics for non-missing values in the node
      // is equal to sum of statistics for all values:
      // then - there are no missing values
      // else - there are missing values
      bool SplitContainsMissingValues(const GradStats e, const NodeEntry& snode);
  
      void ExpandWithDepthWise(const GHistIndexMatrix &gmat,
                               const GHistIndexBlockMatrix &gmatb,
                               const ColumnMatrix &column_matrix,
                               DMatrix *p_fmat,
                               RegTree *p_tree,
                               const std::vector<GradientPair> &gpair_h, int _iter,
                               float* p_last_round_best_loss);
  
      void BuildLocalHistograms(const GHistIndexMatrix &gmat,
                                const GHistIndexBlockMatrix &gmatb,
                                RegTree *p_tree,
                                const std::vector<GradientPair> &gpair_h);
  
      void AddHistRows(int *starting_index, int *sync_count);
  
      void BuildHistogramsLossGuide(
                          ExpandEntry entry,
                          const GHistIndexMatrix &gmat,
                          const GHistIndexBlockMatrix &gmatb,
                          RegTree *p_tree,
                          const std::vector<GradientPair> &gpair_h);
  
      // Split nodes to 2 sets depending on amount of rows in each node
      // Histograms for small nodes will be built explicitly
      // Histograms for big nodes will be built by 'Subtraction Trick'
      void SplitSiblings(const std::vector<ExpandEntry>& nodes,
                     std::vector<ExpandEntry>* small_siblings,
                     std::vector<ExpandEntry>* big_siblings,
                     RegTree *p_tree);
  
      void SyncHistograms(int starting_index,
                          int sync_count,
                          RegTree *p_tree);
  
      void BuildNodeStats(const GHistIndexMatrix &gmat,
                          DMatrix *p_fmat,
                          RegTree *p_tree,
                          const std::vector<GradientPair> &gpair_h);
  
      void EvaluateAndApplySplits(const GHistIndexMatrix &gmat,
                                  const ColumnMatrix &column_matrix,
                                  RegTree *p_tree,
                                  int *num_leaves,
                                  int depth,
                                  unsigned *timestamp,
                                  std::vector<ExpandEntry> *temp_qexpand_depth, 
                                  int _iter, 
                                  float* p_last_round_best_loss);
  
      void AddSplitsToTree(
                const GHistIndexMatrix &gmat,
                RegTree *p_tree,
                int *num_leaves,
                int depth,
                unsigned *timestamp,
                std::vector<ExpandEntry>* nodes_for_apply_split,
                std::vector<ExpandEntry>* temp_qexpand_depth,
                float* p_last_round_best_loss);
  
      void ExpandWithLossGuide(const GHistIndexMatrix& gmat,
                               const GHistIndexBlockMatrix& gmatb,
                               const ColumnMatrix& column_matrix,
                               DMatrix* p_fmat,
                               RegTree* p_tree,
                               const std::vector<GradientPair>& gpair_h, 
                               int _iter);
  
      inline static bool LossGuide(ExpandEntry lhs, ExpandEntry rhs) {
        if (lhs.loss_chg == rhs.loss_chg) {
          return lhs.timestamp > rhs.timestamp;  // favor small timestamp
        } else {
          return lhs.loss_chg < rhs.loss_chg;  // favor large loss_chg
        }
      }
      //  --data fields--
      const TrainParam& param_;
      // number of omp thread used during training
      int nthread_;
      common::ColumnSampler column_sampler_;
      // the internal row sets
      RowSetCollection row_set_collection_;
  
      int last_iter_sampling;
      std::vector<size_t> last_sampling;
      
      // the temp space for split
      std::vector<RowSetCollection::Split> row_split_tloc_;
      std::vector<SplitEntry> best_split_tloc_;
      /*! \brief TreeNode Data: statistics for each constructed node */
      std::vector<NodeEntry> snode_;
      /*! \brief culmulative histogram of gradients. */
      HistCollection hist_;
      /*! \brief feature with least # of bins. to be used for dense specialization
                 of InitNewNode() */
      uint32_t fid_least_bins_;
      /*! \brief local prediction cache; maps node id to leaf value */
      std::vector<float> leaf_value_cache_;
  
      GHistBuilder hist_builder_;
      std::unique_ptr<TreeUpdater> pruner_;
      std::unique_ptr<SplitEvaluator> spliteval_;
      FeatureInteractionConstraintHost interaction_constraints_;
  
      static constexpr size_t kPartitionBlockSize = 2048;
      common::PartitionBuilder<kPartitionBlockSize> partition_builder_;
  
      // back pointers to tree and data matrix
      const RegTree* p_last_tree_;
      DMatrix const* const p_last_fmat_;
  
      using ExpandQueue =
         std::priority_queue<ExpandEntry, std::vector<ExpandEntry>,
                             std::function<bool(ExpandEntry, ExpandEntry)>>;
  
      std::unique_ptr<ExpandQueue> qexpand_loss_guided_;
      std::vector<ExpandEntry> qexpand_depth_wise_;
      // key is the node id which should be calculated by Subtraction Trick, value is the node which
      // provides the evidence for substracts
      std::vector<ExpandEntry> nodes_for_subtraction_trick_;
      // list of nodes whose histograms would be built explicitly.
      std::vector<ExpandEntry> nodes_for_explicit_hist_build_;
  
      enum DataLayout { kDenseDataZeroBased, kDenseDataOneBased, kSparseData };
      DataLayout data_layout_;
  
      common::Monitor builder_monitor_;
      common::ParallelGHistBuilder hist_buffer_;
      rabit::Reducer<GradStats, GradStats::Reduce> histred_;
    };
  
    std::unique_ptr<Builder> builder_;
    std::unique_ptr<TreeUpdater> pruner_;
    std::unique_ptr<SplitEvaluator> spliteval_;
    FeatureInteractionConstraintHost int_constraint_;
  };
  
  }  // namespace tree
  }  // namespace xgboost
  
  #endif  // XGBOOST_TREE_UPDATER_QUANTILE_HIST_H_
  