<commit_before>﻿using BEPUutilities.DataStructures;
using BEPUutilities.ResourceManagement;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace SIMDPrototyping.Trees.SingleArray
{
    partial class Tree
    {
        struct SweepSubtree
        {
            public BoundingBox BoundingBox;
            public int Index;
            public int LeafCount;
        }

        unsafe void ComputeBoundingBox(SweepSubtree* subtrees, int subtreeStart, int subtreeCount, out BoundingBox boundingBox)
        {
            Debug.Assert(subtreeCount > 0);
            Debug.Assert(subtreeStart >= 0);
            subtrees += subtreeStart;

            boundingBox = subtrees->BoundingBox;
            for (int i = 1; i < subtreeCount; ++i)
            {
                BoundingBox.Merge(ref subtrees[i].BoundingBox, ref boundingBox, out boundingBox);
            }
        }

        unsafe void CentroidSort(SweepSubtree* subtrees, int subtreeStart, int subtreeCount, ref BoundingBox boundingBox)
        {
            //Compute dominant axis based on the bounding box.
            //Sort along that axis. This uses an in-place insertion sort for simplicity and to take advantage of the partially sorted data.
            var offset = boundingBox.Max - boundingBox.Min;
            subtrees += subtreeStart;
            //A variety of potential microoptimizations exist here.
            //Don't reallocate centroids (because JIT is forced to zero by roslyn), do swaps better, etc.
            var centroids = stackalloc float[subtreeCount];
            if (offset.X >= offset.Y && offset.X >= offset.Z)
            {
                //X is dominant.
                for (int i = 0; i < subtreeCount; ++i)
                {
                    centroids[i] = subtrees[i].BoundingBox.Min.X + subtrees[i].BoundingBox.Max.X;
                }
            }
            else if (offset.Y >= offset.Z)
            {
                //Y is dominant.
                for (int i = 0; i < subtreeCount; ++i)
                {
                    centroids[i] = subtrees[i].BoundingBox.Min.Y + subtrees[i].BoundingBox.Max.Y;
                }
            }
            else
            {
                //Z is dominant.   
                for (int i = 0; i < subtreeCount; ++i)
                {
                    centroids[i] = subtrees[i].BoundingBox.Min.Z + subtrees[i].BoundingBox.Max.Z;
                }
            }



 
            for (int i = 1; i < subtreeCount; ++i)
            {
                var index = i;
                var previousIndex = index - 1;
                while (centroids[index] < centroids[previousIndex])
                {
                    var tempCentroid = centroids[index];
                    var tempSubtree = subtrees[index];
                    centroids[index] = centroids[previousIndex];
                    subtrees[index] = subtrees[previousIndex];
                    centroids[previousIndex] = tempCentroid;
                    subtrees[previousIndex] = tempSubtree;


                    if (previousIndex == 0)
                        break;
                    index = previousIndex;
                    --previousIndex;
                }<commit_msg>Significant refinement speed boost from minimizes copies in insertion sort.<commit_after>﻿using BEPUutilities.DataStructures;
using BEPUutilities.ResourceManagement;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace SIMDPrototyping.Trees.SingleArray
{
    partial class Tree
    {
        struct SweepSubtree
        {
            public BoundingBox BoundingBox;
            public int Index;
            public int LeafCount;
        }

        unsafe void ComputeBoundingBox(SweepSubtree* subtrees, int subtreeStart, int subtreeCount, out BoundingBox boundingBox)
        {
            Debug.Assert(subtreeCount > 0);
            Debug.Assert(subtreeStart >= 0);
            subtrees += subtreeStart;

            boundingBox = subtrees->BoundingBox;
            for (int i = 1; i < subtreeCount; ++i)
            {
                BoundingBox.Merge(ref subtrees[i].BoundingBox, ref boundingBox, out boundingBox);
            }
        }

        unsafe void CentroidSort(SweepSubtree* subtrees, int subtreeStart, int subtreeCount, ref BoundingBox boundingBox)
        {
            //Compute dominant axis based on the bounding box.
            //Sort along that axis. This uses an in-place insertion sort for simplicity and to take advantage of the partially sorted data.
            var offset = boundingBox.Max - boundingBox.Min;
            subtrees += subtreeStart;
            //A variety of potential microoptimizations exist here.
            //Don't reallocate centroids (because JIT is forced to zero by roslyn), do swaps better, etc.
            var centroids = stackalloc float[subtreeCount];
            var subtreesCopy = stackalloc SweepSubtree[subtreeCount];
            var indexMap = stackalloc int[subtreeCount];
            if (offset.X >= offset.Y && offset.X >= offset.Z)
            {
                //X is dominant.
                for (int i = 0; i < subtreeCount; ++i)
                {
                    centroids[i] = subtrees[i].BoundingBox.Min.X + subtrees[i].BoundingBox.Max.X;
                    indexMap[i] = i;
                    subtreesCopy[i] = subtrees[i];
                }
            }
            else if (offset.Y >= offset.Z)
            {
                //Y is dominant.
                for (int i = 0; i < subtreeCount; ++i)
                {
                    centroids[i] = subtrees[i].BoundingBox.Min.Y + subtrees[i].BoundingBox.Max.Y;
                    indexMap[i] = i;
                    subtreesCopy[i] = subtrees[i];
                }
            }
            else
            {
                //Z is dominant.   
                for (int i = 0; i < subtreeCount; ++i)
                {
                    centroids[i] = subtrees[i].BoundingBox.Min.Z + subtrees[i].BoundingBox.Max.Z;
                    indexMap[i] = i;
                    subtreesCopy[i] = subtrees[i];
                }
            }


 
            for (int i = 1; i < subtreeCount; ++i)
            {
                var index = i;
                var previousIndex = index - 1;
                while (centroids[indexMap[index]] < centroids[indexMap[previousIndex]])
                {
                    //var tempCentroid = centroids[pointers[index]];
                    //var tempSubtree = subtrees[index];
                    //centroids[index] = centroids[previousIndex];
                    //subtrees[index] = subtrees[previousIndex];
                    //centroids[previousIndex] = tempCentroid;
                    //subtrees[previousIndex] = tempSubtree;

                    var tempPointer = indexMap[index];
                    indexMap[index] = indexMap[previousIndex];
                    indexMap[previousIndex] = tempPointer;


                    if (previousIndex == 0)
                        break;
                    index = previousIndex;
                    --previousIndex;
                }
            }

            for (int i = 0; i < subtreeCount; ++i)
            {
                subtrees[i] = subtreesCopy[indexMap[i]];
{'fraction_non_alphanumeric': 0.08831832235515526, 'fraction_numerical': 0.0025541067347761796, 'mean_word_length': 1.4833110814419226, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3829233', 'n_tokens_mistral': 2098, 'n_tokens_neox': 1921, 'n_words': 495}