1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
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
|
