From dc65f9612e9feea1732572e8188d900495349059 Mon Sep 17 00:00:00 2001
From: Boris Kolpackov <boris@codesynthesis.com>
Date: Thu, 18 Jun 2015 12:25:02 +0200
Subject: Move prefix-map from build2 to libbutl

---
 buildfile                   |   2 +-
 butl/prefix-map             | 140 ++++++++++++++++++++++++++++++++++++++++
 butl/prefix-map.txx         |  39 +++++++++++
 tests/buildfile             |   7 ++
 tests/prefix-map/buildfile  |   7 ++
 tests/prefix-map/driver     | Bin 0 -> 199753 bytes
 tests/prefix-map/driver.cxx | 153 ++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 347 insertions(+), 1 deletion(-)
 create mode 100644 butl/prefix-map
 create mode 100644 butl/prefix-map.txx
 create mode 100644 tests/buildfile
 create mode 100644 tests/prefix-map/buildfile
 create mode 100755 tests/prefix-map/driver
 create mode 100644 tests/prefix-map/driver.cxx

diff --git a/buildfile b/buildfile
index 354f9da..3248471 100644
--- a/buildfile
+++ b/buildfile
@@ -2,6 +2,6 @@
 # copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
 # license   : MIT; see accompanying LICENSE file
 
-d = butl/
+d = butl/ tests/
 .: $d
 include $d
diff --git a/butl/prefix-map b/butl/prefix-map
new file mode 100644
index 0000000..188d18f
--- /dev/null
+++ b/butl/prefix-map
@@ -0,0 +1,140 @@
+// file      : butl/prefix-map -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUTL_PREFIX_MAP
+#define BUTL_PREFIX_MAP
+
+#include <map>
+#include <string>
+#include <utility>   // move
+#include <algorithm> // min
+
+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.
+  //
+  // 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'.
+  //
+  template <typename K>
+  struct compare_prefix;
+
+  template <typename C>
+  struct compare_prefix<std::basic_string<C>>
+  {
+    typedef std::basic_string<C> K;
+
+    typedef C delimiter_type;
+    typedef typename K::size_type size_type;
+    typedef typename K::traits_type traits_type;
+
+    explicit
+    compare_prefix (delimiter_type 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 pn == 0 || // Empty key is always a prefix.
+        compare (
+          p.c_str (), pn, k.c_str (), pn == k.size () ? pn : pn + 1) == 0;
+    }
+
+  protected:
+    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:
+    delimiter_type d_;
+  };
+
+  template <typename M>
+  struct prefix_map_common: 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 compare_type::delimiter_type delimiter_type;
+
+    typedef typename map_type::iterator iterator;
+    typedef typename map_type::const_iterator const_iterator;
+
+    explicit
+    prefix_map_common (delimiter_type d)
+        : map_type (compare_type (d)) {}
+
+    prefix_map_common (std::initializer_list<value_type> i, delimiter_type d)
+        : map_type (std::move (i), compare_type (d)) {}
+
+    std::pair<iterator, iterator>
+    find_prefix (const key_type&);
+
+    std::pair<const_iterator, const_iterator>
+    find_prefix (const key_type&) const;
+  };
+
+  template <typename M, typename prefix_map_common<M>::delimiter_type D>
+  struct prefix_map_impl: prefix_map_common<M>
+  {
+    typedef typename prefix_map_common<M>::value_type value_type;
+
+    prefix_map_impl (): prefix_map_common<M> (D) {}
+    prefix_map_impl (std::initializer_list<value_type> i)
+        : prefix_map_common<M> (std::move (i), D) {}
+  };
+
+  template <typename K,
+            typename T,
+            typename compare_prefix<K>::delimiter_type D>
+  using prefix_map = prefix_map_impl<std::map<K, T, compare_prefix<K>>, D>;
+
+  template <typename K,
+            typename T,
+            typename compare_prefix<K>::delimiter_type D>
+  using prefix_multimap =
+    prefix_map_impl<std::multimap<K, T, compare_prefix<K>>, D>;
+}
+
+#include <butl/prefix-map.txx>
+
+#endif // BUTL_PREFIX_MAP
diff --git a/butl/prefix-map.txx b/butl/prefix-map.txx
new file mode 100644
index 0000000..9ead579
--- /dev/null
+++ b/butl/prefix-map.txx
@@ -0,0 +1,39 @@
+// file      : butl/prefix-map.txx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+namespace butl
+{
+  template <typename M>
+  auto prefix_map_common<M>::
+  find_prefix (const key_type& k) -> std::pair<iterator, iterator>
+  {
+    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))
+        break;
+    }
+
+    return r;
+  }
+
+  template <typename M>
+  auto prefix_map_common<M>::
+  find_prefix (const key_type& k) const ->
+    std::pair<const_iterator, const_iterator>
+  {
+    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))
+        break;
+    }
+
+    return r;
+  }
+}
diff --git a/tests/buildfile b/tests/buildfile
new file mode 100644
index 0000000..19d85db
--- /dev/null
+++ b/tests/buildfile
@@ -0,0 +1,7 @@
+# file      : tests/buildfile
+# copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
+# license   : MIT; see accompanying LICENSE file
+
+d = prefix-map/
+.: $d
+include $d
diff --git a/tests/prefix-map/buildfile b/tests/prefix-map/buildfile
new file mode 100644
index 0000000..0fe9664
--- /dev/null
+++ b/tests/prefix-map/buildfile
@@ -0,0 +1,7 @@
+# file      : tests/prefix-map/buildfile
+# copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
+# license   : MIT; see accompanying LICENSE file
+
+exe{driver}: cxx{driver} ../../butl/lib{butl}
+
+include ../../butl/
diff --git a/tests/prefix-map/driver b/tests/prefix-map/driver
new file mode 100755
index 0000000..215146d
Binary files /dev/null and b/tests/prefix-map/driver differ
diff --git a/tests/prefix-map/driver.cxx b/tests/prefix-map/driver.cxx
new file mode 100644
index 0000000..2aa59c7
--- /dev/null
+++ b/tests/prefix-map/driver.cxx
@@ -0,0 +1,153 @@
+// file      : tests/prefix-map/driver.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#include <string>
+#include <cassert>
+#include <iostream>
+
+#include <butl/prefix-map>
+
+using namespace std;
+using namespace butl;
+
+int
+main ()
+{
+  typedef prefix_map<string, int, '.'> pm;
+
+  {
+    const pm m;
+
+    {
+      auto r (m.find_prefix (""));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo"));
+      assert (r.first == r.second);
+    }
+  }
+
+  {
+    pm m {{{"foo", 1}}};
+
+    {
+      auto r (m.find_prefix (""));
+      assert (r.first != r.second && r.first->second == 1 &&
+              ++r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fo"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fox"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fooo"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo.bar"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo"));
+      assert (r.first != r.second && r.first->second == 1 &&
+              ++r.first == r.second);
+    }
+  }
+
+  {
+    pm m {{{"foo", 1}, {"bar", 2}}};
+
+    {
+      auto r (m.find_prefix (""));
+      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"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fox"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fooo"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo.bar"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo"));
+      assert (r.first != r.second && r.first->second == 1 &&
+              ++r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("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_prefix ("fo"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fox"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("fooo"));
+      assert (r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo.bar"));
+      assert (r.first != r.second && r.first->second == 4 &&
+              ++r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("foo.fox"));
+      assert (r.first != r.second && r.first->second == 5 &&
+              ++r.first == r.second);
+    }
+
+    {
+      auto r (m.find_prefix ("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