Sux
FenwickBitL.hpp
Go to the documentation of this file.
1 /*
2  * Sux: Succinct data structures
3  *
4  * Copyright (C) 2019-2020 Stefano Marchini
5  *
6  * This library is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License as published by the Free
8  * Software Foundation; either version 3 of the License, or (at your option)
9  * any later version.
10  *
11  * This library is free software; you can redistribute it and/or modify it under
12  * the terms of the GNU General Public License as published by the Free Software
13  * Foundation; either version 3, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but WITHOUT ANY
16  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
17  * PARTICULAR PURPOSE. See the GNU General Public License for more details.
18  *
19  * Under Section 7 of GPL version 3, you are granted additional permissions
20  * described in the GCC Runtime Library Exception, version 3.1, as published by
21  * the Free Software Foundation.
22  *
23  * You should have received a copy of the GNU General Public License and a copy of
24  * the GCC Runtime Library Exception along with this program; see the files
25  * COPYING3 and COPYING.RUNTIME respectively. If not, see
26  * <http://www.gnu.org/licenses/>.
27  */
28 
29 #pragma once
30 
31 #include "SearchablePrefixSums.hpp"
32 #include "Vector.hpp"
33 
34 namespace sux::util {
35 
42 template <size_t BOUND, AllocType AT = MALLOC> class FenwickBitL : public SearchablePrefixSums, public Expandable {
43  public:
44  static constexpr size_t BOUNDSIZE = ceil_log2_plus1(BOUND);
45  static_assert(BOUNDSIZE >= 1 && BOUNDSIZE <= 64, "Leaves can't be stored in a 64-bit word");
46 
47  protected:
49  size_t Levels, Size;
50 
51  public:
53  FenwickBitL() : Levels(0), Size(0) {}
54 
63  FenwickBitL(uint64_t sequence[], size_t size) : Levels(size != 0 ? lambda(size) + 1 : 1), Size(size) {
64  this->size(size ? size : 1);
65 
66  for (size_t l = 0; l < Levels; l++) {
67  for (size_t node = 1ULL << l; node <= size; node += 1ULL << (l + 1)) {
68  size_t sequence_idx = node - 1;
69  uint64_t value = sequence[sequence_idx];
70 
71  for (size_t j = 0; j < l; j++) {
72  sequence_idx >>= 1;
73  const size_t lowpos = (BOUNDSIZE + j) * sequence_idx;
74  value += bitread(&Tree[j][lowpos / 8], lowpos % 8, BOUNDSIZE + j);
75  }
76 
77  const size_t highpos = (BOUNDSIZE + l) * (node >> (l + 1));
78  bitwrite_inc(&Tree[l][highpos / 8], highpos % 8, BOUNDSIZE + l, value);
79  }
80  }
81  }
82 
83  virtual uint64_t prefix(size_t idx) {
84  uint64_t sum = 0;
85 
86  while (idx != 0) {
87  const int height = rho(idx);
88  const size_t pos = (idx >> (1 + height)) * (BOUNDSIZE + height);
89  sum += bitread(&Tree[height][pos / 8], pos % 8, BOUNDSIZE + height);
90 
91  idx = clear_rho(idx);
92  }
93 
94  return sum;
95  }
96 
97  virtual void add(size_t idx, int64_t inc) {
98  while (idx <= Size) {
99  const int height = rho(idx);
100  const size_t pos = (idx >> (1 + height)) * (BOUNDSIZE + height);
101  bitwrite_inc(&Tree[height][pos / 8], pos % 8, BOUNDSIZE + height, inc);
102 
103  idx += mask_rho(idx);
104  }
105  }
106 
108  virtual size_t find(uint64_t *val) {
109  size_t node = 0, idx = 0;
110 
111  for (size_t height = Levels - 1; height != SIZE_MAX; height--) {
112  const size_t pos = idx * (BOUNDSIZE + height);
113 
114  idx <<= 1;
115 
116  if ((pos + BOUNDSIZE + height) / 8 + 7 >= Tree[height].size()) continue;
117 
118  const uint64_t value = bitread(&Tree[height][pos / 8], pos % 8, BOUNDSIZE + height);
119 
120  if (*val >= value) {
121  idx++;
122  *val -= value;
123  node += 1ULL << height;
124  }
125  }
126 
127  return min(node, Size);
128  }
129 
131  virtual size_t compFind(uint64_t *val) {
132  size_t node = 0, idx = 0;
133 
134  for (size_t height = Levels - 1; height != SIZE_MAX; height--) {
135  const size_t pos = idx * (BOUNDSIZE + height);
136 
137  idx <<= 1;
138 
139  if ((pos + BOUNDSIZE + height) / 8 + 7 >= Tree[height].size()) continue;
140 
141  const uint64_t value = (BOUND << height) - bitread(&Tree[height][pos / 8], pos % 8, BOUNDSIZE + height);
142 
143  if (*val >= value) {
144  idx++;
145  *val -= value;
146  node += 1ULL << height;
147  }
148  }
149 
150  return min(node, Size);
151  }
152 
153  virtual void push(uint64_t val) {
154  Levels = lambda(++Size) + 1;
155 
156  int height = rho(Size);
157  size_t idx = Size >> (1 + height);
158  size_t hipos = (BOUNDSIZE + height) * idx;
159 
160  Tree[height].resize(hipos / 8 + 8);
161  bitwrite_inc(&Tree[height][hipos / 8], hipos % 8, BOUNDSIZE + height, val);
162 
163  idx <<= 1;
164  for (size_t h = height - 1; h != SIZE_MAX; h--) {
165  size_t lopos = (BOUNDSIZE + h) * idx;
166  int64_t inc = bitread(&Tree[h][lopos / 8], lopos % 8, BOUNDSIZE + h);
167  bitwrite_inc(&Tree[height][hipos / 8], hipos % 8, BOUNDSIZE + height, inc);
168 
169  idx = (idx << 1) + 1;
170  }
171  }
172 
173  virtual void pop() {
174  int height = rho(Size);
175  size_t pos = (BOUNDSIZE + height) * (Size >> (1 + height));
176  Tree[height].resize(pos / 8);
177  Size--;
178  }
179 
180  virtual void grow(size_t space) {
181  size_t levels = lambda(space) + 1;
182  for (size_t i = 0; i < levels; i++) Tree[i].grow(((space + (1ULL << i)) / (1ULL << (i + 1))) * (BOUNDSIZE + i) / 8 + 8);
183  }
184 
185  virtual void reserve(size_t space) {
186  size_t levels = lambda(space) + 1;
187  for (size_t i = 0; i < levels; i++) Tree[i].reserve(((space + (1ULL << i)) / (1ULL << (i + 1))) * (BOUNDSIZE + i) / 8 + 8);
188  }
189 
190  using Expandable::trimToFit;
191  virtual void trim(size_t space) {
192  size_t levels = lambda(space) + 1;
193  for (size_t i = 0; i < levels; i++) Tree[i].trim(((space + (1ULL << i)) / (1ULL << (i + 1))) * (BOUNDSIZE + i) / 8 + 8);
194  }
195 
196  virtual void resize(size_t space) {
197  size_t levels = lambda(space) + 1;
198  for (size_t i = 0; i < levels; i++) Tree[i].resize(((space + (1ULL << i)) / (1ULL << (i + 1))) * (BOUNDSIZE + i) / 8 + 8);
199  }
200 
201  virtual void size(size_t space) {
202  size_t levels = lambda(space) + 1;
203  for (size_t i = 0; i < levels; i++) Tree[i].size(((space + (1ULL << i)) / (1ULL << (i + 1))) * (BOUNDSIZE + i) / 8 + 8);
204  }
205 
206  virtual size_t size() const { return Size; }
207 
208  virtual size_t bitCount() const {
209  size_t ret = sizeof(*this) * 8;
210  for (size_t i = 0; i < 64; i++) ret += Tree[i].bitCount() - sizeof(Tree[i]) * 8;
211  return ret;
212  }
213 
214  private:
215  friend std::ostream &operator<<(std::ostream &os, const FenwickBitL<BOUND, AT> &ft) {
216  os.write((char *)&ft.Size, sizeof(uint64_t));
217  os.write((char *)&ft.Levels, sizeof(uint64_t));
218  for (size_t i = 0; i < ft.Levels; i++) os << ft.Tree[i];
219  return os;
220  }
221 
222  friend std::istream &operator>>(std::istream &is, FenwickBitL<BOUND, AT> &ft) {
223  is.read((char *)&ft.Size, sizeof(uint64_t));
224  is.read((char *)&ft.Levels, sizeof(uint64_t));
225  for (size_t i = 0; i < ft.Levels; i++) is >> ft.Tree[i];
226  return is;
227  }
228 };
229 
230 } // namespace sux::util
sux::util::FenwickBitL::FenwickBitL
FenwickBitL(uint64_t sequence[], size_t size)
Definition: FenwickBitL.hpp:63
sux::bitwrite_inc
void bitwrite_inc(void *const word, int from, int length, uint64_t inc)
Definition: common.hpp:315
sux::rho
int rho(uint64_t word)
Definition: common.hpp:168
sux::util::FenwickBitL::Tree
Vector< uint8_t, AT > Tree[64]
Definition: FenwickBitL.hpp:45
sux::util
Definition: Expandable.hpp:37
Vector.hpp
sux::util::Expandable::trimToFit
void trimToFit()
Definition: Expandable.hpp:93
sux::util::Expandable
Definition: Expandable.hpp:43
sux::util::SearchablePrefixSums::find
virtual size_t find(uint64_t *val)=0
sux::util::FenwickBitL
Definition: FenwickBitL.hpp:42
sux::util::FenwickBitL::Size
size_t Size
Definition: FenwickBitL.hpp:49
sux::util::FenwickBitL::BOUNDSIZE
static constexpr size_t BOUNDSIZE
Definition: FenwickBitL.hpp:44
sux::util::Vector::size
void size(size_t size)
Definition: Vector.hpp:178
SearchablePrefixSums.hpp
sux::ceil_log2_plus1
constexpr size_t ceil_log2_plus1(size_t n)
Definition: common.hpp:100
sux::util::FenwickBitL::operator<<
friend std::ostream & operator<<(std::ostream &os, const FenwickBitL< BOUND, AT > &ft)
Definition: FenwickBitL.hpp:215
sux::bitread
uint64_t bitread(const void *const word, int from, int length)
Definition: common.hpp:280
sux::clear_rho
uint64_t clear_rho(uint64_t word)
Definition: common.hpp:194
sux::util::FenwickBitL::size
virtual void size(size_t space)
Definition: FenwickBitL.hpp:201
sux::lambda
int lambda(uint64_t word)
Definition: common.hpp:178
sux::util::FenwickBitL::push
virtual void push(uint64_t val)
Definition: FenwickBitL.hpp:153
sux::util::FenwickBitL::reserve
virtual void reserve(size_t space)
Definition: FenwickBitL.hpp:185
sux::util::SearchablePrefixSums
Definition: SearchablePrefixSums.hpp:53
sux::util::FenwickBitL::pop
virtual void pop()
Definition: FenwickBitL.hpp:173
sux::util::Vector::resize
void resize(size_t size)
Definition: Vector.hpp:166
sux::util::FenwickBitL::find
virtual size_t find(uint64_t *val)
Definition: FenwickBitL.hpp:108
sux::util::FenwickBitL::Levels
size_t Levels
Definition: FenwickBitL.hpp:49
sux::util::FenwickBitL::operator>>
friend std::istream & operator>>(std::istream &is, FenwickBitL< BOUND, AT > &ft)
Definition: FenwickBitL.hpp:222
sux::util::FenwickBitL::add
virtual void add(size_t idx, int64_t inc)
Definition: FenwickBitL.hpp:97
sux::util::FenwickBitL::trim
virtual void trim(size_t space)
Definition: FenwickBitL.hpp:191
sux::mask_rho
uint64_t mask_rho(uint64_t word)
Definition: common.hpp:208
sux::util::FenwickBitL::size
virtual size_t size() const
Definition: FenwickBitL.hpp:206
sux::util::FenwickBitL::bitCount
virtual size_t bitCount() const
Definition: FenwickBitL.hpp:208
sux::util::FenwickBitL::prefix
virtual uint64_t prefix(size_t idx)
Definition: FenwickBitL.hpp:83
sux::util::FenwickBitL::FenwickBitL
FenwickBitL()
Definition: FenwickBitL.hpp:53
sux::util::Vector< uint8_t, AT >
sux::util::FenwickBitL::compFind
virtual size_t compFind(uint64_t *val)
Definition: FenwickBitL.hpp:131
sux::util::FenwickBitL::grow
virtual void grow(size_t space)
Definition: FenwickBitL.hpp:180
sux::util::SearchablePrefixSums::compFind
virtual size_t compFind(uint64_t *val)=0
sux::util::FenwickBitL::resize
virtual void resize(size_t space)
Definition: FenwickBitL.hpp:196