bp_tree.hpp

#pragma once
#include "./bp_tree/bp_internal_node_functions.hpp"
#include "./bp_tree/bp_postorder_iterator.hpp"
#include "./bp_tree/bp_value_forward_iterator.hpp"
#include "./bp_tree/bp_leaf_forward_iterator.hpp"
 
namespace stool
{
    namespace bptree
    {
        inline constexpr int DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE = 126;
        inline constexpr int DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF = 126;
 
        inline static uint64_t time_count2 = 0;
        inline static uint64_t time_count = 0;
 
        template <typename LEAF_CONTAINER, typename VALUE, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>
        class BPTree
        {
        public:
            using NodePointer = BPNodePointer<LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM>;
            using Node = BPInternalNode<LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM>;
            using PostorderIterator = BPPostorderIterator<LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM>;
            using ValueForwardIterator = BPValueForwardIterator<LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM>;
            using LeafForwardIterator = BPLeafForwardIterator<LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM>;
 
            using BPFunctions = BPInternalNodeFunctions<LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, MAX_DEGREE, USE_PSUM>;
 
        private:
            std::vector<LEAF_CONTAINER> leaf_container_vec;
            std::vector<Node *> parent_vec;
            std::stack<uint64_t> unused_leaf_container_indexes;
            std::vector<Node *> unused_node_pointers;
            std::vector<NodePointer> tmp_path;
 
            /*
            uint64_t _max_degree_of_internal_node = 8;
            uint64_t _max_count_of_values_in_leaf = 8;
            */
            Node *root = nullptr;
            BPTree *linked_tree_ = nullptr;
            double density_threshold = 0.5;
            uint64_t density1 = 0;
            uint16_t height_ = 0;
            bool root_is_leaf_ = false;
 
            uint64_t split_process_counter = 0;
            uint64_t insert_operation_counter = 0;
            uint64_t merge_process_counter = 0;
            uint64_t remove_operation_counter = 0;
 
        public:
 
 
            BPTree()
            {
            }
 
            BPTree(BPTree &&other) noexcept
            {
                this->leaf_container_vec = std::move(other.leaf_container_vec);
                this->parent_vec = std::move(other.parent_vec);
                this->unused_leaf_container_indexes = std::move(other.unused_leaf_container_indexes);
                this->unused_node_pointers = std::move(other.unused_node_pointers);
                this->tmp_path = std::move(other.tmp_path);
 
                // this->_max_degree_of_internal_node = other._max_degree_of_internal_node;
                // this->_max_count_of_values_in_leaf = other._max_count_of_values_in_leaf;
                this->root = other.root;
                this->linked_tree_ = other.linked_tree_;
                this->density_threshold = other.density_threshold;
                this->density1 = other.density1;
                this->height_ = other.height_;
                this->root_is_leaf_ = other.root_is_leaf_;
 
                other.leaf_container_vec.clear();
                other.parent_vec.clear();
                other.unused_node_pointers.clear();
                other.tmp_path.clear();
                while (other.unused_leaf_container_indexes.size() > 0)
                {
                    other.unused_leaf_container_indexes.pop();
                }
 
                other.root = nullptr;
                other.linked_tree_ = nullptr;
                other.height_ = 0;
                other.root_is_leaf_ = false;
            }
 
            BPTree(const BPTree &) = delete;
 
            ~BPTree()
            {
                this->clear();
            }
 
 
 
            BPTree &operator=(BPTree &&other) noexcept
            {
                if (this != &other)
                {
                    this->clear();
                    this->leaf_container_vec = std::move(other.leaf_container_vec);
                    this->parent_vec = std::move(other.parent_vec);
                    this->unused_leaf_container_indexes = std::move(other.unused_leaf_container_indexes);
                    this->unused_node_pointers = std::move(other.unused_node_pointers);
                    this->tmp_path = std::move(other.tmp_path);
 
                    // this->_max_degree_of_internal_node = other._max_degree_of_internal_node;
                    // this->_max_count_of_values_in_leaf = other._max_count_of_values_in_leaf;
                    this->root = other.root;
                    this->linked_tree_ = other.linked_tree_;
                    this->density_threshold = other.density_threshold;
                    this->density1 = other.density1;
                    this->height_ = other.height_;
                    this->root_is_leaf_ = other.root_is_leaf_;
 
                    other.leaf_container_vec.clear();
                    other.parent_vec.clear();
                    other.unused_node_pointers.clear();
                    other.tmp_path.clear();
                    while (other.unused_leaf_container_indexes.size() > 0)
                    {
                        other.unused_leaf_container_indexes.pop();
                    }
 
                    other.root = nullptr;
                    other.linked_tree_ = nullptr;
                    other.height_ = 0;
                    other.root_is_leaf_ = false;
 
                    // other->clear();
                }
                return *this;
            }
 
 
 
            PostorderIterator get_postorder_iterator_begin() const
            {
                if (this->empty())
                {
                    return PostorderIterator(nullptr);
                }
                else
                {
                    if (this->root_is_leaf_)
                    {
                        return PostorderIterator((uint64_t)this->root);
                    }
                    else
                    {
                        return PostorderIterator(this->root);
                    }
                }
            }
 
            PostorderIterator get_postorder_iterator_end() const
            {
                return PostorderIterator(nullptr);
            }
 
            ValueForwardIterator get_value_forward_iterator_begin() const
            {
                if (this->empty())
                {
                    return ValueForwardIterator(nullptr, nullptr);
                }
                else
                {
                    PostorderIterator node_it = this->get_postorder_iterator_begin();
                    return ValueForwardIterator(&node_it, &this->leaf_container_vec);
                }
            }
 
            ValueForwardIterator get_value_forward_iterator_end() const
            {
                return ValueForwardIterator(nullptr, nullptr);
            }
 
            LeafForwardIterator get_leaf_forward_iterator_begin() const
            {
                if (this->empty())
                {
                    return LeafForwardIterator(nullptr);
                }
                else
                {
                    return LeafForwardIterator(this->root);
                }
            }
 
            LeafForwardIterator get_leaf_forward_iterator_end() const
            {
                return LeafForwardIterator(nullptr);
            }
 
 
 
            const std::vector<NodePointer> &get_temporary_path() const
            {
                return this->tmp_path;
            }
 
            uint64_t get_max_degree_of_internal_node() const
            {
                return MAX_DEGREE;
            }
 
            uint64_t get_split_process_counter() const
            {
                return this->split_process_counter;
            }
            uint64_t size() const
            {
                if (this->empty())
                {
                    return 0;
                }
                else
                {
                    if (this->root_is_leaf_)
                    {
                        return this->leaf_container_vec[(uint64_t)this->root].size();
                    }
                    else
                    {
                        return this->root->psum_on_count_deque();
                    }
                }
            }
 
            uint64_t capacity() const
            {
                return (this->leaf_container_vec.size() - this->unused_leaf_container_indexes.size()) * this->get_max_count_of_values_in_leaf();
            }
 
            double get_value_density() const
            {
                return (double)this->size() / (double)this->capacity();
            }
 
            uint64_t get_max_count_of_values_in_leaf() const
            {
                return LEAF_CONTAINER_MAX_SIZE;
            }
 
            uint64_t height() const
            {
                return this->height_;
            }
 
            uint64_t get_leaf_count() const
            {
                return this->leaf_container_vec.size() - this->unused_leaf_container_indexes.size();
            }
 
            uint64_t get_leaf_container_vector_size() const
            {
                return this->leaf_container_vec.size();
            }
 
            bool empty() const
            {
                return this->height() == 0;
            }
            LEAF_CONTAINER &get_leaf_container(uint64_t i)
            {
                assert(i < this->get_leaf_container_vector_size());
 
                return this->leaf_container_vec[i];
            }
            const LEAF_CONTAINER &get_leaf_container(uint64_t i) const
            {
                return this->leaf_container_vec[i];
            }
            uint64_t size_in_bytes([[maybe_unused]] bool only_dynamic_memory = false) const
            {
                uint64_t _max_degree = MAX_DEGREE;
                uint64_t _max_count_of_values_in_leaf = LEAF_CONTAINER_MAX_SIZE;
                uint64_t _size = sizeof(_max_degree) + sizeof(_max_count_of_values_in_leaf) + LEAF_CONTAINER::get_byte_size(this->leaf_container_vec);
 
                return _size;
            }
            BPTree *get_linked_tree() const
            {
                return this->linked_tree_;
            }
 
 
 
 
            std::vector<VALUE> to_value_vector() const
            {
 
                if (!this->empty())
                {
                    if (this->root_is_leaf_)
                    {
                        std::vector<VALUE> r;
                        this->leaf_container_vec[(uint64_t)this->root].to_values(r);
                        return r;
                    }
                    else
                    {
 
                        std::vector<VALUE> r;
                        BPFunctions::to_value_vector(*this->root, r, this->leaf_container_vec);
                        return r;
                    }
                }
                else
                {
                    std::vector<VALUE> r;
                    return r;
                }
            }
 
 
 
 
            VALUE at(uint64_t i) const
            {
                if (!this->empty())
                {
                    assert(i < this->size());
                    std::vector<NodePointer> path;
 
                    uint64_t idx = this->compute_path_from_root_to_leaf(i);
 
                    assert(this->tmp_path.size() > 0);
 
                    uint64_t leaf = this->tmp_path[this->tmp_path.size() - 1].get_leaf_container_index();
 
#ifdef TIME_DEBUG
                    auto st3 = std::chrono::system_clock::now();
#endif
                    uint64_t result = this->leaf_container_vec[leaf].at(idx);
 
#ifdef TIME_DEBUG
                    auto st4 = std::chrono::system_clock::now();
                    time_count2 += std::chrono::duration_cast<std::chrono::nanoseconds>(st4 - st3).count();
#endif
 
                    return result;
                }
                else
                {
                    throw std::invalid_argument("Error: BPTree::at()");
                }
            }
 
            uint64_t get_value_index(uint64_t leaf_index_j, uint64_t position_in_leaf_container_p) const
            {
                if (USE_PARENT_FIELD)
                {
                    assert(leaf_index_j < this->parent_vec.size());
                    Node *parent = this->parent_vec[leaf_index_j];
                    uint64_t dist = position_in_leaf_container_p;
 
                    if (parent == nullptr)
                    {
                        return dist;
                    }
                    else
                    {
 
                        Node *node = (Node *)leaf_index_j;
                        while (parent != nullptr)
                        {
 
                            int64_t idx = parent->get_index(node);
                            assert(idx != -1);
 
                            if (idx > 0)
                            {
                                uint64_t sum = parent->psum_on_count_deque(idx - 1);
                                dist += sum;
                            }
                            // uint64_t sum = std::reduce(std::begin(deq), std::next(deq.begin(), idx));
 
                            node = parent;
                            parent = node->get_parent();
                        }
                        return dist;
                    }
                }
                else
                {
                    throw std::runtime_error("BPTree::get_value_index(): this function is not supported.");
                }
            }
 
            uint64_t psum() const
            {
                if (!this->empty())
                {
                    if (this->root_is_leaf_)
                    {
                        return this->leaf_container_vec[(uint64_t)this->root].psum();
                    }
                    else
                    {
                        return BPFunctions::psum(*this->root);
                    }
                }
                else
                {
                    return 0;
                }
            }
 
            uint64_t psum(uint64_t i) const
            {
                if (i >= this->size())
                {
                    throw std::invalid_argument("Error: BPTree::psum(i). The i must be less than the size of the tree.");
                }
                assert(!this->empty());
                if (!this->empty())
                {
                    if (this->root_is_leaf_)
                    {
                        return this->leaf_container_vec[(uint64_t)this->root].psum(i);
                    }
                    else
                    {
                        return BPFunctions::psum(*this->root, i, this->leaf_container_vec);
                    }
                }
                else
                {
                    throw std::runtime_error("Error:psum(i)");
                }
            }
 
            int64_t search(uint64_t u) const
            {
                if (!this->empty())
                {
                    if (this->root_is_leaf_)
                    {
                        return this->leaf_container_vec[(uint64_t)this->root].search(u);
                    }
                    else
                    {
                        return BPFunctions::search(*this->root, u, this->leaf_container_vec);
                    }
                }
                else
                {
                    return -1;
                }
            }
 
            int64_t select0(uint64_t i) const
            {
                if (!this->empty())
                {
                    if (this->root_is_leaf_)
                    {
                        return this->leaf_container_vec[(uint64_t)this->root].select0(i);
                    }
                    else
                    {
                        return BPFunctions::select0(*this->root, i, this->leaf_container_vec);
                    }
                }
                else
                {
                    return -1;
                }
            }
 
            void get_path_from_root_to_first_leaf(std::vector<NodePointer> &output_path) const
            {
                if (!this->empty())
                {
                    Node *current_node = this->root;
                    bool is_leaf = this->root_is_leaf_;
 
                    if (!is_leaf)
                    {
                        output_path.push_back(NodePointer::build_internal_node_pointer(this->root, -1));
                    }
                    else
                    {
                        output_path.push_back(NodePointer::build_leaf_pointer((uint64_t)this->root, -1));
                    }
 
                    while (!is_leaf)
                    {
                        is_leaf = current_node->is_parent_of_leaves();
                        current_node = current_node->get_child(0);
                        if (!is_leaf)
                        {
                            output_path.push_back(NodePointer::build_internal_node_pointer(current_node, 0));
                        }
                        else
                        {
                            output_path.push_back(NodePointer::build_leaf_pointer((uint64_t)current_node, 0));
                        }
                    }
                }
            }
 
            void get_path_from_root_to_last_leaf(std::vector<NodePointer> &output_path) const
            {
                if (!this->empty())
                {
                    Node *current_node = this->root;
                    bool is_leaf = this->root_is_leaf_;
 
                    if (!is_leaf)
                    {
                        output_path.push_back(NodePointer::build_internal_node_pointer(this->root, -1));
                    }
                    else
                    {
                        output_path.push_back(NodePointer::build_leaf_pointer((uint64_t)this->root, -1));
                    }
 
                    while (!is_leaf)
                    {
                        is_leaf = current_node->is_parent_of_leaves();
                        uint64_t idx = current_node->get_degree() - 1;
                        current_node = current_node->get_child(idx);
                        if (!is_leaf)
                        {
                            output_path.push_back(NodePointer::build_internal_node_pointer(current_node, idx));
                        }
                        else
                        {
                            output_path.push_back(NodePointer::build_leaf_pointer((uint64_t)current_node, idx));
                        }
                    }
                }
            }
 
            int64_t compute_path_from_root_to_leaf(uint64_t i) const
            {
                std::vector<NodePointer> &path = const_cast<std::vector<NodePointer> &>(this->tmp_path);
                return this->compute_path_from_root_to_leaf(i, path);
            }
 
            int64_t compute_path_from_root_to_leaf(uint64_t i, std::vector<NodePointer> &output_path) const
            {
                if (output_path.size() != this->height_)
                {
                    output_path.resize(this->height_);
                }
                uint64_t y = 0;
 
                if (!this->empty())
                {
 
                    Node *current_node = this->root;
                    uint64_t current_i = i;
                    bool is_leaf = this->root_is_leaf_;
 
                    // auto st1 = std::chrono::system_clock::now();
 
                    output_path[y++] = is_leaf ? NodePointer::build_leaf_pointer((uint64_t)this->root, -1) : NodePointer::build_internal_node_pointer(this->root, -1);
 
                    while (!is_leaf)
                    {
 
                        assert(current_i <= current_node->psum_on_count_deque());
 
                        // auto st1 = std::chrono::system_clock::now();
                        std::pair<int64_t, uint64_t> result = BPFunctions::access_child_index_by_value_index(*current_node, current_i);
                        // auto st2 = std::chrono::system_clock::now();
                        // time_count += std::chrono::duration_cast<std::chrono::nanoseconds>(st2 - st1).count();
 
                        if (result.first != -1)
                        {
                            is_leaf = current_node->is_parent_of_leaves();
                            current_node = current_node->get_child(result.first);
                            current_i = result.second;
                            output_path[y++] = is_leaf ? NodePointer::build_leaf_pointer((uint64_t)current_node, result.first) : NodePointer::build_internal_node_pointer(current_node, result.first);
                        }
                        else
                        {
                            throw std::runtime_error("Error: get_path_from_root_to_leaf2(1)");
                        }
                    }
                    // auto st2 = std::chrono::system_clock::now();
                    // time_count2 += std::chrono::duration_cast<std::chrono::nanoseconds>(st2 - st1).count();
 
                    assert(output_path.size() == y);
                    return current_i;
                }
                else
                {
                    return -1;
                }
            }
            bool check_if_leaf_container_vec_is_sorted() const
            {
                auto _end = this->get_leaf_forward_iterator_end();
                int64_t prev = -1;
                bool b = true;
                for (auto it = this->get_leaf_forward_iterator_begin(); it != _end; ++it)
                {
                    if (prev + 1 != (int64_t)(*it))
                    {
                        b = false;
                        break;
                    }
                    else
                    {
                        prev = *it;
                    }
                }
                return b;
            }
 
 
 
        public:
            std::vector<std::string> get_memory_usage_info(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::vector<std::string> log;
                uint64_t size_in_bytes = this->size_in_bytes();
                uint64_t size = this->size();
                double bytes_per_value = size > 0 ? ((double)size_in_bytes / (double)size) : 0;
 
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + "=BP Tree: " + std::to_string(size_in_bytes) + " bytes, " + std::to_string(size) + " values, " + std::to_string(bytes_per_value) + " bytes per value =");
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Max Degree of Internal Node: " + std::to_string(MAX_DEGREE));
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Max Count of Values in Leaf: " + std::to_string(LEAF_CONTAINER_MAX_SIZE));
                // log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " The number of values: " + std::to_string(this->size()));
 
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Internal Nodes: " + std::to_string(this->get_internal_node_memory()) + " bytes");
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Ununsed Leaf Pointers: " + std::to_string(this->get_unused_leaf_container_vector_memory()) + " bytes");
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Ununsed Node Pointers: " + std::to_string(this->get_unused_node_pointers_memory()) + " bytes");
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Leaf Vector: " + std::to_string(this->get_leaf_container_vector_memory()) + " bytes (vector capacity: " + std::to_string(this->leaf_container_vec.capacity()) + ")");
 
                uint64_t value_count = this->size();
                uint64_t leaf_total_memory = this->get_leaf_container_memory();
                uint64_t leaf_total_unused_memory = this->get_leaf_container_unused_memory();
 
                double byte_per_value = value_count > 0 ? (double)leaf_total_memory / (double)value_count : 0;
                double unused_byte_per_value = value_count > 0 ? (double)leaf_total_unused_memory / (double)value_count : 0;
 
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Leaves : " + std::to_string(leaf_total_memory) + " bytes (" + std::to_string(byte_per_value) + " bytes per value, leaf count: " + std::to_string(this->leaf_container_vec.size()) + ")");
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Unused memory for leaves : " + std::to_string(leaf_total_unused_memory) + " bytes (" + std::to_string(unused_byte_per_value) + " bytes per value)");
 
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + " Parent Vector : " + std::to_string(this->get_parent_vector_memory()) + " bytes");
                log.push_back(stool::Message::get_paragraph_string(message_paragraph) + "==");
                return log;
            }
 
            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_tree() const
            {
                std::vector<std::string> tree;
                if (!this->empty())
                {
                    if (this->root_is_leaf_)
                    {
                        tree.push_back(this->leaf_container_vec[(uint64_t)this->root].to_string());
                    }
                    else
                    {
                        BPFunctions::get_tree_string(*this->root, tree, this->leaf_container_vec);
                    }
                }
                else
                {
                    tree.push_back("[]");
                }
 
                for (int64_t i = tree.size() - 1; i >= 0; i--)
                {
                    std::cout << tree[i] << std::endl;
                }
            }
 
            void print_info(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "========= BPTREE =========" << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Height: " << this->height_ << std::endl;
 
                // uint64_t id = 0;
                for (PostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer pt = *it;
 
                    if (pt.is_leaf())
                    {
                        std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "Leaf: id = " << pt.get_leaf_container_index() << ", content = " << this->leaf_container_vec[pt.get_leaf_container_index()].to_string() << std::endl;
                    }
                    else
                    {
                        pt.get_node()->print_info(message_paragraph + 1);
                    }
                    // id++;
                }
 
                if (USE_PARENT_FIELD)
                {
                    std::vector<uint64_t> r;
                    for (Node *x : this->parent_vec)
                    {
                        r.push_back((uint64_t)x);
                    }
                    stool::DebugPrinter::print_integers(r);
                }
                std::cout << "==========================" << std::endl;
            }
 
            void print_leaves() const
            {
                // uint64_t id = 0;
                for (PostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer pt = *it;
                    if (pt.is_leaf())
                    {
                        std::cout << "leaf_index: " << pt.get_leaf_container_index() << ", " << this->leaf_container_vec[pt.get_leaf_container_index()].to_string() << std::endl;
                    }
                    // id++;
                }
            }
            void print_internal_nodes() const
            {
                std::cout << "INTERNAL NODES: " << std::endl;
                for (PostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer pt = *it;
                    if (!pt.is_leaf())
                    {
                        Node *node = (Node *)pt.get_node();
                        std::cout << " " << node->to_string() << std::endl;
                    }
                    // id++;
                }
            }
 
            void print_leaf_containers() const
            {
                std::cout << "============ LEAVES ============" << std::endl;
                for (uint64_t i = 0; i < this->leaf_container_vec.size(); i++)
                {
                    std::cout << "leaf_container_vec[" << i << "] = " << this->leaf_container_vec[i].to_string() << std::endl;
                }
                std::cout << "============ LEAVES[END] ============" << std::endl;
            }
            void print_information_about_performance(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Performance Information (BPTree)[" << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "The number of insertion operations: " << this->insert_operation_counter << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "The number of split process in insertion operations: " << this->split_process_counter << std::endl;
                if (this->insert_operation_counter > 0)
                {
                    std::cout << stool::Message::get_paragraph_string(message_paragraph) << "The number of split process per insertion: " << (double)this->split_process_counter / (double)this->insert_operation_counter << std::endl;
                }
 
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "The number of removal operations: " << this->remove_operation_counter << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "The number of merge process in removal operations: " << this->merge_process_counter << std::endl;
                if (this->remove_operation_counter > 0)
                {
                    std::cout << stool::Message::get_paragraph_string(message_paragraph) << "The number of merge process per removal: " << (double)this->merge_process_counter / (double)this->remove_operation_counter << std::endl;
                }
 
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "]" << std::endl;
            }
 
            void print_statistics(int message_paragraph = stool::Message::SHOW_MESSAGE) const
            {
                uint64_t internal_node_count = 0;
                uint64_t leaf_count = 0;
                uint64_t total_degree_of_internal_node = 0;
 
                for (BPPostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer np = *it;
                    if (!np.is_leaf())
                    {
                        internal_node_count++;
                        total_degree_of_internal_node += np.get_node()->children_count();
                    }
                    else
                    {
                        leaf_count++;
                    }
                }
 
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Statistics(BPTree):" << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The number of internal nodes: " << internal_node_count << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The number of used leaf containers: " << leaf_count << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The height of this tree: " << this->height_ << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The number of stored values: " << this->size() << std::endl;
 
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The max degree of internal node (parameter): " << MAX_DEGREE << std::endl;
                if (internal_node_count > 0)
                {
                    std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The average degree of internal node: " << (total_degree_of_internal_node / internal_node_count) << std::endl;
                }
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The max count of values in leaf (parameter): " << LEAF_CONTAINER_MAX_SIZE << std::endl;
                if (this->size() > 0)
                {
                    std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The average count of values in leaf (parameter): " << (this->size() / leaf_count) << std::endl;
                }
 
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The number of unused nodes: " << this->unused_node_pointers.size() << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The number of unused leaf containers: " << this->unused_leaf_container_indexes.size() << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The number of stored parent pointers: " << this->parent_vec.size() << std::endl;
 
                uint64_t total_memory_usage = this->size_in_bytes();
                uint64_t num = this->size();
                if (USE_PARENT_FIELD)
                {
                    total_memory_usage += this->parent_vec.size() * sizeof(Node *);
                }
                std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "Estimated memory usage: " << total_memory_usage << " bytes (Avg: " << (total_memory_usage / num) << " bytes)" << std::endl;
                std::cout << stool::Message::get_paragraph_string(message_paragraph) << "[END]" << std::endl;
            }
            void print_debug_info() const
            {
                std::cout << "BPTree::print_debug_info()" << std::endl;
                /*
                std::cout << "BPInternalNodeFunctions::time_count: " << (double)stool::__time_count / 1000000.0 << " ms" << std::endl;
                std::cout << "BPInternalNodeFunctions::time_count_counter: " << stool::__time_count_counter << std::endl;
                std::cout << "BPInternalNodeFunctions::size_count: " << stool::__size_count << std::endl;
                std::cout << "average: " << (double)stool::__time_count / stool::__time_count_counter << " ns" << std::endl;
                std::cout << "average size: " << (double)stool::__size_count / stool::__time_count_counter << " elements" << std::endl;
                */
                std::cout << "BPTree::time_count: " << (double)bptree::time_count / 1000000.0 << " ms" << std::endl;
                std::cout << "BPTree::time_count2: " << (double)bptree::time_count2 / 1000000.0 << " ms" << std::endl;
            }
            bool verify() const
            {
                bool b1 = this->verify_sub();
                if (USE_PSUM)
                {
                    if (!this->root_is_leaf_ && this->size() > 0)
                    {
                        this->verify_sum_deque(this->root);
                    }
                }
                return b1;
            }
 
 
 
        public:
            void initialize()
            {
                uint64_t __max_degree_of_internal_node = MAX_DEGREE;
                uint64_t __max_count_of_values_in_leaf = LEAF_CONTAINER_MAX_SIZE;
                if (__max_degree_of_internal_node < 4)
                {
                    throw std::runtime_error("Error: BPTree::initialize(__max_degree_of_internal_node, __max_count_of_values_in_leaf). The __max_degree_of_internal_node must be larger than 3.");
                }
                if (__max_count_of_values_in_leaf < 4)
                {
                    throw std::runtime_error("Error: BPTree::initialize(__max_degree_of_internal_node, __max_count_of_values_in_leaf). The __max_count_of_values_in_leaf must be larger than 3.");
                }
 
                this->clear();
                // this->_max_degree_of_internal_node = __max_degree_of_internal_node;
                // this->_max_count_of_values_in_leaf = __max_count_of_values_in_leaf;
                this->root = nullptr;
                this->root_is_leaf_ = false;
            }
 
            void swap(BPTree &_tree, bool swap_linked_tree = true)
            {
                this->leaf_container_vec.swap(_tree.leaf_container_vec);
                this->parent_vec.swap(_tree.parent_vec);
                this->unused_node_pointers.swap(_tree.unused_node_pointers);
                this->unused_leaf_container_indexes.swap(_tree.unused_leaf_container_indexes);
                this->tmp_path.swap(_tree.tmp_path);
                // std::swap(this->_max_degree_of_internal_node, _tree._max_degree_of_internal_node);
                // std::swap(this->_max_count_of_values_in_leaf, _tree._max_count_of_values_in_leaf);
                std::swap(this->root, _tree.root);
                if (swap_linked_tree)
                {
                    std::swap(this->linked_tree_, _tree.linked_tree_);
                }
                std::swap(this->density_threshold, _tree.density_threshold);
                std::swap(this->density1, _tree.density1);
                std::swap(this->height_, _tree.height_);
                std::swap(this->root_is_leaf_, _tree.root_is_leaf_);
            }
 
            void clear()
            {
                std::stack<Node *> nodes;
                if (!this->empty() && !this->root_is_leaf_)
                {
                    nodes.push(this->root);
                }
                while (nodes.size() > 0)
                {
                    Node *top = nodes.top();
                    nodes.pop();
                    if (!top->is_parent_of_leaves())
                    {
                        const stool::SimpleDeque16<Node *> &children = top->get_children();
                        for (Node *child : children)
                        {
                            nodes.push(child);
                        }
                    }
                    delete top;
                }
                this->root = nullptr;
                this->root_is_leaf_ = false;
                this->height_ = 0;
 
                while (unused_node_pointers.size() > 0)
                {
                    Node *top = unused_node_pointers[unused_node_pointers.size() - 1];
                    delete top;
                    unused_node_pointers.pop_back();
                }
 
                this->leaf_container_vec.resize(0);
                this->parent_vec.resize(0);
 
                while (this->unused_leaf_container_indexes.size() > 0)
                {
                    this->unused_leaf_container_indexes.pop();
                }
            }
            void push_back(VALUE value)
            {
                std::vector<VALUE> r;
                r.push_back(value);
                this->push_many(r);
            }
            void push_many(const std::vector<VALUE> &values_Q)
            {
                uint64_t i = 0;
                std::vector<NodePointer> path;
 
                while (i < values_Q.size())
                {
                    path.clear();
                    this->get_path_from_root_to_last_leaf(path);
                    if (path.size() > 0)
                    {
                        i += this->push_many_to_leaf(values_Q, i, path);
                    }
                    else
                    {
                        this->create_root_leaf(values_Q[i]);
                        i++;
                    }
                }
            }
 
            void push_front(VALUE value)
            {
                std::vector<NodePointer> path;
                this->get_path_from_root_to_first_leaf(path);
                if (path.size() > 0)
                {
                    uint64_t leaf = path[path.size() - 1].get_leaf_container_index();
                    this->leaf_container_vec[leaf].push_front(value);
 
                    uint64_t sum = this->leaf_container_vec[leaf].psum(0);
 
                    for (int64_t i = path.size() - 2; i >= 0; --i)
                    {
                        Node *parent = path[i].get_node();
                        uint64_t parent_edge_index = path[i + 1].get_parent_edge_index();
                        parent->increment(parent_edge_index, 1, sum);
                    }
                    this->balance_for_insertion(path, true);
                }
                else
                {
                    this->create_root_leaf(value);
                }
            }
 
            uint64_t remove_using_path(const std::vector<NodePointer> &path, uint64_t position_in_leaf_container_q)
            {
                uint64_t merge_counter = 0;
                uint64_t x = path[path.size() - 1].get_leaf_container_index();
                int64_t delta = leaf_container_vec[x].psum(position_in_leaf_container_q, position_in_leaf_container_q);
                leaf_container_vec[x].remove(position_in_leaf_container_q);
                for (int64_t j = path.size() - 2; j >= 0; j--)
                {
                    Node *node = path[j].get_node();
                    uint64_t child_index = path[j + 1].get_parent_edge_index();
 
                    node->increment(child_index, -1, -delta);
                }
 
                if (path.size() > 1)
                {
                    merge_counter += this->balance_for_removal(this->tmp_path);
                }
                else
                {
                    assert(path.size() == 1);
                    if (leaf_container_vec[x].size() == 0)
                    {
                        this->remove_empty_leaf((uint64_t)this->root, nullptr, -1);
                        this->root = nullptr;
                        this->root_is_leaf_ = false;
                        this->height_ = 0;
                    }
                }
                return merge_counter;
            }
 
            void remove(uint64_t i)
            {
                if (!this->empty())
                {
                    assert(i < this->size());
                    this->remove_operation_counter++;
 
                    int64_t position_to_remove = this->compute_path_from_root_to_leaf(i);
                    this->merge_process_counter += this->remove_using_path(this->tmp_path, position_to_remove);
                }
                else
                {
                    throw std::invalid_argument("Error in BPTree::remove(i). This tree is empty. i = " + std::to_string(i));
                }
            }
 
            void insert(uint64_t i, VALUE v, uint64_t weight_w)
            {
                if (i < this->size())
                {
                    if (!this->empty())
                    {
                        assert(i <= this->size());
 
                        int64_t position_to_insert = this->compute_path_from_root_to_leaf(i);
 
                        if (position_to_insert != -1)
                        {
                            uint64_t x = this->tmp_path[this->tmp_path.size() - 1].get_leaf_container_index();
 
                            this->leaf_container_vec[x].insert(position_to_insert, v);
 
                            for (int64_t j = this->tmp_path.size() - 2; j >= 0; j--)
                            {
                                Node *node = this->tmp_path[j].get_node();
                                uint64_t child_index = this->tmp_path[j + 1].get_parent_edge_index();
 
                                assert(child_index < node->children_count());
 
                                node->increment(child_index, 1, weight_w);
                            }
                            this->split_process_counter += this->balance_for_insertion(this->tmp_path);
                        }
                        else
                        {
                            throw std::runtime_error("Error: insert");
                        }
                    }
                    else
                    {
 
                        if (i == 0)
                        {
                            this->create_root_leaf(v);
                        }
                        else
                        {
                            throw std::invalid_argument("Error(BPTree::insert)");
                        }
                    }
                }
                else
                {
                    assert(i == this->size());
                    this->push_back(v);
                }
                this->insert_operation_counter++;
            }
 
            void increment(uint64_t i, int64_t delta)
            {
                uint64_t pos = this->compute_path_from_root_to_leaf(i);
                NodePointer &leaf_pointer = this->tmp_path[this->tmp_path.size() - 1];
                LEAF_CONTAINER &leaf = this->leaf_container_vec[leaf_pointer.get_leaf_container_index()];
                leaf.increment(pos, delta);
                for (int64_t i = this->tmp_path.size() - 2; i >= 0; --i)
                {
                    uint64_t idx = this->tmp_path[i + 1].get_parent_edge_index();
                    Node *parent = this->tmp_path[i].get_node();
                    parent->increment(idx, 0, delta);
                }
            }
            void resize(uint64_t _size, VALUE default_value)
            {
                if (this->size() < _size)
                {
                    uint64_t i = 0;
                    std::vector<NodePointer> path;
                    uint64_t diff = _size - this->size();
 
                    while (i < diff)
                    {
                        path.clear();
                        this->get_path_from_root_to_last_leaf(path);
                        if (path.size() > 0)
                        {
                            uint64_t leaf = path[path.size() - 1].get_leaf_container_index();
                            uint64_t len = 0;
                            while (i < diff && leaf_container_vec[leaf].size() <= this->get_max_count_of_values_in_leaf())
                            {
                                this->leaf_container_vec[leaf].push_back(default_value);
                                i++;
                                len++;
                            }
                            uint64_t sum = len > 0 ? this->leaf_container_vec[leaf].reverse_psum(len - 1) : 0;
 
                            for (int64_t j = path.size() - 2; j >= 0; --j)
                            {
                                Node *parent = path[j].get_node();
                                uint64_t parent_edge_index = path[j + 1].get_parent_edge_index();
                                parent->increment(parent_edge_index, len, sum);
                            }
                            this->balance_for_insertion(path, true);
                        }
                        else
                        {
                            this->create_root_leaf(default_value);
                            i++;
                        }
                    }
                }
                else
                {
                    while (this->size() > _size)
                    {
                        this->remove(this->size() - 1);
                    }
                }
            }
 
            void set_linked_tree(BPTree *_tree)
            {
                this->linked_tree_ = _tree;
            }
 
            void sort_leaf_containers()
            {
                if (this->size() == 0 || this->root_is_leaf_)
                {
                    return;
                }
 
                auto _end = this->get_postorder_iterator_end();
 
                if (!USE_PARENT_FIELD)
                {
                    this->parent_vec.resize(this->leaf_container_vec.size(), nullptr);
 
                    for (PostorderIterator it = this->get_postorder_iterator_begin(); it != _end; ++it)
                    {
                        NodePointer np = *it;
                        if (!np.is_leaf())
                        {
                            Node *node = np.get_node();
                            if (node->is_parent_of_leaves())
                            {
                                auto &children = node->get_children();
                                for (Node *v : children)
                                {
                                    uint64_t leaf = (uint64_t)v;
                                    this->parent_vec[leaf] = node;
                                }
                            }
                        }
                    }
                }
                uint64_t counter = 0;
 
                for (PostorderIterator it = this->get_postorder_iterator_begin(); it != _end; ++it)
                {
                    NodePointer np = *it;
                    if (!np.is_leaf())
                    {
                        Node *node = np.get_node();
                        if (node->is_parent_of_leaves())
                        {
                            uint64_t _size = node->children_count();
                            auto &children1 = node->get_children();
 
                            for (uint64_t j = 0; j < _size; j++)
                            {
                                this->exchange(children1, j, counter);
 
                                counter++;
                            }
                        }
                    }
                }
                while (this->leaf_container_vec.size() > counter)
                {
                    this->leaf_container_vec.pop_back();
                    this->parent_vec.pop_back();
                }
                while (this->unused_leaf_container_indexes.size() > 0)
                {
                    this->unused_leaf_container_indexes.pop();
                }
 
                if (!USE_PARENT_FIELD)
                {
                    std::vector<Node *> tmp;
                    this->parent_vec.swap(tmp);
                }
 
                if (this->root_is_leaf_)
                {
                    this->root = (Node *)0;
                }
 
                assert(this->check_if_leaf_container_vec_is_sorted());
            }
 
            void build(const std::vector<VALUE> &_values)
            {
                this->clear();
                this->build_sub(_values);
 
                std::vector<Node *> layer = this->build_from_leaf_containers_sub1();
                uint64_t current_height = 2;
                while (layer.size() > 0)
                {
 
                    std::vector<Node *> next_layer = this->build_from_leaf_containers_sub2(layer, current_height);
                    layer.swap(next_layer);
                    current_height++;
                }
            }
 
 
        public:
            static BPTree load_from_bytes(const std::vector<uint8_t> &data, uint64_t &pos)
            {
                BPTree r;
                r.initialize();
                uint64_t _max_degree;
                uint64_t _max_count_of_values_in_leaf;
                r.clear();
                std::memcpy(&_max_degree, data.data() + pos, sizeof(uint64_t));
                pos += sizeof(uint64_t);
                std::memcpy(&_max_count_of_values_in_leaf, data.data() + pos, sizeof(uint64_t));
                pos += sizeof(uint64_t);
 
                auto tmp = LEAF_CONTAINER::load_vector_from_bytes(data, pos);
 
                r.build_from_leaf_containers(tmp);
                return r;
            }
 
            static BPTree load_from_file(std::ifstream &ifs)
            {
                BPTree r;
                r.initialize();
                r.clear();
                uint64_t _max_degree;
                uint64_t _max_count_of_values_in_leaf;
                ifs.read((char *)(&_max_degree), sizeof(uint64_t));
                ifs.read((char *)(&_max_count_of_values_in_leaf), sizeof(uint64_t));
 
                auto tmp = LEAF_CONTAINER::load_vector_from_file(ifs);
 
                r.build_from_leaf_containers(tmp);
                return r;
            }
            static void store_to_bytes(BPTree &item, std::vector<uint8_t> &output, uint64_t &pos)
            {
                if (!item.check_if_leaf_container_vec_is_sorted())
                {
                    item.sort_leaf_containers();
                }
 
                uint64_t _max_degree = MAX_DEGREE;
                uint64_t _max_count_of_values_in_leaf = LEAF_CONTAINER_MAX_SIZE;
 
                uint64_t _size = sizeof(_max_degree) + sizeof(_max_count_of_values_in_leaf) + LEAF_CONTAINER::get_byte_size(item.leaf_container_vec);
                if (pos + _size > output.size())
                {
                    output.resize(pos + _size);
                }
 
                std::memcpy(output.data() + pos, &_max_degree, sizeof(uint64_t));
                pos += sizeof(uint64_t);
                std::memcpy(output.data() + pos, &_max_count_of_values_in_leaf, sizeof(uint64_t));
                pos += sizeof(uint64_t);
 
                LEAF_CONTAINER::store_to_bytes(item.leaf_container_vec, output, pos);
            }
 
            static void store_to_file(BPTree &item, std::ofstream &os)
            {
                if (!item.check_if_leaf_container_vec_is_sorted())
                {
                    item.sort_leaf_containers();
                }
                uint64_t _max_degree = MAX_DEGREE;
                uint64_t _max_count_of_values_in_leaf = LEAF_CONTAINER_MAX_SIZE;
 
                os.write((const char *)(&_max_degree), sizeof(uint64_t));
                os.write((const char *)(&_max_count_of_values_in_leaf), sizeof(uint64_t));
                LEAF_CONTAINER::store_to_file(item.leaf_container_vec, os);
            }
 
 
 
        private:
            void defragmentation()
            {
                std::vector<uint64_t> tmp;
                while (this->unused_leaf_container_indexes.size() > 0)
                {
                    tmp.push_back(this->unused_leaf_container_indexes.top());
                    this->unused_leaf_container_indexes.pop();
                }
 
                std::sort(tmp.begin(), tmp.end(), [](const uint64_t &lhs, const uint64_t &rhs)
                          { return lhs > rhs; });
 
                std::vector<std::pair<Node *, uint64_t>> tmp_nodes;
                {
                    std::unordered_set<uint64_t> checker2;
                    {
                        std::unordered_set<uint64_t> checker1;
                        for (uint64_t p : tmp)
                        {
                            checker1.insert(p);
                        }
 
                        for (int64_t i = this->leaf_container_vec.size() - 1; i >= 0; --i)
                        {
                            auto xs = checker1.find(i);
                            if (xs == checker1.end())
                            {
                                checker2.insert(i);
                            }
                            if (checker2.size() > tmp.size())
                            {
                                break;
                            }
                        }
                    }
 
                    for (BPPostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                    {
                        NodePointer pt = *it;
                        if (!pt.is_leaf() && pt.get_node()->is_parent_of_leaves())
                        {
                            Node *node = pt.get_node();
                            for (int64_t i = 0; i < node->children_count(); i++)
                            {
                                uint64_t x = (uint64_t)node->get_child(i);
                                auto xs = checker2.find(x);
                                if (xs != checker2.end())
                                {
                                    tmp_nodes.push_back(std::pair<Node *, uint64_t>(node, i));
                                }
                            }
                        }
                    }
                    assert(tmp_nodes.size() == checker2.size());
                }
 
                std::sort(tmp_nodes.begin(), tmp_nodes.end(), [](const std::pair<Node *, uint64_t> &lhs, const std::pair<Node *, uint64_t> &rhs)
                          { 
                    uint64_t x = (uint64_t)lhs.first->get_child(lhs.second);
                    uint64_t y = (uint64_t)rhs.first->get_child(rhs.second);
                    return x < y; });
 
                uint64_t k = 0;
                while (tmp.size() > 0 && tmp_nodes.size() > 0)
                {
                    std::pair<Node *, uint64_t> top = tmp_nodes[tmp_nodes.size() - 1];
                    uint64_t idx = (uint64_t)top.first->get_child(top.second);
                    uint64_t x = tmp[tmp.size() - 1];
                    if (x < idx)
                    {
                        top.first->move_container_index(top.second, x, this->leaf_container_vec);
                        tmp_nodes.pop_back();
                        tmp.pop_back();
                        k++;
                    }
                    else
                    {
                        tmp.pop_back();
                        k++;
                    }
                }
                this->leaf_container_vec.resize(this->leaf_container_vec.size() - k);
                /*
                //this->leaf_container_vec.shrink_to_fit();
                uint64_t gap = this->leaf_container_vec.size() * this->density_threshold;
                //this->leaf_container_vec.reserve(this->leaf_container_vec.size() + gap);
                this->density1 = gap;
                */
            }
            void clear_unused_node_pointers()
            {
                for (uint64_t i = 0; i < this->unused_node_pointers.size(); i++)
                {
                    delete this->unused_node_pointers[i];
                }
                this->unused_node_pointers.clear();
                this->unused_node_pointers.shrink_to_fit();
            }
            void create_root_leaf(VALUE value)
            {
                uint64_t p = this->get_new_container_index();
                this->leaf_container_vec[p].push_back(value);
                this->root = (Node *)p;
                this->root_is_leaf_ = true;
                this->height_++;
                if (USE_PARENT_FIELD)
                {
                    this->parent_vec[p] = nullptr;
                }
            }
 
            void remove_empty_leaf(uint64_t idx, Node *parent, int64_t child_index)
            {
                if (parent != nullptr)
                {
                    parent->remove_child(child_index);
                }
                if (USE_PARENT_FIELD)
                {
                    this->parent_vec[idx] = nullptr;
                }
                // this->height_ = 0;
                this->unused_leaf_container_indexes.push(idx);
                this->leaf_container_vec[idx].clear();
            }
 
            void remove_empty_node(Node *node, Node *parent, int64_t child_index)
            {
                // Node *parent = node->get_parent();
                if (parent != nullptr)
                {
                    parent->remove_child(child_index);
 
                    // uint64_t edge = parent->find_child_index_by_child_pointer(node);
                    // parent->remove_child(edge);
                }
                if (this->root == node)
                {
                    this->root = nullptr;
                }
 
                node->clear();
                if (this->unused_node_pointers.size() <= 4096)
                {
                    this->unused_node_pointers.push_back(node);
                }
                else
                {
                    delete node;
                }
            }
 
            uint64_t get_new_container_index()
            {
                if (this->unused_leaf_container_indexes.size() == 0)
                {
                    this->leaf_container_vec.push_back(LEAF_CONTAINER());
                    if (USE_PARENT_FIELD)
                    {
                        this->parent_vec.push_back(nullptr);
                    }
                    this->unused_leaf_container_indexes.push(this->leaf_container_vec.size() - 1);
                }
                assert(this->unused_leaf_container_indexes.size() > 0);
                uint64_t idx = this->unused_leaf_container_indexes.top();
                this->unused_leaf_container_indexes.pop();
 
                return idx;
            }
 
            Node *get_new_node_pointer()
            {
                Node *new_node = nullptr;
                if (this->unused_node_pointers.size() > 0)
                {
                    new_node = this->unused_node_pointers[this->unused_node_pointers.size() - 1];
                    this->unused_node_pointers.pop_back();
                }
                else
                {
                    new_node = new Node();
                }
 
                return new_node;
            }
 
            void split_process(const std::vector<NodePointer> &path, uint64_t t)
            {
                const NodePointer &top = path[t];
 
                Node *node = top.get_node();
                Node *_new_right_node = nullptr;
                uint64_t parent_edge_index = 0;
                if (!top.is_leaf())
                {
                    _new_right_node = this->get_new_node_pointer();
                    _new_right_node->initialize(top.get_node()->is_parent_of_leaves(), this->leaf_container_vec);
                }
                else
                {
                    _new_right_node = (Node *)this->get_new_container_index();
                }
 
                Node *_parent = nullptr;
                if (t > 0)
                {
                    _parent = path[t - 1].get_node();
                    _parent->insert_child(top.get_parent_edge_index() + 1, _new_right_node, 0, 0);
                    parent_edge_index = top.get_parent_edge_index();
                }
                else
                {
                    _parent = this->get_new_node_pointer();
                    if (top.is_leaf())
                    {
                        _parent->initialize((uint64_t)node, (uint64_t)_new_right_node, this->leaf_container_vec);
                    }
                    else
                    {
                        _parent->initialize(node, _new_right_node, this->leaf_container_vec);
                    }
                    parent_edge_index = 0;
 
                    this->root = _parent;
                    this->root_is_leaf_ = false;
                    this->height_++;
 
                    if (USE_PARENT_FIELD)
                    {
                        if (top.is_leaf())
                        {
                            this->parent_vec[(uint64_t)node] = _parent;
                        }
                        else
                        {
                            node->set_parent(_parent);
                        }
                    }
                }
                if (USE_PARENT_FIELD)
                {
                    if (top.is_leaf())
                    {
                        this->parent_vec[(uint64_t)_new_right_node] = _parent;
                    }
                    else
                    {
                        _new_right_node->set_parent(_parent);
                    }
                }
 
                this->split_node(node, _new_right_node, top.is_leaf(), _parent, parent_edge_index, this->parent_vec);
            }
 
            uint64_t balance_for_insertion(const std::vector<NodePointer> &path, bool superLeftPushMode = false)
            {
                uint64_t split_counter = 0;
                for (int64_t t = path.size() - 1; t >= 0; --t)
                {
                    const NodePointer &top = path[t];
                    uint64_t degree = top.get_degree(this->leaf_container_vec);
                    uint64_t threshold = top.is_leaf() ? LEAF_CONTAINER_MAX_SIZE : MAX_DEGREE;
                    uint64_t LR_threshold = threshold;
                    if (superLeftPushMode)
                    {
                        LR_threshold = (threshold * 3) / 4;
                    }
 
                    if (degree > threshold)
                    {
                        // this->split_process(path, t);
 
                        if (t > 0)
                        {
                            Node *parent = path[t - 1].get_node();
                            uint64_t parent_edge_index = top.get_parent_edge_index();
                            Node *leftSibling = parent_edge_index > 0 ? parent->get_child(parent_edge_index - 1) : nullptr;
                            Node *rightSibling = parent_edge_index + 1 < parent->children_count() ? parent->get_child(parent_edge_index + 1) : nullptr;
                            uint64_t leftSiblingDegree = UINT64_MAX;
                            if (parent_edge_index > 0)
                            {
                                leftSiblingDegree = top.is_leaf() ? this->leaf_container_vec[(uint64_t)leftSibling].size() : leftSibling->get_degree();
 
                                // assert(leftSiblingDegree <= threshold);
                            }
 
                            uint64_t rightSiblingDegree = UINT64_MAX;
                            if (parent_edge_index + 1 < parent->children_count())
                            {
                                rightSiblingDegree = top.is_leaf() ? this->leaf_container_vec[(uint64_t)rightSibling].size() : rightSibling->get_degree();
                                // assert(rightSiblingDegree <= threshold);
                            }
 
                            if (leftSiblingDegree < LR_threshold || rightSiblingDegree < LR_threshold)
                            {
                                if (leftSiblingDegree < LR_threshold)
                                {
                                    if (superLeftPushMode)
                                    {
                                        uint64_t diff = LR_threshold - leftSiblingDegree;
                                        this->move_values_left(leftSibling, top.get_node(), diff, top.is_leaf(), parent, parent_edge_index);
                                    }
                                    else
                                    {
                                        this->move_values_left(leftSibling, top.get_node(), 1, top.is_leaf(), parent, parent_edge_index);
                                    }
                                }
                                else
                                {
                                    this->move_values_right(top.get_node(), rightSibling, 1, top.is_leaf(), parent, parent_edge_index);
                                }
                                break;
                            }
                            else
                            {
                                this->split_process(path, t);
                                split_counter++;
                            }
                        }
                        else
                        {
                            this->split_process(path, t);
                            split_counter++;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
                return split_counter;
            }
 
            uint64_t balance_for_removal(const std::vector<NodePointer> &path)
            {
                // Node *current_node = &node;
 
                uint64_t merge_counter = 0;
 
                for (int64_t t = path.size() - 1; t >= 0; --t)
                {
                    const NodePointer &top = path[t];
                    uint64_t max_size = top.is_leaf() ? LEAF_CONTAINER_MAX_SIZE : MAX_DEGREE;
                    uint64_t threshold = max_size / 2;
 
                    uint64_t degree = top.get_degree(this->leaf_container_vec);
                    if (degree >= threshold)
                    {
                        break;
                    }
                    else
                    {
                        if (t > 0)
                        {
                            Node *parent = path[t - 1].get_node();
                            uint64_t parent_edge_index = top.get_parent_edge_index();
                            Node *leftSibling = parent_edge_index > 0 ? parent->get_child(parent_edge_index - 1) : nullptr;
                            Node *rightSibling = parent_edge_index + 1 < parent->children_count() ? parent->get_child(parent_edge_index + 1) : nullptr;
                            uint64_t leftSiblingDegree = 0;
                            if (parent_edge_index > 0)
                            {
                                leftSiblingDegree = top.is_leaf() ? this->leaf_container_vec[(uint64_t)leftSibling].size() : leftSibling->get_degree();
                            }
 
                            uint64_t rightSiblingDegree = 0;
                            if (parent_edge_index + 1 < parent->children_count())
                            {
                                rightSiblingDegree = top.is_leaf() ? this->leaf_container_vec[(uint64_t)rightSibling].size() : rightSibling->get_degree();
                            }
 
                            if (leftSiblingDegree != 0 || rightSiblingDegree != 0)
                            {
                                if (leftSiblingDegree > threshold)
                                {
                                    this->move_values_right(leftSibling, top.get_node(), 1, top.is_leaf(), parent, parent_edge_index - 1);
                                    break;
                                }
                                else if (rightSiblingDegree > threshold)
                                {
                                    this->move_values_left(top.get_node(), rightSibling, 1, top.is_leaf(), parent, parent_edge_index + 1);
                                    break;
                                }
                                else
                                {
                                    assert(leftSiblingDegree == threshold || rightSiblingDegree == threshold);
                                    if (leftSiblingDegree == threshold)
                                    {
                                        this->move_values_left(leftSibling, top.get_node(), degree, top.is_leaf(), parent, parent_edge_index);
                                        if (top.is_leaf())
                                        {
                                            this->remove_empty_leaf(top.get_leaf_container_index(), parent, parent_edge_index);
                                        }
                                        else
                                        {
                                            this->remove_empty_node(top.get_node(), parent, parent_edge_index);
                                        }
                                    }
                                    else
                                    {
                                        this->move_values_right(top.get_node(), rightSibling, degree, top.is_leaf(), parent, parent_edge_index);
                                        if (top.is_leaf())
                                        {
                                            this->remove_empty_leaf(top.get_leaf_container_index(), parent, parent_edge_index);
                                        }
                                        else
                                        {
                                            this->remove_empty_node(top.get_node(), parent, parent_edge_index);
                                        }
                                    }
                                    merge_counter++;
                                }
                            }
                            else
                            {
                                throw std::logic_error("Error(BPTree::balance_for_removal(1))");
                            }
                        }
                        else
                        {
                            assert(t == 0);
                            if (degree == 0)
                            {
                                throw std::logic_error("Error(BPTree::balance_for_removal(2))");
                            }
                            else if (degree == 1)
                            {
                                if (!this->root_is_leaf_)
                                {
 
                                    bool b = this->root->is_parent_of_leaves();
                                    Node *new_root = this->root->get_child(0);
                                    this->root->remove_child(0);
                                    this->remove_empty_node(this->root, nullptr, -1);
                                    this->root = new_root;
                                    this->root_is_leaf_ = b;
 
                                    if (USE_PARENT_FIELD)
                                    {
                                        if (b)
                                        {
                                            this->parent_vec[(uint64_t)new_root] = nullptr;
                                        }
                                        else
                                        {
                                            new_root->set_parent(nullptr);
                                        }
                                    }
                                    this->height_--;
                                }
                                break;
                            }
                            else
                            {
                                break;
                            }
                        }
                    }
                }
                return merge_counter;
            }
 
            uint64_t compute_internal_node_count() const
            {
                uint64_t counter = 0;
 
                for (BPPostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer np = *it;
                    if (!np.is_leaf())
                    {
                        counter++;
                    }
                }
                return counter;
            }
 
            uint64_t compute_leaf_container_count() const
            {
                uint64_t counter = 0;
 
                for (BPPostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer np = *it;
                    if (np.is_leaf())
                    {
                        counter++;
                    }
                }
                return counter;
            }
 
            void move_values_right(Node *left_node, Node *right_node, uint64_t len, bool is_leaf, Node *parent, int64_t parent_edge_index_of_left_node)
            {
                if (is_leaf)
                {
                    uint64_t left_leaf = (uint64_t)left_node;
                    uint64_t right_leaf = (uint64_t)right_node;
                    assert(left_leaf < this->leaf_container_vec.size());
                    assert(right_leaf < this->leaf_container_vec.size());
 
                    if constexpr (USE_PSUM)
                    {
                        if (parent != nullptr)
                        {
                            assert(this->leaf_container_vec[left_leaf].psum() == parent->access_sum_deque(parent_edge_index_of_left_node));
                            int64_t sum = len != 0 ? this->leaf_container_vec[left_leaf].reverse_psum(len - 1) : 0;
 
                            assert(sum <= (int64_t)this->leaf_container_vec[left_leaf].psum());
 
                            parent->decrement_on_sum_deque(parent_edge_index_of_left_node, sum);
                            parent->increment_on_sum_deque(parent_edge_index_of_left_node + 1, sum);
                        }
                    }
 
                    if (parent != nullptr)
                    {
                        parent->decrement_on_count_deque(parent_edge_index_of_left_node, len);
                        parent->increment_on_count_deque(parent_edge_index_of_left_node + 1, len);
                    }
                    auto items = this->leaf_container_vec[left_leaf].pop_back_many(len);
                    this->leaf_container_vec[right_leaf].push_front_many(items);
                }
                else
                {
                    BPFunctions::move_right(*left_node, *right_node, len, parent, parent_edge_index_of_left_node, this->parent_vec);
                }
            }
 
            void move_values_left(Node *left_node, Node *right_node, uint64_t len, bool is_leaf, Node *parent, int64_t parent_edge_index_of_right_node)
            {
                if (is_leaf)
                {
                    uint64_t left_leaf = (uint64_t)left_node;
                    uint64_t right_leaf = (uint64_t)right_node;
                    assert(left_leaf < this->leaf_container_vec.size());
 
                    if (USE_PSUM && parent != nullptr)
                    {
                        uint64_t sum = len != 0 ? this->leaf_container_vec[right_leaf].psum(len - 1) : 0;
                        parent->decrement_on_sum_deque(parent_edge_index_of_right_node, sum);
                        parent->increment_on_sum_deque(parent_edge_index_of_right_node - 1, sum);
                    }
 
                    if (parent != nullptr)
                    {
                        parent->decrement_on_count_deque(parent_edge_index_of_right_node, len);
                        parent->increment_on_count_deque(parent_edge_index_of_right_node - 1, len);
                    }
                    auto items = this->leaf_container_vec[right_leaf].pop_front_many(len);
                    this->leaf_container_vec[left_leaf].push_back_many(items);
                }
                else
                {
                    BPFunctions::move_left(*left_node, *right_node, len, parent, parent_edge_index_of_right_node, this->parent_vec);
                }
            }
 
            void split_node(Node *left_node, Node *right_node, bool is_leaf, Node *parent, int64_t parent_edge_index_of_left_node, [[maybe_unused]] std::vector<Node *> &parent_vec)
            {
 
                uint64_t degree = 0;
                if (is_leaf)
                {
                    degree = leaf_container_vec[(uint64_t)left_node].size();
                    assert((uint64_t)left_node < this->leaf_container_vec.size());
                    assert((uint64_t)right_node < this->leaf_container_vec.size());
                    assert(this->leaf_container_vec[(uint64_t)left_node].size() == this->get_max_count_of_values_in_leaf() + 1);
                }
                else
                {
                    degree = left_node->get_degree();
                }
                uint64_t left_len = degree / 2;
                uint64_t right_len = degree - left_len;
                this->move_values_right(left_node, right_node, right_len, is_leaf, parent, parent_edge_index_of_left_node);
            }
 
        private:
            uint64_t push_many_to_leaf(const std::vector<VALUE> &values, uint64_t value_pos, const std::vector<NodePointer> &path)
            {
                uint64_t x = 0;
                uint64_t leaf = path[path.size() - 1].get_leaf_container_index();
                uint64_t len = 0;
                while ((value_pos + x) < values.size() && leaf_container_vec[leaf].size() <= this->get_max_count_of_values_in_leaf())
                {
 
                    this->leaf_container_vec[leaf].push_back(values[value_pos + x]);
                    x++;
                    len++;
                }
 
                uint64_t sum = len > 0 ? this->leaf_container_vec[leaf].reverse_psum(len - 1) : 0;
 
                for (int64_t j = path.size() - 2; j >= 0; --j)
                {
                    Node *parent = path[j].get_node();
                    uint64_t parent_edge_index = path[j + 1].get_parent_edge_index();
                    assert(parent_edge_index < parent->children_count());
 
                    parent->increment(parent_edge_index, len, sum);
                }
 
                this->balance_for_insertion(path, true);
 
                assert(x > 0);
                return x;
            }
 
        private:
            void preprocess_for_the_exchange_of_two_leaves([[maybe_unused]] uint64_t leaf_index1, [[maybe_unused]] uint64_t leaf_index2)
            {
            }
 
            void exchange(stool::SimpleDeque16<Node *> &children1, uint64_t j, uint64_t leaf_index2)
            {
                uint64_t leaf_index1 = (uint64_t)children1[j];
                assert(this->parent_vec[leaf_index1] != nullptr);
 
                if (leaf_index1 != leaf_index2)
                {
                    this->preprocess_for_the_exchange_of_two_leaves(leaf_index1, leaf_index2);
 
                    if (this->parent_vec[leaf_index2] != nullptr)
                    {
                        auto &children2 = this->parent_vec[leaf_index2]->get_children();
                        uint64_t idx = this->parent_vec[leaf_index2]->get_index((Node *)leaf_index2);
                        this->leaf_container_vec[leaf_index2].swap(this->leaf_container_vec[leaf_index1]);
                        children1[j] = (Node *)leaf_index2;
                        children2[idx] = (Node *)leaf_index1;
                    }
                    else
                    {
                        this->leaf_container_vec[leaf_index2].swap(this->leaf_container_vec[leaf_index1]);
                        children1[j] = (Node *)leaf_index2;
                    }
 
                    Node *tmp_n = this->parent_vec[leaf_index1];
                    this->parent_vec[leaf_index1] = this->parent_vec[leaf_index2];
                    this->parent_vec[leaf_index2] = tmp_n;
                }
            }
            bool verify_sub() const
            {
                bool b = true;
                uint64_t p = 0;
                for (PostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer pt = *it;
                    if (pt.is_leaf())
                    {
                        assert(pt.get_leaf_container_index() < this->leaf_container_vec.size());
                        uint64_t size = this->leaf_container_vec[pt.get_leaf_container_index()].size();
                        if (this->root_is_leaf_ && pt.get_leaf_container_index() == (uint64_t)this->root)
                        {
                            b = b && (size > 0);
                            assert(b);
                        }
                        else
                        {
 
                            b = b && (size > 0) && ((this->get_max_count_of_values_in_leaf() / 2) <= size);
                            assert(b);
                        }
                        p += size;
                    }
                    else
                    {
                        Node *_node = pt.get_node();
                        b = b && BPFunctions::verify(*_node, this->leaf_container_vec, MAX_DEGREE, this->root == pt.get_node());
                        assert(b);
                    }
                    // std::cout << it.idx << "//" << it._st.size() << "/" << std::flush;
                }
                if (p != this->size())
                {
                    throw std::logic_error("Error(BPTree::verify)");
                }
                return b;
            }
            uint64_t get_internal_node_memory() const
            {
                uint64_t sum1 = 0;
 
                for (BPPostorderIterator it = this->get_postorder_iterator_begin(); it != this->get_postorder_iterator_end(); ++it)
                {
                    NodePointer pt = *it;
                    if (!pt.is_leaf())
                    {
                        sum1 += pt.get_node()->size_in_bytes();
                        sum1 += sizeof(Node *);
                    }
                }
                return sum1;
            }
 
            uint64_t get_unused_leaf_container_vector_memory() const
            {
                return sizeof(std::stack<uint64_t>) + (this->unused_leaf_container_indexes.size() * sizeof(uint64_t));
            }
 
            uint64_t get_leaf_container_vector_memory() const
            {
                return sizeof(std::vector<uint64_t>) + (this->leaf_container_vec.capacity() * sizeof(LEAF_CONTAINER));
            }
 
            uint64_t get_leaf_container_memory() const
            {
                uint64_t sum2 = 0;
                for (const LEAF_CONTAINER &leaf : this->leaf_container_vec)
                {
                    sum2 += leaf.size_in_bytes(true);
                }
                return sum2;
            }
 
            uint64_t get_leaf_container_unused_memory() const
            {
                uint64_t sum2 = 0;
                for (const LEAF_CONTAINER &leaf : this->leaf_container_vec)
                {
                    sum2 += leaf.unused_size_in_bytes();
                }
                return sum2;
            }
 
            uint64_t get_unused_node_pointers_memory() const
            {
                uint64_t sum6 = 0;
                for (Node *node : this->unused_node_pointers)
                {
                    sum6 += node->size_in_bytes();
                }
 
                sum6 += (sizeof(Node *) * this->unused_node_pointers.capacity()) + sizeof(std::vector<Node *>);
                return sum6;
            }
 
            uint64_t get_parent_vector_memory() const
            {
                return (sizeof(Node *) * this->parent_vec.capacity()) + sizeof(std::vector<Node *>);
            }
            void verify_sum_deque(Node *node) const
            {
                if (node->is_parent_of_leaves())
                {
                    uint64_t true_sum = 0;
                    auto &children = node->get_children();
                    for (uint64_t i = 0; i < children.size(); i++)
                    {
                        uint64_t id = (uint64_t)children[i];
                        true_sum += this->leaf_container_vec[id].psum();
                    }
                    if (true_sum != node->psum_on_sum_deque())
                    {
                        throw std::runtime_error("Error: verify_sum_deque");
                    }
                }
                else
                {
                    uint64_t true_sum = 0;
                    auto &children = node->get_children();
                    for (uint64_t i = 0; i < children.size(); i++)
                    {
                        Node *child = children[i];
                        this->verify_sum_deque(child);
                        true_sum += child->psum_on_sum_deque();
                    }
 
                    if (true_sum != node->psum_on_sum_deque())
                    {
                        throw std::runtime_error("Error: verify_sum_deque");
                    }
                }
            }
 
            std::vector<Node *> build_from_leaf_containers_sub2(std::vector<Node *> &nodes, uint64_t current_height)
            {
                assert(nodes.size() > 0);
                std::vector<Node *> r;
                if (nodes.size() == 1)
                {
                    this->root = nodes[0];
                    this->root_is_leaf_ = false;
                    this->height_ = current_height;
                }
                else if (nodes.size() <= MAX_DEGREE)
                {
 
                    Node *root = this->get_new_node_pointer();
                    root->initialize(false, this->leaf_container_vec);
                    for (uint64_t i = 0; i < nodes.size(); i++)
                    {
                        if (USE_PARENT_FIELD)
                        {
                            nodes[i]->set_parent(root);
                        }
                        uint64_t count = nodes[i]->psum_on_count_deque();
                        uint64_t sum = 0;
                        if constexpr (USE_PSUM)
                        {
                            sum = nodes[i]->psum_on_sum_deque();
                        }
                        root->append_child(nodes[i], count, sum);
                    }
                    r.push_back(root);
                }
                else
                {
                    uint64_t i = 0;
                    uint64_t counter = nodes.size();
                    uint64_t threshold = MAX_DEGREE * 2;
                    while (counter > 0)
                    {
                        uint64_t d = 0;
                        if (counter >= threshold)
                        {
                            d = MAX_DEGREE;
                        }
                        else if (counter > MAX_DEGREE)
                        {
                            d = MAX_DEGREE / 2;
                        }
                        else
                        {
                            d = counter;
                        }
                        Node *node = this->get_new_node_pointer();
                        node->initialize(false, this->leaf_container_vec);
 
                        for (uint64_t j = 0; j < d; j++)
                        {
                            if (USE_PARENT_FIELD)
                            {
                                nodes[i]->set_parent(node);
                            }
                            uint64_t count = nodes[i]->psum_on_count_deque();
                            uint64_t sum = 0;
                            if constexpr (USE_PSUM)
                            {
                                sum = nodes[i]->psum_on_sum_deque();
                            }
                            node->append_child(nodes[i], count, sum);
                            i++;
                            counter--;
                        }
                        r.push_back(node);
                    }
                }
                return r;
            }
 
            std::vector<Node *> build_from_leaf_containers_sub1()
            {
                std::vector<Node *> r;
 
                if (this->leaf_container_vec.size() == 0)
                {
                    this->root = nullptr;
                    this->root_is_leaf_ = false;
                    this->height_ = 0;
                }
                else if (this->leaf_container_vec.size() == 1)
                {
                    this->root = (Node *)0;
                    this->root_is_leaf_ = true;
                    this->height_ = 1;
                }
                else if (this->leaf_container_vec.size() <= MAX_DEGREE)
                {
                    Node *root = this->get_new_node_pointer();
                    root->initialize(true, this->leaf_container_vec);
                    for (uint64_t i = 0; i < this->leaf_container_vec.size(); i++)
                    {
                        uint64_t psum = 0;
                        if constexpr (USE_PSUM)
                        {
                            psum += this->leaf_container_vec[i].psum();
                        }
                        if (USE_PARENT_FIELD)
                        {
                            this->parent_vec[i] = root;
                        }
 
                        root->append_child((Node *)i, this->leaf_container_vec[i].size(), psum);
                    }
                    r.push_back(root);
                }
                else
                {
 
                    uint64_t i = 0;
                    uint64_t counter = this->leaf_container_vec.size();
                    uint64_t threshold = MAX_DEGREE * 2;
                    while (counter > 0)
                    {
                        uint64_t d = 0;
                        if (counter >= threshold)
                        {
                            d = MAX_DEGREE;
                        }
                        else if (counter > MAX_DEGREE)
                        {
                            d = MAX_DEGREE / 2;
                        }
                        else
                        {
                            d = counter;
                        }
                        Node *node = this->get_new_node_pointer();
                        node->initialize(true, this->leaf_container_vec);
 
                        for (uint64_t j = 0; j < d; j++)
                        {
                            uint64_t psum = 0;
                            if constexpr (USE_PSUM)
                            {
                                psum += this->leaf_container_vec[i].psum();
                            }
                            if (USE_PARENT_FIELD)
                            {
                                this->parent_vec[i] = node;
                            }
                            node->append_child((Node *)i, this->leaf_container_vec[i].size(), psum);
                            i++;
                            counter--;
                        }
                        r.push_back(node);
                    }
                }
                return r;
            }
 
            void build_sub(const std::vector<VALUE> &_values)
            {
                uint64_t i = 0;
                if (_values.size() == 0)
                {
                }
                else if (_values.size() <= LEAF_CONTAINER_MAX_SIZE)
                {
                    uint64_t leaf_index = this->get_new_container_index();
 
                    while (i < _values.size())
                    {
                        this->leaf_container_vec[leaf_index].push_back(_values[i]);
                        i++;
                    }
                }
                else
                {
                    uint64_t threshold = LEAF_CONTAINER_MAX_SIZE * 2;
                    uint64_t counter = _values.size();
 
                    while (i < _values.size())
                    {
                        uint64_t d = 0;
                        if (counter >= threshold)
                        {
                            d = LEAF_CONTAINER_MAX_SIZE;
                        }
                        else if (counter > LEAF_CONTAINER_MAX_SIZE)
                        {
                            d = LEAF_CONTAINER_MAX_SIZE / 2;
                        }
                        else
                        {
                            d = counter;
                        }
                        assert(counter >= (LEAF_CONTAINER_MAX_SIZE / 2));
 
                        uint64_t leaf_index = this->get_new_container_index();
                        for (uint64_t j = 0; j < d; j++)
                        {
                            this->leaf_container_vec[leaf_index].push_back(_values[i]);
                            i++;
                            counter--;
                        }
                    }
                }
            }
 
            void build_from_leaf_containers(std::vector<LEAF_CONTAINER> &_leaf_containers)
            {
                this->clear();
 
                this->leaf_container_vec.swap(_leaf_containers);
                if (USE_PARENT_FIELD)
                {
                    this->parent_vec.resize(this->leaf_container_vec.size(), nullptr);
                }
 
                std::vector<Node *> layer = this->build_from_leaf_containers_sub1();
                uint64_t current_height = 2;
                while (layer.size() > 0)
                {
                    std::vector<Node *> next_layer = this->build_from_leaf_containers_sub2(layer, current_height);
                    layer.swap(next_layer);
                    current_height++;
                }
            }
            /*
            void push_back_leaves(std::vector<LEAF_CONTAINER> &containers)
            {
                uint64_t i = 0;
                std::vector<NodePointer> path;
                while (i < containers.size())
                {
                    path.clear();
                    this->get_path_from_root_to_last_leaf(path);
                    if (path.size() > 1)
                    {
                        uint64_t p = this->get_new_container_index();
                        this->leaf_container_vec[p].swap(containers[i]);
                        path.pop_back();
                        this->push_back_to_internal_node(p, path);
                    }
                    else
                    {
 
                        std::vector<VALUE> tmp_values;
                        containers[i].to_values(tmp_values);
                        this->push_many(tmp_values);
                    }
                    i++;
                }
            }
                void push_back_to_internal_node(uint64_t leaf_index, const std::vector<NodePointer> &path)
            {
                Node *node = path[path.size() - 1].get_node();
                uint64_t child_count = this->leaf_container_vec[leaf_index].size();
                uint64_t child_sum = 0;
                if constexpr (USE_PSUM)
                {
                    child_sum = this->leaf_container_vec[leaf_index].psum();
                }
                node->append_child(leaf_index, child_count, child_sum);
 
                for (int64_t j = path.size() - 2; j >= 0; --j)
                {
                    Node *parent = path[j].get_node();
                    uint64_t parent_edge_index = path[j + 1].get_parent_edge_index();
                    assert(parent_edge_index < parent->children_count());
                    parent->increment(parent_edge_index, child_count, child_sum);
                }
 
                this->balance_for_insertion(path, true);
            }
            */
 
        };
    }
}