SDSL  3.0.0
Succinct Data Structure Library
rank_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_RANK_SUPPORT_SCAN
9 #define INCLUDED_SDSL_RANK_SUPPORT_SCAN
10 
11 #include <sdsl/rank_support.hpp>
12 
14 namespace sdsl
15 {
16 
18 
27 template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
29 {
30  private:
31  static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
32  "rank_support_scan: bit pattern must be `0`,`1`,`10` or `01`");
33  static_assert(t_pat_len == 1u or t_pat_len == 2u, "rank_support_scan: bit pattern length must be 1 or 2");
34 
35  public:
37  enum
38  {
39  bit_pat = t_b
40  };
41  enum
42  {
43  bit_pat_len = t_pat_len
44  };
45 
46  public:
47  explicit rank_support_scan(const bit_vector * v = nullptr)
48  : rank_support(v){};
49  rank_support_scan(const rank_support_scan & rs) = default;
53  size_type rank(size_type idx) const;
54  size_type operator()(size_type idx) const { return rank(idx); };
55  size_type size() const { return m_v->size(); };
56  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
57  {
58  return serialize_empty_object(out, v, name, this);
59  }
60  void load(std::istream &, const int_vector<1> * v = nullptr) { set_vector(v); }
61  void set_vector(const bit_vector * v = nullptr) { m_v = v; }
62  template <typename archive_t>
63  void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
64  {}
65  template <typename archive_t>
66  void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
67  {}
68 
70  bool operator==(rank_support_scan const & other) const noexcept { return (*m_v == *other.m_v); }
71 
73  bool operator!=(rank_support_scan const & other) const noexcept { return !(*this == other); }
74 };
75 
76 template <uint8_t t_b, uint8_t t_pat_len>
78  size_type idx) const
79 {
80  assert(m_v != nullptr);
81  assert(idx <= m_v->size());
82  const uint64_t * p = m_v->data();
83  size_type i = 0;
84  size_type result = 0;
85  while (i + 64 <= idx)
86  {
88  i += 64;
89  }
90  return result + rank_support_trait<t_b, t_pat_len>::word_rank(p, idx);
91 }
92 
93 } // namespace sdsl
94 
95 #endif // end file
size_type size() const noexcept
The number of elements in the int_vector.
A class supporting rank queries in linear time.
void load(std::istream &, const int_vector< 1 > *v=nullptr)
Loads the rank_support.
rank_support_scan & operator=(const rank_support_scan &rs)=default
rank_support_scan(const rank_support_scan &rs)=default
rank_support_scan & operator=(rank_support_scan &&rs)=default
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
void set_vector(const bit_vector *v=nullptr)
Sets the supported bit_vector to the given pointer.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
rank_support_scan(const bit_vector *v=nullptr)
size_type operator()(size_type idx) const
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
size_type rank(size_type idx) const
bool operator==(rank_support_scan const &other) const noexcept
Equality operator.
bool operator!=(rank_support_scan const &other) const noexcept
Inequality operator.
rank_support_scan(rank_support_scan &&rs)=default
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
Namespace for the succinct data structure library.
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", const T *t=nullptr)
Definition: io.hpp:325
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 uint32_t full_word_rank(const uint64_t *, size_type)