From c2339b07fb683355c6a6155ec312b1616167614e Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Wed, 14 Jan 2015 11:46:32 +0200 Subject: Implement prefix_map --- build/prefix_map | 119 +++++++++++++++++++++++++++++ build/prefix_map.txx | 42 ++++++++++ tests/build/prefix_map/buildfile | 2 + tests/build/prefix_map/driver.cxx | 156 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 319 insertions(+) create mode 100644 build/prefix_map create mode 100644 build/prefix_map.txx create mode 100644 tests/build/prefix_map/buildfile create mode 100644 tests/build/prefix_map/driver.cxx diff --git a/build/prefix_map b/build/prefix_map new file mode 100644 index 0000000..13388b2 --- /dev/null +++ b/build/prefix_map @@ -0,0 +1,119 @@ +// file : build/prefix_map -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef BUILD_PREFIX_MAP +#define BUILD_PREFIX_MAP + +#include +#include +#include // move() +#include // min() + +namespace build +{ + template + struct compare_prefix; + + template + struct compare_prefix> + { + typedef std::basic_string K; + + typedef C char_type; + typedef typename K::size_type size_type; + typedef typename K::traits_type traits_type; + + explicit + compare_prefix (C d): d_ (d) {} + + bool + operator() (const K& x, const K& y) const + { + return compare (x.c_str (), x.size (), y.c_str (), y.size ()) < 0; + } + + // Note: doesn't check for k.size () being at least p.size (). + // + bool + prefix (const K& p, const K& k) const + { + size_type pn (p.size ()); + return compare ( + p.c_str (), pn, k.c_str (), pn == k.size () ? pn : pn + 1) == 0; + } + + int + compare (const C* x, size_type xn, + const C* y, size_type yn) const + { + size_type n (std::min (xn, yn)); + int r (traits_type::compare (x, y, n)); + + if (r == 0) + { + // Pretend there is the delimiter characters at the end of the + // shorter string. + // + char xc (xn > n ? x[n] : (xn++, d_)); + char yc (yn > n ? y[n] : (yn++, d_)); + r = traits_type::compare (&xc, &yc, 1); + + // If we are still equal, then compare the lengths. + // + if (r == 0) + r = (xn == yn ? 0 : (xn < yn ? -1 : 1)); + } + + return r; + } + + private: + C d_; + }; + + // 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. + // + // 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 prefix_map_impl: M + { + typedef M map_type; + typedef typename map_type::key_type key_type; + typedef typename map_type::value_type value_type; + typedef typename map_type::key_compare compare_type; + + typedef typename map_type::iterator iterator; + typedef typename map_type::const_iterator const_iterator; + + explicit + prefix_map_impl (typename compare_type::char_type delimiter) + : map_type (compare_type (delimiter)) {} + + prefix_map_impl (std::initializer_list init, + typename compare_type::char_type delimiter) + : map_type (std::move (init), compare_type (delimiter)) {} + + std::pair + find (const key_type&); + + std::pair + find (const key_type&) const; + }; + + template + using prefix_map = prefix_map_impl>>; + + template + using prefix_multimap = + prefix_map_impl>>; +} + +#include + +#endif // BUILD_PREFIX_MAP diff --git a/build/prefix_map.txx b/build/prefix_map.txx new file mode 100644 index 0000000..17a8ca0 --- /dev/null +++ b/build/prefix_map.txx @@ -0,0 +1,42 @@ +// file : build/prefix_map.txx -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +namespace build +{ + template + auto prefix_map_impl:: + find (const key_type& k) -> std::pair + { + 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)) + break; + } + + return r; + } + + template + auto prefix_map_impl:: + find (const key_type& k) const -> std::pair + { + 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)) + break; + } + + return r; + } +} diff --git a/tests/build/prefix_map/buildfile b/tests/build/prefix_map/buildfile new file mode 100644 index 0000000..dbef7db --- /dev/null +++ b/tests/build/prefix_map/buildfile @@ -0,0 +1,2 @@ +exe{driver}: obj{driver} +obj{driver}: cxx{driver} diff --git a/tests/build/prefix_map/driver.cxx b/tests/build/prefix_map/driver.cxx new file mode 100644 index 0000000..ba9478c --- /dev/null +++ b/tests/build/prefix_map/driver.cxx @@ -0,0 +1,156 @@ +// file : tests/build/prefix_map/driver.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include +#include +#include + +#include + +using namespace std; +using namespace build; + +int +main () +{ + typedef prefix_map pm; + + { + const pm m ('.'); + + { + auto r (m.find ("")); + assert (r.first == r.second); + } + + { + auto r (m.find ("foo")); + assert (r.first == r.second); + } + } + + { + pm m {{{"foo", 1}}, '.'}; + + { + auto r (m.find ("")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fo")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fox")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fooo")); + assert (r.first == r.second); + } + + { + auto r (m.find ("foo.bar")); + assert (r.first == r.second); + } + + { + auto r (m.find ("foo")); + assert (r.first != r.second && r.first->second == 1 && + ++r.first == r.second); + } + } + + { + pm m {{{"foo", 1}, {"bar", 2}}, '.'}; + + { + auto r (m.find ("")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fo")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fox")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fooo")); + assert (r.first == r.second); + } + + { + auto r (m.find ("foo.bar")); + assert (r.first == r.second); + } + + { + auto r (m.find ("foo")); + assert (r.first != r.second && r.first->second == 1 && + ++r.first == r.second); + } + + { + auto r (m.find ("bar")); + assert (r.first != r.second && r.first->second == 2 && + ++r.first == r.second); + } + } + + { + pm m ( + {{"boo", 1}, + {"foo", 2}, {"fooa", 3}, {"foo.bar", 4}, {"foo.fox", 5}, + {"xoo", 5}}, + '.'); + + { + auto r (m.find ("")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fo")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fox")); + assert (r.first == r.second); + } + + { + auto r (m.find ("fooo")); + assert (r.first == r.second); + } + + { + auto r (m.find ("foo.bar")); + assert (r.first != r.second && r.first->second == 4 && + ++r.first == r.second); + } + + { + auto r (m.find ("foo.fox")); + assert (r.first != r.second && r.first->second == 5 && + ++r.first == r.second); + } + + { + auto r (m.find ("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); + } + } +} -- cgit v1.1