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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
|
#pragma once
#include "base/buffer_vector.hpp"
#include "std/algorithm.hpp"
#include "std/cstdint.hpp"
#include "std/iterator.hpp"
#include "std/limits.hpp"
#include "std/regex.hpp"
#include "std/sstream.hpp"
#include "std/string.hpp"
#include "3party/utfcpp/source/utf8/unchecked.h"
/// All methods work with strings in utf-8 format
namespace strings
{
typedef uint32_t UniChar;
//typedef buffer_vector<UniChar, 32> UniString;
/// Make new type, not typedef. Need to specialize DebugPrint.
class UniString : public buffer_vector<UniChar, 32>
{
typedef buffer_vector<UniChar, 32> BaseT;
public:
UniString() {}
explicit UniString(size_t n, UniChar c = UniChar()) : BaseT(n, c) {}
template <class IterT> UniString(IterT b, IterT e) : BaseT(b, e) {}
bool IsEqualAscii(char const * s) const;
};
/// Performs full case folding for string to make it search-compatible according
/// to rules in ftp://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt
/// For implementation @see base/lower_case.cpp
void MakeLowerCaseInplace(UniString & s);
UniString MakeLowerCase(UniString const & s);
/// Performs NFKD - Compatibility decomposition for Unicode according
/// to rules in ftp://ftp.unicode.org/Public/UNIDATA/UnicodeData.txt
/// For implementation @see base/normilize_unicode.cpp
void NormalizeInplace(UniString & s);
UniString Normalize(UniString const & s);
/// Replaces "full width" unicode digits with ascii ones.
void NormalizeDigits(string & utf8);
/// Counts number of start symbols in string s (that is not lower and not normalized) that maches
/// to lower and normalized string low_s. If s doen't starts with low_s then returns 0; otherwise
/// returns number of start symbols in s that equivalent to lowStr
/// For implementation @see base/lower_case.cpp
size_t CountNormLowerSymbols(UniString const & s, UniString const & lowStr);
void AsciiToLower(string & s);
// TODO(AlexZ): current boost impl uses default std::locale() to trim.
// In general, it does not work for any unicode whitespace except ASCII U+0020 one.
void Trim(string & s);
/// Remove any characters that contain in "anyOf" on left and right side of string s
void Trim(string & s, char const * anyOf);
void MakeLowerCaseInplace(string & s);
string MakeLowerCase(string const & s);
bool EqualNoCase(string const & s1, string const & s2);
UniString MakeUniString(string const & utf8s);
string ToUtf8(UniString const & s);
bool IsASCIIString(string const & str);
inline string DebugPrint(UniString const & s)
{
return ToUtf8(s);
}
template <typename DelimFuncT, typename UniCharIterT = UniString::const_iterator>
class TokenizeIterator
{
UniCharIterT m_beg, m_end, m_finish;
DelimFuncT m_delimFunc;
void move()
{
m_beg = m_end;
while (m_beg != m_finish)
{
if (m_delimFunc(*m_beg))
++m_beg;
else
break;
}
m_end = m_beg;
while (m_end != m_finish)
{
if (m_delimFunc(*m_end))
break;
else
++m_end;
}
}
public:
/// @warning string S must be not temporary!
TokenizeIterator(string const & s, DelimFuncT const & delimFunc)
: m_beg(s.begin()), m_end(s.begin()), m_finish(s.end()), m_delimFunc(delimFunc)
{
move();
}
/// @warning unistring S must be not temporary!
TokenizeIterator(UniString const & s, DelimFuncT const & delimFunc)
: m_beg(s.begin()), m_end(s.begin()), m_finish(s.end()), m_delimFunc(delimFunc)
{
move();
}
/// Use default-constructed iterator for operator == to determine an end of a token stream.
TokenizeIterator() = default;
/// Explicitly disabled, because we're storing iterators for string
TokenizeIterator(char const *, DelimFuncT const &) = delete;
string operator*() const
{
ASSERT( m_beg != m_finish, ("dereferencing of empty iterator") );
return string(m_beg.base(), m_end.base());
}
operator bool() const { return m_beg != m_finish; }
TokenizeIterator & operator++()
{
move();
return (*this);
}
bool IsLast() const
{
if (!*this)
return false;
TokenizeIterator<DelimFuncT, UniCharIterT> copy(*this);
++copy;
return !copy;
}
UniString GetUniString() const
{
return UniString(m_beg, m_end);
}
/// Same as operator bool() in expression it == end(...)
bool operator==(TokenizeIterator const &) { return !(*this); }
/// Same as operator bool() in expression it != end(...)
bool operator!=(TokenizeIterator const &) { return (*this); }
};
class SimpleDelimiter
{
UniString m_delims;
public:
SimpleDelimiter(char const * delimChars);
// Used in TokenizeIterator to allow past the end iterator construction.
SimpleDelimiter() = default;
/// @return true if c is delimiter
bool operator()(UniChar c) const;
};
typedef TokenizeIterator<SimpleDelimiter,
::utf8::unchecked::iterator<string::const_iterator> > SimpleTokenizer;
template <typename TFunctor>
void Tokenize(string const & str, char const * delims, TFunctor && f)
{
SimpleTokenizer iter(str, delims);
while (iter)
{
f(*iter);
++iter;
}
}
/// @return code of last symbol in string or 0 if s is empty
UniChar LastUniChar(string const & s);
template <class T, size_t N, class TT> bool IsInArray(T (&arr) [N], TT const & t)
{
for (size_t i = 0; i < N; ++i)
if (arr[i] == t)
return true;
return false;
}
/// @name From string to numeric.
//@{
bool to_int(char const * s, int & i, int base = 10);
bool to_uint64(char const * s, uint64_t & i);
bool to_int64(char const * s, int64_t & i);
bool to_double(char const * s, double & d);
inline bool is_number(string const & s) { int64_t dummy; return to_int64(s.c_str(), dummy); }
inline bool to_int(string const & s, int & i, int base = 10) { return to_int(s.c_str(), i, base); }
inline bool to_uint64(string const & s, uint64_t & i) { return to_uint64(s.c_str(), i); }
inline bool to_int64(string const & s, int64_t & i) { return to_int64(s.c_str(), i); }
inline bool to_double(string const & s, double & d) { return to_double(s.c_str(), d); }
//@}
/// @name From numeric to string.
//@{
inline string to_string(string const & s)
{
return s;
}
inline string to_string(char const * s)
{
return s;
}
template <typename T> string to_string(T t)
{
ostringstream ss;
ss << t;
return ss.str();
}
namespace impl
{
template <typename T>
int UpperBoundOnChars()
{
// It's wrong to return just numeric_limits<T>::digits10 + [is
// signed] because digits10 for a type T is computed as:
//
// floor(log10(2 ^ (CHAR_BITS * sizeof(T)))) =
// floor(CHAR_BITS * sizeof(T) * log10(2))
//
// Therefore, due to rounding, we need to compensate possible
// error.
//
// NOTE: following code works only on two-complement systems!
return numeric_limits<T>::digits10 + is_signed<T>::value + 1;
}
template <typename T> char * to_string_digits(char * buf, T i)
{
do
{
--buf;
*buf = static_cast<char>(i % 10) + '0';
i = i / 10;
} while (i != 0);
return buf;
}
template <typename T> string to_string_signed(T i)
{
bool const negative = i < 0;
int const sz = UpperBoundOnChars<T>();
char buf[sz];
char * end = buf + sz;
char * beg = to_string_digits(end, negative ? -i : i);
if (negative)
{
--beg;
*beg = '-';
}
return string(beg, end - beg);
}
template <typename T> string to_string_unsigned(T i)
{
int const sz = UpperBoundOnChars<T>();
char buf[sz];
char * end = buf + sz;
char * beg = to_string_digits(end, i);
return string(beg, end - beg);
}
}
inline string to_string(int64_t i)
{
return impl::to_string_signed(i);
}
inline string to_string(uint64_t i)
{
return impl::to_string_unsigned(i);
}
/// Use this function to get string with fixed count of
/// "Digits after comma".
string to_string_dac(double d, int dac);
//@}
bool StartsWith(UniString const & s, UniString const & p);
bool StartsWith(string const & s1, char const * s2);
bool EndsWith(string const & s1, char const * s2);
bool EndsWith(string const & s1, string const & s2);
/// Try to guess if it's HTML or not. No guarantee.
bool IsHTML(string const & utf8);
/// Compare str1 and str2 and return if they are equal except for mismatchedSymbolsNum symbols
bool AlmostEqual(string const & str1, string const & str2, size_t mismatchedCount);
template <typename TIterator, typename TDelimiter>
typename TIterator::value_type JoinStrings(TIterator begin, TIterator end,
TDelimiter const & delimiter)
{
if (begin == end)
return {};
auto result = *begin++;
for (TIterator it = begin; it != end; ++it)
{
result += delimiter;
result += *it;
}
return result;
}
template <typename TContainer, typename TDelimiter>
typename TContainer::value_type JoinStrings(TContainer const & container,
TDelimiter const & delimiter)
{
return JoinStrings(container.begin(), container.end(), delimiter);
}
template <typename TFn>
void ForEachMatched(string const & s, regex const & regex, TFn && fn)
{
for (sregex_token_iterator cur(s.begin(), s.end(), regex), end; cur != end; ++cur)
fn(*cur);
}
// Computes the minimum number of insertions, deletions and alterations
// of characters needed to transform one string into another.
// The function works in O(length1 * length2) time and memory
// where length1 and length2 are the lengths of the argument strings.
// See https://en.wikipedia.org/wiki/Levenshtein_distance.
// One string is [b1, e1) and the other is [b2, e2). The iterator
// form is chosen to fit both std::string and strings::UniString.
// This function does not normalize either of the strings.
template <typename TIter>
size_t EditDistance(TIter const & b1, TIter const & e1, TIter const & b2, TIter const & e2)
{
size_t const n = distance(b1, e1);
size_t const m = distance(b2, e2);
// |cur| and |prev| are current and previous rows of the
// dynamic programming table.
vector<size_t> prev(m + 1);
vector<size_t> cur(m + 1);
for (size_t j = 0; j <= m; j++)
prev[j] = j;
auto it1 = b1;
// 1-based to avoid corner cases.
for (size_t i = 1; i <= n; ++i, ++it1)
{
cur[0] = i;
auto const & c1 = *it1;
auto it2 = b2;
for (size_t j = 1; j <= m; ++j, ++it2)
{
auto const & c2 = *it2;
cur[j] = min(cur[j - 1], prev[j]) + 1;
cur[j] = min(cur[j], prev[j - 1] + (c1 == c2 ? 0 : 1));
}
prev.swap(cur);
}
return prev[m];
}
} // namespace strings
namespace std
{
template <typename ... Args>
struct iterator_traits<strings::TokenizeIterator<Args...>>
{
using difference_type = std::ptrdiff_t;
using value_type = string;
using pointer = void;
using reference = string;
using iterator_category = std::input_iterator_tag;
};
} // namespace std
|