<commit_before>﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Octree.cs" company="Helix Toolkit">
//   Copyright (c) 2017 Helix Toolkit contributors
// </copyright>
// <summary>
// An octree implementation reference from https://www.gamedev.net/resources/_/technical/game-programming/introduction-to-octrees-r3529
// </summary>
// --------------------------------------------------------------------------------------------------------------------


using HelixToolkit.Wpf.SharpDX;
using HelixToolkit.Wpf.SharpDX.Core;
using SharpDX;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;

namespace HelixToolkit.SharpDX.Shared.Utilities
{
    public interface IOctree
    {
        byte ActiveNodes { get; }
        bool HasChildren { get; }
        bool IsRoot { get; }
        IOctree Parent { get; }
        BoundingBox Bound { get; }
        IOctree[] ChildNodes { get; }
        bool IsEmpty { get; }
        bool HitTest(GeometryModel3D model, Matrix modelMatrix, Ray rayWS, ref List<HitTestResult> hits);
        /// <summary>
        /// Build tree from top to bottom
        /// </summary>
        void BuildTree();

        /// <summary>
        /// Build current node level only, this will only build current node and its children. To build from top to bottom, call BuildTree
        /// </summary>
        void BuildCurrent();
        void Clear();
    }

    public interface IOctreeBase<T> : IOctree
    {
        List<T> Objects { get; }
    }

    public abstract class OctreeBase<T> : IOctreeBase<T>
    {
        /// <summary>
        /// The minumum size for enclosing region is a 1x1x1 cube.
        /// </summary>
        public const int MIN_SIZE = 1;

        public BoundingBox Bound { protected set; get; }

        public List<T> Objects { protected set; get; }

        /// <summary>
        /// These are all of the possible child octants for this node in the tree.
        /// </summary>
        private readonly IOctree[] childNodes = new IOctree[8];
        public IOctree[] ChildNodes { get { return childNodes; } }
        /// <summary>
        /// This is a bitmask indicating which child nodes are actively being used.
        /// It adds slightly more complexity, but is faster for performance since there is only one comparison instead of 8.
        /// </summary>
        public byte ActiveNodes { protected set; get; }

        /// <summary>
        /// A reference to the parent node is sometimes required. If we are a node and we realize that we no longer have items contained within ourselves,
        /// we need to let our parent know that we're empty so that it can delete us.
        /// </summary>
        public IOctree Parent { protected set; get; }

        protected bool treeReady = false;       //the tree has a few objects which need to be inserted before it is complete
        protected bool treeBuilt = false;       //there is no pre-existing tree yet.


        /*Note: we want to avoid allocating memory for as long as possible since there can be lots of nodes.*/
        /// <summary>
        /// Creates an oct tree which encloses the given region and contains the provided objects.
        /// </summary>
        /// <param name="bound">The bounding region for the oct tree.</param>
        /// <param name="objList">The list of objects contained within the bounding region</param>
        protected OctreeBase(BoundingBox bound, List<T> objList)
        {
            Bound = bound;
            Objects = objList;
        }

        public OctreeBase()
        {
            Objects = new List<T>();
            Bound = new BoundingBox(Vector3.Zero, Vector3.Zero);
        }

        /// <summary>
        /// Creates an octTree with a suggestion for the bounding region containing the items.
        /// </summary>
        /// <param name="bound">The suggested dimensions for the bounding region. 
        /// Note: if items are outside this region, the region will be automatically resized.</param>
        public OctreeBase(BoundingBox bound)
            : this()
        {
            Bound = bound;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="bound"></param>
        /// <param name="objList"></param>
        /// <returns></returns>
        protected abstract IOctree CreateNode(BoundingBox bound, List<T> objList);  //complete & tested

        /// <summary>
        /// 
        /// </summary>
        /// <param name="bound"></param>
        /// <param name="Item"></param>
        /// <returns></returns>
        protected IOctree CreateNode(BoundingBox bound, T Item)
        {
            return CreateNode(bound, new List<T> { Item });
        }

        /// <summary>
        /// Build the whole tree from top to bottom iteratively.
        /// </summary>
        public void BuildTree()
        {
#if DEBUG
            var sw = Stopwatch.StartNew();
#endif
            var queue = new Queue<IOctree>();
            queue.Enqueue(this);
            while (queue.Count > 0)
            {
                var tree = queue.Dequeue();
                tree.BuildCurrent();
                if (tree.HasChildren)
                {
                    foreach(var subTree in tree.ChildNodes)
                    {
                        if (subTree != null)
                        {
                            queue.Enqueue(subTree);
                        }
                    }
                }
            }
#if DEBUG
            sw.Stop();
            Debug.WriteLine("Buildtree time =" + sw.ElapsedMilliseconds);
#endif
        }

        /// <summary>
        /// Update this tree node and create its children, to build its children iteratively, please call BuildTree
        /// </summary><commit_msg>Set queue default capacity to 64<commit_after>﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Octree.cs" company="Helix Toolkit">
//   Copyright (c) 2017 Helix Toolkit contributors
// </copyright>
// <summary>
// An octree implementation reference from https://www.gamedev.net/resources/_/technical/game-programming/introduction-to-octrees-r3529
// </summary>
// --------------------------------------------------------------------------------------------------------------------


using HelixToolkit.Wpf.SharpDX;
using HelixToolkit.Wpf.SharpDX.Core;
using SharpDX;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;

namespace HelixToolkit.SharpDX.Shared.Utilities
{
    public interface IOctree
    {
        byte ActiveNodes { get; }
        bool HasChildren { get; }
        bool IsRoot { get; }
        IOctree Parent { get; }
        BoundingBox Bound { get; }
        IOctree[] ChildNodes { get; }
        bool IsEmpty { get; }
        bool HitTest(GeometryModel3D model, Matrix modelMatrix, Ray rayWS, ref List<HitTestResult> hits);
        /// <summary>
        /// Build tree from top to bottom
        /// </summary>
        void BuildTree();

        /// <summary>
        /// Build current node level only, this will only build current node and its children. To build from top to bottom, call BuildTree
        /// </summary>
        void BuildCurrent();
        void Clear();
    }

    public interface IOctreeBase<T> : IOctree
    {
        List<T> Objects { get; }
    }

    public abstract class OctreeBase<T> : IOctreeBase<T>
    {
        /// <summary>
        /// The minumum size for enclosing region is a 1x1x1 cube.
        /// </summary>
        public const int MIN_SIZE = 1;

        public BoundingBox Bound { protected set; get; }

        public List<T> Objects { protected set; get; }

        /// <summary>
        /// These are all of the possible child octants for this node in the tree.
        /// </summary>
        private readonly IOctree[] childNodes = new IOctree[8];
        public IOctree[] ChildNodes { get { return childNodes; } }
        /// <summary>
        /// This is a bitmask indicating which child nodes are actively being used.
        /// It adds slightly more complexity, but is faster for performance since there is only one comparison instead of 8.
        /// </summary>
        public byte ActiveNodes { protected set; get; }

        /// <summary>
        /// A reference to the parent node is sometimes required. If we are a node and we realize that we no longer have items contained within ourselves,
        /// we need to let our parent know that we're empty so that it can delete us.
        /// </summary>
        public IOctree Parent { protected set; get; }

        protected bool treeReady = false;       //the tree has a few objects which need to be inserted before it is complete
        protected bool treeBuilt = false;       //there is no pre-existing tree yet.


        /*Note: we want to avoid allocating memory for as long as possible since there can be lots of nodes.*/
        /// <summary>
        /// Creates an oct tree which encloses the given region and contains the provided objects.
        /// </summary>
        /// <param name="bound">The bounding region for the oct tree.</param>
        /// <param name="objList">The list of objects contained within the bounding region</param>
        protected OctreeBase(BoundingBox bound, List<T> objList)
        {
            Bound = bound;
            Objects = objList;
        }

        public OctreeBase()
        {
            Objects = new List<T>();
            Bound = new BoundingBox(Vector3.Zero, Vector3.Zero);
        }

        /// <summary>
        /// Creates an octTree with a suggestion for the bounding region containing the items.
        /// </summary>
        /// <param name="bound">The suggested dimensions for the bounding region. 
        /// Note: if items are outside this region, the region will be automatically resized.</param>
        public OctreeBase(BoundingBox bound)
            : this()
        {
            Bound = bound;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="bound"></param>
        /// <param name="objList"></param>
        /// <returns></returns>
        protected abstract IOctree CreateNode(BoundingBox bound, List<T> objList);  //complete & tested

        /// <summary>
        /// 
        /// </summary>
        /// <param name="bound"></param>
        /// <param name="Item"></param>
        /// <returns></returns>
        protected IOctree CreateNode(BoundingBox bound, T Item)
        {
            return CreateNode(bound, new List<T> { Item });
        }

        /// <summary>
        /// Build the whole tree from top to bottom iteratively.
        /// </summary>
        public void BuildTree()
        {
#if DEBUG
            var sw = Stopwatch.StartNew();
#endif
            var queue = new Queue<IOctree>(64);
            queue.Enqueue(this);
            while (queue.Count > 0)
            {
                var tree = queue.Dequeue();
                tree.BuildCurrent();
                if (tree.HasChildren)
                {
                    foreach(var subTree in tree.ChildNodes)
                    {
                        if (subTree != null)
                        {
                            queue.Enqueue(subTree);
                        }
                    }
                }
            }
#if DEBUG
            sw.Stop();
            Debug.WriteLine("Buildtree time =" + sw.ElapsedMilliseconds);
#endif
        }

        /// <summary>
        /// Update this tree node and create its children, to build its children iteratively, please call BuildTree
        /// </summary>
{'fraction_non_alphanumeric': 0.14137669559356306, 'fraction_numerical': 0.003370123852051563, 'mean_word_length': 1.5759548611111112, 'pattern_counts': {'":': 0, '<': 117, '<?xml version=': 0, '>': 119, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, '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': '3745408', 'n_tokens_mistral': 3018, 'n_tokens_neox': 2872, 'n_words': 1030}