Tree.hpp

Go to the documentation of this file.

/**--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants 
Licensee a limited, non-exclusive, non-transferable, royalty-free license 
(without the right to sublicense) to use the API solely for the purpose of 
Licensee's internal development efforts to develop applications for which 
the API was provided.
 
The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: Tree
File: Tree
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/TreeIterator.h>
#include <NDEVR/Node.h>
#include <NDEVR/BaseValues.h>
#include <NDEVR/Buffer.h>
#include <NDEVR/Bounds.h>
#include <NDEVR/ProgressInfo.h>
#include <NDEVR/Vector.h>
#include <NDEVR/VectorFunctions.h>
#include <NDEVR/Intersection.h>
#include <NDEVR/BinaryHeap.h>
 
 
namespace NDEVR
{
    class TreeObject
    {
 
    };
 
    template<class t_node_type, class t_type, uint01 t_node_child_size>
    class TreeBase : public TreeObject
    {
        static_assert(std::is_base_of<TreeNode, t_node_type>::value, "t_node_type must inherit from Node");
    protected:
        explicit TreeBase(uint04 bucket_size)
            : m_indices(bucket_size)
            , m_nodes(1, t_node_type(0))
            , m_bucket_size(bucket_size)
        {
            m_indices.addSpace<false>(bucket_size);
        }
        TreeBase(const TreeBase& tree)
            : m_indices(tree.m_indices)
            , m_nodes(tree.m_nodes)
            , m_available_node_positions(tree.m_available_node_positions)
            , m_available_indexed_positions(tree.m_available_indexed_positions)
            , m_bucket_size(tree.m_bucket_size)
        {}
        TreeBase(TreeBase&& tree)
            : m_indices()
            , m_nodes()
            , m_available_node_positions()
            , m_available_indexed_positions()
            , m_bucket_size(tree.m_bucket_size)
        {
            std::swap(m_indices, tree.m_indices);
            std::swap(m_nodes, tree.m_nodes);
            std::swap(m_available_node_positions, tree.m_available_node_positions);
            std::swap(m_available_indexed_positions, tree.m_available_indexed_positions);
        }
        TreeBase(const Buffer<t_node_type>& nodes, const Buffer<uint04>& indices, bool is_read_only)
            : m_indices(indices)
            , m_nodes(nodes)
            , m_available_node_positions()
            , m_available_indexed_positions()
        {
            UNUSED(is_read_only);
        }
        virtual ~TreeBase(){}
    public:
        uint04 getIndex(uint04 index) const { return m_indices[index]; }
        void clear()
        {
            m_indices.clear();
            m_indices.addSpace<false>(m_bucket_size);
            m_nodes.clear();
            m_nodes.add(t_node_type(0));
            m_available_node_positions.clear();
            m_available_indexed_positions.clear();
        }
 
        uint04 getNumberOfNodes() const
        {
            return m_nodes.size();
        }
        const t_node_type& getNode(uint04 node_id) const
        {
            return m_nodes[node_id];
        }
 
        void removeIndices(const Buffer<bool>& deletion_indices)
        {
            Buffer<uint04> new_indices(deletion_indices.size());
            uint04 index = 0;
            for (uint04 i = 0; i < deletion_indices.size(); i++)
            {
                new_indices.add(index);
                if (!deletion_indices[i])
                    index++;
            }
            TreeIterator iterator(root_node);
            while (iterator.valid())
            {
                uint04 node_index = iterator.get();
                t_node_type& node = m_nodes[node_index];
                iterator.pop();
                if (node.isLeaf())
                {
                    const uint04 end = node.end();
                    for (uint04 i = node.begin(); i < end; i++)
                    {
                        lib_assert(!deletion_indices[m_indices[i]], "Must Call remove values prior to removeIndices");
                        m_indices[i] = new_indices[m_indices[i]];
                    }
                }
                else
                {
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
                }
            }
        }
 
        void removeIndices(uint04 begin, uint04 end)
        {
            uint04 size = end - begin;
            TreeIterator iterator(root_node);
            while (iterator.valid())
            {
                uint04 node_index = iterator.get();
                t_node_type& node = m_nodes[node_index];
                iterator.pop();
                if (node.isLeaf())
                {
                    const uint04 node_end = node.end();
                    for (uint04 i = node.begin(); i < node_end; i++)
                    {
                        lib_assert(end <= m_indices[i] || begin > m_indices[i], "Must Call remove values prior to removeIndices");
                        if (m_indices[i] >= end)
                            m_indices[i] -= size;
                    }
                }
                else
                {
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
                }
            }
        }
 
 
        void addIndices(const Buffer<bool>& insertion_indices)
        {
            Buffer<uint04> index_mapping(m_indices.size());
            uint04 index = 0;
            for (uint04 i = 0; i < insertion_indices.size(); i++)
            {
                if (!insertion_indices[i])
                    index_mapping.add(index);
                index++;
            }
            lib_assert(index_mapping.size() == m_indices.size(), "Unexpected Insertion Structure");
            TreeIterator iterator(root_node);
            while (iterator.valid())
            {
                uint04 node_index = iterator.get();
                t_node_type& node = m_nodes[node_index];
                iterator.pop();
                if (node.isLeaf())
                {
                    const uint04 end = node.end();
                    for (uint04 i = node.begin(); i < end; i++)
                    {
                        m_indices[i] = index_mapping[m_indices[i]];
                    }
                }
                else
                {
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
                }
            }
        }
 
        void addIndices(uint04 begin, uint04 end)
        {
            uint04 size = end - begin;
            TreeIterator iterator(root_node);
            while (iterator.valid())
            {
                uint04 node_index = iterator.get();
                t_node_type& node = m_nodes[node_index];
                iterator.pop();
                if (node.isLeaf())
                {
                    const uint04 node_end = node.end();
                    for (uint04 i = node.begin(); i < node_end; i++)
                    {
                        if (m_indices[i] > end)
                            m_indices[i] += size;
                    }
                }
                else
                {
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
                }
            }
        }
 
        uint04 size() const
        {
            return m_nodes[root_node].size();;
        }
 
        void removeIndex(uint04 index) const
        {
            TreeIterator iterator(root_node);
            while (iterator.valid())
            {
                const t_node_type& node = m_nodes[iterator.get()];
                iterator.pop();
                if (node.isLeaf())
                {
                    uint04 end = node.end();
                    for (uint04 i = node.begin(); i < end; i++)
                    {
                        if (m_indices[index] > index)
                            --index;
                        lib_assert(index != m_indices[index], "Must Call remove value prior to removeIndex");
                    }
                }
                else
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
            }
        }
 
        template<uint01 t_dims, class t_buffer_type>
        Bounds<t_dims, t_type> _getBounds(const Buffer<uint04>& indices, const t_buffer_type& elements, uint04 start, uint04 end)
        {
            Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
            for (uint04 i = start; i < end; i++)
            {
                bounds.addToBoundingBox(elements[indices[i]]);
            }
            return bounds;
        }
 
        void addIndex(uint04 index) const
        {
            TreeIterator iterator(index);
            while (iterator.valid())
            {
                const t_node_type& node = m_nodes[iterator.get()];
                iterator.pop();
                if (node.isLeaf())
                {
                    uint04 end = node.end();
                    for (uint04 i = node.begin(); i < end; i++)
                    {
                        if (m_indices[index] >= index)
                            ++index;
                    }
                }
                else
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
            }
        }
        const Buffer<uint04>& indices() const
        {
            return m_indices;
        }
        template<class t_buffer_type>
        void sortVertices(const t_buffer_type& elements, t_buffer_type& sorted) const
        {
            sorted.setSize(indexSize());
            for (uint04 i = 0; i < m_indices.size(); ++i)
            {
                if (m_indices[i] < elements.size())
                    sorted[i] = elements[m_indices[i]];
            }
        }
    public:
        //Operators
        //-------------------
        inline TreeBase& operator=(const TreeBase& value)
        {
            m_indices = value.m_indices;//setting equal to ourselves
            m_nodes = value.m_nodes;
            m_available_node_positions = value.m_available_node_positions;
            m_available_indexed_positions = value.m_available_indexed_positions;
            return (*this);
        }
        inline TreeBase& operator=(TreeBase&& value)
        {
            std::swap(m_indices, value.m_indices);//setting equal to ourselves
            std::swap(m_nodes, value.m_nodes);
            std::swap(m_available_node_positions, value.m_available_node_positions);
            std::swap(m_available_indexed_positions, value.m_available_indexed_positions);
            return (*this);
        }
    protected:
        template<bool t_use_values>
        Buffer<uint04> prepareAddAll(const Buffer<bool>& index_values)
        {
            uint04 index_count = index_values.count(true);
            Buffer<uint04> indices(t_use_values ? index_count : index_values.size() - index_count);
            for (uint04 i = 0; i < index_values.size(); i++)
                if (t_use_values == index_values[i])
                    indices.add(i);
            return indices;
        }
        template<class t_buffer_type>
        Buffer<uint04> prepareAddAll(uint04 start_index, uint04 end_index, const t_buffer_type& elements)
        {
            Buffer<uint04> indices(end_index - start_index);
            for (uint04 i = start_index; i < end_index; i++)
            {
                if(!isNaN(elements[i]))
                    indices.add(i);
            }
            return indices;
        }
 
        uint04 getNumberOfFreeIndices()
        {
            return m_available_indexed_positions.size() * m_bucket_size;
        }
 
        uint04 getNumberOfFreeNodes()
        {
            return m_available_node_positions.size() * t_node_child_size;
        }
 
        void splitLeafNode(uint04 index)
        {
            uint04 child_node_index;
            if (m_available_node_positions.size() == 0)
            {
                child_node_index = m_nodes.size();
                m_nodes.add(t_node_type(m_nodes[index].begin()));
                for (uint04 i = 0; i < t_node_child_size - 1; ++i)
                {
                    if (m_available_indexed_positions.size() == 0)
                    {
                        m_nodes.add(t_node_type(m_indices.size()));
                        m_indices.addSpace<true>(m_bucket_size);
                    }
                    else
                    {
                        m_nodes.add(t_node_type(m_available_indexed_positions.last()));
                        m_available_indexed_positions.removeLast();
                    }
                }
            }
            else
            {
                child_node_index = m_available_node_positions.last();
                m_available_node_positions.removeLast();
 
                m_nodes[child_node_index + 0].clear(m_nodes[index].begin());
                for (uint04 i = 1; i < t_node_child_size; ++i)
                {
                    if (m_available_indexed_positions.size() == 0)
                    {
                        m_nodes[child_node_index + i].clear(m_indices.size());
                        m_indices.addSpace<true>(m_bucket_size);
                    }
                    else
                    {
                        m_nodes[child_node_index + i].clear(m_available_indexed_positions.last());
                        m_available_indexed_positions.removeLast();
                    }
                }
            }
            m_nodes[index].setChildNodeStart(child_node_index);
        }
 
        void reclaimChildren(uint04 index)
        {
            if (!m_nodes[index].isLeaf())
            {
                TreeIterator iterator(index);
                while (iterator.valid())
                {
                    uint04 i = iterator.get();
                    iterator.pop();
                    if (m_nodes[i].isLeaf())
                    {
                        lib_assert(!m_available_indexed_positions.contains(m_nodes[i].begin()), "Bad contains");
                        m_available_indexed_positions.add(m_nodes[i].begin());
                    }
                    else
                    {
                        m_available_node_positions.add(m_nodes[i].childNodeStart());
                        iterator.addAndGoToIndex(m_nodes[i].left(), m_nodes[i].right());
                    }
                }
                m_nodes[index].setBegin(m_available_indexed_positions.last());
                m_available_indexed_positions.removeLast();
            }
        }
 
        template<bool t_set_true>
        void _getAllT(const uint04& node_index, Buffer<bool>& indices) const
        {
            TreeIterator iterator(node_index);
            while (iterator.valid())
            {
                const t_node_type& node = m_nodes[iterator.get()];
                iterator.pop();
                if (node.isLeaf())
                {
                    const uint04 end = node.end();
                    for (uint04 i = node.begin(); i < end; i++)
                    {
                        indices[m_indices[i]] = t_set_true;
                    }
                }
                else
                {
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
                }
            }
        }
        template<bool t_is_presorted>
        void _getAll(const uint04& node_index, Buffer<uint04>& indices) const
        {
            TreeIterator iterator(node_index);
            while (iterator.valid())
            {
                const t_node_type& node = m_nodes[iterator.get()];
                iterator.pop();
                if (node.isLeaf())
                {
                    if constexpr (!t_is_presorted)
                    {
                        indices.addAll(m_indices.begin(node.begin()), node.size());
                    }
                    else
                    {
                        const uint04 end = node.begin() + node.size();
                        for(uint04 i = node.begin(); i < end; i++)
                            indices.add(i);
                    }
                }
                else
                    iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
            }
        }
    public:
        uint04 indexSize() const
        {
            return m_indices.size();
        }
        uint04 nodeSize() const
        {
            return m_nodes.size();
        }
    protected:
        Buffer<uint04> m_indices;
        Buffer<t_node_type, uint04, ObjectAllocator<true>> m_nodes;
        Buffer<uint04> m_available_node_positions;
        Buffer<uint04> m_available_indexed_positions;
        static const uint04 root_node = 0;
        uint04 m_bucket_size;
    };
 
    template<uint01 t_dims, class t_type, class t_child_tree>
    class Tree : public t_child_tree
    {
    protected:
        explicit Tree(uint04 bucket_size)
            : t_child_tree(bucket_size)
        {}
        Tree(const t_child_tree& tree)
            : t_child_tree(tree)
        {}
        Tree(t_child_tree&& tree)
            : t_child_tree(std::move(tree))
        {}
    public:
        void getAll(Buffer<bool>& indices) const
        {
            t_child_tree::template _getAllT<true>(t_child_tree::root_node, indices);
        }
        
        void getAll(Buffer<uint04>& indices) const
        {
            t_child_tree::template _getAll<false>(t_child_tree::root_node, indices);
        }
        template<class t_reference_type, class t_buffer_type>
        uint04 closestElement(const t_reference_type& point, const t_buffer_type& elements, t_type epsilon = cast<t_type>(0)) const
        {
            t_type max_distance = Constant<t_type>::Max;
            return closestElement(point, elements, max_distance, epsilon);
        }
        template<class t_reference_type, class t_buffer_type>
        uint04 closestElement(const t_reference_type& point, const t_buffer_type& elements, t_type& max_distance_squared, t_type epsilon = cast<t_type>(0)) const
        {
            uint04 index = Constant<uint04>::NaN;
            t_child_tree::template _getClosestElement<false>(t_child_tree::root_node, point, elements, max_distance_squared, epsilon, index);
            return index;
        }
        template<class t_reference_type, class t_buffer_type>
        uint04 closestElementPresorted(const t_reference_type& point, const t_buffer_type& elements, t_type epsilon = cast<t_type>(0)) const
        {
            t_type max_distance = Constant<t_type>::Max;
            return closestElementPresorted(point, elements, max_distance, epsilon);
        }
        template<class t_reference_type, class t_buffer_type>
        uint04 closestElementPresorted(const t_reference_type& point, const t_buffer_type& elements, t_type& max_distance_squared, t_type epsilon = cast<t_type>(0)) const
        {
            uint04 index = Constant<uint04>::NaN;
            t_child_tree::template _getClosestElement<true>(t_child_tree::root_node, point, elements, max_distance_squared, epsilon, index);
            return index;
        }
        template<class t_area_type, class t_buffer_type>
        void enclosedElements(const t_area_type& area, Buffer<uint04>& indices, const t_buffer_type& elements) const
        {
            t_child_tree::template _getEnclosedElements<false>(t_child_tree::root_node, area, indices, elements);
        }
        template<class t_area_type, class t_buffer_type>
        void presortedEnclosedElements(const t_area_type& area, Buffer<uint04>& indices, const t_buffer_type& elements) const
        {
            t_child_tree::template _getEnclosedElements<true>(t_child_tree::root_node, area, indices, elements);
        }
 
 
        template<class t_area_type, class t_buffer_type>
        void getChangedElements(const t_area_type& new_area, const t_area_type& old_area, Buffer<bool>& indices, const t_buffer_type& elements, bool allow_enable, bool allow_disable) const
        {
            t_child_tree::template _getChangedElements(t_child_tree::root_node, new_area, old_area, indices, elements, allow_enable, allow_disable);
        }
        template<class t_area_type, class t_buffer_type>
        void enclosedElements(const t_area_type& area, Buffer<bool>& indices, const t_buffer_type& elements) const
        {
            t_child_tree::template _getEnclosedElements(t_child_tree::root_node, area, indices, elements);
        }
 
        template<class t_area_type, class t_buffer_type>
        uint04 getNumberOfEnclosedElements(const t_area_type& area, const t_buffer_type& elements) const
        {
            return t_child_tree::template _getNumberOfEnclosedElements(t_child_tree::root_node, area, elements);
        }
 
        template<class t_reference_type, class t_buffer_type>
        void closestElements(const t_reference_type& point, uint04 size, Buffer<uint04>& indices, const t_buffer_type& elements, t_type& max_distance, t_type epsilon = cast<t_type>(0)) const
        {
            if (size <= 1)
            {
                uint04 index = closestElement(point, elements, max_distance, epsilon);
                if(!isNaN(index))
                    indices.add(index);
                return;
            }
            MinHeap<t_type, uint04> heap(size + 1);
            t_child_tree::template _getClosestElements<false>(t_child_tree::root_node, point, elements, max_distance, epsilon, heap, size);
            indices.addAll(heap.sortedIndices());
        }
 
        template<class t_reference_type, class t_buffer_type>
        void closestElements(const t_reference_type& point, uint04 size, MinHeap<t_type, uint04>& value_heap, const t_buffer_type& elements, t_type& max_distance, t_type epsilon = cast<t_type>(0)) const
        {
            t_child_tree::template _getClosestElements<false>(t_child_tree::root_node, point, elements, max_distance, epsilon, value_heap, size);
        }
        template<class t_reference_type, class t_buffer_type>
        void presortedClosestElements(const t_reference_type& point, uint04 size, MinHeap<t_type, uint04>& value_heap, const t_buffer_type& elements, t_type& max_distance, t_type epsilon = cast<t_type>(0)) const
        {
            t_child_tree::template _getClosestElements<true>(t_child_tree::root_node, point, elements, max_distance, epsilon, value_heap, size);
        }
        void swapIndices(uint04 index_a, uint04 index_b)
        {
            t_child_tree::m_indices.swapAllElements(index_a, index_b);
        }
 
 
        template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
        void addValue(uint04 index, const t_buffer_type& elements, bool rebalance)
        {
            t_child_tree::template _addValue<t_has_nans, t_uses_boundary>(t_child_tree::root_node, index, elements, rebalance);
        }
        
        template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
        void addValues(const Buffer<bool>& insertion_indices, const t_buffer_type& elements, bool is_precise, ProgressInfo* progress = nullptr)
        {
            if (t_child_tree::useBulkResize(insertion_indices.count(true)))
            {
                t_child_tree::template _addValues<t_has_nans, t_uses_boundary>(t_child_tree::root_node, t_child_tree::template prepareAddAll<true>(insertion_indices), elements, is_precise, progress);
            }
            else
            {
                for (uint04 i = 0; i < elements.size(); i++)
                {
                    if (insertion_indices[i])
                        addValue<t_has_nans, t_uses_boundary>(i, elements);
                }
            }
        }
        template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
        void addValues(const t_buffer_type& elements, bool is_precise, ProgressInfo* progress = nullptr)
        {
            addValues<t_has_nans, t_uses_boundary>(0, elements.size(), elements, is_precise, progress);
        }
        template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
        void addValues(uint04 start_index, uint04 end_index, const t_buffer_type& elements, bool is_precise, ProgressInfo* progress = nullptr)
        {
            if (t_child_tree::useBulkResize(end_index - start_index))
            {
                t_child_tree::template _addValues<t_has_nans, t_uses_boundary>(t_child_tree::root_node, t_child_tree::template prepareAddAll(start_index, end_index, elements), elements, is_precise, progress);
            }
            else
            {
                for (uint04 i = start_index; i < end_index; i++)
                {
                    if constexpr (t_has_nans)
                    {
                        if (isNaN(elements[i]))
                            continue;
                    }
                    addValue<t_has_nans, t_uses_boundary>(i, elements, is_precise);
                }
            }
        };
 
        template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
        void addValues(const Buffer<uint04>& indices, const t_buffer_type& elements, bool is_precise, ProgressInfo* progress = nullptr)
        {
            if (t_child_tree::useBulkResize(indices.size()))
            {
                t_child_tree::template _addValues<t_has_nans, t_uses_boundary>(t_child_tree::root_node, indices, elements, is_precise, progress);
            }
            else
            {
                for (uint04 i = 0; i < indices.size(); i++)
                {
                    addValue<t_has_nans, t_uses_boundary>(indices[i], elements, is_precise);
                }
            }
        }
 
        
 
        template<class t_buffer_type>
        void removeValue(uint04 index, const t_buffer_type& elements)
        {
            t_child_tree::template _removeValue(t_child_tree::root_node, index, elements);
        }
 
        template<class t_buffer_type>
        void removeValues(const Buffer<bool>& insertion_indices, const t_buffer_type& elements, ProgressInfo* progress = nullptr)
        {
            if (t_child_tree::useBulkResize(insertion_indices.count(true)))
            {
                t_child_tree::template clear();
                t_child_tree::template _addValues(t_child_tree::root_node, t_child_tree::template prepareAddAll<false>(insertion_indices), elements, progress);
            }
            else
            {
                for (uint04 i = 0; i < elements.size(); i++)
                {
                    if (insertion_indices[i])
                        t_child_tree::template removeValue(i, elements);
                }
            }
        }
 
        template<class t_buffer_type>
        void removeValues(uint04 start_index, uint04 end_index, const t_buffer_type& elements, ProgressInfo* progress = nullptr)
        {
            if (t_child_tree::template useBulkResize(end_index - start_index))
            {
                t_child_tree::template clear();
                Buffer<uint04> indices(elements.size() - (end_index - start_index));
                for (uint04 i = 0; i < start_index; i++)
                    indices.add(i);
                for (uint04 i = end_index; i < elements.size(); i++)
                    indices.add(i);
                t_child_tree::template _addValues(t_child_tree::root_node, indices, elements, progress);
            }
            else
            {
                for (uint04 i = start_index; i < end_index; i++)
                {
                    removeValue(i, elements);
                }
            }
        }
 
        
        /*Tree getAsReadOnly() const
        {
            Buffer<uint04> indices(t_child_tree::size());
            auto nodes = t_child_tree::m_nodes;
            TreeIterator iterator(t_child_tree::root_node);
            while (iterator.valid())
            {
                uint04 node_index = iterator.get();
                iterator.pop();
                if (nodes[node_index].isLeaf())
                {
                    nodes[node_index].setBegin(indices.size());
                    indices.addAll(t_child_tree::m_indices.begin(t_child_tree::m_nodes[node_index].begin()), t_child_tree::m_nodes[node_index].size());
                }
                else
                {
                    iterator.addAndGoToIndex(t_child_tree::m_nodes[node_index].left(), t_child_tree::m_nodes[node_index].right());
                }
 
            }
            return Tree(nodes, indices, true);
        }*/
 
        virtual const char* getTreeType() const = 0;
    };
};