inline bool leq()

in include/PatriciaTreeMap.h [610:707]

• 69 lines of code
• 24 McCabe index (conditional complexity)

inline bool leq(
    const boost::intrusive_ptr<PatriciaTree<IntegerType, Value>>& s,
    const boost::intrusive_ptr<PatriciaTree<IntegerType, Value>>& t) {

  RUNTIME_CHECK(Value::default_value().is_top() ||
                    Value::default_value().is_bottom(),
                undefined_operation());

  if (s == t) {
    // This condition allows the leq operation to run in sublinear time when
    // comparing Patricia trees that share some structure.
    return true;
  }
  if (s == nullptr) {
    return Value::default_value().is_bottom();
  }
  if (t == nullptr) {
    return Value::default_value().is_top();
  }
  if (s->is_leaf()) {
    const auto& s_leaf =
        boost::static_pointer_cast<PatriciaTreeLeaf<IntegerType, Value>>(s);

    if (t->is_branch()) {
      // t has at least one non-default binding that s doesn't have.
      if (Value::default_value().is_top()) {
        // The non-default binding in t can never be <= Top.
        return false;
      }

      // Otherwise, find if t contains s.
      // The missing bindings in s are bound to Bottom in this case. Even if we
      // know t contains strictly more bindings than s, they all satisfy the leq
      // condition. For each key k in t but not in s, s[k] == Bottom <= t[k]
      // always hold.
      auto* t_value = find_value(s_leaf->key(), t);
      if (t_value == nullptr) {
        // Always false if default_value is Bottom, which we already assume.
        return false;
      }
      return Value::leq(s_leaf->value(), *t_value);
    }

    // Both nodes are leaves. s leq to t iff
    // key(s) == key(t) && value(s) <= value(t).
    const auto& t_leaf =
        boost::static_pointer_cast<PatriciaTreeLeaf<IntegerType, Value>>(t);
    return s_leaf->key() == t_leaf->key() &&
           Value::leq(s_leaf->value(), t_leaf->value());
  } else if (t->is_leaf()) {
    // s has at least one non-default binding that t doesn't have.
    if (Value::default_value().is_bottom()) {
      // There exists a key such that s[key] != Bottom and t[key] == Bottom.
      return false;
    }

    const auto& t_leaf =
        boost::static_pointer_cast<PatriciaTreeLeaf<IntegerType, Value>>(t);
    auto* s_value = find_value(t_leaf->key(), s);
    if (s_value == nullptr) {
      // Always false if default_value is Top, which we already assume.
      return false;
    }
    return Value::leq(*s_value, t_leaf->value());
  }

  // Neither s nor t is a leaf.
  const auto& s_branch =
      boost::static_pointer_cast<PatriciaTreeBranch<IntegerType, Value>>(s);
  const auto& t_branch =
      boost::static_pointer_cast<PatriciaTreeBranch<IntegerType, Value>>(t);
  IntegerType m = s_branch->branching_bit();
  IntegerType n = t_branch->branching_bit();
  IntegerType p = s_branch->prefix();
  IntegerType q = t_branch->prefix();
  const auto& s0 = s_branch->left_tree();
  const auto& s1 = s_branch->right_tree();
  const auto& t0 = t_branch->left_tree();
  const auto& t1 = t_branch->right_tree();
  if (m == n && p == q) {
    // The two trees have the same prefix, compare each subtrees.
    return leq(s0, t0) && leq(s1, t1);
  }
  if (m < n && match_prefix(q, p, m)) {
    // The tree t only contains bindings present in a subtree of s, and s has
    // bindings not present in t.
    return Value::default_value().is_top() &&
           leq(is_zero_bit(q, m) ? s0 : s1, t);
  }
  if (m > n && match_prefix(p, q, n)) {
    // The tree s only contains bindings present in a subtree of t, and t has
    // bindings not present in s.
    return Value::default_value().is_bottom() &&
           leq(s, is_zero_bit(p, n) ? t0 : t1);
  }
  // s and t both have bindings that are not present in the other tree.
  return false;
}