SDSL 3.0.1
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 <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
23namespace sdsl
24{
25
26namespace k2_treap_ns
27{
28
29// Precomputed value for fast k^2 treap operations
30template <uint8_t t_k>
31struct 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
50template <>
51struct 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
60template <>
61struct 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
70template <>
71struct 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
80template <>
81struct 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
90template <uint8_t t_k>
92
93typedef std::complex<uint64_t> t_p;
96
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;
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.
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
node_type(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
node_type & operator=(node_type &&)=default
node_type & operator=(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