| 1498 | * for more complicated types. |
| 1499 | */ |
| 1500 | template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const |
| 1501 | { |
| 1502 | // We cannot use a lambda here, as lambdas are non assignable, and the set operations |
| 1503 | // below require moving the comparators around. |
| 1504 | struct Comp { |
| 1505 | const Ctx* ctx_ptr; |
| 1506 | Comp(const Ctx& ctx) : ctx_ptr(&ctx) {} |
| 1507 | bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); } |
| 1508 | }; |
| 1509 | |
| 1510 | // state in the recursive computation: |
| 1511 | // - std::nullopt means "this node has duplicates" |
| 1512 | // - an std::set means "this node has no duplicate keys, and they are: ...". |
| 1513 | using keyset = std::set<Key, Comp>; |
| 1514 | using state = std::optional<keyset>; |
| 1515 | |
| 1516 | auto upfn = [&ctx](const Node& node, std::span<state> subs) -> state { |
| 1517 | // If this node is already known to have duplicates, nothing left to do. |
| 1518 | if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {}; |
| 1519 | |
| 1520 | // Check if one of the children is already known to have duplicates. |
| 1521 | for (auto& sub : subs) { |
| 1522 | if (!sub.has_value()) { |
| 1523 | node.has_duplicate_keys = true; |
| 1524 | return {}; |
| 1525 | } |
| 1526 | } |
| 1527 | |
| 1528 | // Start building the set of keys involved in this node and children. |
| 1529 | // Start by keys in this node directly. |
| 1530 | size_t keys_count = node.keys.size(); |
| 1531 | keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)}; |
| 1532 | if (key_set.size() != keys_count) { |
| 1533 | // It already has duplicates; bail out. |
| 1534 | node.has_duplicate_keys = true; |
| 1535 | return {}; |
| 1536 | } |
| 1537 | |
| 1538 | // Merge the keys from the children into this set. |
| 1539 | for (auto& sub : subs) { |
| 1540 | keys_count += sub->size(); |
| 1541 | // Small optimization: std::set::merge is linear in the size of the second arg but |
| 1542 | // logarithmic in the size of the first. |
| 1543 | if (key_set.size() < sub->size()) std::swap(key_set, *sub); |
| 1544 | key_set.merge(*sub); |
| 1545 | if (key_set.size() != keys_count) { |
| 1546 | node.has_duplicate_keys = true; |
| 1547 | return {}; |
| 1548 | } |
| 1549 | } |
| 1550 | |
| 1551 | node.has_duplicate_keys = false; |
| 1552 | return key_set; |
| 1553 | }; |
| 1554 | |
| 1555 | TreeEval<state>(upfn); |
| 1556 | } |
| 1557 | |