< 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: 202
Uncovered lines: 0
Coverable lines: 202
Total lines: 548
Line coverage: 100%
Branch coverage
100%
Covered branches: 74
Total branches: 74
Branch coverage: 100%
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(...)100%44100%
RefreshAncestors(...)100%22100%
EnsureCapacity(...)100%22100%
Resize(...)100%44100%
ResizeBuckets(...)100%11100%
GetCombinedBounds(...)100%11100%
Query(...)100%44100%
QueryNode(...)100%44100%
PushChildNodes(...)100%11100%
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 System;
 9using System.Collections.Generic;
 10using System.Runtime.CompilerServices;
 11using SwiftCollections.Diagnostics;
 12using SwiftCollections.Utility;
 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, MatchesEntryKey, IsLeafNode, GetNodeValue);
 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>
 74    /// <remarks>
 75    /// Prefer BVH APIs. Direct structural mutation must preserve tree invariants; invalid edits may fail fast.
 76    /// </remarks>
 805377    public SwiftBVHNode<TKey, TVolume>[] NodePool => _nodePool;
 78
 79    /// <summary>
 80    /// Gets the root node of the BVH.
 81    /// </summary>
 682    public SwiftBVHNode<TKey, TVolume> RootNode => _rootNodeIndex >= 0 && _nodePool[_rootNodeIndex].IsAllocated
 683        ? _nodePool[_rootNodeIndex]
 684        : SwiftBVHNode<TKey, TVolume>.Default;
 85
 86    /// <summary>
 87    /// Gets the index of the root node in the BVH.
 88    /// </summary>
 20489    public int RootNodeIndex => _rootNodeIndex;
 90
 91    /// <summary>
 92    /// Gets the total number of leaf nodes in the BVH.
 93    /// </summary>
 694    public int Count => _leafCount;
 95
 96    #endregion
 97
 98    #region Collection Manipulation
 99
 100    /// <summary>
 101    /// Allocates a new node with the specified value, bounds, and leaf status.
 102    /// Reuses indices from the freelist when available.
 103    /// </summary>
 104    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 105    private int AllocateNode(TKey value, TVolume bounds, bool isLeaf)
 106    {
 107        int index;
 108
 109        // Check if there are any reusable indices in the freelist
 26442110        if (_freeIndices.Count > 0)
 4111            index = _freeIndices.Pop(); // Reuse an available index
 112        else
 113        {
 26438114            if (_peakIndex + 1 >= _nodePool.Length)
 27115                Resize(_nodePool.Length * 2);
 116
 117            // Allocate a new index if freelist is empty
 26438118            index = _peakIndex++;
 119        }
 120
 26442121        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 26442122        node.Reset(); // Explicit reset
 26442123        node.MyIndex = index;
 26442124        node.Value = value;
 26442125        node.Bounds = bounds;
 126
 26442127        if (isLeaf)
 128        {
 13241129            node.IsLeaf = isLeaf;
 13241130            node.SubtreeSize = 1;
 13241131            _leafCount++;
 132        }
 133
 26442134        node.IsAllocated = true;
 135
 26442136        return index;
 137    }
 138
 139    /// <summary>
 140    /// Inserts a bounding volume with an associated value into the BVH.
 141    /// Ensures tree balance and updates hash buckets.
 142    /// </summary>
 143    public bool Insert(TKey value, TVolume bounds)
 144    {
 13241145        int newNodeIndex = AllocateNode(value, bounds, true); // Allocate new node as a leaf
 13241146        _rootNodeIndex = InsertIntoTree(_rootNodeIndex, newNodeIndex);
 13241147        InsertIntoBuckets(value, newNodeIndex);
 13241148        return true;
 149    }
 150
 151    /// <summary>
 152    /// Inserts a node into the tree while maintaining tree balance.
 153    /// Adjusts parent-child relationships as necessary.
 154    /// </summary>
 155    [MethodImpl(MethodImplOptions.NoInlining)]
 156    private int InsertIntoTree(int parentNodeIndex, int newNodeIndex)
 157    {
 151880158        if (parentNodeIndex < 0 || !_nodePool[parentNodeIndex].IsAllocated)
 40159            return newNodeIndex;
 160
 151840161        if (_nodePool[parentNodeIndex].IsLeaf)
 13201162            return CreateParentForLeaves(parentNodeIndex, newNodeIndex);
 163
 138639164        InsertIntoBestChild(parentNodeIndex, newNodeIndex);
 138639165        RefreshParentNode(parentNodeIndex);
 138639166        return parentNodeIndex;
 167    }
 168
 169    private int CreateParentForLeaves(int existingLeafIndex, int newLeafIndex)
 170    {
 13201171        TVolume combinedBounds = _nodePool[existingLeafIndex].Bounds.Union(_nodePool[newLeafIndex].Bounds);
 13201172        int oldParentIndex = _nodePool[existingLeafIndex].ParentIndex;
 13201173        int newParentIndex = AllocateNode(default!, combinedBounds, false);
 174
 13201175        ref SwiftBVHNode<TKey, TVolume> newParentNode = ref _nodePool[newParentIndex];
 13201176        newParentNode.ParentIndex = oldParentIndex;
 13201177        newParentNode.LeftChildIndex = existingLeafIndex;
 13201178        newParentNode.RightChildIndex = newLeafIndex;
 13201179        newParentNode.SubtreeSize = 1 + _nodePool[existingLeafIndex].SubtreeSize + _nodePool[newLeafIndex].SubtreeSize;
 180
 13201181        _nodePool[existingLeafIndex].ParentIndex = newParentIndex;
 13201182        _nodePool[newLeafIndex].ParentIndex = newParentIndex;
 183
 13201184        return newParentIndex;
 185    }
 186
 187    private void InsertIntoBestChild(int parentNodeIndex, int newNodeIndex)
 188    {
 138639189        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 138639190        if (ShouldInsertIntoLeftChild(parentNodeIndex, newNodeIndex))
 70202191            parentNode.LeftChildIndex = InsertIntoTree(parentNode.LeftChildIndex, newNodeIndex);
 192        else
 68437193            parentNode.RightChildIndex = InsertIntoTree(parentNode.RightChildIndex, newNodeIndex);
 68437194    }
 195
 196    private bool ShouldInsertIntoLeftChild(int parentNodeIndex, int newNodeIndex)
 197    {
 138639198        SwiftBVHNode<TKey, TVolume> parentNode = _nodePool[parentNodeIndex];
 138639199        SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parentNode.LeftChildIndex];
 138639200        SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parentNode.RightChildIndex];
 138639201        int leftSize = GetSubtreeSize(leftChild);
 138639202        int rightSize = GetSubtreeSize(rightChild);
 203
 138639204        if (IsSeverelyUnbalanced(leftSize, rightSize))
 12627205            return leftSize <= rightSize;
 206
 126012207        return ShouldInsertIntoLowerCostChild(
 126012208            leftChild,
 126012209            rightChild,
 126012210            leftSize,
 126012211            rightSize,
 126012212            _nodePool[newNodeIndex].Bounds);
 213    }
 214
 215    private static bool IsSeverelyUnbalanced(int leftSize, int rightSize)
 216    {
 138639217        int maxSize = Math.Max(leftSize, rightSize);
 138639218        int minSize = Math.Min(leftSize, rightSize);
 138639219        return maxSize > minSize * 2;
 220    }
 221
 222    private static bool ShouldInsertIntoLowerCostChild(
 223        SwiftBVHNode<TKey, TVolume> leftChild,
 224        SwiftBVHNode<TKey, TVolume> rightChild,
 225        int leftSize,
 226        int rightSize,
 227        TVolume newBounds)
 228    {
 126012229        long leftCost = leftChild.Bounds.GetCost(newBounds);
 126012230        long rightCost = rightChild.Bounds.GetCost(newBounds);
 231
 126012232        if (leftCost == rightCost)
 5700233            return leftSize <= rightSize;
 234
 120312235        return leftCost < rightCost;
 236    }
 237
 238    private void RefreshParentNode(int parentNodeIndex)
 239    {
 139128240        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 139128241        SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parentNode.LeftChildIndex];
 139128242        SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parentNode.RightChildIndex];
 243
 139128244        parentNode.Bounds = GetCombinedBounds(leftChild, rightChild);
 139128245        parentNode.SubtreeSize = 1 + GetSubtreeSize(leftChild) + GetSubtreeSize(rightChild);
 139128246    }
 247
 248    private static int GetSubtreeSize(SwiftBVHNode<TKey, TVolume> node)
 249    {
 555534250        return node.SubtreeSize;
 251    }
 252
 253    /// <summary>
 254    /// Inserts a value into the hash bucket for fast lookup.
 255    /// Handles collisions with linear probing.
 256    /// </summary>
 257    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 258    private void InsertIntoBuckets(TKey value, int nodeIndex)
 259    {
 13241260        _keyToNodeIndex.Insert(value, nodeIndex);
 13241261    }
 262
 263    /// <summary>
 264    /// Updates the bounding volume of a node and propagates changes up the tree.
 265    /// Ensures consistency in parent bounds and subtree sizes.
 266    /// </summary>
 267    public void UpdateEntryBounds(TKey value, TVolume newBounds)
 268    {
 8269        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 270
 8271        int index = _keyToNodeIndex.Find(value);
 9272        if (index == -1) return;
 273
 7274        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 8275        if (!node.IsAllocated) return; // Skip update if node has been removed
 276
 6277        TVolume oldBounds = node.Bounds;
 6278        if (oldBounds.BoundsEquals(newBounds))
 1279            return; // Skip unnecessary updates
 280
 5281        node.Bounds = newBounds;
 282
 283        // Propagate changes up the tree
 5284        int parentIndex = node.ParentIndex;
 9285        while (parentIndex != -1)
 286        {
 5287            ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 5288            SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parent.LeftChildIndex];
 5289            SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parent.RightChildIndex];
 290
 5291            TVolume newParentBounds = GetCombinedBounds(leftChild, rightChild);
 5292            if (parent.Bounds.BoundsEquals(newParentBounds))
 293                break; // No further updates needed
 294
 4295            parent.Bounds = newParentBounds;
 4296            parentIndex = parent.ParentIndex;
 297        }
 5298    }
 299
 300    /// <summary>
 301    /// Removes a value and its associated bounding volume from the BVH.
 302    /// Updates tree structure and clears hash bucket entries.
 303    /// </summary>
 304    public bool Remove(TKey value)
 305    {
 135306        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 307
 135308        int nodeIndex = _keyToNodeIndex.Find(value);
 137309        if (nodeIndex == -1) return false;
 310
 311        // If the node is the root and the only node, reset the BVH
 133312        if (nodeIndex == RootNodeIndex && _leafCount == 1)
 313        {
 2314            Clear();
 2315            return true;
 316        }
 317
 131318        RemoveFromBuckets(value); // Ensure the bucket is cleared before further operations
 319
 320        // Remove node and update tree structure
 131321        RemoveFromTree(nodeIndex);
 322
 131323        return true;
 324    }
 325
 326    /// <summary>
 327    /// Removes an entry from the hash buckets, resolving collisions as necessary.
 328    /// </summary>
 329    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 330    private void RemoveFromBuckets(TKey value)
 331    {
 131332        _keyToNodeIndex.Remove(value);
 131333    }
 334
 335    /// <summary>
 336    /// Removes a leaf node from the tree, collapses its parent, and propagates
 337    /// bound and subtree-size updates upward.  Every internal node is guaranteed
 338    /// to have exactly two children after this operation completes.
 339    /// </summary>
 340    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 341    private void RemoveFromTree(int nodeIndex)
 342    {
 131343        int parentIndex = _nodePool[nodeIndex].ParentIndex;
 344
 131345        int siblingIndex = ReleaseLeafAndParent(nodeIndex, parentIndex, out int grandParentIndex);
 131346        PromoteSiblingToGrandParent(siblingIndex, parentIndex, grandParentIndex);
 131347        if (grandParentIndex != -1)
 125348            RefreshAncestors(grandParentIndex);
 131349    }
 350
 351    private int ReleaseLeafAndParent(int nodeIndex, int parentIndex, out int grandParentIndex)
 352    {
 131353        ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 131354        int siblingIndex = parent.LeftChildIndex == nodeIndex
 131355            ? parent.RightChildIndex
 131356            : parent.LeftChildIndex;
 131357        grandParentIndex = parent.ParentIndex;
 358
 359        // Push parent before the leaf so that the leaf index sits on top of the
 360        // freelist stack and is reused first by the next allocation.
 131361        parent.Reset();
 131362        _freeIndices.Push(parentIndex);
 363
 131364        _leafCount--;
 131365        _nodePool[nodeIndex].Reset();
 131366        _freeIndices.Push(nodeIndex);
 367
 131368        return siblingIndex;
 369    }
 370
 371    private void PromoteSiblingToGrandParent(int siblingIndex, int parentIndex, int grandParentIndex)
 372    {
 131373        _nodePool[siblingIndex].ParentIndex = grandParentIndex;
 374
 131375        if (grandParentIndex == -1)
 376        {
 6377            _rootNodeIndex = siblingIndex;
 6378            return;
 379        }
 380
 125381        ref SwiftBVHNode<TKey, TVolume> grandParent = ref _nodePool[grandParentIndex];
 125382        if (grandParent.LeftChildIndex == parentIndex)
 65383            grandParent.LeftChildIndex = siblingIndex;
 384        else
 60385            grandParent.RightChildIndex = siblingIndex;
 60386    }
 387
 388    private void RefreshAncestors(int current)
 389    {
 614390        while (current != -1)
 391        {
 489392            RefreshParentNode(current);
 489393            current = _nodePool[current].ParentIndex;
 394        }
 125395    }
 396
 397    #endregion
 398
 399    #region Capacity Management
 400
 401    /// <summary>
 402    /// Ensures the BVH has sufficient capacity, resizing the node pool and buckets if needed.
 403    /// </summary>
 404    public void EnsureCapacity(int capacity)
 405    {
 2406        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 2407        if (capacity > _nodePool.Length)
 1408            Resize(capacity);
 2409    }
 410
 411    /// <summary>
 412    /// Resizes the internal node pool to accommodate additional nodes.
 413    /// Preserves existing nodes and reinitializes the expanded capacity.
 414    /// </summary>
 415    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 416    private void Resize(int newSize)
 417    {
 28418        SwiftBVHNode<TKey, TVolume>[] newArray = new SwiftBVHNode<TKey, TVolume>[newSize];
 28419        Array.Copy(_nodePool, 0, newArray, 0, _peakIndex);
 420
 70450421        for (int i = _peakIndex; i < newSize; i++)
 35197422            newArray[i].Reset(); // set default index lookup values
 423
 28424        _nodePool = newArray;
 425
 28426        ResizeBuckets(newSize);
 28427        SwiftCollectionDiagnostics.Shared.Info($"Resized BVH storage to {newSize} nodes.", _diagnosticSource);
 28428    }
 429
 430    /// <summary>
 431    /// Resizes and rehashes the hash buckets to maintain lookup efficiency.
 432    /// Rehashes existing nodes after resizing.
 433    /// </summary>
 434    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 435    private void ResizeBuckets(int newSize)
 436    {
 28437        _keyToNodeIndex.ResizeAndRehash(newSize, _peakIndex);
 28438    }
 439
 440    #endregion
 441
 442    #region Utility Methods
 443
 444    /// <summary>
 445    /// Gets the combined bounding volume of two child nodes.
 446    /// Handles cases where one or both children are missing.
 447    /// </summary>
 448    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 449    private static TVolume GetCombinedBounds(SwiftBVHNode<TKey, TVolume> leftChild, SwiftBVHNode<TKey, TVolume> rightChi
 450    {
 139133451        return leftChild.Bounds.Union(rightChild.Bounds);
 452    }
 453
 454    /// <summary>
 455    /// Queries the BVH for values whose bounding volumes intersect with the specified volume.
 456    /// Uses a stack-based approach for efficient traversal.
 457    /// </summary>
 458    public void Query(TVolume queryBounds, ICollection<TKey> results)
 459    {
 30460        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 461
 33462        if (RootNodeIndex == -1) return;
 463
 27464        SwiftIntStack nodeStack = _queryScratch.RentIntStack(_peakIndex + 1);
 27465        nodeStack.Push(RootNodeIndex);
 466
 21080467        while (nodeStack.Count > 0)
 468        {
 21055469            int index = nodeStack.Pop();
 21055470            QueryNode(index, queryBounds, results, nodeStack);
 471        }
 25472    }
 473
 474    private void QueryNode(int index, TVolume queryBounds, ICollection<TKey> results, SwiftIntStack nodeStack)
 475    {
 21055476        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 21055477        ThrowIfQueryNodeIsUnallocated(index, node);
 478
 21053479        if (!queryBounds.Intersects(node.Bounds))
 307480            return;
 481
 20746482        if (node.IsLeaf)
 483        {
 10232484            results.Add(node.Value);
 10232485            return;
 486        }
 487
 10514488        PushChildNodes(node, nodeStack);
 10514489    }
 490
 491    private static void PushChildNodes(SwiftBVHNode<TKey, TVolume> node, SwiftIntStack nodeStack)
 492    {
 10514493        nodeStack.Push(node.LeftChildIndex);
 10514494        nodeStack.Push(node.RightChildIndex);
 10514495    }
 496
 497    private static void ThrowIfQueryNodeIsUnallocated(int index, SwiftBVHNode<TKey, TVolume> node)
 498    {
 21055499        if (node.IsAllocated)
 21053500            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);
 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)]
 18530536    private TKey GetNodeValue(int index) => _nodePool[index].Value;
 537
 538    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 35135539    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.11.0
08/05/2026 - 03:54:48
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)