SDSL  3.0.0
Succinct Data Structure Library
rank_support_v.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_RANK_SUPPORT_V
9 #define INCLUDED_SDSL_RANK_SUPPORT_V
10 
11 #include <sdsl/rank_support.hpp>
12 
14 namespace sdsl
15 {
16 
18 
38 template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
40 {
41  private:
42  static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11,
43  "rank_support_v: bit pattern must be `0`,`1`,`10` or `01`");
44  static_assert(t_pat_len == 1u or t_pat_len == 2u, "rank_support_v: bit pattern length must be 1 or 2");
45 
46  public:
49  enum
50  {
51  bit_pat = t_b
52  };
53  enum
54  {
55  bit_pat_len = t_pat_len
56  };
57 
58  private:
59  // basic block for interleaved storage of superblockrank and blockrank
60  int_vector<64> m_basic_block;
61 
62  public:
63  explicit rank_support_v(const bit_vector * v = nullptr)
64  {
65  set_vector(v);
66  if (v == nullptr) { return; }
67  else if (v->empty())
68  {
69  m_basic_block = int_vector<64>(2, 0); // resize structure for basic_blocks
70  return;
71  }
72  size_type basic_block_size = (((v->bit_size() + 63) >> 9) + 1) << 1;
73  m_basic_block.resize(basic_block_size); // resize structure for basic_blocks
74  if (m_basic_block.empty()) return;
75  const uint64_t * data = m_v->data();
76  size_type i, j = 0;
77  m_basic_block[0] = m_basic_block[1] = 0;
78 
79  uint64_t carry = trait_type::init_carry();
80  uint64_t sum = trait_type::args_in_the_word(*data, carry);
81  uint64_t second_level_cnt = 0;
82  for (i = 1; i < ((m_v->bit_size() + 63) >> 6); ++i)
83  {
84  if (!(i & 0x7))
85  { // if i%8==0
86  j += 2;
87  m_basic_block[j - 1] = second_level_cnt;
88  m_basic_block[j] = m_basic_block[j - 2] + sum;
89  second_level_cnt = sum = 0;
90  }
91  else
92  {
93  second_level_cnt |= sum << (63 - 9 * (i & 0x7)); // 54, 45, 36, 27, 18, 9, 0
94  }
95  sum += trait_type::args_in_the_word(*(++data), carry);
96  }
97  if (i & 0x7)
98  { // if i%8 != 0
99  second_level_cnt |= sum << (63 - 9 * (i & 0x7));
100  m_basic_block[j + 1] = second_level_cnt;
101  }
102  else
103  { // if i%8 == 0
104  j += 2;
105  m_basic_block[j - 1] = second_level_cnt;
106  m_basic_block[j] = m_basic_block[j - 2] + sum;
107  m_basic_block[j + 1] = 0;
108  }
109  }
110 
111  rank_support_v(const rank_support_v &) = default;
115 
117  {
118  assert(m_v != nullptr);
119  assert(idx <= m_v->size());
120  const uint64_t * p = m_basic_block.data() + ((idx >> 8) & 0xFFFFFFFFFFFFFFFEULL); // (idx/512)*2
121  if (idx & 0x3F) // if (idx%64)!=0
122  return *p + ((*(p + 1) >> (63 - 9 * ((idx & 0x1FF) >> 6))) & 0x1FF) +
123  trait_type::word_rank(m_v->data(), idx);
124  else
125  return *p + ((*(p + 1) >> (63 - 9 * ((idx & 0x1FF) >> 6))) & 0x1FF);
126  }
127 
128  inline size_type operator()(size_type idx) const { return rank(idx); }
129 
130  size_type size() const { return m_v->size(); }
131 
132  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
133  {
134  size_type written_bytes = 0;
135  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
136  written_bytes += m_basic_block.serialize(out, child, "cumulative_counts");
137  structure_tree::add_size(child, written_bytes);
138  return written_bytes;
139  }
140 
141  void load(std::istream & in, const int_vector<1> * v = nullptr)
142  {
143  set_vector(v);
144  m_basic_block.load(in);
145  }
146 
147  template <typename archive_t>
148  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
149  {
150  ar(CEREAL_NVP(m_basic_block));
151  }
152 
153  template <typename archive_t>
154  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
155  {
156  ar(CEREAL_NVP(m_basic_block));
157  }
158 
159  bool operator==(const rank_support_v & other) const noexcept { return m_basic_block == other.m_basic_block; }
160 
161  bool operator!=(const rank_support_v & other) const noexcept { return !(*this == other); }
162 
163  void set_vector(const bit_vector * v = nullptr) { m_v = v; }
164 };
165 
166 } // namespace sdsl
167 
168 #endif // end file
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
bool empty() const noexcept
Equivalent to size() == 0.
Definition: int_vector.hpp:524
size_type bit_size() const noexcept
The number of bits in the int_vector.
Definition: int_vector.hpp:571
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:590
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
A rank structure proposed by Sebastiano Vigna.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
rank_support_trait< t_b, t_pat_len > trait_type
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
bool operator!=(const rank_support_v &other) const noexcept
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type size() const
rank_support_v & operator=(rank_support_v &&)=default
rank_support_v(const rank_support_v &)=default
bool operator==(const rank_support_v &other) const noexcept
size_type operator()(size_type idx) const
Alias for rank(i)
void set_vector(const bit_vector *v=nullptr)
Sets the supported bit_vector to the given pointer.
void load(std::istream &in, const int_vector< 1 > *v=nullptr)
Loads the rank_support.
rank_support_v & operator=(const rank_support_v &)=default
rank_support_v(rank_support_v &&)=default
rank_support_v(const bit_vector *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time.
const bit_vector * m_v
Pointer to the rank supported bit_vector.
bit_vector::size_type size_type
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
Namespace for the succinct data structure library.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
static uint32_t word_rank(const uint64_t *, size_type)
static uint64_t init_carry()
static size_type args_in_the_word(uint64_t, uint64_t &)