From e3bf8b04654d4131be6ea4be670e66827b489d2e Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 18 Jan 2018 11:39:56 +0200 Subject: Move find_sup() from path_map to prefix_map and fix --- libbutl/path-map.mxx | 35 ++------------------ libbutl/prefix-map.mxx | 35 +++++++++++++------- libbutl/prefix-map.txx | 60 +++++++++++++++++++++++++++++++--- tests/prefix-map/driver.cxx | 80 +++++++++++++++++++++++++++++++++------------ 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 - struct path_map_impl: prefix_map - { - using base = prefix_map; - 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 - using path_map = path_map_impl; + using path_map = prefix_map; template - using dir_path_map = path_map_impl; + using dir_path_map = + prefix_map; } 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 struct compare_prefix; @@ -120,11 +120,22 @@ LIBBUTL_MODEXPORT namespace butl prefix_map_common (std::initializer_list 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 - find_prefix (const key_type&); + find_sub (const key_type&); std::pair - 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 ::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 auto prefix_map_common:: - find_prefix (const key_type& k) -> std::pair + find_sub (const key_type& k) -> std::pair { + const auto& c (this->key_comp ()); + std::pair 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 auto prefix_map_common:: - find_prefix (const key_type& k) const -> + find_sub (const key_type& k) const -> std::pair { + const auto& c (this->key_comp ()); + std::pair 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 + auto prefix_map_common:: + 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 + auto prefix_map_common:: + 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); + } + } } -- cgit v1.1