dynamic_bit_sequence.hpp

Go to the documentation of this file.

 
#pragma once
#include "../bp_tree/bp_tree.hpp"
#include "./bit_container.hpp"
 
#include "./bit_forward_iterator.hpp"
#include "./bit_deque_container.hpp"
#include "stool/include/light_stool.hpp"
namespace stool
{
    namespace bptree
    {
 
        template <typename CONTAINER, typename CONTAINER_ITERATOR, uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>
        class DynamicBitSequence
        {
            
            using NodePointer = bptree::BPNodePointer<CONTAINER, bool, MAX_TREE_DEGREE, true>;
            using T = uint64_t;
            using Tree = bptree::BPTree<CONTAINER, bool, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE,false, true>;
            
            static inline constexpr int DEFAULT_CONTAINER_DEGREE = 62;
            //static inline constexpr int DEFAULT_CONTAINER_DEGREE = 124;
 
        public:
            Tree tree;
 
            DynamicBitSequence(const DynamicBitSequence &) = delete;
 
            DynamicBitSequence()
            {
            }
 
            DynamicBitSequence &operator=(const DynamicBitSequence &) = delete;
 
            DynamicBitSequence(DynamicBitSequence &&) noexcept = default;
 
            DynamicBitSequence &operator=(DynamicBitSequence &&) noexcept = default;
 
        public:
 
 
            uint64_t size() const
            {
                return this->tree.size();
            }
 
            uint64_t height() const {
                return this->tree.height();
            }
 
            uint64_t size_in_bytes([[maybe_unused]] bool only_extra_bytes = false) const
            {
                return this->tree.size_in_bytes(only_extra_bytes);
            }
 
 
 
 
            bool empty() const
            {
                return this->tree.empty();
            }
 
            bool at(uint64_t pos) const
            {
                return this->tree.at(pos) & 1;
            }
 
            int64_t rank1(uint64_t i) const
            {
                if (i == 0)
                {
                    return 0;
                }
                else if (i <= this->size())
                {
                    uint64_t p = this->tree.psum(i - 1);
 
 
                    return p;
                }
                else
                {
                    assert(false);
                    throw std::range_error("Error: DynamicBitSequence::rank1()");
                }
            }
 
            int64_t rank0(uint64_t i) const
            {
                return i - this->rank1(i);
            }
 
            int64_t rank(uint64_t i, bool c) const
            {
                return c ? this->rank1(i) : this->rank0(i);
            }
 
            int64_t select1(uint64_t i) const
            {
                int64_t p = this->tree.search(i + 1);
                if (p == -1)
                {
                    return p;
                }
                else
                {
                    if (p >= (int64_t)this->size())
                    {
                        return -1;
                    }
                    else
                    {
                        return p;
                    }
                }
            }
 
            int64_t select0(uint64_t i) const
            {
                int64_t p = this->tree.select0(i);
                if (p == -1)
                {
                    return p;
                }
                else
                {
                    if (p >= (int64_t)this->size())
                    {
                        return -1;
                    }
                    else
                    {
                        return p;
                    }
                }
            }
 
            int64_t select(uint64_t i, bool c) const
            {
                return c ? this->select1(i) : this->select0(i);
            }
 
            int64_t count_c(bool c) const
            {
                uint64_t _size = this->size();
                if (_size > 0)
                {
                    return this->rank(_size, c);
                }
                else
                {
                    return 0;
                }
            }
 
            int64_t count0() const {
                uint64_t _size = this->size();
                if(_size > 0){
                    return this->rank0(_size);
                }else{
                    return 0;
                }
            }
            int64_t count1() const{
                uint64_t _size = this->size();
                if(_size > 0){
                    return this->rank1(_size);
                }else{
                    return 0;
                }
            }
 
            bool operator[](uint64_t n) const
            {
                return this->at(n);
            }
 
            uint64_t psum(uint64_t x) const
            {
                return this->tree.psum(x);
            }
 
            uint64_t psum() const
            {
                return this->tree.psum();
            }
 
            int64_t search(uint64_t sum) const
            {
                return this->tree.search(sum);
            }
 
 
 
 
            void set_degree(uint64_t degree)
            {
                this->tree.initialize(degree, DynamicBitSequence::DEFAULT_CONTAINER_DEGREE);
            }
 
            void swap(DynamicBitSequence &item)
            {
                this->tree.swap(item.tree);
            }
 
            void clear()
            {
                this->tree.clear();
            }
 
            void push_back(bool value)
            {
#if DEBUG
                uint64_t p = this->size();
#endif
                this->tree.push_back(value);
#if DEBUG
                assert(p + 1 == this->size());
#endif
            }
 
            void push_front(bool value)
            {
                this->tree.push_front(value);
            }
 
            void insert(uint64_t pos, bool value)
            {
                this->tree.insert(pos, value, value);
            }
 
            void remove(uint64_t pos)
            {
                assert(pos < this->size());
                this->tree.remove(pos);
            }
 
            void set_bit(uint64_t i, bool b)
            {
                bool b1 = this->at(i);
                if (b != b1)
                {
                    if (b)
                    {
                        this->tree.increment(i, 1);
                    }
                    else
                    {
                        this->tree.increment(i, -1);
                    }
                }
            }
 
            void set_bits(uint64_t i, std::vector<bool> &bits){
                for(uint64_t j = 0; j < bits.size(); j++){
                    this->set_bit(i + j, bits[j]);
                }
            }
 
            void sort_leaf_containers()
            {
                bool b = this->tree.check_if_leaf_container_vec_is_sorted();
                if (!b)
                {
                    std::cout << "unsorted" << std::endl;
                    this->tree.sort_leaf_containers();
                }
            }
 
            void push_many(const std::vector<bool> &items)
            {
                this->tree.push_many(items);
            }
 
            void print_debug_info() const{
                std::cout << "DynamicBitSequence::print_debug_info()" << std::endl;
                this->tree.print_debug_info();
            }
 
 
 
 
            std::vector<std::string> get_memory_usage_info(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::vector<std::string> log1 = this->tree.get_memory_usage_info(message_paragraph + 1);
 
                std::vector<std::string> r;
                uint64_t size_in_bytes = this->size_in_bytes();
                uint64_t size = this->size();
                double bits_per_element = size > 0 ? ((double)size_in_bytes / (double)size) : 0;
 
                r.push_back(stool::Message::get_paragraph_string(message_paragraph) + "=DynamicBitSequence: " + std::to_string(this->size_in_bytes()) 
                + " bytes, " + std::to_string(size) + " elements, " + std::to_string(bits_per_element)  + " bytes per element =");
                for (std::string &s : log1)
                {
                    r.push_back(s);
                }
                r.push_back(stool::Message::get_paragraph_string(message_paragraph) + "==");
                return r;
            }
 
            void print_memory_usage(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::vector<std::string> log = this->get_memory_usage_info(message_paragraph);
                for (std::string &s : log)
                {
                    std::cout << s << std::endl;
                }
            }
 
            void print_statistics(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Statistics(DynamicBitSequence):" << std::endl;
                this->tree.print_statistics(message_paragraph + 1);
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "[END]" << std::endl;
            }
 
            void print_content(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Content(DynamicBitSequence):" << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "Bits: " << this->to_string() << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "[END]" << std::endl;
            }
 
            void print(std::string name = "DynamicBitSequence", int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << name << ": " << this->to_string() << std::endl;
            }
 
 
 
            std::vector<uint64_t> to_value_vector() const
            {
                auto vec = this->tree.to_value_vector();
                std::vector<uint64_t> r;
                r.resize(vec.size());
                for (uint64_t i = 0; i < vec.size(); i++)
                {
                    r[i] = vec[i];
                }
                return r;
            }
 
            std::string to_string() const
            {
                std::string s;
                std::vector<uint64_t> bits = this->to_value_vector();
                s.push_back('[');
                for (uint64_t i = 0; i < bits.size(); i++)
                {
                    s.push_back(bits[i] >= 1 ? '1' : '0');
                    //assert(bits[i] == this->at(i));
                }
                s.push_back(']');
                return s;
            }
 
            std::vector<bool> to_vector() const
            {
                uint64_t _size = this->size();
                std::vector<bool> r;
                r.resize(_size, false);
                uint64_t counter = 0;
 
 
 
 
                auto _end = this->get_leaf_forward_iterator_end();
 
                BitForwardIterator<CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE> it = this->get_bit_forward_iterator_begin();
                while(!it.is_end()){
                    uint64_t bits = *it;
                    uint64_t i = 0;
 
                    while (i < 64 && counter < _size)
                    {
                        bool b = stool::MSBByte::get_bit(bits, i);
                        r[counter] = b;
 
                        
                        counter++;
                        i++;
                    }
                    ++it;
 
                }
 
                /*
                for (BitForwardIterator<CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE> it = this->get_bit_forward_iterator_begin(); it != _end; ++it)
                {
                    
                    uint64_t bits = *it;
                    uint64_t i = 0;
 
 
                    while (i < 64 && counter < _size)
                    {
                        bool b = stool::MSBByte::get_bit(bits, i);
                        r[counter] = b;
 
                        
                        counter++;
                        i++;
                    }
                }
                */
                assert(counter == _size);
                return r;
            }
 
 
 
            static void store_to_bytes(DynamicBitSequence &item, std::vector<uint8_t> &output, uint64_t &pos)
            {
                Tree::store_to_bytes(item.tree, output, pos);
            }
 
            static void store_to_file(DynamicBitSequence &item, std::ofstream &os)
            {
                Tree::store_to_file(item.tree, os);
            }
 
            static DynamicBitSequence build(const std::vector<bool> &items)
            {
                DynamicBitSequence r;
                r.tree.initialize();
                r.tree.build(items);
                return r;
            }
 
 
            static DynamicBitSequence load_from_bytes(const std::vector<uint8_t> &data, uint64_t &pos)
            {
                DynamicBitSequence r;
                r.tree.load_from_bytes(data, pos);
                return r;
            }
 
            static DynamicBitSequence load_from_file(std::ifstream &ifs)
            {
                DynamicBitSequence r;
                r.tree.load_from_file(ifs);
                return r;
            }
 
 
 
            BitForwardIterator<CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE> get_bit_forward_iterator_begin() const
            {
                auto leaf_it = this->tree.get_leaf_forward_iterator_begin();
                return BitForwardIterator<CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE>(&leaf_it, &this->tree);
            }
 
            BitForwardIterator<CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE> get_leaf_forward_iterator_end() const
            {
                return BitForwardIterator<CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE>(nullptr, &this->tree);
            }
 
 
 
            static std::string name()
            {
                std::string s;
                s += "DynamicSequence(";
                s += CONTAINER::name();
                s += ")";
                return s;
            }
 
            void print_information_about_performance(int message_paragraph = stool::Message::SHOW_MESSAGE) const{
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Performance Information (DynamicSequence)[" << std::endl;                
                this->tree.print_information_about_performance(message_paragraph + 1);
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "]" << std::endl;
            }
 
            double density() const{
                return this->tree.get_value_density();
            }
 
            void verify() const{
                this->tree.verify();
            }
 
 
 
 
 
            
        };
 
        using BDC = typename stool::bptree::BitVectorContainer<10000ULL>;
 
        using DynamicBitDequeSequence = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, 1024>;
        //using SimpleDynamicBitSequence = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 8192>;
        using SimpleDynamicBitSequence = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 8192>;
 
        /*
        using DynamicBitDequeSequenceA = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 512>;
        using DynamicBitDequeSequenceB = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 1024>;
        using DynamicBitDequeSequenceC = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 2048>;
        using DynamicBitDequeSequenceD = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 4096>;
 
        using DynamicBitDequeSequence1 = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 14, 8192>;
        using DynamicBitDequeSequence2 = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 30, 8192>;
        using DynamicBitDequeSequence3 = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 62, 8192>;
        using DynamicBitDequeSequence4 = DynamicBitSequence<BDC, BDC::BitVectorContainerIterator, 126, 8192>;
        */
 
        //using DynamicBitDequeSequenceE = DynamicBitSequence<stool::bptree::BitVectorContainer, stool::bptree::BitVectorContainer::BitVectorContainerIterator, 8190, 2048>;
 
        // template <typename T>
        // using VLCDequeSeq = DynamicSequence<VLCDeque, T>;
    }
 
}