SDSL  3.0.0
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 
12 namespace sdsl
13 {
14 
15 template <typename t_wt>
16 struct has_interval_symbols;
17 
18 template <typename t_wt, bool t_has_interval_symbols>
19 struct _interval_symbols_wt;
20 
21 template <typename, typename T>
22 struct has_expand;
23 
25 
34 template <class t_wt>
35 std::vector<std::pair<typename t_wt::value_type, typename t_wt::size_type>>
36 intersect(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 
102 template <class t_wt>
103 std::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 
138 template <class t_wt>
139 void _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 
169 template <class t_wt>
170 void _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 
217 template <class t_wt>
218 void 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
242 template <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 
266 template <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 
284 template <typename t_wt>
285 struct _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 
300 template <typename, typename T>
302 {
303  static_assert(std::integral_constant<T, false>::value, "Second template parameter needs to be of function type.");
304 };
305 
306 template <typename t_wt, typename t_ret, typename... t_args>
307 struct 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 
324 template <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 
357 template <class t_wt>
358 std::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 
415 template <class t_wt>
416 std::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 
467 template <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 
477 template <class t_wt>
478 struct _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 
487 template <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 
513 template <class t_wt>
514 std::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 
528 template <class t_wt>
529 std::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 
545 template <class t_wt>
546 std::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
624 template <typename T>
625 struct void_
626 {
627  typedef void type;
628 };
629 
630 template <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 
640 template <typename t_wt>
641 struct 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.
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].
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_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::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::array< int_vector<>::size_type, 2 > range_type
Definition: wt_helper.hpp:20
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::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,...
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_gte(const t_wt &wt, value_type c)
static std::pair< bool, value_type > call_symbol_lte(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)
constexpr static uint64_t all_set
64bit mask with all bits set to 1.
Definition: bits.hpp:59
constexpr static 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:197
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
static constexpr bool value
static constexpr std::false_type check(...)
decltype(check< t_wt >(nullptr)) typedef 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 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
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
static constexpr std::false_type check(...)