SDSL 3.0.1
Succinct Data Structure Library
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 <sdsl/int_vector.hpp>
13#include <sdsl/util.hpp>
14
16namespace sdsl
17{
18
20
29template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
31{
32 private:
33 static_assert(t_b == 1u or t_b == 0u or t_b == 10u,
34 "select_support_scan: bit pattern must be `0`,`1`,`10` or `01`");
35 static_assert(t_pat_len == 1u or t_pat_len == 2u, "select_support_scan: bit pattern length must be 1 or 2");
36
37 public:
39 enum
40 {
41 bit_pat = t_b
42 };
43
44 public:
45 explicit select_support_scan(const bit_vector * v = nullptr)
47 {}
50 {}
51
52 inline size_type select(size_type i) const;
53 inline size_type operator()(size_type i) const { return select(i); }
54 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
55 {
56 return serialize_empty_object(out, v, name, this);
57 }
58 void load(std::istream &, SDSL_UNUSED const bit_vector * v = nullptr) { set_vector(v); }
60 template <typename archive_t>
61 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
63 template <typename archive_t>
64 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
65 void set_vector(const bit_vector * v = nullptr) { m_v = v; }
67 {
68 set_vector(ss.m_v);
69 return *this;
70 }
71
73 bool operator==(select_support_scan const & other) const noexcept { return (*m_v == *other.m_v); }
74
76 bool operator!=(select_support_scan const & other) const noexcept { return !(*this == other); }
77};
78
79template <uint8_t t_b, uint8_t t_pat_len>
80template <typename archive_t>
82{}
83
84template <uint8_t t_b, uint8_t t_pat_len>
85template <typename archive_t>
87{}
88
89template <uint8_t t_b, uint8_t t_pat_len>
91 size_type i) const
92{
93 const uint64_t * data = m_v->data();
94 size_type word_pos = 0;
95 size_type word_off = 0;
96 uint64_t carry = select_support_trait<t_b, t_pat_len>::init_carry(data, word_pos);
98 if (args >= i)
99 {
100 return (word_pos << 6) +
102 }
103 word_pos += 1;
104 size_type sum_args = args;
106 uint64_t old_carry = carry;
108 while (sum_args + args < i)
109 {
110 sum_args += args;
111 assert(data + 1 < m_v->data() + (m_v->capacity() >> 6));
112 old_carry = carry;
114 word_pos += 1;
115 }
116 return (word_pos << 6) +
118}
119
120} // namespace sdsl
121#endif
A class supporting linear time select queries.
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(const select_support_scan< t_b, t_pat_len > &ss)
select_support_scan< t_b, t_pat_len > & operator=(const select_support_scan &ss)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
size_type operator()(size_type i) const
Alias for select.
void set_vector(const bit_vector *v=nullptr)
This method sets the supported bit_vector.
void load(std::istream &, SDSL_UNUSED const bit_vector *v=nullptr)
select_support_scan(const bit_vector *v=nullptr)
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
const int_vector< 1 > * m_v
Pointer to the select supported sdsl::bit_vector.
int_vector< 1 >::size_type size_type
#define SDSL_UNUSED
Definition: config.hpp:13
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", const T *t=nullptr)
Definition: io.hpp:325
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 size_type args_in_the_word(uint64_t, uint64_t &)
static uint64_t init_carry(const uint64_t *, size_type)
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)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.