SDSL  3.0.0
Succinct Data Structure Library
k2_treap_helper.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.
8 #ifndef INCLUDED_SDSL_K2_TREAP_HELPER
9 #define INCLUDED_SDSL_K2_TREAP_HELPER
10 
11 #include <algorithm>
12 #include <array>
13 #include <complex>
14 #include <iterator>
15 #include <queue>
16 #include <tuple>
17 #include <vector>
18 
19 #include <sdsl/bits.hpp>
20 #include <sdsl/vectors.hpp>
21 
23 namespace sdsl
24 {
25 
26 namespace k2_treap_ns
27 {
28 
29 // Precomputed value for fast k^2 treap operations
30 template <uint8_t t_k>
31 struct precomp
32 {
33  static struct impl
34  {
35  uint64_t exp[65];
36  impl()
37  {
38  exp[0] = 1;
39  for (uint8_t i = 1; i < 65; ++i) { exp[i] = t_k * exp[i - 1]; }
40  }
41  } data;
42 
43  static uint64_t exp(uint8_t l) { return data.exp[l]; }
44 
45  static uint64_t divexp(uint64_t x, uint8_t l) { return x / data.exp[l]; }
46 
47  static uint64_t modexp(uint64_t x, uint8_t l) { return x % data.exp[l]; }
48 };
49 
50 template <>
51 struct precomp<2>
52 {
53  static uint64_t exp(uint8_t l) { return 1ULL << l; }
54 
55  static uint64_t divexp(uint64_t x, uint8_t l) { return x >> l; }
56 
57  static uint64_t modexp(uint64_t x, uint8_t l) { return x & bits::lo_set[l]; }
58 };
59 
60 template <>
61 struct precomp<4>
62 {
63  static uint64_t exp(uint8_t l) { return 1ULL << (2 * l); }
64 
65  static uint64_t divexp(uint64_t x, uint8_t l) { return x >> (2 * l); }
66 
67  static uint64_t modexp(uint64_t x, uint8_t l) { return x & bits::lo_set[2 * l]; }
68 };
69 
70 template <>
71 struct precomp<8>
72 {
73  static uint64_t exp(uint8_t l) { return 1ULL << (3 * l); }
74 
75  static uint64_t divexp(uint64_t x, uint8_t l) { return x >> (3 * l); }
76 
77  static uint64_t modexp(uint64_t x, uint8_t l) { return x & bits::lo_set[3 * l]; }
78 };
79 
80 template <>
81 struct precomp<16>
82 {
83  static uint64_t exp(uint8_t l) { return 1ULL << (4 * l); }
84 
85  static uint64_t divexp(uint64_t x, uint8_t l) { return x >> (4 * l); }
86 
87  static uint64_t modexp(uint64_t x, uint8_t l) { return x & bits::lo_set[4 * l]; }
88 };
89 
90 template <uint8_t t_k>
92 
93 typedef std::complex<uint64_t> t_p;
94 typedef t_p point_type;
95 typedef t_p range_type;
96 
97 struct node_type
98 {
99  uint8_t t; // level; size of node 1<<t
100  t_p p; // lower left corner
101  uint64_t idx; // index in bp
102  uint64_t max_v; // maximal value
103  t_p max_p; // maximal point
104 
105  node_type() = default;
106  node_type(uint8_t _t, t_p _p, uint64_t _idx, uint64_t _max_v, t_p _max_p)
107  : t(_t)
108  , p(_p)
109  , idx(_idx)
110  , max_v(_max_v)
111  , max_p(_max_p)
112  {}
113  node_type(node_type &&) = default;
114  node_type(const node_type &) = default;
115  node_type & operator=(node_type &&) = default;
116  node_type & operator=(const node_type &) = default;
117 
118  bool operator<(const node_type & v) const
119  {
120  if (max_v != v.max_v) { return max_v < v.max_v; }
121  if (real(max_p) != real(v.max_p)) { return real(max_p) > real(v.max_p); }
122  return imag(max_p) > imag(v.max_p);
123  }
124 };
125 
126 } // namespace k2_treap_ns
127 
128 } // namespace sdsl
129 #endif
bits.hpp contains the sdsl::bits class.
std::complex< uint64_t > t_p
Namespace for the succinct data structure library.
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
node_type & operator=(node_type &&)=default
node_type(node_type &&)=default
node_type & operator=(const node_type &)=default
node_type(uint8_t _t, t_p _p, uint64_t _idx, uint64_t _max_v, t_p _max_p)
node_type(const node_type &)=default
bool operator<(const node_type &v) const
static uint64_t divexp(uint64_t x, uint8_t l)
static uint64_t modexp(uint64_t x, uint8_t l)
static uint64_t exp(uint8_t l)
static uint64_t modexp(uint64_t x, uint8_t l)
static uint64_t exp(uint8_t l)
static uint64_t divexp(uint64_t x, uint8_t l)
static uint64_t divexp(uint64_t x, uint8_t l)
static uint64_t modexp(uint64_t x, uint8_t l)
static uint64_t exp(uint8_t l)
static uint64_t modexp(uint64_t x, uint8_t l)
static uint64_t divexp(uint64_t x, uint8_t l)
static uint64_t exp(uint8_t l)
static uint64_t exp(uint8_t l)
static uint64_t modexp(uint64_t x, uint8_t l)
static uint64_t divexp(uint64_t x, uint8_t l)
static struct sdsl::k2_treap_ns::precomp::impl data