ThreadedRTree.h

/*--------------------------------------------------------------------------------------------
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: ThreadedRTree
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/RTree.h>
#include <NDEVR/Thread.h>
#include <NDEVR/BasicThread.h>
#include <NDEVR/RWLock.h>
namespace NDEVR
{
    template<uint01 t_dims, class t_type>
    class ThreadedRTree : public RTree<t_dims, t_type>
    {
 
    public:
        explicit ThreadedRTree<t_dims, t_type>(uint04 bucket_size)
            : RTree<t_dims, t_type>(bucket_size)
            , m_number_of_threads(4)
        {
            m_indices.allocateSpace<false>(bucket_size);
        }
        ThreadedRTree<t_dims, t_type>(const RTree<t_dims, t_type>& tree)
            : RTree<t_dims, t_type>(tree)
            , m_number_of_threads(tree.m_number_of_threads)
        {}
        ThreadedRTree<t_dims, t_type>(RTree<t_dims, t_type>&& tree)
            : RTree<t_dims, t_type, t_bucket_size>(std::move(tree))
            , m_number_of_threads(tree.m_number_of_threads)
        {}
    
        template<class t_node_type>
        bool addAllThreaded(const Buffer<t_node_type>& elements, InfoPipe* progress = nullptr)
        {
            Buffer<uint04> indices = prepareAddAll(0, elements.size());
 
            m_nodes[root_node].clear(m_nodes[root_node].begin(), _getBoundingBoxThreaded(0, indices, elements, 0, indices.size()));
 
            if (progress != nullptr) progress->allowCancel(true);//if you change this, be ready to catch the exception that gets thrown when you cancel
            bool did_balance = _balanceLeafNodeThreaded(root_node, 0, elements, indices, 0, indices.size(), progress);
            if (progress != nullptr) progress->allowCancel(false);
 
            m_indices.ensureCapacity(cast<uint04>(1.1 * (m_indices.size())), true, true);
            m_nodes.ensureCapacity(cast<uint04>(1.1 * (m_nodes.size())), true, true);
 
            return did_balance;
            
        }

        template<class t_node_type>
        bool addAllThreaded(const Buffer<t_node_type>& elements, uint04 start_index, uint04 end_index, InfoPipe* progress = nullptr)
        {
            Buffer<uint04> indices = prepareAddAll(start_index, end_index);
 
            m_nodes[root_node].clear(m_nodes[root_node].begin(), bounds);
 
            if (progress != nullptr) progress->allowCancel(true);//if you change this, be ready to catch the exception that gets thrown when you cancel
            bool did_balance = _balanceLeafNodeThreaded(root_node, 1, elements, indices, 0, indices.size(), progress);
            if (progress != nullptr) progress->allowCancel(false);
 
            m_indices.ensureCapacity(cast<uint04>(1.1 * (m_indices.size())), true, true);
            m_nodes.ensureCapacity(cast<uint04>(1.1 * (m_nodes.size())), true, true);
 
            return did_balance;
        }
        
        
        
        template<class t_node_type>
        bool _balanceLeafNodeThreaded(uint04 level, const uint04 node_index, const Buffer<t_node_type>& elements, Buffer<uint04>& indices, uint04 start, uint04 end, ProgressInfo& progress)
        {
            uint04 level_value = pow(2U, level);
            if (m_number_of_threads <= level_value || (end - start) < 1000)
            {
                _balanceLeafNode(node_index, elements, indices, start, end, progress);
            }
            else
            {
                const uint04 new_left = _calculateAndSplit(node_index, elements, indices, start, end);
                splitThread(
                    [this, level, start, new_left, node_index, &progress, &indices, &elements] {
                        //uint08 start_time = Time::SystemTime();
                        _balanceLeafNodeThreaded(level + 1, m_nodes[node_index].left(), elements, indices, start, new_left, progress);
                        //if (progress != nullptr) progress->addMessage(String("Finished: Level = ") + level + " Time: " + (Time::SystemTime() - start_time));
                    }, 
                    [this, level, end, new_left, node_index, &progress, &indices, &elements] {
                        //uint08 start_time = Time::SystemTime();
                        _balanceLeafNodeThreaded(level + 1, m_nodes[node_index].right(), elements, indices, new_left, end, progress);
                        //if (progress != nullptr) progress->addMessage(String("Finished: Level = ") + level + " Time: " + (Time::SystemTime() - start_time));
                    });
            }
            return true;
        }

        template<class t_node_type>
        Bounds<t_dims, t_type> _getBoundingBoxThreaded(uint04 top_level, const Buffer<uint04>& indices, const Buffer<t_node_type>& elements, uint04 start, uint04 end)
        {
            if (m_number_of_threads <= pow(2U, top_level) || end - start < 100)
            {
                return _getBounds(indices, elements, start, end);
            }
            else
            {
                const uint04 middle = start + (end - start) / 2;
                Bounds<t_dims, t_type> left;
                Bounds<t_dims, t_type> right;
                splitThread(
                    [this, &left, &indices, &elements, start, middle, top_level] {
                    left  = _getBoundingBoxThreaded(top_level + 1, indices, elements, start, middle);
                },
                    [this, &right, &indices, &elements, end, middle, top_level] {
                    right = _getBoundingBoxThreaded(top_level + 1, indices, elements, middle, end);
                });
                return Bounds<t_dims, t_type>(left, right);
            }
        }

        void splitLeafNode(uint04 index) final override
        {
            m_split_lock.lock();
            RTree<t_dims, t_type, t_bucket_size>::splitLeafNode(index);
            m_split_lock.unlock();
 
        }
        std::mutex m_split_lock;        
        uint04 m_number_of_threads;     
    };
};