SDSL  3.0.0
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>
12 #include <sdsl/select_support.hpp>
13 #include <sdsl/util.hpp>
14 
16 namespace sdsl
17 {
18 
20 
29 template <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)
46  : select_support(v)
47  {}
49  : select_support(ss.m_v)
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 
79 template <uint8_t t_b, uint8_t t_pat_len>
80 template <typename archive_t>
82 {}
83 
84 template <uint8_t t_b, uint8_t t_pat_len>
85 template <typename archive_t>
87 {}
88 
89 template <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.
select_support_scan< t_b, t_pat_len > & operator=(const select_support_scan &ss)
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)
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.