void Merge()

in tfx_bsl/cc/sketches/weighted_quantiles_summary.h [110:182]

• 52 lines of code
• 9 McCabe index (conditional complexity)

  void Merge(const WeightedQuantilesSummary& other_summary) {
    // Make sure we have something to merge.
    const auto& other_entries = other_summary.entries_;
    if (other_entries.empty()) {
      return;
    }
    if (entries_.empty()) {
      BuildFromSummaryEntries(other_summary.entries_);
      return;
    }

    // Move current entries to make room for a new buffer.
    std::vector<SummaryEntry> base_entries(std::move(entries_));
    entries_.clear();
    entries_.reserve(base_entries.size() + other_entries.size());

    // Merge entries maintaining ranks. The idea is to stack values
    // in order which we can do in linear time as the two summaries are
    // already sorted. We keep track of the next lower rank from either
    // summary and update it as we pop elements from the summaries.
    // We handle the special case when the next two elements from either
    // summary are equal, in which case we just merge the two elements
    // and simultaneously update both ranks.
    auto it1 = base_entries.cbegin();
    auto it2 = other_entries.cbegin();
    WeightType next_min_rank1 = 0;
    WeightType next_min_rank2 = 0;
    while (it1 != base_entries.cend() && it2 != other_entries.cend()) {
      if (kCompFn(it1->value, it2->value)) {  // value1 < value2
        // Take value1 and use the last added value2 to compute
        // the min rank and the current value2 to compute the max rank.
        entries_.emplace_back(it1->value, it1->weight,
                              it1->min_rank + next_min_rank2,
                              it1->max_rank + it2->PrevMaxRank());
        // Update next min rank 1.
        next_min_rank1 = it1->NextMinRank();
        ++it1;
      } else if (kCompFn(it2->value, it1->value)) {  // value1 > value2
        // Take value2 and use the last added value1 to compute
        // the min rank and the current value1 to compute the max rank.
        entries_.emplace_back(it2->value, it2->weight,
                              it2->min_rank + next_min_rank1,
                              it2->max_rank + it1->PrevMaxRank());
        // Update next min rank 2.
        next_min_rank2 = it2->NextMinRank();
        ++it2;
      } else {  // value1 == value2
        // Straight additive merger of the two entries into one.
        entries_.emplace_back(it1->value, it1->weight + it2->weight,
                              it1->min_rank + it2->min_rank,
                              it1->max_rank + it2->max_rank);
        // Update next min ranks for both.
        next_min_rank1 = it1->NextMinRank();
        next_min_rank2 = it2->NextMinRank();
        ++it1;
        ++it2;
      }
    }

    // Fill in any residual.
    while (it1 != base_entries.cend()) {
      entries_.emplace_back(it1->value, it1->weight,
                            it1->min_rank + next_min_rank2,
                            it1->max_rank + other_entries.back().max_rank);
      ++it1;
    }
    while (it2 != other_entries.cend()) {
      entries_.emplace_back(it2->value, it2->weight,
                            it2->min_rank + next_min_rank1,
                            it2->max_rank + base_entries.back().max_rank);
      ++it2;
    }
  }