< Summary

Information
Class: SwiftCollections.Query.SwiftBVH<T1, T2>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Query/BoundingVolume/SwiftBVH.cs
Line coverage
100%
Covered lines: 205
Uncovered lines: 0
Coverable lines: 205
Total lines: 548
Line coverage: 100%
Branch coverage
96%
Covered branches: 77
Total branches: 80
Branch coverage: 96.2%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%22100%
get_NodePool()100%11100%
get_RootNode()100%44100%
get_RootNodeIndex()100%11100%
get_Count()100%11100%
AllocateNode(...)100%66100%
Insert(...)100%11100%
InsertIntoTree(...)100%66100%
CreateParentForLeaves(...)100%11100%
InsertIntoBestChild(...)100%22100%
ShouldInsertIntoLeftChild(...)100%22100%
IsSeverelyUnbalanced(...)100%11100%
ShouldInsertIntoLowerCostChild(...)100%22100%
RefreshParentNode(...)100%11100%
GetSubtreeSize(...)100%11100%
InsertIntoBuckets(...)100%11100%
UpdateEntryBounds(...)100%1010100%
Remove(...)100%66100%
RemoveFromBuckets(...)100%11100%
RemoveFromTree(...)100%22100%
ReleaseLeafAndParent(...)100%22100%
PromoteSiblingToGrandParent(...)83.33%66100%
RefreshAncestors(...)100%22100%
EnsureCapacity(...)100%22100%
Resize(...)100%44100%
ResizeBuckets(...)100%11100%
GetCombinedBounds(...)100%11100%
Query(...)100%44100%
QueryNode(...)100%44100%
PushChildNodes(...)50%44100%
ThrowIfQueryNodeIsUnallocated(...)100%44100%
FindEntry(...)100%11100%
Clear()100%44100%
GetNodeValue(...)100%11100%
IsLeafNode(...)100%11100%
MatchesEntryKey(...)100%22100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Query/BoundingVolume/SwiftBVH.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftBVH.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using SwiftCollections.Diagnostics;
 9using SwiftCollections.Utility;
 10using System;
 11using System.Collections.Generic;
 12using System.Runtime.CompilerServices;
 13
 14namespace SwiftCollections.Query;
 15
 16/// <summary>
 17/// Represents a Bounding Volume Hierarchy (BVH) optimized for spatial queries.
 18/// </summary>
 19/// <remarks>
 20/// <para>
 21/// This class is not thread-safe. Concurrent access from multiple threads must be
 22/// serialized externally (e.g., with a lock or by limiting access to a single thread).
 23/// </para>
 24/// </remarks>
 25public class SwiftBVH<TKey, TVolume>
 26    where TKey : notnull
 27    where TVolume : struct, IBoundVolume<TVolume>
 28{
 29    #region Static & Constants
 30
 31    private const string _diagnosticSource = nameof(SwiftBVH<TKey, TVolume>);
 32
 33    #endregion
 34
 35    #region Fields
 36
 37    private SwiftBVHNode<TKey, TVolume>[] _nodePool;
 38    private int _peakIndex;
 39    private int _leafCount;
 40
 41    private readonly QueryKeyIndexMap<TKey> _keyToNodeIndex;
 4442    private readonly QueryTraversalScratch _queryScratch = new();
 43
 4444    private readonly SwiftIntStack _freeIndices = new();
 45
 46    private int _rootNodeIndex;
 47
 48    #endregion
 49
 50    #region Constructor
 51
 52    /// <summary>
 53    /// Initializes a new instance of the <see cref="SwiftBVH{TKey, TVolume}"/> class with the specified capacity.
 54    /// </summary>
 4455    public SwiftBVH(int capacity)
 56    {
 4457        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 4458        _nodePool = new SwiftBVHNode<TKey, TVolume>[capacity].Populate(() =>
 4459            new SwiftBVHNode<TKey, TVolume>() { ParentIndex = -1, LeftChildIndex = -1, RightChildIndex = -1 });
 4460        _keyToNodeIndex = new QueryKeyIndexMap<TKey>(capacity);
 61
 4462        _rootNodeIndex = -1;
 63
 4464        _freeIndices = new SwiftIntStack(SwiftIntStack.DefaultCapacity);
 4465    }
 66
 67    #endregion
 68
 69    #region Properties
 70
 71    /// <summary>
 72    /// Gets the underlying pool of nodes used in the BVH.
 73    /// </summary>
 805374    public SwiftBVHNode<TKey, TVolume>[] NodePool => _nodePool;
 75
 76    /// <summary>
 77    /// Gets the root node of the BVH.
 78    /// </summary>
 679    public SwiftBVHNode<TKey, TVolume> RootNode => _rootNodeIndex >= 0 && _nodePool[_rootNodeIndex].IsAllocated
 680        ? _nodePool[_rootNodeIndex]
 681        : SwiftBVHNode<TKey, TVolume>.Default;
 82
 83    /// <summary>
 84    /// Gets the index of the root node in the BVH.
 85    /// </summary>
 20486    public int RootNodeIndex => _rootNodeIndex;
 87
 88    /// <summary>
 89    /// Gets the total number of leaf nodes in the BVH.
 90    /// </summary>
 691    public int Count => _leafCount;
 92
 93    #endregion
 94
 95    #region Collection Manipulation
 96
 97    /// <summary>
 98    /// Allocates a new node with the specified value, bounds, and leaf status.
 99    /// Reuses indices from the freelist when available.
 100    /// </summary>
 101    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 102    private int AllocateNode(TKey value, TVolume bounds, bool isLeaf)
 103    {
 104        int index;
 105
 106        // Check if there are any reusable indices in the freelist
 26440107        if (_freeIndices.Count > 0)
 4108            index = _freeIndices.Pop(); // Reuse an available index
 109        else
 110        {
 26436111            if (_peakIndex + 1 >= _nodePool.Length)
 26112                Resize(_nodePool.Length * 2);
 113
 114            // Allocate a new index if freelist is empty
 26436115            index = _peakIndex++;
 116        }
 117
 26440118        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 26440119        node.Reset(); // Explicit reset
 26440120        node.MyIndex = index;
 26440121        node.Value = value;
 26440122        node.Bounds = bounds;
 123
 26440124        if (isLeaf)
 125        {
 13240126            node.IsLeaf = isLeaf;
 13240127            node.SubtreeSize = 1;
 13240128            _leafCount++;
 129        }
 130
 26440131        node.IsAllocated = true;
 132
 26440133        return index;
 134    }
 135
 136    /// <summary>
 137    /// Inserts a bounding volume with an associated value into the BVH.
 138    /// Ensures tree balance and updates hash buckets.
 139    /// </summary>
 140    public bool Insert(TKey value, TVolume bounds)
 141    {
 13240142        int newNodeIndex = AllocateNode(value, bounds, true); // Allocate new node as a leaf
 13240143        _rootNodeIndex = InsertIntoTree(_rootNodeIndex, newNodeIndex);
 13240144        InsertIntoBuckets(value, newNodeIndex);
 13240145        return true;
 146    }
 147
 148    /// <summary>
 149    /// Inserts a node into the tree while maintaining tree balance.
 150    /// Adjusts parent-child relationships as necessary.
 151    /// </summary>
 152    [MethodImpl(MethodImplOptions.NoInlining)]
 153    private int InsertIntoTree(int parentNodeIndex, int newNodeIndex)
 154    {
 151862155        if (parentNodeIndex < 0 || !_nodePool[parentNodeIndex].IsAllocated)
 40156            return newNodeIndex;
 157
 151822158        if (_nodePool[parentNodeIndex].IsLeaf)
 13200159            return CreateParentForLeaves(parentNodeIndex, newNodeIndex);
 160
 138622161        InsertIntoBestChild(parentNodeIndex, newNodeIndex);
 138622162        RefreshParentNode(parentNodeIndex);
 138622163        return parentNodeIndex;
 164    }
 165
 166    private int CreateParentForLeaves(int existingLeafIndex, int newLeafIndex)
 167    {
 13200168        TVolume combinedBounds = _nodePool[existingLeafIndex].Bounds.Union(_nodePool[newLeafIndex].Bounds);
 13200169        int oldParentIndex = _nodePool[existingLeafIndex].ParentIndex;
 13200170        int newParentIndex = AllocateNode(default!, combinedBounds, false);
 171
 13200172        ref SwiftBVHNode<TKey, TVolume> newParentNode = ref _nodePool[newParentIndex];
 13200173        newParentNode.ParentIndex = oldParentIndex;
 13200174        newParentNode.LeftChildIndex = existingLeafIndex;
 13200175        newParentNode.RightChildIndex = newLeafIndex;
 13200176        newParentNode.SubtreeSize = 1 + _nodePool[existingLeafIndex].SubtreeSize + _nodePool[newLeafIndex].SubtreeSize;
 177
 13200178        _nodePool[existingLeafIndex].ParentIndex = newParentIndex;
 13200179        _nodePool[newLeafIndex].ParentIndex = newParentIndex;
 180
 13200181        return newParentIndex;
 182    }
 183
 184    private void InsertIntoBestChild(int parentNodeIndex, int newNodeIndex)
 185    {
 138622186        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 138622187        if (ShouldInsertIntoLeftChild(parentNodeIndex, newNodeIndex))
 70128188            parentNode.LeftChildIndex = InsertIntoTree(parentNode.LeftChildIndex, newNodeIndex);
 189        else
 68494190            parentNode.RightChildIndex = InsertIntoTree(parentNode.RightChildIndex, newNodeIndex);
 68494191    }
 192
 193    private bool ShouldInsertIntoLeftChild(int parentNodeIndex, int newNodeIndex)
 194    {
 138622195        SwiftBVHNode<TKey, TVolume> parentNode = _nodePool[parentNodeIndex];
 138622196        SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parentNode.LeftChildIndex];
 138622197        SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parentNode.RightChildIndex];
 138622198        int leftSize = GetSubtreeSize(leftChild);
 138622199        int rightSize = GetSubtreeSize(rightChild);
 200
 138622201        if (IsSeverelyUnbalanced(leftSize, rightSize))
 12649202            return leftSize <= rightSize;
 203
 125973204        return ShouldInsertIntoLowerCostChild(
 125973205            leftChild,
 125973206            rightChild,
 125973207            leftSize,
 125973208            rightSize,
 125973209            _nodePool[newNodeIndex].Bounds);
 210    }
 211
 212    private static bool IsSeverelyUnbalanced(int leftSize, int rightSize)
 213    {
 138622214        int maxSize = Math.Max(leftSize, rightSize);
 138622215        int minSize = Math.Min(leftSize, rightSize);
 138622216        return maxSize > minSize * 2;
 217    }
 218
 219    private static bool ShouldInsertIntoLowerCostChild(
 220        SwiftBVHNode<TKey, TVolume> leftChild,
 221        SwiftBVHNode<TKey, TVolume> rightChild,
 222        int leftSize,
 223        int rightSize,
 224        TVolume newBounds)
 225    {
 125973226        long leftCost = leftChild.Bounds.GetCost(newBounds);
 125973227        long rightCost = rightChild.Bounds.GetCost(newBounds);
 228
 125973229        if (leftCost == rightCost)
 5737230            return leftSize <= rightSize;
 231
 120236232        return leftCost < rightCost;
 233    }
 234
 235    private void RefreshParentNode(int parentNodeIndex)
 236    {
 139111237        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 139111238        SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parentNode.LeftChildIndex];
 139111239        SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parentNode.RightChildIndex];
 240
 139111241        parentNode.Bounds = GetCombinedBounds(leftChild, rightChild);
 139111242        parentNode.SubtreeSize = 1 + GetSubtreeSize(leftChild) + GetSubtreeSize(rightChild);
 139111243    }
 244
 245    private static int GetSubtreeSize(SwiftBVHNode<TKey, TVolume> node)
 246    {
 555466247        return node.SubtreeSize;
 248    }
 249
 250    /// <summary>
 251    /// Inserts a value into the hash bucket for fast lookup.
 252    /// Handles collisions with linear probing.
 253    /// </summary>
 254    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 255    private void InsertIntoBuckets(TKey value, int nodeIndex)
 256    {
 13240257        _keyToNodeIndex.Insert(value, nodeIndex);
 13240258    }
 259
 260    /// <summary>
 261    /// Updates the bounding volume of a node and propagates changes up the tree.
 262    /// Ensures consistency in parent bounds and subtree sizes.
 263    /// </summary>
 264    public void UpdateEntryBounds(TKey value, TVolume newBounds)
 265    {
 8266        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 267
 8268        int index = _keyToNodeIndex.Find(value, MatchesEntryKey);
 9269        if (index == -1) return;
 270
 7271        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 8272        if (!node.IsAllocated) return; // Skip update if node has been removed
 273
 6274        TVolume oldBounds = node.Bounds;
 6275        if (oldBounds.BoundsEquals(newBounds))
 1276            return; // Skip unnecessary updates
 277
 5278        node.Bounds = newBounds;
 279
 280        // Propagate changes up the tree
 5281        int parentIndex = node.ParentIndex;
 9282        while (parentIndex != -1)
 283        {
 5284            ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 5285            SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parent.LeftChildIndex];
 5286            SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parent.RightChildIndex];
 287
 5288            TVolume newParentBounds = GetCombinedBounds(leftChild, rightChild);
 5289            if (parent.Bounds.BoundsEquals(newParentBounds))
 290                break; // No further updates needed
 291
 4292            parent.Bounds = newParentBounds;
 4293            parentIndex = parent.ParentIndex;
 294        }
 5295    }
 296
 297    /// <summary>
 298    /// Removes a value and its associated bounding volume from the BVH.
 299    /// Updates tree structure and clears hash bucket entries.
 300    /// </summary>
 301    public bool Remove(TKey value)
 302    {
 135303        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 304
 135305        int nodeIndex = _keyToNodeIndex.Find(value, MatchesEntryKey);
 137306        if (nodeIndex == -1) return false;
 307
 308        // If the node is the root and the only node, reset the BVH
 133309        if (nodeIndex == RootNodeIndex && _leafCount == 1)
 310        {
 2311            Clear();
 2312            return true;
 313        }
 314
 131315        RemoveFromBuckets(value); // Ensure the bucket is cleared before further operations
 316
 317        // Remove node and update tree structure
 131318        RemoveFromTree(nodeIndex);
 319
 131320        return true;
 321    }
 322
 323    /// <summary>
 324    /// Removes an entry from the hash buckets, resolving collisions as necessary.
 325    /// </summary>
 326    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 327    private void RemoveFromBuckets(TKey value)
 328    {
 131329        _keyToNodeIndex.Remove(value, MatchesEntryKey, IsLeafNode, GetNodeValue);
 131330    }
 331
 332    /// <summary>
 333    /// Removes a leaf node from the tree, collapses its parent, and propagates
 334    /// bound and subtree-size updates upward.  Every internal node is guaranteed
 335    /// to have exactly two children after this operation completes.
 336    /// </summary>
 337    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 338    private void RemoveFromTree(int nodeIndex)
 339    {
 131340        int parentIndex = _nodePool[nodeIndex].ParentIndex;
 341
 131342        int siblingIndex = ReleaseLeafAndParent(nodeIndex, parentIndex, out int grandParentIndex);
 131343        PromoteSiblingToGrandParent(siblingIndex, parentIndex, grandParentIndex);
 131344        if (grandParentIndex != -1)
 125345            RefreshAncestors(grandParentIndex);
 131346    }
 347
 348    private int ReleaseLeafAndParent(int nodeIndex, int parentIndex, out int grandParentIndex)
 349    {
 131350        ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 131351        int siblingIndex = parent.LeftChildIndex == nodeIndex
 131352            ? parent.RightChildIndex
 131353            : parent.LeftChildIndex;
 131354        grandParentIndex = parent.ParentIndex;
 355
 356        // Push parent before the leaf so that the leaf index sits on top of the
 357        // freelist stack and is reused first by the next allocation.
 131358        parent.Reset();
 131359        _freeIndices.Push(parentIndex);
 360
 131361        _leafCount--;
 131362        _nodePool[nodeIndex].Reset();
 131363        _freeIndices.Push(nodeIndex);
 364
 131365        return siblingIndex;
 366    }
 367
 368    private void PromoteSiblingToGrandParent(int siblingIndex, int parentIndex, int grandParentIndex)
 369    {
 131370        if (siblingIndex != -1)
 131371            _nodePool[siblingIndex].ParentIndex = grandParentIndex;
 372
 131373        if (grandParentIndex == -1)
 374        {
 6375            _rootNodeIndex = siblingIndex;
 6376            return;
 377        }
 378
 125379        ref SwiftBVHNode<TKey, TVolume> grandParent = ref _nodePool[grandParentIndex];
 125380        if (grandParent.LeftChildIndex == parentIndex)
 65381            grandParent.LeftChildIndex = siblingIndex;
 382        else
 60383            grandParent.RightChildIndex = siblingIndex;
 60384    }
 385
 386    private void RefreshAncestors(int current)
 387    {
 614388        while (current != -1)
 389        {
 489390            RefreshParentNode(current);
 489391            current = _nodePool[current].ParentIndex;
 392        }
 125393    }
 394
 395    #endregion
 396
 397    #region Capacity Management
 398
 399    /// <summary>
 400    /// Ensures the BVH has sufficient capacity, resizing the node pool and buckets if needed.
 401    /// </summary>
 402    public void EnsureCapacity(int capacity)
 403    {
 2404        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 2405        if (capacity > _nodePool.Length)
 1406            Resize(capacity);
 2407    }
 408
 409    /// <summary>
 410    /// Resizes the internal node pool to accommodate additional nodes.
 411    /// Preserves existing nodes and reinitializes the expanded capacity.
 412    /// </summary>
 413    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 414    private void Resize(int newSize)
 415    {
 27416        SwiftBVHNode<TKey, TVolume>[] newArray = new SwiftBVHNode<TKey, TVolume>[newSize];
 27417        Array.Copy(_nodePool, 0, newArray, 0, _peakIndex);
 418
 70438419        for (int i = _peakIndex; i < newSize; i++)
 35192420            newArray[i].Reset(); // set default index lookup values
 421
 27422        _nodePool = newArray;
 423
 27424        ResizeBuckets(newSize);
 27425        SwiftCollectionDiagnostics.Shared.Info($"Resized BVH storage to {newSize} nodes.", _diagnosticSource);
 27426    }
 427
 428    /// <summary>
 429    /// Resizes and rehashes the hash buckets to maintain lookup efficiency.
 430    /// Rehashes existing nodes after resizing.
 431    /// </summary>
 432    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 433    private void ResizeBuckets(int newSize)
 434    {
 27435        _keyToNodeIndex.ResizeAndRehash(newSize, _peakIndex, IsLeafNode, GetNodeValue);
 27436    }
 437
 438    #endregion
 439
 440    #region Utility Methods
 441
 442    /// <summary>
 443    /// Gets the combined bounding volume of two child nodes.
 444    /// Handles cases where one or both children are missing.
 445    /// </summary>
 446    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 447    private static TVolume GetCombinedBounds(SwiftBVHNode<TKey, TVolume> leftChild, SwiftBVHNode<TKey, TVolume> rightChi
 448    {
 139116449        return leftChild.Bounds.Union(rightChild.Bounds);
 450    }
 451
 452    /// <summary>
 453    /// Queries the BVH for values whose bounding volumes intersect with the specified volume.
 454    /// Uses a stack-based approach for efficient traversal.
 455    /// </summary>
 456    public void Query(TVolume queryBounds, ICollection<TKey> results)
 457    {
 30458        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 459
 33460        if (RootNodeIndex == -1) return;
 461
 27462        SwiftIntStack nodeStack = _queryScratch.RentIntStack(_peakIndex + 1);
 27463        nodeStack.Push(RootNodeIndex);
 464
 21078465        while (nodeStack.Count > 0)
 466        {
 21053467            int index = nodeStack.Pop();
 21053468            QueryNode(index, queryBounds, results, nodeStack);
 469        }
 25470    }
 471
 472    private void QueryNode(int index, TVolume queryBounds, ICollection<TKey> results, SwiftIntStack nodeStack)
 473    {
 21053474        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 21053475        ThrowIfQueryNodeIsUnallocated(index, node);
 476
 21051477        if (!queryBounds.Intersects(node.Bounds))
 307478            return;
 479
 20744480        if (node.IsLeaf)
 481        {
 10231482            results.Add(node.Value);
 10231483            return;
 484        }
 485
 10513486        PushChildNodes(node, nodeStack);
 10513487    }
 488
 489    private static void PushChildNodes(SwiftBVHNode<TKey, TVolume> node, SwiftIntStack nodeStack)
 490    {
 10513491        if (node.HasLeftChild)
 10513492            nodeStack.Push(node.LeftChildIndex);
 10513493        if (node.HasRightChild)
 10513494            nodeStack.Push(node.RightChildIndex);
 10513495    }
 496
 497    private static void ThrowIfQueryNodeIsUnallocated(int index, SwiftBVHNode<TKey, TVolume> node)
 498    {
 21053499        if (node.IsAllocated)
 21051500            return;
 501
 2502        SwiftCollectionDiagnostics.Shared.Error($"Encountered an unallocated node at index {index} during query traversa
 2503        throw new InvalidOperationException($"Encountered an unallocated node at index {index} during query traversal.")
 504    }
 505
 506    /// <summary>
 507    /// Finds the index of a node by its value in the BVH using hash buckets.
 508    /// Returns -1 if the value is not found.
 509    /// </summary>
 510    public int FindEntry(TKey value)
 511    {
 12512        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 12513        return _keyToNodeIndex.Find(value, MatchesEntryKey);
 514    }
 515
 516    /// <summary>
 517    /// Clears the BVH, resetting all nodes, buckets, and metadata.
 518    /// </summary>
 519    public void Clear()
 520    {
 5521        if (RootNodeIndex == -1) return;
 522
 208523        for (int i = 0; i < _peakIndex; i++)
 101524            _nodePool[i].Reset();
 525
 3526        _keyToNodeIndex.Clear();
 527
 3528        _freeIndices.Reset();
 529
 3530        _leafCount = 0;
 3531        _peakIndex = 0;
 3532        _rootNodeIndex = -1;
 3533    }
 534
 535    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 18528536    private TKey GetNodeValue(int index) => _nodePool[index].Value;
 537
 538    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 36082539    private bool IsLeafNode(int index) => _nodePool[index].IsLeaf;
 540
 541    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 542    private bool MatchesEntryKey(int index, TKey value)
 543    {
 286544        return _nodePool[index].IsLeaf && EqualityComparer<TKey>.Default.Equals(_nodePool[index].Value, value);
 545    }
 546
 547    #endregion
 548}
Generated by: ReportGenerator 5.5.10.0
07/01/2026 - 04:31:31
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Int32)
get_NodePool()
get_RootNode()
get_RootNodeIndex()
get_Count()
AllocateNode(TKey,TVolume,System.Boolean)
Insert(TKey,TVolume)
InsertIntoTree(System.Int32,System.Int32)
CreateParentForLeaves(System.Int32,System.Int32)
InsertIntoBestChild(System.Int32,System.Int32)
ShouldInsertIntoLeftChild(System.Int32,System.Int32)
IsSeverelyUnbalanced(System.Int32,System.Int32)
ShouldInsertIntoLowerCostChild(SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>,SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>,System.Int32,System.Int32,TVolume)
RefreshParentNode(System.Int32)
GetSubtreeSize(SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>)
InsertIntoBuckets(TKey,System.Int32)
UpdateEntryBounds(TKey,TVolume)
Remove(TKey)
RemoveFromBuckets(TKey)
RemoveFromTree(System.Int32)
ReleaseLeafAndParent(System.Int32,System.Int32,System.Int32&)
PromoteSiblingToGrandParent(System.Int32,System.Int32,System.Int32)
RefreshAncestors(System.Int32)
EnsureCapacity(System.Int32)
Resize(System.Int32)
ResizeBuckets(System.Int32)
GetCombinedBounds(SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>,SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>)
Query(TVolume,System.Collections.Generic.ICollection`1<TKey>)
QueryNode(System.Int32,TVolume,System.Collections.Generic.ICollection`1<TKey>,SwiftCollections.SwiftIntStack)
PushChildNodes(SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>,SwiftCollections.SwiftIntStack)
ThrowIfQueryNodeIsUnallocated(System.Int32,SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>)
FindEntry(TKey)
Clear()
GetNodeValue(System.Int32)
IsLeafNode(System.Int32)
MatchesEntryKey(System.Int32,TKey)