SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <assert.h>
12#include <iosfwd>
13#include <stdint.h>
14#include <string>
15
16#include <sdsl/cereal.hpp>
17#include <sdsl/int_vector.hpp>
18#include <sdsl/io.hpp>
19#include <sdsl/rank_support.hpp>
20
21namespace sdsl
22{
24
35template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
37{
38private:
39 static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
40 "rank_support_scan: bit pattern must be `0`,`1`,`10` or `01`");
41 static_assert(t_pat_len == 1u or t_pat_len == 2u, "rank_support_scan: bit pattern length must be 1 or 2");
42
43public:
45 enum
46 {
47 bit_pat = t_b
48 };
49 enum
50 {
51 bit_pat_len = t_pat_len
52 };
53
54public:
55 explicit rank_support_scan(bit_vector const * v = nullptr) : rank_support(v){};
56 rank_support_scan(rank_support_scan const & rs) = default;
60 size_type rank(size_type idx) const;
62 {
63 return rank(idx);
64 };
66 {
67 return m_v->size();
68 };
69 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
70 {
71 return serialize_empty_object(out, v, name, this);
72 }
73 void load(std::istream &, int_vector<1> const * v = nullptr)
74 {
75 set_vector(v);
76 }
77 void set_vector(bit_vector const * v = nullptr)
78 {
79 m_v = v;
80 }
81 template <typename archive_t>
82 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
83 {}
84 template <typename archive_t>
85 void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
86 {}
87
89 bool operator==(rank_support_scan const & other) const noexcept
90 {
91 return (*m_v == *other.m_v);
92 }
93
95 bool operator!=(rank_support_scan const & other) const noexcept
96 {
97 return !(*this == other);
98 }
99};
100
101template <uint8_t t_b, uint8_t t_pat_len>
104{
105 assert(m_v != nullptr);
106 assert(idx <= m_v->size());
107 uint64_t const * p = m_v->data();
108 size_type i = 0;
109 size_type result = 0;
110 while (i + 64 <= idx)
111 {
113 i += 64;
114 }
115 return result + rank_support_trait<t_b, t_pat_len>::word_rank(p, idx);
116}
117
118} // namespace sdsl
119
120#endif // end file
cereal.hpp offers cereal support
A generic vector class for integers of width .
rank_support_scan(rank_support_scan const &rs)=default
rank_support_scan(bit_vector const *v=nullptr)
void set_vector(bit_vector const *v=nullptr)
Sets the supported bit_vector to the given pointer.
rank_support_scan & operator=(rank_support_scan &&rs)=default
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void load(std::istream &, int_vector< 1 > const *v=nullptr)
Loads the rank_support.
size_type operator()(size_type idx) const
Alias for rank(i)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
rank_support_scan & operator=(rank_support_scan const &rs)=default
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
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
rank_support(bit_vector const *v=nullptr)
Constructor.
bit_vector const * m_v
Pointer to the rank supported bit_vector.
bit_vector::size_type size_type
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.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector ::size_type size(range_type const &r)
Size of a range.
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", T const *t=nullptr)
Definition io.hpp:339
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
static uint32_t word_rank(uint64_t const *, size_type)
static uint32_t full_word_rank(uint64_t const *, size_type)