libstdc++: functional Source File (original) (raw)

30#ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL

31#define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1

33#pragma GCC system_header

37#if __cplusplus >= 201402L

48namespace std _GLIBCXX_VISIBILITY(default)

49{

50_GLIBCXX_BEGIN_NAMESPACE_VERSION

52namespace experimental

53{

54inline namespace fundamentals_v1

55{

59 template<typename _Tp>

63 template<typename _Tp>

66#define __cpp_lib_experimental_boyer_moore_searching 201411

70 template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>

71 class default_searcher

72 {

73 public:

74 default_searcher(_ForwardIterator1 __pat_first,

75 _ForwardIterator1 __pat_last,

76 _BinaryPredicate __pred = _BinaryPredicate())

77 : _M_m(__pat_first, __pat_last, std::move(__pred))

78 { }

80 template<typename _ForwardIterator2>

81 _ForwardIterator2

82 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const

83 {

84 return std::search(__first, __last,

85 std::get<0>(_M_m), std::get<1>(_M_m),

86 std::get<2>(_M_m));

87 }

89 private:

91 };

93 template<typename _Key, typename _Tp, typename _Hash, typename _Pred>

94 struct __boyer_moore_map_base

95 {

96 template<typename _RAIter>

97 __boyer_moore_map_base(_RAIter __pat, size_t __patlen,

98 _Hash&& __hf, _Pred&& __pred)

99 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }

100 {

101 if (__patlen > 0)

102 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)

103 _M_bad_char[__pat[__i]] = __patlen - 1 - __i;

104 }

105

106 using __diff_type = _Tp;

107

108 __diff_type

109 _M_lookup(_Key __key, __diff_type __not_found) const

110 {

111 auto __iter = _M_bad_char.find(__key);

112 if (__iter == _M_bad_char.end())

113 return __not_found;

114 return __iter->second;

115 }

116

117 _Pred

118 _M_pred() const { return _M_bad_char.key_eq(); }

119

120 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;

121 };

122

123 template<typename _Tp, size_t _Len, typename _Pred>

124 struct __boyer_moore_array_base

125 {

126 template<typename _RAIter, typename _Unused>

127 __boyer_moore_array_base(_RAIter __pat, size_t __patlen,

128 _Unused&&, _Pred&& __pred)

129 : _M_bad_char{ std::array<_Tp, _Len>{}, std::move(__pred) }

130 {

131 std::get<0>(_M_bad_char).fill(__patlen);

132 if (__patlen > 0)

133 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)

134 {

135 auto __ch = __pat[__i];

137 auto __uch = static_cast<_UCh>(__ch);

138 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;

139 }

140 }

141

142 using __diff_type = _Tp;

143

144 template<typename _Key>

145 __diff_type

146 _M_lookup(_Key __key, __diff_type __not_found) const

147 {

149 if (__ukey >= _Len)

150 return __not_found;

151 return std::get<0>(_M_bad_char)[__ukey];

152 }

153

154 const _Pred&

155 _M_pred() const { return std::get<1>(_M_bad_char); }

156

158 };

159

160

161

162 template<typename _RAIter, typename _Hash, typename _Pred,

163 typename _Val = typename iterator_traits<_RAIter>::value_type,

164 typename _Diff = typename iterator_traits<_RAIter>::difference_type>

165 using __boyer_moore_base_t

166 = std::__conditional_t<std::__is_byte_like<_Val, _Pred>::value,

167 __boyer_moore_array_base<_Diff, 256, _Pred>,

168 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;

169

170 template<typename _RAIter, typename _Hash

173 class boyer_moore_searcher

174 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>

175 {

176 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;

177 using typename _Base::__diff_type;

178

179 public:

180 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,

181 _Hash __hf = _Hash(),

182 _BinaryPredicate __pred = _BinaryPredicate());

183

184 template<typename _RandomAccessIterator2>

185 _RandomAccessIterator2

186 operator()(_RandomAccessIterator2 __first,

187 _RandomAccessIterator2 __last) const;

188

189 private:

190 bool

191 _M_is_prefix(_RAIter __word, __diff_type __len,

192 __diff_type __pos)

193 {

194 const auto& __pred = this->_M_pred();

195 __diff_type __suffixlen = __len - __pos;

196 for (__diff_type __i = 0; __i < __suffixlen; ++__i)

197 if (!__pred(__word[__i], __word[__pos + __i]))

198 return false;

199 return true;

200 }

201

202 __diff_type

203 _M_suffix_length(_RAIter __word, __diff_type __len,

204 __diff_type __pos)

205 {

206 const auto& __pred = this->_M_pred();

207 __diff_type __i = 0;

208 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])

209 && __i < __pos)

210 {

211 ++__i;

212 }

213 return __i;

214 }

215

216 template<typename _Tp>

217 __diff_type

218 _M_bad_char_shift(_Tp __c) const

219 { return this->_M_lookup(__c, _M_pat_end - _M_pat); }

220

221 _RAIter _M_pat;

222 _RAIter _M_pat_end;

223 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;

224 };

225

226 template<typename _RAIter, typename _Hash

229 class boyer_moore_horspool_searcher

230 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>

231 {

232 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;

233 using typename _Base::__diff_type;

234

235 public:

236 boyer_moore_horspool_searcher(_RAIter __pat,

237 _RAIter __pat_end,

238 _Hash __hf = _Hash(),

239 _BinaryPredicate __pred

240 = _BinaryPredicate())

241 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),

242 _M_pat(__pat), _M_pat_end(__pat_end)

243 { }

244

245 template<typename _RandomAccessIterator2>

246 _RandomAccessIterator2

247 operator()(_RandomAccessIterator2 __first,

248 _RandomAccessIterator2 __last) const

249 {

250 const auto& __pred = this->_M_pred();

251 auto __patlen = _M_pat_end - _M_pat;

252 if (__patlen == 0)

253 return __first;

254 auto __len = __last - __first;

255 while (__len >= __patlen)

256 {

257 for (auto __scan = __patlen - 1;

258 __pred(__first[__scan], _M_pat[__scan]); --__scan)

259 if (__scan == 0)

260 return __first;

261 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);

262 __len -= __shift;

263 __first += __shift;

264 }

265 return __last;

266 }

267

268 private:

269 template<typename _Tp>

270 __diff_type

271 _M_bad_char_shift(_Tp __c) const

272 { return this->_M_lookup(__c, _M_pat_end - _M_pat); }

273

274 _RAIter _M_pat;

275 _RAIter _M_pat_end;

276 };

277

278

279 template<typename _ForwardIterator,

281 inline default_searcher<_ForwardIterator, _BinaryPredicate>

283 _ForwardIterator __pat_last,

284 _BinaryPredicate __pred = _BinaryPredicate())

285 { return { __pat_first, __pat_last, __pred }; }

286

287

288 template<typename _RAIter, typename _Hash

290 typename _BinaryPredicate = equal_to<>>

291 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>

293 _Hash __hf = _Hash(),

294 _BinaryPredicate __pred = _BinaryPredicate())

295 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }

296

297

298 template<typename _RAIter, typename _Hash

300 typename _BinaryPredicate = equal_to<>>

301 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>

303 _Hash __hf = _Hash(),

304 _BinaryPredicate __pred

305 = _BinaryPredicate())

306 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }

307

308 template<typename _RAIter, typename _Hash, typename _BinaryPredicate>

309 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::

310 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,

311 _Hash __hf, _BinaryPredicate __pred)

312 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),

313 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)

314 {

315 auto __patlen = __pat_end - __pat;

316 if (__patlen == 0)

317 return;

318 __diff_type __last_prefix = __patlen - 1;

319 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)

320 {

321 if (_M_is_prefix(__pat, __patlen, __p + 1))

322 __last_prefix = __p + 1;

323 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);

324 }

325 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)

326 {

327 auto __slen = _M_suffix_length(__pat, __patlen, __p);

328 auto __pos = __patlen - 1 - __slen;

329 if (!__pred(__pat[__p - __slen], __pat[__pos]))

330 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;

331 }

332 }

333

334 template<typename _RAIter, typename _Hash, typename _BinaryPredicate>

335 template<typename _RandomAccessIterator2>

336 _RandomAccessIterator2

337 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::

338 operator()(_RandomAccessIterator2 __first,

339 _RandomAccessIterator2 __last) const

340 {

341 auto __patlen = _M_pat_end - _M_pat;

342 if (__patlen == 0)

343 return __first;

344 const auto& __pred = this->_M_pred();

345 __diff_type __i = __patlen - 1;

346 auto __stringlen = __last - __first;

347 while (__i < __stringlen)

348 {

349 __diff_type __j = __patlen - 1;

350 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))

351 {

352 --__i;

353 --__j;

354 }

355 if (__j < 0)

356 return __first + __i + 1;

357 __i += std::max(_M_bad_char_shift(__first[__i]),

358 _M_good_suffix[__j]);

359 }

360 return __last;

361 }

362}

363

364inline namespace fundamentals_v2

365{

366#define __cpp_lib_experimental_not_fn 201406

367

368

369 template<typename _Fn>

370 inline auto

373 {

375 }

376}

377}

378

379_GLIBCXX_END_NAMESPACE_VERSION

380}

381

382#endif

383

384#endif

typename make_unsigned< _Tp >::type make_unsigned_t

Alias template for make_unsigned.

constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept

Convert a value to an rvalue.

constexpr const _Tp & max(const _Tp &, const _Tp &)

This does what you think it does.

ISO C++ entities toplevel namespace is std.

auto not_fn(_Fn &&__fn) noexcept(std::is_nothrow_constructible< std::decay_t< _Fn >, _Fn && >::value)

[func.not_fn] Function template not_fn

boyer_moore_horspool_searcher< _RAIter, _Hash, _BinaryPredicate > make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, _Hash __hf=_Hash(), _BinaryPredicate __pred=_BinaryPredicate())

Generator function for boyer_moore_horspool_searcher.

boyer_moore_searcher< _RAIter, _Hash, _BinaryPredicate > make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, _Hash __hf=_Hash(), _BinaryPredicate __pred=_BinaryPredicate())

Generator function for boyer_moore_searcher.

default_searcher< _ForwardIterator, _BinaryPredicate > make_default_searcher(_ForwardIterator __pat_first, _ForwardIterator __pat_last, _BinaryPredicate __pred=_BinaryPredicate())

Generator function for default_searcher.

Trait that identifies a bind expression.

Determines if the given type _Tp is a placeholder in a bind() expression and, if so,...

Primary class template hash.

Primary class template, tuple.

One of the comparison functors.