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
141
142
143
144
145
146
147
|
// 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 <map>
#include <string>
#include <utility> // move()
#include <algorithm> // min()
namespace build
{
template <typename K>
struct compare_prefix;
template <typename C>
struct compare_prefix<std::basic_string<C>>
{
typedef std::basic_string<C> 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 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:
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.
//
// 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 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::char_type char_type;
typedef typename map_type::iterator iterator;
typedef typename map_type::const_iterator const_iterator;
explicit
prefix_map_common (char_type delimiter)
: map_type (compare_type (delimiter)) {}
prefix_map_common (std::initializer_list<value_type> init,
char_type delimiter)
: map_type (std::move (init), compare_type (delimiter)) {}
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>::char_type D = 0>
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> init)
: prefix_map_common<M> (std::move (init), D) {}
};
template <typename M>
struct prefix_map_impl<M, 0>: prefix_map_common<M>
{
using prefix_map_common<M>::prefix_map_common;
};
template <typename K,
typename T,
typename compare_prefix<K>::char_type D = 0>
using prefix_map = prefix_map_impl<std::map<K, T, compare_prefix<K>>, D>;
template <typename K,
typename T,
typename compare_prefix<K>::char_type D = 0>
using prefix_multimap =
prefix_map_impl<std::multimap<K, T, compare_prefix<K>>, D>;
}
#include <build/prefix-map.txx>
#endif // BUILD_PREFIX_MAP
|
