SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <complex>
12#include <cstdint>
13
14#include <sdsl/bits.hpp>
15
17namespace sdsl
18{
19
20namespace k2_treap_ns
21{
22
23// Precomputed value for fast k^2 treap operations
24template <uint8_t t_k>
25struct precomp
26{
27 static struct impl
28 {
29 uint64_t exp[65];
30 impl()
31 {
32 exp[0] = 1;
33 for (uint8_t i = 1; i < 65; ++i)
34 {
35 exp[i] = t_k * exp[i - 1];
36 }
37 }
38 } data;
39
40 static uint64_t exp(uint8_t l)
41 {
42 return data.exp[l];
43 }
44
45 static uint64_t divexp(uint64_t x, uint8_t l)
46 {
47 return x / data.exp[l];
48 }
49
50 static uint64_t modexp(uint64_t x, uint8_t l)
51 {
52 return x % data.exp[l];
53 }
54};
55
56template <>
57struct precomp<2>
58{
59 static uint64_t exp(uint8_t l)
60 {
61 return 1ULL << l;
62 }
63
64 static uint64_t divexp(uint64_t x, uint8_t l)
65 {
66 return x >> l;
67 }
68
69 static uint64_t modexp(uint64_t x, uint8_t l)
70 {
71 return x & bits::lo_set[l];
72 }
73};
74
75template <>
76struct precomp<4>
77{
78 static uint64_t exp(uint8_t l)
79 {
80 return 1ULL << (2 * l);
81 }
82
83 static uint64_t divexp(uint64_t x, uint8_t l)
84 {
85 return x >> (2 * l);
86 }
87
88 static uint64_t modexp(uint64_t x, uint8_t l)
89 {
90 return x & bits::lo_set[2 * l];
91 }
92};
93
94template <>
95struct precomp<8>
96{
97 static uint64_t exp(uint8_t l)
98 {
99 return 1ULL << (3 * l);
100 }
101
102 static uint64_t divexp(uint64_t x, uint8_t l)
103 {
104 return x >> (3 * l);
105 }
106
107 static uint64_t modexp(uint64_t x, uint8_t l)
108 {
109 return x & bits::lo_set[3 * l];
110 }
111};
112
113template <>
114struct precomp<16>
115{
116 static uint64_t exp(uint8_t l)
117 {
118 return 1ULL << (4 * l);
119 }
120
121 static uint64_t divexp(uint64_t x, uint8_t l)
122 {
123 return x >> (4 * l);
124 }
125
126 static uint64_t modexp(uint64_t x, uint8_t l)
127 {
128 return x & bits::lo_set[4 * l];
129 }
130};
131
132template <uint8_t t_k>
133typename precomp<t_k>::impl precomp<t_k>::data;
134
135typedef std::complex<uint64_t> t_p;
138
140{
141 uint8_t t; // level; size of node 1<<t
142 t_p p; // lower left corner
143 uint64_t idx; // index in bp
144 uint64_t max_v; // maximal value
145 t_p max_p; // maximal point
146
147 node_type() = default;
148 node_type(uint8_t _t, t_p _p, uint64_t _idx, uint64_t _max_v, t_p _max_p) :
149 t(_t),
150 p(_p),
151 idx(_idx),
152 max_v(_max_v),
153 max_p(_max_p)
154 {}
155 node_type(node_type &&) = default;
156 node_type(node_type const &) = default;
158 node_type & operator=(node_type const &) = default;
159
160 bool operator<(node_type const & v) const
161 {
162 if (max_v != v.max_v)
163 {
164 return max_v < v.max_v;
165 }
166 if (real(max_p) != real(v.max_p))
167 {
168 return real(max_p) > real(v.max_p);
169 }
170 return imag(max_p) > imag(v.max_p);
171 }
172};
173
174} // namespace k2_treap_ns
175
176} // namespace sdsl
177#endif
bits.hpp contains the sdsl::bits class.
std::complex< uint64_t > t_p
Namespace for the succinct data structure library.
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:194
node_type & operator=(node_type const &)=default
node_type(node_type &&)=default
node_type(node_type const &)=default
node_type(uint8_t _t, t_p _p, uint64_t _idx, uint64_t _max_v, t_p _max_p)
bool operator<(node_type const &v) const
node_type & operator=(node_type &&)=default
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