Add prefix_map::find_sup_if()

2 files changed, 82 insertions, 0 deletions

diff --git a/libbutl/prefix-map.mxx b/libbutl/prefix-map.mxx
index 75931da..634b8da 100644
--- a/libbutl/prefix-map.mxx
+++ b/libbutl/prefix-map.mxx
@@ -149,6 +149,18 @@ LIBBUTL_MODEXPORT namespace butl
 
     const_iterator
     find_sup (const key_type&) const;
+
+
+    // As above but additionally evaluate a predicate on each matching entry
+    // returning the one for which it returns true.
+    //
+    template <typename P>
+    iterator
+    find_sup_if (const key_type&, P);
+
+    template <typename P>
+    const_iterator
+    find_sup_if (const key_type&, P) const;
   };
 
   template <typename M, typename prefix_map_common<M>::delimiter_type D>
diff --git a/libbutl/prefix-map.txx b/libbutl/prefix-map.txx
index e9a99c9..edab8e1 100644
--- a/libbutl/prefix-map.txx
+++ b/libbutl/prefix-map.txx
@@ -127,4 +127,74 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
     return i;
 #endif
   }
+
+  template <typename M>
+  template <typename P>
+  auto prefix_map_common<M>::
+  find_sup_if (const key_type& k, P pred) -> iterator
+  {
+#if 0
+    const auto& c (this->key_comp ());
+
+    for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; )
+    {
+      --i;
+      if (c.prefix (i->first, k) && pred (*i))
+        return i;
+    }
+
+    return this->end ();
+#else
+    auto i (this->find (k)), e (this->end ());
+
+    if (i == e || !pred (*i))
+    {
+      const auto& c (this->key_comp ());
+
+      for (key_type p (k); c.prefix (p); )
+      {
+        i = this->find (p);
+        if (i != e && pred (*i))
+          break;
+      }
+    }
+
+    return i;
+#endif
+  }
+
+  template <typename M>
+  template <typename P>
+  auto prefix_map_common<M>::
+  find_sup_if (const key_type& k, P pred) const -> const_iterator
+  {
+#if 0
+    const auto& c (this->key_comp ());
+
+    for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; )
+    {
+      --i;
+      if (c.prefix (i->first, k) && pred (*i))
+        return i;
+    }
+
+    return this->end ();
+#else
+    auto i (this->find (k)), e (this->end ());
+
+    if (i == e || !pred (*i))
+    {
+      const auto& c (this->key_comp ());
+
+      for (key_type p (k); c.prefix (p); )
+      {
+        i = this->find (p);
+        if (i != e && pred (*i))
+          break;
+      }
+    }
+
+    return i;
+#endif
+  }
 }