<commit_before>﻿/*
* Box2D.XNA port of Box2D:
* Copyright (c) 2009 <NAME>, <NAME>
*
* Original source Box2D:
* Copyright (c) 2006-2009 <NAME> http://www.gphysics.com 
* 
* This software is provided 'as-is', without any express or implied 
* warranty.  In no event will the authors be held liable for any damages 
* arising from the use of this software. 
* Permission is granted to anyone to use this software for any purpose, 
* including commercial applications, and to alter it and redistribute it 
* freely, subject to the following restrictions: 
* 1. The origin of this software must not be misrepresented; you must not 
* claim that you wrote the original software. If you use this software 
* in a product, an acknowledgment in the product documentation would be 
* appreciated but is not required. 
* 2. Altered source versions must be plainly marked as such, and must not be 
* misrepresented as being the original software. 
* 3. This notice may not be removed or altered from any source distribution. 
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using FarseerPhysics.Common;
using Microsoft.Xna.Framework;

namespace FarseerPhysics.Collision
{
    /// A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt.
    public delegate float RayCastCallbackInternal(ref RayCastInput input, int userData);

    /// A node in the dynamic tree. The client does not interact with this directly.
    internal struct DynamicTreeNode
    {
        /// This is the fattened AABB.
        internal AABB aabb;

        internal int child1;
        internal int child2;

        internal int leafCount;
        internal int parentOrNext;
        internal object userData;

        internal bool IsLeaf()
        {
            return child1 == DynamicTree.NullNode;
        }
    }

    /// A dynamic tree arranges data in a binary tree to accelerate
    /// queries such as volume queries and ray casts. Leafs are proxies
    /// with an AABB. In the tree we expand the proxy AABB by Settings.b2_fatAABBFactor
    /// so that the proxy AABB is bigger than the client object. This allows the client
    /// object to move by small amounts without triggering a tree update.
    ///
    /// Nodes are pooled and relocatable, so we use node indices rather than pointers.
    public class DynamicTree
    {
        internal const int NullNode = -1;
        private static Stack<int> stack = new Stack<int>(256);
        private int _freeList;
        private int _insertionCount;
        private int _nodeCapacity;
        private int _nodeCount;
        private DynamicTreeNode[] _nodes;

        /// This is used incrementally traverse the tree for re-balancing.
        private int _path;

        private int _root;

        /// ructing the tree initializes the node pool.
        public DynamicTree()
        {
            _root = NullNode;

            _nodeCapacity = 16;
            _nodeCount = 0;
            _nodes = new DynamicTreeNode[_nodeCapacity];

            // Build a linked list for the free list.
            for (int i = 0; i < _nodeCapacity - 1; ++i)
            {
                _nodes[i].parentOrNext = i + 1;
            }
            _nodes[_nodeCapacity - 1].parentOrNext = NullNode;
            _freeList = 0;

            _path = 0;
        }

        /// Create a proxy. Provide a tight fitting AABB and a userData pointer.
        public int CreateProxy(ref AABB aabb, object userData)
        {
            int proxyId = AllocateNode();

            // Fatten the aabb.
            Vector2 r = new Vector2(Settings.AABBExtension, Settings.AABBExtension);
            _nodes[proxyId].aabb.LowerBound = aabb.LowerBound - r;
            _nodes[proxyId].aabb.UpperBound = aabb.UpperBound + r;
            _nodes[proxyId].userData = userData;
            _nodes[proxyId].leafCount = 1;

            InsertLeaf(proxyId);

            // Rebalance if necessary.
            int iterationCount = _nodeCount >> 4;
            int tryCount = 0;
            int height = ComputeHeight();
            while (height > 64 && tryCount < 10)
            {
                Rebalance(iterationCount);
                height = ComputeHeight();
                ++tryCount;
            }

            return proxyId;
        }

        /// Destroy a proxy. This asserts if the id is invalid.
        public void DestroyProxy(int proxyId)
        {
            Debug.Assert(0 <= proxyId && proxyId < _nodeCapacity);
            Debug.Assert(_nodes[proxyId].IsLeaf());<commit_msg>Fixed bug I reported in Box2D.XNA: http://box2dxna.codeplex.com/workitem/13709<commit_after>﻿/*
* Box2D.XNA port of Box2D:
* Copyright (c) 2009 <NAME>, <NAME>
*
* Original source Box2D:
* Copyright (c) 2006-2009 <NAME> http://www.gphysics.com 
* 
* This software is provided 'as-is', without any express or implied 
* warranty.  In no event will the authors be held liable for any damages 
* arising from the use of this software. 
* Permission is granted to anyone to use this software for any purpose, 
* including commercial applications, and to alter it and redistribute it 
* freely, subject to the following restrictions: 
* 1. The origin of this software must not be misrepresented; you must not 
* claim that you wrote the original software. If you use this software 
* in a product, an acknowledgment in the product documentation would be 
* appreciated but is not required. 
* 2. Altered source versions must be plainly marked as such, and must not be 
* misrepresented as being the original software. 
* 3. This notice may not be removed or altered from any source distribution. 
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using FarseerPhysics.Common;
using Microsoft.Xna.Framework;

namespace FarseerPhysics.Collision
{
    /// A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt.
    public delegate float RayCastCallbackInternal(ref RayCastInput input, int userData);

    /// A node in the dynamic tree. The client does not interact with this directly.
    internal struct DynamicTreeNode
    {
        /// This is the fattened AABB.
        internal AABB aabb;

        internal int child1;
        internal int child2;

        internal int leafCount;
        internal int parentOrNext;
        internal object userData;

        internal bool IsLeaf()
        {
            return child1 == DynamicTree.NullNode;
        }
    }

    /// A dynamic tree arranges data in a binary tree to accelerate
    /// queries such as volume queries and ray casts. Leafs are proxies
    /// with an AABB. In the tree we expand the proxy AABB by Settings.b2_fatAABBFactor
    /// so that the proxy AABB is bigger than the client object. This allows the client
    /// object to move by small amounts without triggering a tree update.
    ///
    /// Nodes are pooled and relocatable, so we use node indices rather than pointers.
    public class DynamicTree
    {
        internal const int NullNode = -1;
        private static Stack<int> stack = new Stack<int>(256);
        private int _freeList;
        private int _insertionCount;
        private int _nodeCapacity;
        private int _nodeCount;
        private DynamicTreeNode[] _nodes;

        /// This is used incrementally traverse the tree for re-balancing.
        private int _path;

        private int _root;

        /// ructing the tree initializes the node pool.
        public DynamicTree()
        {
            _root = NullNode;

            _nodeCapacity = 16;
            _nodeCount = 0;
            _nodes = new DynamicTreeNode[_nodeCapacity];

            // Build a linked list for the free list.
            for (int i = 0; i < _nodeCapacity - 1; ++i)
            {
                _nodes[i].parentOrNext = i + 1;
            }
            _nodes[_nodeCapacity - 1].parentOrNext = NullNode;
            _freeList = 0;

            _path = 0;
        }

        /// Create a proxy. Provide a tight fitting AABB and a userData pointer.
        public int CreateProxy(ref AABB aabb, object userData)
        {
            int proxyId = AllocateNode();

            // Fatten the aabb.
            Vector2 r = new Vector2(Settings.AABBExtension, Settings.AABBExtension);
            _nodes[proxyId].aabb.LowerBound = aabb.LowerBound - r;
            _nodes[proxyId].aabb.UpperBound = aabb.UpperBound + r;
            _nodes[proxyId].userData = userData;
            _nodes[proxyId].leafCount = 1;

            InsertLeaf(proxyId);

            return proxyId;
        }

        /// Destroy a proxy. This asserts if the id is invalid.
        public void DestroyProxy(int proxyId)
        {
            Debug.Assert(0 <= proxyId && proxyId < _nodeCapacity);
            Debug.Assert(_nodes[proxyId].IsLeaf());
{'fraction_non_alphanumeric': 0.07247863247863248, 'fraction_numerical': 0.01037037037037037, 'mean_word_length': 2.2229159015791407, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 16, 'https://': 0, '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': '2638384', 'n_tokens_mistral': 2465, 'n_tokens_neox': 2304, 'n_words': 927}