TreeSorter.h

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: TreeSorter
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/Buffer.h>
#include <NDEVR/Vector.h>
#include <NDEVR/Bounds.h>
#include <NDEVR/Median.h>
#include <NDEVR/TypeInfo.h>
#include <NDEVR/Dictionary.h>
#include <NDEVR/ProgressInfo.h>
#include <algorithm>
 
#include <NDEVR/OpenMP.h>
#ifdef _WIN32
    #include <execution>
#endif
#if NDEVR_SUPPORTS_THREADING
#define TREE_SORTER_USE_THREAD 0
#ifdef TREE_SORTER_USE_THREAD
    #include <NDEVR/BasicThread.h>
#endif
#else
#define TREE_SORTER_USE_THREAD 0
#endif
namespace NDEVR
{
    template<uint01 t_dims, class t_type>
    class TreeSorterBase
    {
    public:
        void getList(uint01 dimension, uint04 start, uint04 end, Buffer<uint04>& values, uint04 index_offset)
        {
            uint04 size = end - start;
            values.setAll(center_ordered[dimension], index_offset, start, size);
        }
    protected:
        static void _sortList(const Buffer<bool>& list_sorter, Buffer<uint04>& list, Buffer<uint04>& temp, uint04 start, uint04 end)
        {
            temp.clear();
            temp.setSize(end - start);
            uint04 temp_location = 0;
            uint04 left_location = start;
            for (uint04 i = start; i < end; i++)
            {
                if (list_sorter[list[i]])
                {
                    list[left_location++] = list[i];
                }
                else
                {
                    temp[temp_location++] = list[i];
                }
            }
            list.setAll(temp, left_location, temp_location);
            
        }
    protected:
        Buffer<bool> temp_memory;
        Buffer<uint04> temp_array;
        Buffer<uint04> center_ordered[t_dims];
    };
 
    template<uint01 t_dims, class t_type>
    class TreeBoundarySorter : public TreeSorterBase<t_dims, t_type>
    {
    public:
        template<bool t_has_nans, class t_list_type>
        void createCenterSortList(const Buffer<uint04>& indices, const t_list_type& locations, ProgressInfo* progress)
        {
            if(progress) progress->addMessage("Creating tree sort list");
            uint04 size = indices.size();
            TreeSorterBase<t_dims, t_type>::temp_memory.setSize(locations.size());
            TreeSorterBase<t_dims, t_type>::temp_array.ensureCapacity((size / 2) + 1);
            TreeSorterBase<t_dims, t_type>::center_ordered[0].setSize(size);
 
            for(uint04 i = 0; i < size; i++)
            {
                TreeSorterBase<t_dims, t_type>::center_ordered[0][i] = indices[i];
            }
            if (progress) progress->addMessage("Sorting boundary");
            m_uses_boundary = false;
            for (uint01 dimension = 1; dimension < t_dims; ++dimension)
                TreeSorterBase<t_dims, t_type>::center_ordered[dimension] = TreeSorterBase<t_dims, t_type>::center_ordered[0];
            for (uint01 dimension = 0; dimension < t_dims; ++dimension)
                sortList<t_has_nans>(dimension, locations, Buffer<Bounds<t_dims, t_type>>(), progress);
        }
        template<bool t_has_nans, class t_list_type>
        void createBoundarySortList(const Buffer<uint04>& indices, const t_list_type& locations, ProgressInfo* progress)
        {
            if (progress) progress->addMessage("Creating tree sort list");
            uint04 size = indices.size();
            TreeSorterBase<t_dims, t_type>::temp_memory.setSize(locations.size());
            TreeSorterBase<t_dims, t_type>::temp_array.ensureCapacity((size / 2) + 1);
            TreeSorterBase<t_dims, t_type>::center_ordered[0].setSize(size);
 
            Buffer<Vector<t_dims, t_type>> centers;
            Buffer<Bounds<t_dims, t_type>> bounds;
            centers.setSize(locations.size());
            bounds.setSize(locations.size());
            for (uint04 i = 0; i < size; i++)
            {
                TreeSorterBase<t_dims, t_type>::center_ordered[0][i] = indices[i];
            }
            if (progress) progress->addMessage("Sorting boundary");
            m_uses_boundary = true;
            for (uint04 i = 0; i < locations.size(); i++)
            {
                auto value = locations[i].template as<t_dims, t_type>();
                centers[i] = value.center();
                bounds[i] = Bounds<t_dims, t_type>(value);
                lib_assert(isNaN(centers[i]) || bounds[i].contains(centers[i]), "Tree Sorter: Bounds did not contain center");
            }
            for (uint01 dimension = 1; dimension < t_dims; ++dimension)
                TreeSorterBase<t_dims, t_type>::center_ordered[dimension] = TreeSorterBase<t_dims, t_type>::center_ordered[0];
            for (uint01 dimension = 0; dimension < t_dims; ++dimension)
                sortList<t_has_nans>(dimension, centers, bounds, progress);
        }
        template<bool t_has_nans, class t_list_type>
        void createHashSortList(const Buffer<uint04>& indices, const t_list_type& locations, ProgressInfo* progress)
        {
            if (progress) progress->addMessage("Creating tree sort list");
            uint04 size = indices.size();
            TreeSorterBase<t_dims, t_type>::temp_memory.setSize(size);
            TreeSorterBase<t_dims, t_type>::temp_array.ensureCapacity((size / 2) + 1);
            TreeSorterBase<t_dims, t_type>::center_ordered[0].setSize(size);
 
            Dictionary<uint04, Vector<t_dims, t_type>> centers;
            Dictionary<uint04, Bounds<t_dims, t_type>> bounds;
            for (uint04 i = 0; i < size; i++)
            {
                TreeSorterBase<t_dims, t_type>::center_ordered[0][i] = indices[i];
            }
            if (progress) progress->addMessage("Sorting boundary");
            m_uses_boundary = true;
            for (uint04 i = 0; i < indices.size(); i++)
            {
                auto value = locations[indices[i]].template as<t_dims, t_type>();
                centers[indices[i]] = value.center();
                bounds[indices[i]] = Bounds<t_dims, t_type>(value);
            }
            for (uint01 dimension = 1; dimension < t_dims; ++dimension)
                TreeSorterBase<t_dims, t_type>::center_ordered[dimension] = TreeSorterBase<t_dims, t_type>::center_ordered[0];
            for (uint01 dimension = 0; dimension < t_dims; ++dimension)
            {
                sortList<t_has_nans>(dimension, centers, bounds, progress);
            }
        }
        template<bool t_has_nans, class t_center_buffer, class t_bounds_buffer>
        void sortList(uint01 dimension, const t_center_buffer& centers, const t_bounds_buffer& bounds, ProgressInfo* progress)
        {
            if (progress)
            {
                progress->setProgress(Constant<fltp04>::NaN);
                switch (dimension)
                {
                case 0: progress->addMessage("Sorting dimension 1"); break;
                case 1: progress->addMessage("Sorting dimension 2"); break;
                case 2: progress->addMessage("Sorting dimension 3"); break;
                case 3: progress->addMessage("Sorting dimension 4"); break;
                }
            }
#ifdef _WIN32
            std::sort(std::execution::par_unseq, TreeSorterBase<t_dims, t_type>::center_ordered[dimension].begin(), TreeSorterBase<t_dims, t_type>::center_ordered[dimension].end(), [&centers, dimension](uint04 a, uint04 b)
#else
            std::sort(TreeSorterBase<t_dims, t_type>::center_ordered[dimension].begin(), TreeSorterBase<t_dims, t_type>::center_ordered[dimension].end(), [&centers, dimension](uint04 a, uint04 b)
#endif
            {
                const auto a_val = centers[a][dimension];
                const auto b_val = centers[b][dimension];
                if(t_has_nans)
                { 
                    if (isNaN(a_val) != isNaN(b_val))
                        return isNaN(a_val);
                }
                return (a_val < b_val);
            });
            if (m_uses_boundary)
            {
                if (progress) progress->addMessage("Bounding Box sorting");
                min_ordered[dimension] = TreeSorterBase<t_dims, t_type>::center_ordered[dimension];
                max_ordered[dimension] = TreeSorterBase<t_dims, t_type>::center_ordered[dimension];
#ifdef _WIN32
                std::sort(std::execution::par_unseq, min_ordered[dimension].begin(), min_ordered[dimension].end(), [&bounds, dimension](uint04 a, uint04 b)
#else
                std::sort(min_ordered[dimension].begin(), min_ordered[dimension].end(), [&bounds, dimension](uint04 a, uint04 b)
#endif
                {
                    const auto& a_val = bounds[a][MIN][dimension];
                    const auto& b_val = bounds[b][MIN][dimension];
                    if(t_has_nans)
                    { 
                        if (isNaN(a_val) != isNaN(b_val))
                            return isNaN(a_val);
                    }
                    return (a_val < b_val);
                });
#ifdef _WIN32
                std::sort(std::execution::par_unseq, max_ordered[dimension].begin(), max_ordered[dimension].end(), [&bounds, dimension](uint04 a, uint04 b)
#else
                std::sort(max_ordered[dimension].begin(), max_ordered[dimension].end(), [&bounds, dimension](uint04 a, uint04 b)
#endif
                {
                    auto a_val = bounds[a][MAX][dimension];
                    auto b_val = bounds[b][MAX][dimension];
                    if (isNaN(a_val) != isNaN(b_val))
                        return isNaN(a_val);
                    return (a_val < b_val);
                });
            }
            if (progress) progress->setProgress(1.0f);
        }
 
 
        template<class t_list_type>
        Bounds<t_dims, t_type> getBounds(uint04 start, uint04 finish, const t_list_type& locations) const
        {
            Bounds<t_dims, t_type> box;
            if (m_uses_boundary)
            {
                for (uint01 dim = 0; dim < t_dims; ++dim)
                {
                    box[MIN][dim] = Bounds<t_dims, t_type>(locations[min_ordered[dim][start]].template as<t_dims, t_type>())[MIN][dim];
                    box[MAX][dim] = Bounds<t_dims, t_type>(locations[max_ordered[dim][finish - 1]].template as<t_dims, t_type>())[MAX][dim];
                }
            }
            else
            {
                for (uint01 dim = 0; dim < t_dims; ++dim)
                {
                    box[MIN][dim] = locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][start]].template as<t_dims, t_type>().center()[dim];
                    box[MAX][dim] = locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][finish - 1]].template as<t_dims, t_type>().center()[dim];
                }
            }
            return box;
        }
        template<class t_list_type>
        Vector<2, Bounds<t_dims, t_type>> getMedianBounds(uint01 dimension, uint04 start, uint04 end, const t_list_type& locations)
        {
            Vector<2, Bounds<t_dims, t_type>> bounds;//The bounds on each side of the median
            const uint04 median_location = ((end - start) / 2) + start;
            for(uint04 i = start; i < median_location; ++i)
            {
                TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dimension][i]] = true;
            }
            for (uint04 i = median_location; i < end; ++i)
            {
                TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dimension][i]] = false;
            }
            for (uint01 dim = 0; dim < t_dims; ++dim)
            {
                if (m_uses_boundary)
                {
                    if (TreeSorterBase<t_dims, t_type>::temp_memory[min_ordered[dim][start]])
                    {
                        bounds[0][MIN][dim] = Bounds<t_dims, t_type>(locations[min_ordered[dim][start]].template as<t_dims, t_type>())[MIN][dim];
                        for (uint04 n = start + 1; n < end; ++n)
                        {
                            if (!TreeSorterBase<t_dims, t_type>::temp_memory[min_ordered[dim][n]])
                            {
                                bounds[1][MIN][dim] = Bounds<t_dims, t_type>(locations[min_ordered[dim][n]].template as<t_dims, t_type>())[MIN][dim];
                                break;
                            }
                        }
                    }
                    else
                    {
                        bounds[1][MIN][dim] = Bounds<t_dims, t_type>(locations[min_ordered[dim][start]].template as<t_dims, t_type>())[MIN][dim];
                        for (uint04 n = start + 1; n < end; ++n)
                        {
                            if (TreeSorterBase<t_dims, t_type>::temp_memory[min_ordered[dim][n]])
                            {
                                bounds[0][MIN][dim] = Bounds<t_dims, t_type>(locations[min_ordered[dim][n]].template as<t_dims, t_type>())[MIN][dim];
                                break;
                            }
                        }
                    }
                    if (TreeSorterBase<t_dims, t_type>::temp_memory[max_ordered[dim][end - 1]])
                    {
                        bounds[0][MAX][dim] = Bounds<t_dims, t_type>(locations[max_ordered[dim][end - 1]].template as<t_dims, t_type>())[MAX][dim];
                        for (uint04 n = end - 2; n >= start && !isNaN(n); --n)
                        {
                            if (!TreeSorterBase<t_dims, t_type>::temp_memory[max_ordered[dim][n]])
                            {
                                bounds[1][MAX][dim] = Bounds<t_dims, t_type>(locations[max_ordered[dim][n]].template as<t_dims, t_type>())[MAX][dim];
                                break;
                            }
                        }
                    }
                    else
                    {
                        bounds[1][MAX][dim] = Bounds<t_dims, t_type>(locations[max_ordered[dim][end - 1]].template as<t_dims, t_type>())[MAX][dim];
                        for (uint04 n = end - 2; n >= start && !isNaN(n); --n)
                        {
                            if (TreeSorterBase<t_dims, t_type>::temp_memory[max_ordered[dim][n]])
                            {
                                bounds[0][MAX][dim] = Bounds<t_dims, t_type>(locations[max_ordered[dim][n]].template as<t_dims, t_type>())[MAX][dim];
                                break;
                            }
                        }
                    }
                }
                else
                {
                    if (TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dim][start]])
                    {
                        bounds[0][MIN][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][start]].template as<t_dims, t_type>())[MIN][dim];
                        for (uint04 n = start + 1; n < end; ++n)
                        {
                            if (!TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]])
                            {
                                bounds[1][MIN][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]].template as<t_dims, t_type>())[MIN][dim];
                                break;
                            }
                        }
                    }
                    else
                    {
                        bounds[1][MIN][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][start]].template as<t_dims, t_type>())[MIN][dim];
                        for (uint04 n = start + 1; n < end; ++n)
                        {
                            if (TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]])
                            {
                                bounds[0][MIN][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]].template as<t_dims, t_type>())[MIN][dim];
                                break;
                            }
                        }
                    }
                    if (TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dim][end - 1]])
                    {
                        bounds[0][MAX][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][end - 1]].template as<t_dims, t_type>())[MAX][dim];
                        for (uint04 n = end - 2; n >= start && !isNaN(n); --n)
                        {
                            if (!TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]])
                            {
                                bounds[1][MAX][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]].template as<t_dims, t_type>())[MAX][dim];
                                break;
                            }
                        }
                    }
                    else
                    {
                        bounds[1][MAX][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][end - 1]].template as<t_dims, t_type>())[MAX][dim];
                        for (uint04 n = end - 2; n >= start && !isNaN(n); --n)
                        {
                            if (TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]])
                            {
                                bounds[0][MAX][dim] = Bounds<t_dims, t_type>(locations[TreeSorterBase<t_dims, t_type>::center_ordered[dim][n]].template as<t_dims, t_type>())[MAX][dim];
                                break;
                            }
                        }
                    }
                }
            }
            return bounds;
        }
 
        uint04 getMedian(uint01 dimension, uint04 start, uint04 end)
        {
            const uint04 median_location = ((end - start) / 2) + start;
            for (uint04 i = start; i < median_location; i++)
            {
                TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dimension][i]] = true;
            }
            for (uint04 i = median_location; i < end; i++)
            {
                TreeSorterBase<t_dims, t_type>::temp_memory[TreeSorterBase<t_dims, t_type>::center_ordered[dimension][i]] = false;
            }
            for (uint01 dim = 0; dim < t_dims; ++dim)
            {
                if (dimension != dim)
                {
                    TreeSorterBase<t_dims, t_type>::_sortList(TreeSorterBase<t_dims, t_type>::temp_memory, TreeSorterBase<t_dims, t_type>::center_ordered[dim], TreeSorterBase<t_dims, t_type>::temp_array, start, end);
                }
                if (m_uses_boundary)
                {
                    TreeSorterBase<t_dims, t_type>::_sortList(TreeSorterBase<t_dims, t_type>::temp_memory, min_ordered[dim], TreeSorterBase<t_dims, t_type>::temp_array, start, end);
                    TreeSorterBase<t_dims, t_type>::_sortList(TreeSorterBase<t_dims, t_type>::temp_memory, max_ordered[dim], TreeSorterBase<t_dims, t_type>::temp_array, start, end);
                }
            }
            return TreeSorterBase<t_dims, t_type>::center_ordered[dimension][median_location];
        }
        
    protected:
        Buffer<uint04> min_ordered[t_dims];
        Buffer<uint04> max_ordered[t_dims];
        bool m_uses_boundary = true;
    };
    
    template<class t_type>
    class TreeSorter;
 
}