SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
select_support_scan.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_SELECT_SUPPORT_SCAN
9#define INCLUDED_SDSL_SELECT_SUPPORT_SCAN
10
11#include <assert.h>
12#include <iosfwd>
13#include <stdint.h>
14#include <string>
15
16#include <sdsl/cereal.hpp>
17#include <sdsl/config.hpp>
18#include <sdsl/int_vector.hpp>
19#include <sdsl/io.hpp>
21
23namespace sdsl
24{
25class structure_tree_node;
26
28
37template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
39{
40private:
41 static_assert(t_b == 1u or t_b == 0u or t_b == 10u,
42 "select_support_scan: bit pattern must be `0`,`1`,`10` or `01`");
43 static_assert(t_pat_len == 1u or t_pat_len == 2u, "select_support_scan: bit pattern length must be 1 or 2");
44
45public:
47 enum
48 {
49 bit_pat = t_b
50 };
51
52public:
53 explicit select_support_scan(bit_vector const * v = nullptr) : select_support(v)
54 {}
57
58 inline size_type select(size_type i) const;
60 {
61 return select(i);
62 }
63 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
64 {
65 return serialize_empty_object(out, v, name, this);
66 }
67 void load(std::istream &, SDSL_UNUSED bit_vector const * v = nullptr)
68 {
69 set_vector(v);
70 }
72 template <typename archive_t>
73 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
75 template <typename archive_t>
76 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
77 void set_vector(bit_vector const * v = nullptr)
78 {
79 m_v = v;
80 }
82 {
83 set_vector(ss.m_v);
84 return *this;
85 }
86
88 bool operator==(select_support_scan const & other) const noexcept
89 {
90 return (*m_v == *other.m_v);
91 }
92
94 bool operator!=(select_support_scan const & other) const noexcept
95 {
96 return !(*this == other);
97 }
98};
99
100template <uint8_t t_b, uint8_t t_pat_len>
101template <typename archive_t>
104
105template <uint8_t t_b, uint8_t t_pat_len>
106template <typename archive_t>
109
110template <uint8_t t_b, uint8_t t_pat_len>
113{
114 uint64_t const * data = m_v->data();
115 size_type word_pos = 0;
116 size_type word_off = 0;
117 uint64_t carry = select_support_trait<t_b, t_pat_len>::init_carry(data, word_pos);
119 if (args >= i)
120 {
121 return (word_pos << 6)
123 }
124 word_pos += 1;
125 size_type sum_args = args;
127 uint64_t old_carry = carry;
129 while (sum_args + args < i)
130 {
131 sum_args += args;
132 assert(data + 1 < m_v->data() + (m_v->capacity() >> 6));
133 old_carry = carry;
135 word_pos += 1;
136 }
137 return (word_pos << 6)
139}
140
141} // namespace sdsl
142#endif
cereal.hpp offers cereal support
A class supporting linear time select queries.
select_support_scan< t_b, t_pat_len > & operator=(select_support_scan const &ss)
bool operator==(select_support_scan const &other) const noexcept
Equality operator.
bool operator!=(select_support_scan const &other) const noexcept
Inequality operator.
size_type select(size_type i) const
Select returns the index of the i-th 1-bit in the supported bit_vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize the select_support to an out file stream.
select_support_scan(select_support_scan< t_b, t_pat_len > const &ss)
void load(std::istream &, SDSL_UNUSED bit_vector const *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
void set_vector(bit_vector const *v=nullptr)
This method sets the supported bit_vector.
size_type operator()(size_type i) const
Alias for select.
select_support_scan(bit_vector const *v=nullptr)
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
int_vector< 1 > const * m_v
Pointer to the select supported sdsl::bit_vector.
int_vector< 1 >::size_type size_type
#define SDSL_UNUSED
Definition config.hpp:12
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", T const *t=nullptr)
Definition io.hpp:339
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static uint64_t get_carry(uint64_t)
static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t)
static uint64_t init_carry(uint64_t const *, size_type)
static size_type args_in_the_word(uint64_t, uint64_t &)
static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t)
static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t)