Move find_sup() from path_map to prefix_map and fix

4 files changed, 141 insertions, 69 deletions

diff --git a/libbutl/path-map.mxx b/libbutl/path-map.mxx
index c526a89..2697a48 100644
--- a/libbutl/path-map.mxx
+++ b/libbutl/path-map.mxx
@@ -126,39 +126,10 @@ LIBBUTL_MODEXPORT namespace butl
   // Note that the delimiter character is not used (is_delimiter() from
   // path_traits is used instead).
   //
-  template <typename P, typename T>
-  struct path_map_impl: prefix_map<P, T, P::traits::directory_separator>
-  {
-    using base = prefix_map<P, T, P::traits::directory_separator>;
-    using base::base;
-
-    using iterator = typename base::iterator;
-    using const_iterator = typename base::const_iterator;
-
-    // Find the most qualified entry that is a superpath of this path.
-    //
-    iterator
-    find_sup (const P& p)
-    {
-      // Get the greatest less than, if any. We might still not be a sub. Note
-      // also that we still have to check the last element if upper_bound()
-      // returned end().
-      //
-      auto i (this->upper_bound (p));
-      return i == this->begin () || !p.sub ((--i)->first) ? this->end () : i;
-    }
-
-    const_iterator
-    find_sup (const P& p) const
-    {
-      auto i (this->upper_bound (p));
-      return i == this->begin () || !p.sub ((--i)->first) ? this->end () : i;
-    }
-  };
-
   template <typename T>
-  using path_map = path_map_impl<path, T>;
+  using path_map = prefix_map<path, T, path::traits::directory_separator>;
 
   template <typename T>
-  using dir_path_map = path_map_impl<dir_path, T>;
+  using dir_path_map =
+    prefix_map<dir_path, T, dir_path::traits::directory_separator>;
 }
diff --git a/libbutl/prefix-map.mxx b/libbutl/prefix-map.mxx
index 95a4f3b..882f46e 100644
--- a/libbutl/prefix-map.mxx
+++ b/libbutl/prefix-map.mxx
@@ -28,18 +28,18 @@ import std.core;
 
 LIBBUTL_MODEXPORT namespace butl
 {
-  // A map of hierarchical "paths", e.g., 'foo.bar' or 'foo/bar' with
-  // the ability to retrieve a range of entries that have a specific
-  // prefix. The '.' and '/' above are the delimiter characters.
+  // A map of hierarchical "paths", e.g., 'foo.bar' or 'foo/bar' with the
+  // ability to retrieve a range of entries that have a specific prefix as
+  // well as finding the most qualified entry for specific path. The '.' and
+  // '/' above are the delimiter characters.
   //
-  // Note that as a special rule, the default implementation of
-  // compare_prefix treats empty key as everyone's prefix even if
-  // the paths don't start with the delimiter (useful to represent
-  // a "root path").
+  // Note that as a special rule, the default implementation of compare_prefix
+  // treats empty key as everyone's prefix even if the paths don't start with
+  // the delimiter (useful to represent a "root path").
   //
-  // Implementation-wise, the idea is to pretend that each key ends
-  // with the delimiter. This way we automatically avoid matching
-  // 'foobar' as having a prefix 'foo'.
+  // Implementation-wise, the idea is to pretend that each key ends with the
+  // delimiter. This way we automatically avoid matching 'foobar' as having a
+  // prefix 'foo'.
   //
   template <typename K>
   struct compare_prefix;
@@ -120,11 +120,22 @@ LIBBUTL_MODEXPORT namespace butl
     prefix_map_common (std::initializer_list<value_type> i, delimiter_type d)
         : map_type (std::move (i), compare_type (d)) {}
 
+    // Find all the entries that are sub-prefixes of the specified prefix.
+    //
     std::pair<iterator, iterator>
-    find_prefix (const key_type&);
+    find_sub (const key_type&);
 
     std::pair<const_iterator, const_iterator>
-    find_prefix (const key_type&) const;
+    find_sub (const key_type&) const;
+
+    // Find the most qualified entry that is a super-prefix of the specified
+    // prefix.
+    //
+    iterator
+    find_sup (const key_type&);
+
+    const_iterator
+    find_sup (const key_type&) 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 efcee88..fb50570 100644
--- a/libbutl/prefix-map.txx
+++ b/libbutl/prefix-map.txx
@@ -6,14 +6,16 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
 {
   template <typename M>
   auto prefix_map_common<M>::
-  find_prefix (const key_type& k) -> std::pair<iterator, iterator>
+  find_sub (const key_type& k) -> std::pair<iterator, iterator>
   {
+    const auto& c (this->key_comp ());
+
     std::pair<iterator, iterator> r;
     r.first = this->lower_bound (k);
 
     for (r.second = r.first; r.second != this->end (); ++r.second)
     {
-      if (!this->key_comp ().prefix (k, r.second->first))
+      if (!c.prefix (k, r.second->first))
         break;
     }
 
@@ -22,18 +24,68 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
 
   template <typename M>
   auto prefix_map_common<M>::
-  find_prefix (const key_type& k) const ->
+  find_sub (const key_type& k) const ->
     std::pair<const_iterator, const_iterator>
   {
+    const auto& c (this->key_comp ());
+
     std::pair<const_iterator, const_iterator> r;
     r.first = this->lower_bound (k);
 
     for (r.second = r.first; r.second != this->end (); ++r.second)
     {
-      if (!this->key_comp ().prefix (k, r.second->first))
+      if (!c.prefix (k, r.second->first))
         break;
     }
 
     return r;
   }
+
+  template <typename M>
+  auto prefix_map_common<M>::
+  find_sup (const key_type& k) -> iterator
+  {
+    // There seems to be only two possible algorithms here:
+    //
+    // 1. Iterate over the key: get progressively outer prefixes and look
+    //    for a match in the map.
+    //
+    // 2. Iterate over entries: get the upper bound for the key and iterate
+    //    backwards looking for a prefix.
+    //
+    // The drawback of the first approach is that we have to create a new key
+    // which will most likely involve a memory allocation (we can probably
+    // limit it to a single allocation by reusing the key).
+    //
+    // The drawback of the second approch is that we may have a lot of entries
+    // between the lower bound and the prefix (in contrast, keys normally only
+    // have a handful of components).
+    //
+    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))
+        return i;
+    }
+
+    return this->end ();
+  }
+
+  template <typename M>
+  auto prefix_map_common<M>::
+  find_sup (const key_type& k) const -> const_iterator
+  {
+    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))
+        return i;
+    }
+
+    return this->end ();
+  }
 }
diff --git a/tests/prefix-map/driver.cxx b/tests/prefix-map/driver.cxx
index 3e165b2..2fb8a99 100644
--- a/tests/prefix-map/driver.cxx
+++ b/tests/prefix-map/driver.cxx
@@ -33,12 +33,12 @@ main ()
     const pm m;
 
     {
-      auto r (m.find_prefix (""));
+      auto r (m.find_sub (""));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo"));
+      auto r (m.find_sub ("foo"));
       assert (r.first == r.second);
     }
   }
@@ -47,33 +47,33 @@ main ()
     pm m {{{"foo", 1}}};
 
     {
-      auto r (m.find_prefix (""));
+      auto r (m.find_sub (""));
       assert (r.first != r.second && r.first->second == 1 &&
               ++r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fo"));
+      auto r (m.find_sub ("fo"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fox"));
+      auto r (m.find_sub ("fox"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fooo"));
+      auto r (m.find_sub ("fooo"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo.bar"));
+      auto r (m.find_sub ("foo.bar"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo"));
+      auto r (m.find_sub ("foo"));
       assert (r.first != r.second && r.first->second == 1 &&
               ++r.first == r.second);
     }
@@ -83,40 +83,40 @@ main ()
     pm m {{{"foo", 1}, {"bar", 2}}};
 
     {
-      auto r (m.find_prefix (""));
+      auto r (m.find_sub (""));
       assert (r.first != r.second && r.first->second == 2 &&
               ++r.first != r.second && r.first->second == 1 &&
               ++r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fo"));
+      auto r (m.find_sub ("fo"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fox"));
+      auto r (m.find_sub ("fox"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fooo"));
+      auto r (m.find_sub ("fooo"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo.bar"));
+      auto r (m.find_sub ("foo.bar"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo"));
+      auto r (m.find_sub ("foo"));
       assert (r.first != r.second && r.first->second == 1 &&
               ++r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("bar"));
+      auto r (m.find_sub ("bar"));
       assert (r.first != r.second && r.first->second == 2 &&
               ++r.first == r.second);
     }
@@ -129,38 +129,76 @@ main ()
        {"xoo", 5}});
 
     {
-      auto r (m.find_prefix ("fo"));
+      auto r (m.find_sub ("fo"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fox"));
+      auto r (m.find_sub ("fox"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("fooo"));
+      auto r (m.find_sub ("fooo"));
       assert (r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo.bar"));
+      auto r (m.find_sub ("foo.bar"));
       assert (r.first != r.second && r.first->second == 4 &&
               ++r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo.fox"));
+      auto r (m.find_sub ("foo.fox"));
       assert (r.first != r.second && r.first->second == 5 &&
               ++r.first == r.second);
     }
 
     {
-      auto r (m.find_prefix ("foo"));
+      auto r (m.find_sub ("foo"));
       assert (r.first != r.second && r.first->second == 2 &&
               ++r.first != r.second && r.first->second == 4 &&
               ++r.first != r.second && r.first->second == 5 &&
               ++r.first == r.second);
     }
   }
+
+  {
+    pm m (
+      {{"foo",         1},
+       {"fooa",        2},
+       {"foo.bar",     3},
+       {"foo.baz.aaa", 4},
+       {"foo.baz.bbb", 5},
+       {"foo.baz.xxx", 6},
+       {"xoo",         7}});
+
+    auto e (m.end ());
+
+    {
+      auto i (m.find_sup ("fox"));
+      assert (i == e);
+    }
+
+    {
+      auto i (m.find_sup ("foo.baz.bbb"));
+      assert (i != e && i->second == 5);
+    }
+
+    {
+      auto i (m.find_sup ("foo.baz.ccc"));
+      assert (i != e && i->second == 1);
+    }
+
+    {
+      auto i (m.find_sup ("foo.baz"));
+      assert (i != e && i->second == 1);
+    }
+
+    {
+      auto i (m.find_sup ("xoo.bar"));
+      assert (i != e && i->second == 7);
+    }
+  }
 }