SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
rank_support_int_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.
9#ifndef INCLUDED_SDSL_RANK_SUPPORT_INT_V
10#define INCLUDED_SDSL_RANK_SUPPORT_INT_V
11
12#include <algorithm>
13#include <array>
14#include <assert.h>
15#include <iosfwd>
16#include <iterator>
17#include <stddef.h>
18#include <stdint.h>
19#include <string>
20#include <type_traits>
21#include <vector>
22
23#include <sdsl/bits.hpp>
24#include <sdsl/cereal.hpp>
25#include <sdsl/int_vector.hpp>
26#include <sdsl/io.hpp>
29#include <sdsl/util.hpp>
30
31namespace sdsl
32{
33namespace detail
34{
35
45template <typename value_t, size_t bits_per_value>
47{
48private:
49 static_assert(bits_per_value <= 64, "The maximum bit size is 64 for a value.");
50
52 static constexpr uint64_t max_size = (sizeof(uint64_t) << 3) / bits_per_value;
54 static constexpr uint64_t bit_mask = bits::lo_set[bits_per_value];
55
57 uint64_t word{};
58
59public:
61 using size_type = size_t;
62
75
85 template <typename it_t>
86 constexpr bit_compressed_word(it_t it, it_t end) noexcept
87 {
88 assign(it, end);
89 }
90
95 constexpr value_t operator[](size_t const index) const noexcept
96 {
97 assert(index < max_size);
98 uint64_t offset = index * bits_per_value;
99 return static_cast<value_t>((word >> offset) & bit_mask);
100 }
101
105 template <typename it_t>
106 constexpr void assign(it_t it, it_t end) noexcept
107 {
108 assert(static_cast<uint64_t>(std::distance(it, end)) <= max_size);
109
110 for (size_t index = 0; it != end; ++it, ++index)
111 {
112 uint64_t offset = index * bits_per_value;
113 word = (word & ~(bit_mask << offset)) | uint64_t{*it} << offset;
114 }
115 }
116
118 constexpr operator uint64_t() const noexcept
119 {
120 return word;
121 }
122
124 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, const std::string name = "") const
125 {
126 structure_tree_node * child = structure_tree::add_child(v, name, sdsl::util::class_name(*this));
127 size_type written_bytes = sdsl::serialize(word, out, child, "compressed_word");
128 structure_tree::add_size(child, written_bytes);
129 return written_bytes;
130 }
131
133 void load(std::istream & in)
134 {
135 sdsl::load(word, in);
136 }
137
139 template <typename archive_t>
140 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
141 {
142 ar(CEREAL_NVP(word));
143 }
144
146 template <typename archive_t>
147 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
148 {
149 ar(CEREAL_NVP(word));
150 }
151};
152} // namespace detail
153} // namespace sdsl
154
156namespace sdsl
157{
158
175template <uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
176class rank_support_int_v : public rank_support_int<alphabet_size>
177{
178private:
181
182 // Import sigma specific constants from base class.
184 using base_t::sigma;
185 using base_t::sigma_bits;
186
188 static constexpr uint64_t values_per_word{64ULL / sigma_bits};
190 static constexpr uint64_t values_per_block{words_per_block * values_per_word};
192 static constexpr uint64_t values_per_superblock{blocks_per_superblock * values_per_block};
194 static constexpr uint64_t words_per_superblock{words_per_block * blocks_per_superblock};
196 static constexpr uint64_t effective_alphabet_size = alphabet_size - 1;
197
198 struct superblock_entry;
199
201 std::vector<superblock_entry> superblocks{};
203 typename base_t::size_type text_size{};
204
205public:
207 using typename base_t::size_type;
209 using typename base_t::value_type;
210
220 explicit rank_support_int_v(int_vector<> const * text_ptr = nullptr) : rank_support_int<alphabet_size>(nullptr)
221 {
222 static_assert(blocks_per_superblock > 1, "There must be at least two blocks per superblock!");
223
224 if (text_ptr == nullptr || text_ptr->empty())
225 return;
226
227 text_size = text_ptr->size();
228
229 // NOTE: number of elements is artificially increased by one because rank can be called on m_v[size()]
230 uint64_t const word_count = (text_size + values_per_word - 1) / values_per_word;
231 size_type const superblock_count = (word_count + words_per_superblock - 1) / words_per_superblock;
232
233 // Buffers to keep track of the cumulative sums for the superblocks and blocks inside of a superblock.
234 std::array<uint64_t, effective_alphabet_size> buf_blocks{};
235 std::array<uint64_t, effective_alphabet_size> buf_superblocks{};
236
237 // Allocate memory for the superblocks.
238 superblocks.resize(superblock_count);
239
240 // Iterate over the superblock entries and initialise them.
241 auto text_slice_it = text_ptr->begin();
242 uint64_t word_id = 0; // We basically iterate over all words of the underlying text.
243 for (auto entry_it = superblocks.begin(); entry_it != superblocks.end(); ++entry_it)
244 {
245 // First initialise the superblock text.
246 for (auto & compressed_word : entry_it->superblock_text)
247 {
248 // Get the text slice that can be stored in one word.
249 auto text_slice_end =
250 std::next(text_slice_it,
251 std::min<size_t>(std::distance(text_slice_it, text_ptr->end()), values_per_word));
252 compressed_word.assign(text_slice_it, text_slice_end); // Assign text slice to compressed word.
253 text_slice_it = text_slice_end; // Set to next text slice begin.
254 }
255
256 // Second initialise the superblock counts.
257 // The rank values are stored for every symbol of the alphabet in consecutive order.
258 // The last symbol can be ignored since it's prefix sum will always be same as the prefix length.
259 auto superblock_it = entry_it->superblocks.begin(); // Store the begin of the super block in the node.
260 for (size_t letter_rank = 0; letter_rank < effective_alphabet_size; ++letter_rank, ++superblock_it)
261 {
262 buf_superblocks[letter_rank] += buf_blocks[letter_rank]; // Update sum with previous superblock
263 *superblock_it = buf_superblocks[letter_rank]; // Store the counts.
264 buf_blocks[letter_rank] = 0; // Reset the block counts for the next superblock.
265 }
266
267 // Third initialise the block counts:
268 // The stored block counts represent the cumulative sum of the previous blocks in the super block.
269 // The first block of the superblock is not stored explicitly since it has no predecessor.
270 // A block stores the counts for the letters consecutive in memory from [0..max_letter] and starts then the
271 // next block at offset `i * effective_alphabet_size`, where `i` is the current block id.
272 // TODO: Make the implementation safe for multiple words per block
273 auto text_it = entry_it->superblock_text.begin();
274 for (auto block_it = entry_it->blocks.begin(); word_id < word_count && block_it != entry_it->blocks.end();
275 ++word_id, ++text_it)
276 {
277 // Get the prefix ranks for the current word for each letter and store them in the respective block
278 for (size_t letter_rank = 0; letter_rank < effective_alphabet_size; ++letter_rank, ++block_it)
279 {
280 buf_blocks[letter_rank] += base_t::full_word_prefix_rank(*text_it, letter_rank);
281 *block_it = buf_blocks[letter_rank];
282 }
283 }
284
285 // Count the last block which is not stored explicitly.
286 if (word_id < word_count)
287 {
288 for (uint64_t letter = 0; letter < effective_alphabet_size; ++letter)
289 buf_blocks[letter] += base_t::full_word_prefix_rank(*text_it, letter);
290
291 ++word_id;
292 }
293 }
294 }
295
306
313 size_type rank(const size_type position, const value_type v) const
314 {
315 switch (v)
316 {
317 case 0:
318 return prefix_rank_impl<false>(position, v);
319 case sigma - 1:
320 return position - prefix_rank_impl<false>(position, v - 1);
321 default:
322 return prefix_rank_impl<true>(position, v);
323 }
324 }
325
327 inline size_type operator()(const size_type position, const value_type v) const
328 {
329 return rank(position, v);
330 }
331
338 size_type prefix_rank(const size_type position, const value_type v) const
339 {
340 assert(position <= text_size);
341 assert(v <= sigma);
342
343 if (unlikely(v == sigma - 1))
344 return position;
345
346 return prefix_rank_impl<false>(position, v);
347 // TODO: Enable me!
348 // compute in-block queries for all words before the in-block queries
349 // this only applies when multiple words are in one block
350 // if constexpr (words_per_block > 1)
351 // {
352 // size_type const word_id{idx / values_per_word};
353 // uint64_t w{word_id - (word_id % words_per_block)};
354 // while (w < word_id)
355 // {
356 // res += this->full_word_prefix_rank(this->m_v->data(), w, v);
357 // ++w;
358 // }
359 // // std::cout << "res3=" << res << '\n';
360 // }
361 }
362
365 {
366 return text_size;
367 }
368
372 value_type value_at(const size_type position) const
373 {
374 assert(position < text_size);
375 return superblocks[to_superblock_position(position)].value_at(position);
376 }
377
379 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, const std::string name = "") const
380 {
381 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
382 size_type written_bytes = sdsl::serialize(superblocks, out, child, "superblocks_vector");
383 written_bytes += write_member(text_size, out, child, "text_size");
384 structure_tree::add_size(child, written_bytes);
385 return written_bytes;
386 }
387
389 void load(std::istream & in, int_vector<> const * /*v*/)
390 {
391 this->m_v = nullptr;
392 sdsl::load(superblocks, in);
393 read_member(text_size, in);
394 }
395
397 friend bool operator==(rank_support_int_v const & lhs, rank_support_int_v const & rhs) noexcept
398 {
399 return (lhs.superblocks == rhs.superblocks) && (lhs.text_size == rhs.text_size);
400 }
401
403 friend bool operator!=(rank_support_int_v const & lhs, rank_support_int_v const & rhs) noexcept
404 {
405 return !(lhs == rhs);
406 }
407
409 template <typename archive_t>
410 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
411 {
412 ar(CEREAL_NVP(superblocks));
413 ar(CEREAL_NVP(text_size));
414 }
415
417 template <typename archive_t>
418 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
419 {
420 ar(CEREAL_NVP(superblocks));
421 ar(CEREAL_NVP(text_size));
422 }
423
425 void set_vector(int_vector<> const * /*other_text*/)
426 {} // TODO: Check where this interface is needed, since it is dangerous?
427 // I would be able to reset the text without recomputing the rank support structure which is in general a
428 // bad design.
429
430private:
435 constexpr size_type to_superblock_position(size_t const position) const noexcept
436 {
437 return position / values_per_superblock;
438 }
439
445 template <bool compute_prefix_delta>
446 size_type prefix_rank_impl(size_type const position, const value_type v) const
447 {
448 assert(position <= text_size);
449
450 if (unlikely(text_size == 0)) // TODO: Maybe there could be some logic in the constructor for this case?
451 return 0;
452
453 superblock_entry const & entry = superblocks[to_superblock_position(position)];
454 return entry.template superblock_rank<compute_prefix_delta>(v)
455 + entry.template block_rank<compute_prefix_delta>(position, v)
456 + entry.template in_block_rank<compute_prefix_delta>(position, v);
457
458 // TODO: Enable me!
459 // if constexpr (words_per_block > 1)
460 // {
461 // size_type const word_id{position / values_per_word};
462 // uint64_t w{word_id - (word_id % words_per_block)};
463 // while (w < word_id)
464 // {
465 // res_upper += this->full_word_prefix_rank(this->m_v->data(), w, v);
466 // res_lower += this->full_word_prefix_rank(this->m_v->data(), w, v - 1);
467 // ++w;
468 // }
469 // }
470 }
471};
472
483template <uint8_t alphabet_size, uint8_t words_per_block, uint8_t blocks_per_superblock>
484struct rank_support_int_v<alphabet_size, words_per_block, blocks_per_superblock>::superblock_entry
485{
486 using size_type = typename base_t::size_type;
488 static constexpr size_t block_offset = effective_alphabet_size;
490 static constexpr size_t bits_per_block_value = ceil_log2(values_per_superblock);
492 using block_value_type = std::conditional_t<bits_per_block_value <= 8,
493 uint8_t,
494 std::conditional_t<bits_per_block_value <= 16, uint16_t, uint32_t>>;
495
497 std::array<uint64_t, (alphabet_size - 1)> superblocks;
499 std::array<block_value_type, (blocks_per_superblock - 1) * (alphabet_size - 1)> blocks;
501 std::array<detail::bit_compressed_word<uint8_t, sigma_bits>, words_per_superblock> superblock_text;
502
508 template <bool compute_prefix_delta>
509 constexpr size_type superblock_rank(value_type const v) const noexcept
510 {
511 return superblocks[v] - ((compute_prefix_delta) ? superblocks[v - 1] : 0);
512 }
513
525 template <bool compute_prefix_delta>
526 constexpr size_type block_rank(size_t const position, value_type const v) const noexcept
527 {
528 size_type const block_id = block_position_in_superblock(position);
529 size_type const block_position = absolute_block_position(block_id) + v;
530 return (block_id != 0) * (blocks[block_position] - ((compute_prefix_delta) ? blocks[block_position - 1] : 0));
531 }
532
543 template <bool compute_prefix_delta>
544 constexpr size_type in_block_rank(size_t const position, value_type const v) const noexcept
545 {
546 // First, get the local bit position within the data of the super block.
547 size_type const bit_pos = absolute_bit_position(position);
548 // Second, compute the word that contains this value.
549 uint64_t const word = superblock_text[absolute_word_position(bit_pos)];
550 // Third, compute the in-block rank given the current word.
551 return (position % values_per_block != 0) * word_prefix_rank<compute_prefix_delta>(word, bit_pos, v);
552 }
553
557 value_type value_at(size_type position) const noexcept
558 {
559 size_type bit_position = absolute_bit_position(position);
560 return superblock_text[absolute_word_position(bit_position)][position % values_per_word];
561 }
562
564 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, const std::string name = "") const
565 {
566 structure_tree_node * child = structure_tree::add_child(v, name, sdsl::util::class_name(*this));
567 size_type written_bytes = 0;
568 written_bytes += sdsl::serialize(superblocks.size(), out, child, "prefix_superblock_counts");
569 for (auto const & x : superblocks)
570 written_bytes += sdsl::serialize(x, out, child, "[]");
571
572 written_bytes += sdsl::serialize(blocks.size(), out, child, "prefix_block_counts");
573 for (auto const & x : blocks)
574 written_bytes += sdsl::serialize(x, out, child, "[]");
575
576 written_bytes += sdsl::serialize(superblock_text.size(), out, child, "superblock_text");
577 for (auto const & x : superblock_text)
578 written_bytes += sdsl::serialize(x, out, child, "[]");
579
580 structure_tree::add_size(child, written_bytes);
581 return written_bytes;
582 }
583
585 void load(std::istream & in)
586 {
587 size_type array_size;
588 sdsl::load(array_size, in);
589 assert(array_size == superblocks.size());
590 for (size_type idx = 0; idx < array_size; ++idx)
591 sdsl::load(superblocks[idx], in);
592
593 sdsl::load(array_size, in);
594 assert(array_size == blocks.size());
595 for (size_type idx = 0; idx < array_size; ++idx)
596 sdsl::load(blocks[idx], in);
597
598 sdsl::load(array_size, in);
599 assert(array_size == superblock_text.size());
600 for (size_type idx = 0; idx < array_size; ++idx)
601 sdsl::load(superblock_text[idx], in);
602 }
603
605 friend bool operator==(superblock_entry const & lhs, superblock_entry const & rhs) noexcept
606 {
607 return (lhs.superblocks == rhs.superblocks) && (lhs.blocks == rhs.blocks)
608 && (lhs.superblock_text == rhs.superblock_text);
609 }
610
612 friend bool operator!=(superblock_entry const & lhs, superblock_entry const & rhs) noexcept
613 {
614 return !(lhs == rhs);
615 }
616
618 template <typename archive_t>
619 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
620 {
621 ar(CEREAL_NVP(superblocks));
622 ar(CEREAL_NVP(blocks));
623 ar(CEREAL_NVP(superblock_text));
624 }
625
627 template <typename archive_t>
628 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
629 {
630 ar(CEREAL_NVP(superblocks));
631 ar(CEREAL_NVP(blocks));
632 ar(CEREAL_NVP(superblock_text));
633 }
634
635private:
637 static constexpr size_type block_position_in_superblock(size_t const position) noexcept
638 { // if constexpr (blocks_per_superblock power of 2)
639 return (position / values_per_block) % blocks_per_superblock;
640 }
641
643 static constexpr size_type absolute_block_position(size_t const block_position) noexcept
644 {
645 return (block_position + (block_position == 0) - 1) * block_offset;
646 }
647
649 static constexpr size_type absolute_bit_position(size_t const position) noexcept
650 {
651 return (position % values_per_superblock) * sigma_bits;
652 }
653
655 static constexpr size_type absolute_word_position(size_t const bit_position) noexcept
656 { // We don't care if it overflows as we protect against it later.
657 return bit_position / bits_per_word;
658 }
659
661 template <bool compute_prefix_delta>
662 static constexpr auto word_prefix_rank(const uint64_t word, const uint64_t bit_pos, const value_type v) ->
663 typename std::enable_if<compute_prefix_delta, size_type>::type
664 {
665 auto && prefix_rank = base_t::word_prefix_rank(word, bit_pos, v - 1, v);
666 return prefix_rank[1] - prefix_rank[0];
667 }
668
670 template <bool compute_prefix_delta>
671 static constexpr auto word_prefix_rank(const uint64_t word, const uint64_t bit_pos, const value_type v) ->
672 typename std::enable_if<!compute_prefix_delta, size_type>::type
673 {
674 return base_t::word_prefix_rank(word, bit_pos, v)[0];
675 }
676};
677
678} // end namespace sdsl
679
680#endif // end file
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
void load(std::istream &in)
Loads from the stream.
bit_compressed_word(bit_compressed_word const &)=default
The copy constructor.
bit_compressed_word()=default
The default constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
Saves to the stream.
bit_compressed_word & operator=(bit_compressed_word &&)=default
The move assignment.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Saves to the archive.
constexpr void assign(it_t it, it_t end) noexcept
Assigns a range to the word.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Loads from the archive.
constexpr value_t operator[](size_t const index) const noexcept
Extracts the value from the given index.
~bit_compressed_word()=default
The destructor.
constexpr bit_compressed_word(it_t it, it_t end) noexcept
Constructs from a range of values.
bit_compressed_word(bit_compressed_word &&)=default
The move constructor.
bit_compressed_word & operator=(bit_compressed_word const &)=default
The copy assignment.
size_t size_type
The size type needed for serialisation.
A generic vector class for integers of width .
Definition io.hpp:36
A rank structure proposed by Christopher Pockrandt.
void load(std::istream &in, int_vector<> const *)
Loads from the stream.
int_vector ::value_type value_type
rank_support_int_v(rank_support_int_v &&)=default
Defaulted move constructor.
size_type rank(const size_type position, const value_type v) const
Counts the occurrences of v in the prefix [0..idx-1].
void set_vector(int_vector<> const *)
Does nothing for the rank_support_int structure.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Loads from the archive.
size_type operator()(const size_type position, const value_type v) const
Alias for rank(position, v)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
Saves to the stream.
rank_support_int_v(rank_support_int_v const &)=default
Defaulted copy constructor.
friend bool operator==(rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept
Equality operator.
rank_support_int_v & operator=(rank_support_int_v &&)=default
Defaulted move assignment.
~rank_support_int_v()=default
Defaulted destructor.
size_type prefix_rank(const size_type position, const value_type v) const
Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].
size_type size() const
Returns the size of the original text.
friend bool operator!=(rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept
Inequality operator.
value_type value_at(const size_type position) const
Returns the text value at the given position.
rank_support_int_v(int_vector<> const *text_ptr=nullptr)
Constructs and initialises the rank support structure for the given text.
rank_support_int_v & operator=(rank_support_int_v const &)=default
Defaulted copy assignment.
int_vector ::size_type size_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Saves to the archive.
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.
int_vector ::value_type value_type
static constexpr uint8_t sigma_bits
static constexpr uint8_t sigma
static constexpr uint8_t bits_per_word
static constexpr uint32_t full_word_prefix_rank(const uint64_t word, const value_type v) noexcept
Counts the occurrences of v in the word starting at data up to position idx.
int_vector ::size_type size_type
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
constexpr size_t ceil_log2(size_t const n)
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
Definition io.hpp:160
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize(X const &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:139
rank_support_int.hpp contains classes that support a sdsl::int_vector with constant time rank informa...
#define unlikely(x)
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition bits.hpp:194
Stores a superblock entry in a cache friendly pattern.
value_type value_at(size_type position) const noexcept
Extracts the value at the given position.
std::array< detail::bit_compressed_word< uint8_t, sigma_bits >, words_per_superblock > superblock_text
The array storing the bit compressed text.
typename base_t::size_type size_type
friend bool operator==(superblock_entry const &lhs, superblock_entry const &rhs) noexcept
Equality operator.
std::array< block_value_type,(blocks_per_superblock - 1) *(alphabet_size - 1)> blocks
The array storing the block values.
constexpr size_type superblock_rank(value_type const v) const noexcept
Returns the rank value from the superblock.
std::conditional_t< bits_per_block_value<=8, uint8_t, std::conditional_t< bits_per_block_value<=16, uint16_t, uint32_t > > block_value_type
The smallest integer type needed to store the block ranks.
constexpr size_type block_rank(size_t const position, value_type const v) const noexcept
Returns the rank value from the block.
void load(std::istream &in)
Loads from the stream.
constexpr size_type in_block_rank(size_t const position, value_type const v) const noexcept
Returns the rank value from the in-block query.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Loads from the archive.
friend bool operator!=(superblock_entry const &lhs, superblock_entry const &rhs) noexcept
Inequality operator.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Saves to the archive.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
Saves to the stream.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.