SDSL 3.0.1
Succinct Data Structure Library
wt_algorithm.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
4#ifndef INCLUDED_SDSL_WT_ALGORITHM
5#define INCLUDED_SDSL_WT_ALGORITHM
6
7#include <algorithm>
8#include <utility>
9
10#include <sdsl/wt_helper.hpp>
11
12namespace sdsl
13{
14
15template <typename t_wt>
16struct has_interval_symbols;
17
18template <typename t_wt, bool t_has_interval_symbols>
19struct _interval_symbols_wt;
20
21template <typename, typename T>
22struct has_expand;
23
25
34template <class t_wt>
35std::vector<std::pair<typename t_wt::value_type, typename t_wt::size_type>>
36intersect(const t_wt & wt, const std::vector<range_type> & ranges, typename t_wt::size_type t = 0)
37{
38 using std::get;
39 using size_type = typename t_wt::size_type;
40 using value_type = typename t_wt::value_type;
41 using node_type = typename t_wt::node_type;
42 using pnvr_type = std::pair<node_type, range_vec_type>;
43 typedef std::stack<pnvr_type> stack_type;
44
45 static_assert(has_expand<t_wt, std::array<node_type, 2>(const node_type &)>::value,
46 "intersect requires t_wt to have expand(const node_type&)");
47
48 using p_t = std::pair<value_type, size_type>;
49 std::vector<p_t> res;
50
51 auto push_node = [&t](stack_type & s, node_type & child, range_vec_type & child_range) {
52 auto end = std::remove_if(child_range.begin(), child_range.end(), [&](const range_type & x) {
53 return empty(x);
54 });
55 if (end > child_range.begin() + t - 1)
56 {
57 s.emplace(pnvr_type(child, range_vec_type(child_range.begin(), end)));
58 }
59 };
60
61 if (ranges.empty()) return res;
62
63 t = (t == 0) ? ranges.size() : t;
64
65 std::stack<pnvr_type> stack;
66 stack.emplace(pnvr_type(wt.root(), ranges));
67
68 while (!stack.empty())
69 {
70 pnvr_type x = stack.top();
71 stack.pop();
72
73 if (wt.is_leaf(x.first))
74 {
75 const auto & iv = x.second;
76 if (t <= iv.size())
77 {
78 auto freq = std::accumulate(iv.begin(), iv.end(), 0ULL, [](size_type acc, const range_type & r) {
79 return acc + (r[1] - r[0] + 1);
80 });
81 res.emplace_back(wt.sym(x.first), freq);
82 }
83 }
84 else
85 {
86 auto child = wt.expand(x.first);
87 auto child_ranges = wt.expand(x.first, x.second);
88
89 push_node(stack, get<1>(child), get<1>(child_ranges));
90 push_node(stack, get<0>(child), get<0>(child_ranges));
91 }
92 }
93 return res;
94}
95
97
102template <class t_wt>
103std::pair<typename t_wt::value_type, typename t_wt::size_type> quantile_freq(const t_wt & wt,
104 typename t_wt::size_type lb,
105 typename t_wt::size_type rb,
106 typename t_wt::size_type q)
107{
108 static_assert(t_wt::lex_ordered, "quantile_freq requires a lex_ordered WT");
109 using std::get;
110 using node_type = typename t_wt::node_type;
111 static_assert(has_expand<t_wt, std::array<node_type, 2>(const node_type &)>::value,
112 "quantile_freq requires t_wt to have expand(const node_type&)");
113
114 node_type v = wt.root();
115 range_type r{ { lb, rb } };
116
117 while (!wt.is_leaf(v))
118 {
119 auto child = wt.expand(v);
120 auto child_ranges = wt.expand(v, r);
121 auto num_zeros = size(get<0>(child_ranges));
122
123 if (q >= num_zeros)
124 {
125 q -= num_zeros;
126 v = get<1>(child);
127 r = get<1>(child_ranges);
128 }
129 else
130 {
131 v = get<0>(child);
132 r = get<0>(child_ranges);
133 }
134 }
135 return { wt.sym(v), size(r) };
136}
137
138template <class t_wt>
139void _interval_symbols_rec(const t_wt & wt,
140 range_type r,
141 typename t_wt::size_type & k,
142 std::vector<typename t_wt::value_type> & cs,
143 std::vector<typename t_wt::size_type> & rank_c_i,
144 std::vector<typename t_wt::size_type> & rank_c_j,
145 const typename t_wt::node_type & v)
146{
147 using std::get;
148 if (wt.is_leaf(v))
149 {
150 rank_c_i[k] = r[0];
151 rank_c_j[k] = r[1] + 1;
152 cs[k++] = wt.sym(v);
153 }
154 else
155 {
156 auto child = wt.expand(v);
157 auto child_ranges = wt.expand(v, r);
158 if (!empty(get<0>(child_ranges)))
159 {
160 _interval_symbols_rec(wt, get<0>(child_ranges), k, cs, rank_c_i, rank_c_j, get<0>(child));
161 }
162 if (!empty(get<1>(child_ranges)))
163 {
164 _interval_symbols_rec(wt, get<1>(child_ranges), k, cs, rank_c_i, rank_c_j, get<1>(child));
165 }
166 }
167}
168
169template <class t_wt>
170void _interval_symbols(const t_wt & wt,
171 typename t_wt::size_type i,
172 typename t_wt::size_type j,
173 typename t_wt::size_type & k,
174 std::vector<typename t_wt::value_type> & cs,
175 std::vector<typename t_wt::size_type> & rank_c_i,
176 std::vector<typename t_wt::size_type> & rank_c_j)
177{
178
179 assert(i <= j and j <= wt.size());
180 k = 0;
181 if ((i + 1) == j)
182 {
183 auto res = wt.inverse_select(i);
184 cs[0] = res.second;
185 rank_c_i[0] = res.first;
186 rank_c_j[0] = res.first + 1;
187 k = 1;
188 return;
189 }
190 else if (j > i)
191 {
192 _interval_symbols_rec(wt, range_type{ { i, j - 1 } }, k, cs, rank_c_i, rank_c_j, wt.root());
193 }
194}
195
197
217template <class t_wt>
218void interval_symbols(const t_wt & wt,
219 typename t_wt::size_type i,
220 typename t_wt::size_type j,
221 typename t_wt::size_type & k,
222 std::vector<typename t_wt::value_type> & cs,
223 std::vector<typename t_wt::size_type> & rank_c_i,
224 std::vector<typename t_wt::size_type> & rank_c_j)
225{
226 // check if wt has a built-in interval_symbols method
227 constexpr bool has_own = has_interval_symbols<t_wt>::value;
228 if (has_own)
229 { // if yes, call it
230 _interval_symbols_wt<t_wt, has_own>::call(wt, i, j, k, cs, rank_c_i, rank_c_j);
231 }
232 else
233 { // otherwise use generic implementation based on expand
234 _interval_symbols(wt, i, j, k, cs, rank_c_i, rank_c_j);
235 }
236}
237
238// has_interval_symbols<X>::value is true if class X has
239// implement method interval_symbols
240// Adapted solution from jrok's proposal:
241// http://stackoverflow.com/questions/87372/check-if-a-class-has-a-member-function-of-a-given-signature
242template <typename t_wt>
244{
245 template <typename T>
246 static constexpr auto
247 check(T *) -> typename std::is_same<decltype(std::declval<T>().interval_symbols(std::declval<typename T::size_type>(),
248 std::declval<typename T::size_type>(),
249 std::declval<typename T::size_type &>(),
250 std::declval<std::vector<typename T::value_type> &>(),
251 std::declval<std::vector<typename T::size_type> &>(),
252 std::declval<std::vector<typename T::size_type> &>())),
253 void>::type
254 {
255 return std::true_type();
256 }
257 template <typename>
258 static constexpr std::false_type check(...)
259 {
260 return std::false_type();
261 }
262 typedef decltype(check<t_wt>(nullptr)) type;
263 static constexpr bool value = type::value;
264};
265
266template <typename t_wt, bool t_has_interval_symbols>
268{
269 typedef typename t_wt::size_type size_type;
270 typedef typename t_wt::value_type value_type;
271
272 static void call(const t_wt & wt,
273 size_type i,
274 size_type j,
275 size_type & k,
276 std::vector<value_type> & cs,
277 std::vector<size_type> & rank_c_i,
278 std::vector<size_type> & rank_c_j)
279 {
280 wt.interval_symbols(i, j, k, cs, rank_c_i, rank_c_j);
281 }
282};
283
284template <typename t_wt>
285struct _interval_symbols_wt<t_wt, false>
286{
287 typedef typename t_wt::size_type size_type;
288 typedef typename t_wt::value_type value_type;
289
290 static void call(const t_wt &,
291 size_type,
292 size_type,
293 size_type &,
294 std::vector<value_type> &,
295 std::vector<size_type> &,
296 std::vector<size_type> &)
297 {}
298};
299
300template <typename, typename T>
302{
303 static_assert(std::integral_constant<T, false>::value, "Second template parameter needs to be of function type.");
304};
305
306template <typename t_wt, typename t_ret, typename... t_args>
307struct has_expand<t_wt, t_ret(t_args...)>
308{
309 template <typename T>
310 static constexpr auto
311 check(T *) -> typename std::is_same<decltype(std::declval<T>().expand(std::declval<t_args>()...)), t_ret>::type
312 {
313 return std::true_type();
314 }
315 template <typename>
316 static constexpr std::false_type check(...)
317 {
318 return std::false_type();
319 }
320 typedef decltype(check<t_wt>(nullptr)) type;
321 static constexpr bool value = type::value;
322};
323
324template <typename t_wt>
326{
327 template <typename T>
328 static constexpr auto
329 check(T *) -> typename std::is_same<decltype(std::declval<T>().range_search_2d( //
330 std::declval<typename T::size_type>(),
331 std::declval<typename T::size_type>(),
332 std::declval<typename T::value_type>(),
333 std::declval<typename T::value_type>(),
334 false)),
335 std::pair<typename T::size_type,
336 std::vector<std::pair<typename T::value_type,
337 typename T::size_type>>>>::type
338 {
339 return std::true_type();
340 }
341
342 template <typename>
343 static constexpr std::false_type check(...)
344 {
345 return std::false_type();
346 }
347 typedef decltype(check<t_wt>(nullptr)) type;
348 static constexpr bool value = type::value;
349};
350
352
357template <class t_wt>
358std::pair<bool, typename t_wt::value_type> _symbol_lte(const t_wt & wt, typename t_wt::value_type c)
359{
360 if (((1ULL) << (wt.max_level)) <= c)
361 {
362 // c is greater than any symbol in wt. return the largest symbol!
363 c = sdsl::bits::lo_set[wt.max_level];
364 }
365 auto node = wt.root();
366 auto predecessor_subtree = node;
367 uint64_t mask = (1ULL) << (wt.max_level - 1);
368 while (!wt.is_leaf(node))
369 {
370 auto children = wt.expand(node);
371 auto left_child = std::get<0>(children);
372 auto right_child = std::get<1>(children);
373 if (c & (mask >> node.level))
374 { // go right
375 if (right_child.size)
376 {
377 node = right_child;
378 if (left_child.size)
379 { // potential predecessor subtree?
380 predecessor_subtree = left_child;
381 }
382 }
383 else
384 { // dead end
385 // left child can't be empty if left child is
386 node = left_child;
388 }
389 }
390 else
391 { // go left
392 if (left_child.size) { node = left_child; }
393 else
394 { // dead end
395 if (predecessor_subtree == wt.root())
396 {
397 // there is no valid predecessor. symbol must be
398 // smaller than the smallest symbol in the wt.
399 return { false, 0 };
400 }
401 node = predecessor_subtree;
403 }
404 }
405 }
406 return { true, node.sym };
407}
408
410
415template <class t_wt>
416std::pair<bool, typename t_wt::value_type> _symbol_gte(const t_wt & wt, typename t_wt::value_type c)
417{
418 if (((1ULL) << (wt.max_level)) <= c)
419 {
420 // c is greater than any symbol in wt
421 return { false, 0 };
422 }
423 auto node = wt.root();
424 auto successor_subtree = node;
425 uint64_t mask = (1ULL) << (wt.max_level - 1);
426 while (!wt.is_leaf(node))
427 {
428 auto children = wt.expand(node);
429 auto left_child = std::get<0>(children);
430 auto right_child = std::get<1>(children);
431 if (c & (mask >> node.level))
432 { // go right
433 if (right_child.size) { node = right_child; }
434 else
435 { // dead end
436 if (successor_subtree == wt.root())
437 {
438 // there is no valid successor. symbol must be
439 // bigger than the largest symbol in the wt.
440 return { false, 0 };
441 }
442 node = successor_subtree;
443 c = 0;
444 }
445 }
446 else
447 { // go left
448 if (left_child.size)
449 {
450 node = left_child;
451 if (right_child.size)
452 { // potential successor subtree?
453 successor_subtree = right_child;
454 }
455 }
456 else
457 { // dead end
458 // right child can't be empty if left child is
459 node = right_child;
460 c = 0;
461 }
462 }
463 }
464 return { true, node.sym };
465}
466
467template <class t_wt, bool t_has_interval_symbols>
469{
470 typedef typename t_wt::value_type value_type;
471
472 static std::pair<bool, value_type> call_symbol_gte(const t_wt & wt, value_type c) { return wt.symbol_gte(c); }
473
474 static std::pair<bool, value_type> call_symbol_lte(const t_wt & wt, value_type c) { return wt.symbol_lte(c); }
475};
476
477template <class t_wt>
478struct _symbols_calls_wt<t_wt, false>
479{
480 typedef typename t_wt::value_type value_type;
481
482 static std::pair<bool, value_type> call_symbol_gte(const t_wt & wt, value_type c) { return _symbol_gte(wt, c); }
483
484 static std::pair<bool, value_type> call_symbol_lte(const t_wt & wt, value_type c) { return _symbol_lte(wt, c); }
485};
486
487template <typename t_wt>
489{
490 template <typename T>
491 static constexpr auto
492 check(T *) -> typename std::is_same<decltype(std::declval<T>().symbol_gte(std::declval<typename T::value_type>())),
493 std::pair<bool, typename T::value_type>>::type
494 {
495 return std::true_type();
496 }
497
498 template <typename>
499 static constexpr std::false_type check(...)
500 {
501 return std::false_type();
502 }
503 typedef decltype(check<t_wt>(nullptr)) type;
504 static constexpr bool value = type::value;
505};
506
508
513template <class t_wt>
514std::pair<bool, typename t_wt::value_type> symbol_lte(const t_wt & wt, typename t_wt::value_type c)
515{
516 static_assert(t_wt::lex_ordered, "symbols_lte requires a lex_ordered WT");
517 // check if wt has a built-in interval_symbols method
518 constexpr bool has_own = has_symbols_wt<t_wt>::value;
520}
521
523
528template <class t_wt>
529std::pair<bool, typename t_wt::value_type> symbol_gte(const t_wt & wt, typename t_wt::value_type c)
530{
531 static_assert(t_wt::lex_ordered, "symbols_gte requires a lex_ordered WT");
532 // check if wt has a built-in interval_symbols method
533 constexpr bool has_own = has_symbols_wt<t_wt>::value;
535}
536
539
545template <class t_wt>
546std::vector<typename t_wt::value_type> restricted_unique_range_values(const t_wt & wt,
547 typename t_wt::size_type x_i,
548 typename t_wt::size_type x_j,
549 typename t_wt::value_type y_i,
550 typename t_wt::value_type y_j)
551{
552 static_assert(t_wt::lex_ordered, "restricted_unique_range_values requires a lex_ordered WT");
553
554 std::vector<typename t_wt::value_type> unique_values;
555
556 // make sure things are within bounds
557 if (x_j > wt.size() - 1) x_j = wt.size() - 1;
558 if ((x_i > x_j) || (y_i > y_j)) { return unique_values; }
559 auto lower_y_bound = symbol_gte(wt, y_i);
560 auto upper_y_bound = symbol_lte(wt, y_j);
561 // is the y range valid?
562 if (!lower_y_bound.first || !upper_y_bound.first || (lower_y_bound.second > upper_y_bound.second))
563 {
564 return unique_values;
565 }
566
567 auto lower_y_bound_path = wt.path(lower_y_bound.second);
568 auto upper_y_bound_path = wt.path(upper_y_bound.second);
569
570 auto compare_path = [](uint64_t node_path,
571 uint64_t node_path_len,
572 std::pair<uint64_t, uint64_t> bound_path) -> int {
573 auto bound_path_len = bound_path.first;
574 auto bound_path_val = bound_path.second;
575 /* align to same length */
576 if (bound_path_len > node_path_len) bound_path_val = bound_path_val >> (bound_path_len - node_path_len);
577 if (bound_path_len < node_path_len) bound_path_val = bound_path_val << (node_path_len - bound_path_len);
578 /* cmp */
579 if (node_path < bound_path_val) return -1;
580 if (node_path > bound_path_val) return 1;
581 return 0;
582 };
583
584 std::stack<std::tuple<typename t_wt::node_type, sdsl::range_type, uint64_t, uint64_t>> stack;
585 sdsl::range_type initial_range = { { x_i, x_j } };
586 stack.emplace(wt.root(), initial_range, 0, 0);
587 while (!stack.empty())
588 {
589 auto node_data = stack.top();
590 stack.pop();
591 auto node = std::get<0>(node_data);
592 auto range = std::get<1>(node_data);
593 auto node_path = std::get<2>(node_data);
594 auto node_level = std::get<3>(node_data);
595 if (wt.is_leaf(node)) { unique_values.emplace_back(wt.sym(node)); }
596 else
597 {
598 auto children = wt.expand(node);
599 auto left_path = node_path << 1ULL;
600 auto right_path = (node_path << 1ULL) | 1ULL;
601 auto child_ranges = wt.expand(node, range);
602 if (compare_path(right_path, node_level + 1, upper_y_bound_path) < 1)
603 {
604 auto right_child = std::get<1>(children);
605 auto right_range = std::get<1>(child_ranges);
606 if (!sdsl::empty(right_range)) stack.emplace(right_child, right_range, right_path, node_level + 1);
607 }
608 if (compare_path(left_path, node_level + 1, lower_y_bound_path) > -1)
609 {
610 auto left_child = std::get<0>(children);
611 auto left_range = std::get<0>(child_ranges);
612 if (!sdsl::empty(left_range)) stack.emplace(left_child, left_range, left_path, node_level + 1);
613 }
614 }
615 }
616
617 return unique_values;
618}
619
620// Check for node_type of wavelet_tree
621// http://stackoverflow.com/questions/7834226/detecting-typedef-at-compile-time-template-metaprogramming
622// + trick to make it work for VC++
623// https://connect.microsoft.com/VisualStudio/feedback/details/790269/compile-error-with-explicitly-specified-template-arguments
624template <typename T>
625struct void_
626{
627 typedef void type;
628};
629
630template <typename t_wt, typename T = void>
632{
633 typedef std::false_type t_expr;
634 enum
635 {
636 value = t_expr::value
637 };
638};
639
640template <typename t_wt>
641struct has_node_type<t_wt, typename void_<typename t_wt::node_type>::type>
642{
643 typedef std::true_type t_expr;
644 enum
645 {
646 value = t_expr::value
647 };
648};
649
650} // namespace sdsl
651
652#endif
int_vector ::size_type size_type
Namespace for the succinct data structure library.
std::pair< bool, typename t_wt::value_type > _symbol_lte(const t_wt &wt, typename t_wt::value_type c)
Returns for a symbol c the previous smaller or equal symbol in the WT.
void interval_symbols(const t_wt &wt, typename t_wt::size_type i, typename t_wt::size_type j, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j)
For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).
std::pair< bool, typename t_wt::value_type > symbol_lte(const t_wt &wt, typename t_wt::value_type c)
Returns for a symbol c the previous smaller or equal symbol in the WT.
std::vector< std::pair< typename t_wt::value_type, typename t_wt::size_type > > intersect(const t_wt &wt, const std::vector< range_type > &ranges, typename t_wt::size_type t=0)
Intersection of elements in WT[s_0,e_0], WT[s_1,e_1],...,WT[s_k,e_k].
std::pair< bool, typename t_wt::value_type > symbol_gte(const t_wt &wt, typename t_wt::value_type c)
Returns for a symbol c the next larger or equal symbol in the WT.
void _interval_symbols(const t_wt &wt, typename t_wt::size_type i, typename t_wt::size_type j, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j)
bool empty(const range_type &r)
Empty range check.
Definition: wt_helper.hpp:782
std::pair< typename t_wt::value_type, typename t_wt::size_type > quantile_freq(const t_wt &wt, typename t_wt::size_type lb, typename t_wt::size_type rb, typename t_wt::size_type q)
Returns the q-th smallest element and its frequency in wt[lb..rb].
std::array< int_vector<>::size_type, 2 > range_type
Definition: wt_helper.hpp:20
std::vector< typename t_wt::value_type > restricted_unique_range_values(const t_wt &wt, typename t_wt::size_type x_i, typename t_wt::size_type x_j, typename t_wt::value_type y_i, typename t_wt::value_type y_j)
Returns for a x range [x_i,x_j] and a value range [y_i,y_j] all unique y values occuring in [x_i,...
void _interval_symbols_rec(const t_wt &wt, range_type r, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j, const typename t_wt::node_type &v)
std::pair< bool, typename t_wt::value_type > _symbol_gte(const t_wt &wt, typename t_wt::value_type c)
Returns for a symbol c the next larger or equal symbol in the WT.
std::vector< range_type > range_vec_type
Definition: wt_helper.hpp:21
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
static void call(const t_wt &, size_type, size_type, size_type &, std::vector< value_type > &, std::vector< size_type > &, std::vector< size_type > &)
t_wt::value_type value_type
static void call(const t_wt &wt, size_type i, size_type j, size_type &k, std::vector< value_type > &cs, std::vector< size_type > &rank_c_i, std::vector< size_type > &rank_c_j)
static std::pair< bool, value_type > call_symbol_lte(const t_wt &wt, value_type c)
static std::pair< bool, value_type > call_symbol_gte(const t_wt &wt, value_type c)
t_wt::value_type value_type
static std::pair< bool, value_type > call_symbol_lte(const t_wt &wt, value_type c)
static std::pair< bool, value_type > call_symbol_gte(const t_wt &wt, value_type c)
static constexpr uint64_t all_set
64bit mask with all bits set to 1.
Definition: bits.hpp:49
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition: bits.hpp:187
static constexpr std::false_type check(...)
static constexpr auto check(T *) -> typename std::is_same< decltype(std::declval< T >().expand(std::declval< t_args >()...)), t_ret >::type
decltype(check< t_wt >(nullptr)) type
static constexpr bool value
static constexpr std::false_type check(...)
decltype(check< t_wt >(nullptr)) type
static constexpr auto check(T *) -> typename std::is_same< decltype(std::declval< T >().interval_symbols(std::declval< typename T::size_type >(), std::declval< typename T::size_type >(), std::declval< typename T::size_type & >(), std::declval< std::vector< typename T::value_type > & >(), std::declval< std::vector< typename T::size_type > & >(), std::declval< std::vector< typename T::size_type > & >())), void >::type
std::false_type t_expr
static constexpr bool value
static constexpr std::false_type check(...)
static constexpr auto check(T *) -> typename std::is_same< decltype(std::declval< T >().range_search_2d(std::declval< typename T::size_type >(), std::declval< typename T::size_type >(), std::declval< typename T::value_type >(), std::declval< typename T::value_type >(), false)), std::pair< typename T::size_type, std::vector< std::pair< typename T::value_type, typename T::size_type > > > >::type
decltype(check< t_wt >(nullptr)) type
static constexpr bool value
static constexpr std::false_type check(...)
decltype(check< t_wt >(nullptr)) type
static constexpr auto check(T *) -> typename std::is_same< decltype(std::declval< T >().symbol_gte(std::declval< typename T::value_type >())), std::pair< bool, typename T::value_type > >::type