void quantiles_sketch::standard_merge()

in quantiles/include/quantiles_sketch_impl.hpp [1063:1124]

• 48 lines of code
• 14 McCabe index (conditional complexity)

void quantiles_sketch<T, C, A>::standard_merge(quantiles_sketch& tgt, FwdSk&& src) {
  if (src.get_k() != tgt.get_k()) {
    throw std::invalid_argument("src.get_k() != tgt.get_k()");
  }
  if (src.is_empty()) {
    return;
  }

  uint64_t new_n = src.get_n() + tgt.get_n();

  // move items from src's base buffer
  for (uint16_t i = 0; i < src.base_buffer_.size(); ++i) {
    tgt.update(conditional_forward<FwdSk>(src.base_buffer_[i]));
  }

  // check (after moving raw items) if we need to extend levels array
  uint8_t levels_needed = compute_levels_needed(tgt.get_k(), new_n);
  if (levels_needed > tgt.levels_.size()) {
    tgt.levels_.reserve(levels_needed);
    while (tgt.levels_.size() < levels_needed) {
      Level empty_level(tgt.allocator_);
      empty_level.reserve(tgt.get_k());
      tgt.levels_.push_back(std::move(empty_level));
    }
  }

  Level scratch_buf(tgt.allocator_);
  scratch_buf.reserve(2 * tgt.get_k());

  uint64_t src_pattern = src.bit_pattern_;
  for (uint8_t src_lvl = 0; src_pattern != 0; ++src_lvl, src_pattern >>= 1) {
    if ((src_pattern & 1) > 0) {
      scratch_buf.clear();

      // propagate-carry
      in_place_propagate_carry(src_lvl,
                               src.levels_[src_lvl], scratch_buf,
                               false, tgt);
      // update n_ at the end
    }
  }
  tgt.n_ = new_n;
  if ((tgt.get_n() / (2 * tgt.get_k())) != tgt.bit_pattern_) {
    throw std::logic_error("Failed internal consistency check after standard_merge()");
  }

  // update min and max items
  // can't just check is_empty() since min and max might not have been set if
  // there were no base buffer items added via update()
  if (!tgt.min_item_) {
    tgt.min_item_.emplace(conditional_forward<FwdSk>(*src.min_item_));
  } else {
    if (tgt.comparator_(*src.min_item_, *tgt.min_item_))
      *tgt.min_item_ = conditional_forward<FwdSk>(*src.min_item_);
  }
  if (!tgt.max_item_) {
    tgt.max_item_.emplace(conditional_forward<FwdSk>(*src.max_item_));
  } else {
    if (tgt.comparator_(*tgt.max_item_, *src.max_item_))
      *tgt.max_item_ = conditional_forward<FwdSk>(*src.max_item_);
  }
}