aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2021-03-19 15:26:28 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2021-03-19 15:26:28 +0200
commit5ecdb9a3b5cb85418f69126226b2636caed2e4da (patch)
treedf53881ecdb8c9efd1480097756a20ec262b1300
parente283b08481cfec9aa55b3ddbf369d632c7aa7b0f (diff)
Add prefix_map::find_sup_if()
-rw-r--r--libbutl/prefix-map.mxx12
-rw-r--r--libbutl/prefix-map.txx70
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
+ }
}