SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <array>
8#include <assert.h>
9#include <cstdint>
10#include <iterator>
11#include <numeric>
12#include <stack>
13#include <tuple>
14#include <type_traits>
15#include <utility>
16#include <vector>
17
18#include <sdsl/bits.hpp>
19#include <sdsl/wt_helper.hpp>
20
21namespace sdsl
22{
23
24template <typename t_wt>
25struct has_interval_symbols;
26template <typename t_wt, bool t_has_interval_symbols>
27struct _interval_symbols_wt;
28template <typename, typename T>
29struct has_expand;
30
32
41template <class t_wt>
42std::vector<std::pair<typename t_wt::value_type, typename t_wt::size_type>>
43intersect(t_wt const & wt, std::vector<range_type> const & ranges, typename t_wt::size_type t = 0)
44{
45 using std::get;
46 using size_type = typename t_wt::size_type;
47 using value_type = typename t_wt::value_type;
48 using node_type = typename t_wt::node_type;
49 using pnvr_type = std::pair<node_type, range_vec_type>;
50 typedef std::stack<pnvr_type> stack_type;
51
52 static_assert(has_expand<t_wt, std::array<node_type, 2>(node_type const &)>::value,
53 "intersect requires t_wt to have expand(const node_type&)");
54
55 using p_t = std::pair<value_type, size_type>;
56 std::vector<p_t> res;
57
58 auto push_node = [&t](stack_type & s, node_type & child, range_vec_type & child_range)
59 {
60 auto end = std::remove_if(child_range.begin(),
61 child_range.end(),
62 [&](const range_type & x)
63 {
64 return empty(x);
65 });
66 if (end > child_range.begin() + t - 1)
67 {
68 s.emplace(pnvr_type(child, range_vec_type(child_range.begin(), end)));
69 }
70 };
71
72 if (ranges.empty())
73 return res;
74
75 t = (t == 0) ? ranges.size() : t;
76
77 std::stack<pnvr_type> stack;
78 stack.emplace(pnvr_type(wt.root(), ranges));
79
80 while (!stack.empty())
81 {
82 pnvr_type x = stack.top();
83 stack.pop();
84
85 if (wt.is_leaf(x.first))
86 {
87 auto const & iv = x.second;
88 if (t <= iv.size())
89 {
90 auto freq = std::accumulate(iv.begin(),
91 iv.end(),
92 0ULL,
93 [](size_type acc, range_type const & r)
94 {
95 return acc + (r[1] - r[0] + 1);
96 });
97 res.emplace_back(wt.sym(x.first), freq);
98 }
99 }
100 else
101 {
102 auto child = wt.expand(x.first);
103 auto child_ranges = wt.expand(x.first, x.second);
104
105 push_node(stack, get<1>(child), get<1>(child_ranges));
106 push_node(stack, get<0>(child), get<0>(child_ranges));
107 }
108 }
109 return res;
110}
111
113
118template <class t_wt>
119std::pair<typename t_wt::value_type, typename t_wt::size_type>
120quantile_freq(t_wt const & wt, typename t_wt::size_type lb, typename t_wt::size_type rb, typename t_wt::size_type q)
121{
122 static_assert(t_wt::lex_ordered, "quantile_freq requires a lex_ordered WT");
123 using std::get;
124 using node_type = typename t_wt::node_type;
125 static_assert(has_expand<t_wt, std::array<node_type, 2>(node_type const &)>::value,
126 "quantile_freq requires t_wt to have expand(const node_type&)");
127
128 node_type v = wt.root();
129 range_type r{{lb, rb}};
130
131 while (!wt.is_leaf(v))
132 {
133 auto child = wt.expand(v);
134 auto child_ranges = wt.expand(v, r);
135 auto num_zeros = size(get<0>(child_ranges));
136
137 if (q >= num_zeros)
138 {
139 q -= num_zeros;
140 v = get<1>(child);
141 r = get<1>(child_ranges);
142 }
143 else
144 {
145 v = get<0>(child);
146 r = get<0>(child_ranges);
147 }
148 }
149 return {wt.sym(v), size(r)};
150}
151
152template <class t_wt>
153void _interval_symbols_rec(t_wt const & wt,
154 range_type r,
155 typename t_wt::size_type & k,
156 std::vector<typename t_wt::value_type> & cs,
157 std::vector<typename t_wt::size_type> & rank_c_i,
158 std::vector<typename t_wt::size_type> & rank_c_j,
159 const typename t_wt::node_type & v)
160{
161 using std::get;
162 if (wt.is_leaf(v))
163 {
164 rank_c_i[k] = r[0];
165 rank_c_j[k] = r[1] + 1;
166 cs[k++] = wt.sym(v);
167 }
168 else
169 {
170 auto child = wt.expand(v);
171 auto child_ranges = wt.expand(v, r);
172 if (!empty(get<0>(child_ranges)))
173 {
174 _interval_symbols_rec(wt, get<0>(child_ranges), k, cs, rank_c_i, rank_c_j, get<0>(child));
175 }
176 if (!empty(get<1>(child_ranges)))
177 {
178 _interval_symbols_rec(wt, get<1>(child_ranges), k, cs, rank_c_i, rank_c_j, get<1>(child));
179 }
180 }
181}
182
183template <class t_wt>
184void _interval_symbols(t_wt const & wt,
185 typename t_wt::size_type i,
186 typename t_wt::size_type j,
187 typename t_wt::size_type & k,
188 std::vector<typename t_wt::value_type> & cs,
189 std::vector<typename t_wt::size_type> & rank_c_i,
190 std::vector<typename t_wt::size_type> & rank_c_j)
191{
192
193 assert(i <= j and j <= wt.size());
194 k = 0;
195 if ((i + 1) == j)
196 {
197 auto res = wt.inverse_select(i);
198 cs[0] = res.second;
199 rank_c_i[0] = res.first;
200 rank_c_j[0] = res.first + 1;
201 k = 1;
202 return;
203 }
204 else if (j > i)
205 {
206 _interval_symbols_rec(wt, range_type{{i, j - 1}}, k, cs, rank_c_i, rank_c_j, wt.root());
207 }
208}
209
211
231template <class t_wt>
232void interval_symbols(t_wt const & wt,
233 typename t_wt::size_type i,
234 typename t_wt::size_type j,
235 typename t_wt::size_type & k,
236 std::vector<typename t_wt::value_type> & cs,
237 std::vector<typename t_wt::size_type> & rank_c_i,
238 std::vector<typename t_wt::size_type> & rank_c_j)
239{
240 // check if wt has a built-in interval_symbols method
241 constexpr bool has_own = has_interval_symbols<t_wt>::value;
242 if (has_own)
243 { // if yes, call it
244 _interval_symbols_wt<t_wt, has_own>::call(wt, i, j, k, cs, rank_c_i, rank_c_j);
245 }
246 else
247 { // otherwise use generic implementation based on expand
248 _interval_symbols(wt, i, j, k, cs, rank_c_i, rank_c_j);
249 }
250}
251
252// has_interval_symbols<X>::value is true if class X has
253// implement method interval_symbols
254// Adapted solution from jrok's proposal:
255// http://stackoverflow.com/questions/87372/check-if-a-class-has-a-member-function-of-a-given-signature
256template <typename t_wt>
258{
259 template <typename T>
260 static constexpr auto check(T *) -> typename std::is_same<
261 decltype(std::declval<T>().interval_symbols(std::declval<typename T::size_type>(),
262 std::declval<typename T::size_type>(),
263 std::declval<typename T::size_type &>(),
264 std::declval<std::vector<typename T::value_type> &>(),
265 std::declval<std::vector<typename T::size_type> &>(),
266 std::declval<std::vector<typename T::size_type> &>())),
267 void>::type
268 {
269 return std::true_type();
270 }
271 template <typename>
272 static constexpr std::false_type check(...)
273 {
274 return std::false_type();
275 }
276 typedef decltype(check<t_wt>(nullptr)) type;
277 static constexpr bool value = type::value;
278};
279
280template <typename t_wt, bool t_has_interval_symbols>
282{
283 typedef typename t_wt::size_type size_type;
284 typedef typename t_wt::value_type value_type;
285
286 static void call(t_wt const & wt,
287 size_type i,
288 size_type j,
289 size_type & k,
290 std::vector<value_type> & cs,
291 std::vector<size_type> & rank_c_i,
292 std::vector<size_type> & rank_c_j)
293 {
294 wt.interval_symbols(i, j, k, cs, rank_c_i, rank_c_j);
295 }
296};
297
298template <typename t_wt>
299struct _interval_symbols_wt<t_wt, false>
300{
301 typedef typename t_wt::size_type size_type;
302 typedef typename t_wt::value_type value_type;
303
304 static void call(t_wt const &,
305 size_type,
306 size_type,
307 size_type &,
308 std::vector<value_type> &,
309 std::vector<size_type> &,
310 std::vector<size_type> &)
311 {}
312};
313
314template <typename, typename T>
316{
317 static_assert(std::integral_constant<T, false>::value, "Second template parameter needs to be of function type.");
318};
319
320template <typename t_wt, typename t_ret, typename... t_args>
321struct has_expand<t_wt, t_ret(t_args...)>
322{
323 template <typename T>
324 static constexpr auto check(T *) ->
325 typename std::is_same<decltype(std::declval<T>().expand(std::declval<t_args>()...)), t_ret>::type
326 {
327 return std::true_type();
328 }
329 template <typename>
330 static constexpr std::false_type check(...)
331 {
332 return std::false_type();
333 }
334 typedef decltype(check<t_wt>(nullptr)) type;
335 static constexpr bool value = type::value;
336};
337
338template <typename t_wt>
340{
341 template <typename T>
342 static constexpr auto check(T *) -> typename std::is_same<
343 decltype(std::declval<T>().range_search_2d( //
344 std::declval<typename T::size_type>(),
345 std::declval<typename T::size_type>(),
346 std::declval<typename T::value_type>(),
347 std::declval<typename T::value_type>(),
348 false)),
349 std::pair<typename T::size_type, std::vector<std::pair<typename T::value_type, typename T::size_type>>>>::type
350 {
351 return std::true_type();
352 }
353
354 template <typename>
355 static constexpr std::false_type check(...)
356 {
357 return std::false_type();
358 }
359 typedef decltype(check<t_wt>(nullptr)) type;
360 static constexpr bool value = type::value;
361};
362
364
369template <class t_wt>
370std::pair<bool, typename t_wt::value_type> _symbol_lte(t_wt const & wt, typename t_wt::value_type c)
371{
372 if (((1ULL) << (wt.max_level)) <= c)
373 {
374 // c is greater than any symbol in wt. return the largest symbol!
375 c = sdsl::bits::lo_set[wt.max_level];
376 }
377 auto node = wt.root();
378 auto predecessor_subtree = node;
379 uint64_t mask = (1ULL) << (wt.max_level - 1);
380 while (!wt.is_leaf(node))
381 {
382 auto children = wt.expand(node);
383 auto left_child = std::get<0>(children);
384 auto right_child = std::get<1>(children);
385 if (c & (mask >> node.level))
386 { // go right
387 if (right_child.size)
388 {
389 node = right_child;
390 if (left_child.size)
391 { // potential predecessor subtree?
392 predecessor_subtree = left_child;
393 }
394 }
395 else
396 { // dead end
397 // left child can't be empty if left child is
398 node = left_child;
400 }
401 }
402 else
403 { // go left
404 if (left_child.size)
405 {
406 node = left_child;
407 }
408 else
409 { // dead end
410 if (predecessor_subtree == wt.root())
411 {
412 // there is no valid predecessor. symbol must be
413 // smaller than the smallest symbol in the wt.
414 return {false, 0};
415 }
416 node = predecessor_subtree;
418 }
419 }
420 }
421 return {true, node.sym};
422}
423
425
430template <class t_wt>
431std::pair<bool, typename t_wt::value_type> _symbol_gte(t_wt const & wt, typename t_wt::value_type c)
432{
433 if (((1ULL) << (wt.max_level)) <= c)
434 {
435 // c is greater than any symbol in wt
436 return {false, 0};
437 }
438 auto node = wt.root();
439 auto successor_subtree = node;
440 uint64_t mask = (1ULL) << (wt.max_level - 1);
441 while (!wt.is_leaf(node))
442 {
443 auto children = wt.expand(node);
444 auto left_child = std::get<0>(children);
445 auto right_child = std::get<1>(children);
446 if (c & (mask >> node.level))
447 { // go right
448 if (right_child.size)
449 {
450 node = right_child;
451 }
452 else
453 { // dead end
454 if (successor_subtree == wt.root())
455 {
456 // there is no valid successor. symbol must be
457 // bigger than the largest symbol in the wt.
458 return {false, 0};
459 }
460 node = successor_subtree;
461 c = 0;
462 }
463 }
464 else
465 { // go left
466 if (left_child.size)
467 {
468 node = left_child;
469 if (right_child.size)
470 { // potential successor subtree?
471 successor_subtree = right_child;
472 }
473 }
474 else
475 { // dead end
476 // right child can't be empty if left child is
477 node = right_child;
478 c = 0;
479 }
480 }
481 }
482 return {true, node.sym};
483}
484
485template <class t_wt, bool t_has_interval_symbols>
487{
488 typedef typename t_wt::value_type value_type;
489
490 static std::pair<bool, value_type> call_symbol_gte(t_wt const & wt, value_type c)
491 {
492 return wt.symbol_gte(c);
493 }
494
495 static std::pair<bool, value_type> call_symbol_lte(t_wt const & wt, value_type c)
496 {
497 return wt.symbol_lte(c);
498 }
499};
500
501template <class t_wt>
502struct _symbols_calls_wt<t_wt, false>
503{
504 typedef typename t_wt::value_type value_type;
505
506 static std::pair<bool, value_type> call_symbol_gte(t_wt const & wt, value_type c)
507 {
508 return _symbol_gte(wt, c);
509 }
510
511 static std::pair<bool, value_type> call_symbol_lte(t_wt const & wt, value_type c)
512 {
513 return _symbol_lte(wt, c);
514 }
515};
516
517template <typename t_wt>
519{
520 template <typename T>
521 static constexpr auto check(T *) ->
522 typename std::is_same<decltype(std::declval<T>().symbol_gte(std::declval<typename T::value_type>())),
523 std::pair<bool, typename T::value_type>>::type
524 {
525 return std::true_type();
526 }
527
528 template <typename>
529 static constexpr std::false_type check(...)
530 {
531 return std::false_type();
532 }
533 typedef decltype(check<t_wt>(nullptr)) type;
534 static constexpr bool value = type::value;
535};
536
538
543template <class t_wt>
544std::pair<bool, typename t_wt::value_type> symbol_lte(t_wt const & wt, typename t_wt::value_type c)
545{
546 static_assert(t_wt::lex_ordered, "symbols_lte requires a lex_ordered WT");
547 // check if wt has a built-in interval_symbols method
548 constexpr bool has_own = has_symbols_wt<t_wt>::value;
550}
551
553
558template <class t_wt>
559std::pair<bool, typename t_wt::value_type> symbol_gte(t_wt const & wt, typename t_wt::value_type c)
560{
561 static_assert(t_wt::lex_ordered, "symbols_gte requires a lex_ordered WT");
562 // check if wt has a built-in interval_symbols method
563 constexpr bool has_own = has_symbols_wt<t_wt>::value;
565}
566
569
575template <class t_wt>
576std::vector<typename t_wt::value_type> restricted_unique_range_values(t_wt const & wt,
577 typename t_wt::size_type x_i,
578 typename t_wt::size_type x_j,
579 typename t_wt::value_type y_i,
580 typename t_wt::value_type y_j)
581{
582 static_assert(t_wt::lex_ordered, "restricted_unique_range_values requires a lex_ordered WT");
583
584 std::vector<typename t_wt::value_type> unique_values;
585
586 // make sure things are within bounds
587 if (x_j > wt.size() - 1)
588 x_j = wt.size() - 1;
589 if ((x_i > x_j) || (y_i > y_j))
590 {
591 return unique_values;
592 }
593 auto lower_y_bound = symbol_gte(wt, y_i);
594 auto upper_y_bound = symbol_lte(wt, y_j);
595 // is the y range valid?
596 if (!lower_y_bound.first || !upper_y_bound.first || (lower_y_bound.second > upper_y_bound.second))
597 {
598 return unique_values;
599 }
600
601 auto lower_y_bound_path = wt.path(lower_y_bound.second);
602 auto upper_y_bound_path = wt.path(upper_y_bound.second);
603
604 auto compare_path = [](uint64_t node_path, uint64_t node_path_len, std::pair<uint64_t, uint64_t> bound_path) -> int
605 {
606 auto bound_path_len = bound_path.first;
607 auto bound_path_val = bound_path.second;
608 /* align to same length */
609 if (bound_path_len > node_path_len)
610 bound_path_val = bound_path_val >> (bound_path_len - node_path_len);
611 if (bound_path_len < node_path_len)
612 bound_path_val = bound_path_val << (node_path_len - bound_path_len);
613 /* cmp */
614 if (node_path < bound_path_val)
615 return -1;
616 if (node_path > bound_path_val)
617 return 1;
618 return 0;
619 };
620
621 std::stack<std::tuple<typename t_wt::node_type, sdsl::range_type, uint64_t, uint64_t>> stack;
622 sdsl::range_type initial_range = {{x_i, x_j}};
623 stack.emplace(wt.root(), initial_range, 0, 0);
624 while (!stack.empty())
625 {
626 auto node_data = stack.top();
627 stack.pop();
628 auto node = std::get<0>(node_data);
629 auto range = std::get<1>(node_data);
630 auto node_path = std::get<2>(node_data);
631 auto node_level = std::get<3>(node_data);
632 if (wt.is_leaf(node))
633 {
634 unique_values.emplace_back(wt.sym(node));
635 }
636 else
637 {
638 auto children = wt.expand(node);
639 auto left_path = node_path << 1ULL;
640 auto right_path = (node_path << 1ULL) | 1ULL;
641 auto child_ranges = wt.expand(node, range);
642 if (compare_path(right_path, node_level + 1, upper_y_bound_path) < 1)
643 {
644 auto right_child = std::get<1>(children);
645 auto right_range = std::get<1>(child_ranges);
646 if (!sdsl::empty(right_range))
647 stack.emplace(right_child, right_range, right_path, node_level + 1);
648 }
649 if (compare_path(left_path, node_level + 1, lower_y_bound_path) > -1)
650 {
651 auto left_child = std::get<0>(children);
652 auto left_range = std::get<0>(child_ranges);
653 if (!sdsl::empty(left_range))
654 stack.emplace(left_child, left_range, left_path, node_level + 1);
655 }
656 }
657 }
658
659 return unique_values;
660}
661
662// Check for node_type of wavelet_tree
663// http://stackoverflow.com/questions/7834226/detecting-typedef-at-compile-time-template-metaprogramming
664// + trick to make it work for VC++
665// https://connect.microsoft.com/VisualStudio/feedback/details/790269/compile-error-with-explicitly-specified-template-arguments
666template <typename T>
667struct void_
668{
669 typedef void type;
670};
671
672template <typename t_wt, typename T = void>
674{
675 typedef std::false_type t_expr;
676 enum
677 {
678 value = t_expr::value
679 };
680};
681
682template <typename t_wt>
683struct has_node_type<t_wt, typename void_<typename t_wt::node_type>::type>
684{
685 typedef std::true_type t_expr;
686 enum
687 {
688 value = t_expr::value
689 };
690};
691
692} // namespace sdsl
693
694#endif
bits.hpp contains the sdsl::bits class.
Namespace for the succinct data structure library.
std::vector< std::pair< typename t_wt::value_type, typename t_wt::size_type > > intersect(t_wt const &wt, std::vector< range_type > const &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].
void _interval_symbols(t_wt const &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)
std::pair< bool, typename t_wt::value_type > _symbol_gte(t_wt const &wt, typename t_wt::value_type c)
Returns for a symbol c the next larger or equal symbol in the WT.
std::pair< bool, typename t_wt::value_type > symbol_lte(t_wt const &wt, typename t_wt::value_type c)
Returns for a symbol c the previous smaller or equal symbol in the WT.
std::pair< typename t_wt::value_type, typename t_wt::size_type > quantile_freq(t_wt const &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:27
void interval_symbols(t_wt const &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).
void _interval_symbols_rec(t_wt const &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)
bool empty(range_type const &r)
Empty range check.
int_vector ::size_type size(range_type const &r)
Size of a range.
std::pair< bool, typename t_wt::value_type > _symbol_lte(t_wt const &wt, typename t_wt::value_type c)
Returns for a symbol c the previous smaller or equal symbol in the WT.
std::vector< range_type > range_vec_type
Definition wt_helper.hpp:28
std::pair< bool, typename t_wt::value_type > symbol_gte(t_wt const &wt, typename t_wt::value_type c)
Returns for a symbol c the next larger or equal symbol in the WT.
std::vector< typename t_wt::value_type > restricted_unique_range_values(t_wt const &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,...
static void call(t_wt const &, size_type, size_type, size_type &, std::vector< value_type > &, std::vector< size_type > &, std::vector< size_type > &)
static void call(t_wt const &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(t_wt const &wt, value_type c)
static std::pair< bool, value_type > call_symbol_gte(t_wt const &wt, value_type c)
t_wt::value_type value_type
static std::pair< bool, value_type > call_symbol_gte(t_wt const &wt, value_type c)
static std::pair< bool, value_type > call_symbol_lte(t_wt const &wt, value_type c)
static constexpr uint64_t all_set
64bit mask with all bits set to 1.
Definition bits.hpp:58
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:193
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