123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108 |
- // Copyright 2016 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "components/zucchini/targets_affinity.h"
- #include <algorithm>
- #include "base/check_op.h"
- #include "components/zucchini/equivalence_map.h"
- namespace zucchini {
- namespace {
- constexpr uint32_t kNoLabel = 0;
- }
- TargetsAffinity::TargetsAffinity() = default;
- TargetsAffinity::~TargetsAffinity() = default;
- void TargetsAffinity::InferFromSimilarities(
- const EquivalenceMap& equivalences,
- const std::deque<offset_t>& old_targets,
- const std::deque<offset_t>& new_targets) {
- forward_association_.assign(old_targets.size(), {});
- backward_association_.assign(new_targets.size(), {});
- if (old_targets.empty() || new_targets.empty())
- return;
- key_t new_key = 0;
- for (auto candidate : equivalences) { // Sorted by |dst_offset|.
- DCHECK_GT(candidate.similarity, 0.0);
- while (new_key < new_targets.size() &&
- new_targets[new_key] < candidate.eq.dst_offset) {
- ++new_key;
- }
- // Visit each new target covered by |candidate.eq| and find / update its
- // associated old target.
- for (; new_key < new_targets.size() &&
- new_targets[new_key] < candidate.eq.dst_end();
- ++new_key) {
- if (backward_association_[new_key].affinity >= candidate.similarity)
- continue;
- DCHECK_GE(new_targets[new_key], candidate.eq.dst_offset);
- offset_t old_target = new_targets[new_key] - candidate.eq.dst_offset +
- candidate.eq.src_offset;
- auto old_it =
- std::lower_bound(old_targets.begin(), old_targets.end(), old_target);
- // If new target can be mapped via |candidate.eq| to an old target, then
- // attempt to associate them. Multiple new targets can compete for the
- // same old target. The heuristic here makes selections to maximize
- // |candidate.similarity|, and if a tie occurs, minimize new target offset
- // (by first-come, first-served).
- if (old_it != old_targets.end() && *old_it == old_target) {
- key_t old_key = static_cast<key_t>(old_it - old_targets.begin());
- if (candidate.similarity > forward_association_[old_key].affinity) {
- // Reset other associations.
- if (forward_association_[old_key].affinity > 0.0)
- backward_association_[forward_association_[old_key].other] = {};
- if (backward_association_[new_key].affinity > 0.0)
- forward_association_[backward_association_[new_key].other] = {};
- // Assign new association.
- forward_association_[old_key] = {new_key, candidate.similarity};
- backward_association_[new_key] = {old_key, candidate.similarity};
- }
- }
- }
- }
- }
- uint32_t TargetsAffinity::AssignLabels(double min_affinity,
- std::vector<uint32_t>* old_labels,
- std::vector<uint32_t>* new_labels) {
- old_labels->assign(forward_association_.size(), kNoLabel);
- new_labels->assign(backward_association_.size(), kNoLabel);
- uint32_t label = kNoLabel + 1;
- for (key_t old_key = 0; old_key < forward_association_.size(); ++old_key) {
- Association association = forward_association_[old_key];
- if (association.affinity >= min_affinity) {
- (*old_labels)[old_key] = label;
- DCHECK_EQ(0U, (*new_labels)[association.other]);
- (*new_labels)[association.other] = label;
- ++label;
- }
- }
- return label;
- }
- double TargetsAffinity::AffinityBetween(key_t old_key, key_t new_key) const {
- DCHECK_LT(old_key, forward_association_.size());
- DCHECK_LT(new_key, backward_association_.size());
- if (forward_association_[old_key].affinity > 0.0 &&
- forward_association_[old_key].other == new_key) {
- DCHECK_EQ(backward_association_[new_key].other, old_key);
- DCHECK_EQ(forward_association_[old_key].affinity,
- backward_association_[new_key].affinity);
- return forward_association_[old_key].affinity;
- }
- return -std::max(forward_association_[old_key].affinity,
- backward_association_[new_key].affinity);
- }
- } // namespace zucchini
|