OXYGENHUB
◆ main openmsx / src / utils / StringReplacer.hh
4.1 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
#ifndef STRING_REPLACER_HH
2 
#define STRING_REPLACER_HH
3
4 
// First create a 'replacer' by passing a list of replacement-pairs
5 
// (creation can fully be evaluated at-compile-time):
6 
//     static constexpr auto replacer = StringReplacer::create(
7 
//         "original", "replacement",
8 
//         ...
9 
//         "some string", "another string");
10 
// Then use it to replace strings:
11 
//     assert(replacer("original") == "replacement");    // enumerate strings are replaced
12 
//     assert(replacer("not-in-list") == "not-in-list"); // not-enumerated strings are left unchanged
13 
//
14 
// So this is equivalent to
15 
//     string_view input = ...
16 
//     if      (input == "original"  ) input = "replacement";
17 
//     ...
18 
//     else if (input == "some string) input = "another string";
19 
//     else // leave 'input' unchanged
20 
// Though (for a long list of replacement-pairs) this utility may run faster
21 
// than a manual chain of comparisons. This is because internally uses
22 
// perfect-hashing to speed up the string comparisons.
23 
//
24 
// Note: the return type of StringReplacer::create() is intentionally
25 
// unspecified (and it can indeed be different for different inputs).
26
27 
#include "MinimalPerfectHash.hh"
28
29 
#include "narrow.hh"
30
31 
#include <array>
32 
#include <cassert>
33 
#include <string_view>
34 
#include <tuple>
35 
#include <utility>
36
37 
namespace StringReplacer {
38 
namespace detail {
39
40 
[[nodiscard]] constexpr unsigned fnvHash(std::string_view s)
41 
{
42 
	constexpr unsigned PRIME = 0x811C9DC5;
43 
	auto hash = narrow<unsigned>(s.size());
44 
	for (char c : s) {
45 
		hash *= PRIME;
46 
		hash ^= c;
47 
	}
48 
	return hash;
49 
}
50
51
52 
[[nodiscard]] constexpr auto create_simple_replacer()
53 
{
54 
	return [](std::string_view s) { return s; };
55 
}
56
57 
[[nodiscard]] constexpr auto create_simple_replacer(
58 
    std::string_view from1, std::string_view to1)
59 
{
60 
	return [=](std::string_view s) {
61 
		if (s == from1) return to1;
62 
		return s;
63 
	};
64 
}
65
66 
[[nodiscard]] constexpr auto create_simple_replacer(
67 
	std::string_view from1, std::string_view to1,
68 
	std::string_view from2, std::string_view to2)
69 
{
70 
	return [=](std::string_view s) {
71 
		if (s == from1) return to1;
72 
		if (s == from2) return to2;
73 
		return s;
74 
	};
75 
}
76
77 
[[nodiscard]] constexpr auto create_simple_replacer(
78 
	std::string_view from1, std::string_view to1,
79 
	std::string_view from2, std::string_view to2,
80 
	std::string_view from3, std::string_view to3)
81 
{
82 
	return [=](std::string_view s) {
83 
		if (s == from1) return to1;
84 
		if (s == from2) return to2;
85 
		if (s == from3) return to3;
86 
		return s;
87 
	};
88 
}
89
90 
[[nodiscard]] constexpr auto create_simple_replacer(
91 
	std::string_view from1, std::string_view to1,
92 
	std::string_view from2, std::string_view to2,
93 
	std::string_view from3, std::string_view to3,
94 
	std::string_view from4, std::string_view to4)
95 
{
96 
	return [=](std::string_view s) {
97 
		if (s == from1) return to1;
98 
		if (s == from2) return to2;
99 
		if (s == from3) return to3;
100 
		if (s == from4) return to4;
101 
		return s;
102 
	};
103 
}
104
105 
struct FromTo {
106 
	std::string_view from;
107 
	std::string_view to;
108 
};
109
110 
template<size_t N, typename PMH>
111 
struct PmhReplacer {
112 
	std::array<FromTo, N> map;
113 
	PMH pmh;
114
115 
	[[nodiscard]] constexpr std::string_view operator()(std::string_view input) const
116 
	{
117 
		auto idx = pmh.lookupIndex(input);
118 
		assert(idx < map.size());
119
120 
		if (map[idx].from == input) {
121 
			return map[idx].to;
122 
		}
123 
		return input;
124 
	}
125 
};
126
127 
template<typename Tuple, size_t... Is>
128 
[[nodiscard]] constexpr auto create_pmh_replacer(const Tuple& tuple, std::index_sequence<Is...>)
129 
{
130 
	constexpr size_t N = sizeof...(Is);
131 
	std::array<FromTo, N> arr{FromTo{std::get<2 * Is>(tuple), std::get<2 * Is + 1>(tuple)}...};
132
133 
	auto hash = [](std::string_view s) { return fnvHash(s); };
134 
	auto getKey = [&](size_t i) { return arr[i].from; };
135 
	auto pmh = PerfectMinimalHash::create<N>(hash, getKey);
136
137 
	return PmhReplacer<N, decltype(pmh)>{arr, pmh};
138 
}
139
140 
} // namespace detail
141
142 
template<typename ...Args>
143 
[[nodiscard]] constexpr auto create(Args ...args)
144 
{
145 
	constexpr size_t N2 = sizeof...(args);
146 
	static_assert((N2 & 1) == 0, "Must pass an even number of strings");
147 
	if constexpr (N2 <= 2 * 4) {
148 
		return detail::create_simple_replacer(args...);
149 
	} else {
150 
		return detail::create_pmh_replacer(std::tuple(args...), std::make_index_sequence<N2 / 2>());
151 
	}
152 
}
153
154 
} // namespace StringReplacer
155
156 
#endif