< 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: 549
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 Chronicler.Diagnostics;
 12using SwiftCollections.Diagnostics;
 13using SwiftCollections.Utility;
 14
 15namespace SwiftCollections.Query;
 16
 17/// <summary>
 18/// Represents a Bounding Volume Hierarchy (BVH) optimized for spatial queries.
 19/// </summary>
 20/// <remarks>
 21/// <para>
 22/// This class is not thread-safe. Concurrent access from multiple threads must be
 23/// serialized externally (e.g., with a lock or by limiting access to a single thread).
 24/// </para>
 25/// </remarks>
 26public class SwiftBVH<TKey, TVolume>
 27    where TKey : notnull
 28    where TVolume : struct, IBoundVolume<TVolume>
 29{
 30    #region Static & Constants
 31
 32    private const string _diagnosticSource = nameof(SwiftBVH<TKey, TVolume>);
 33
 34    #endregion
 35
 36    #region Fields
 37
 38    private SwiftBVHNode<TKey, TVolume>[] _nodePool;
 39    private int _peakIndex;
 40    private int _leafCount;
 41
 42    private readonly QueryKeyIndexMap<TKey> _keyToNodeIndex;
 4043    private readonly QueryTraversalScratch _queryScratch = new();
 44
 4045    private readonly SwiftIntStack _freeIndices = new();
 46
 47    private int _rootNodeIndex;
 48
 49    #endregion
 50
 51    #region Constructor
 52
 53    /// <summary>
 54    /// Initializes a new instance of the <see cref="SwiftBVH{TKey, TVolume}"/> class with the specified capacity.
 55    /// </summary>
 4056    public SwiftBVH(int capacity)
 57    {
 4058        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 4059        _nodePool = new SwiftBVHNode<TKey, TVolume>[capacity].Populate(() =>
 4060            new SwiftBVHNode<TKey, TVolume>() { ParentIndex = -1, LeftChildIndex = -1, RightChildIndex = -1 });
 4061        _keyToNodeIndex = new QueryKeyIndexMap<TKey>(capacity, MatchesEntryKey, IsLeafNode, GetNodeValue);
 62
 4063        _rootNodeIndex = -1;
 64
 4065        _freeIndices = new SwiftIntStack(SwiftIntStack.DefaultCapacity);
 4066    }
 67
 68    #endregion
 69
 70    #region Properties
 71
 72    /// <summary>
 73    /// Gets the underlying pool of nodes used in the BVH.
 74    /// </summary>
 75    /// <remarks>
 76    /// Prefer BVH APIs. Direct structural mutation must preserve tree invariants; invalid edits may fail fast.
 77    /// </remarks>
 805378    public SwiftBVHNode<TKey, TVolume>[] NodePool => _nodePool;
 79
 80    /// <summary>
 81    /// Gets the root node of the BVH.
 82    /// </summary>
 683    public SwiftBVHNode<TKey, TVolume> RootNode => _rootNodeIndex >= 0 && _nodePool[_rootNodeIndex].IsAllocated
 684        ? _nodePool[_rootNodeIndex]
 685        : SwiftBVHNode<TKey, TVolume>.Default;
 86
 87    /// <summary>
 88    /// Gets the index of the root node in the BVH.
 89    /// </summary>
 19690    public int RootNodeIndex => _rootNodeIndex;
 91
 92    /// <summary>
 93    /// Gets the total number of leaf nodes in the BVH.
 94    /// </summary>
 695    public int Count => _leafCount;
 96
 97    #endregion
 98
 99    #region Collection Manipulation
 100
 101    /// <summary>
 102    /// Allocates a new node with the specified value, bounds, and leaf status.
 103    /// Reuses indices from the freelist when available.
 104    /// </summary>
 105    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 106    private int AllocateNode(TKey value, TVolume bounds, bool isLeaf)
 107    {
 108        int index;
 109
 110        // Check if there are any reusable indices in the freelist
 26430111        if (_freeIndices.Count > 0)
 4112            index = _freeIndices.Pop(); // Reuse an available index
 113        else
 114        {
 26426115            if (_peakIndex + 1 >= _nodePool.Length)
 26116                Resize(_nodePool.Length * 2);
 117
 118            // Allocate a new index if freelist is empty
 26426119            index = _peakIndex++;
 120        }
 121
 26430122        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 26430123        node.Reset(); // Explicit reset
 26430124        node.MyIndex = index;
 26430125        node.Value = value;
 26430126        node.Bounds = bounds;
 127
 26430128        if (isLeaf)
 129        {
 13233130            node.IsLeaf = isLeaf;
 13233131            node.SubtreeSize = 1;
 13233132            _leafCount++;
 133        }
 134
 26430135        node.IsAllocated = true;
 136
 26430137        return index;
 138    }
 139
 140    /// <summary>
 141    /// Inserts a bounding volume with an associated value into the BVH.
 142    /// Ensures tree balance and updates hash buckets.
 143    /// </summary>
 144    public bool Insert(TKey value, TVolume bounds)
 145    {
 13233146        int newNodeIndex = AllocateNode(value, bounds, true); // Allocate new node as a leaf
 13233147        _rootNodeIndex = InsertIntoTree(_rootNodeIndex, newNodeIndex);
 13233148        InsertIntoBuckets(value, newNodeIndex);
 13233149        return true;
 150    }
 151
 152    /// <summary>
 153    /// Inserts a node into the tree while maintaining tree balance.
 154    /// Adjusts parent-child relationships as necessary.
 155    /// </summary>
 156    [MethodImpl(MethodImplOptions.NoInlining)]
 157    private int InsertIntoTree(int parentNodeIndex, int newNodeIndex)
 158    {
 151871159        if (parentNodeIndex < 0 || !_nodePool[parentNodeIndex].IsAllocated)
 36160            return newNodeIndex;
 161
 151835162        if (_nodePool[parentNodeIndex].IsLeaf)
 13197163            return CreateParentForLeaves(parentNodeIndex, newNodeIndex);
 164
 138638165        InsertIntoBestChild(parentNodeIndex, newNodeIndex);
 138638166        RefreshParentNode(parentNodeIndex);
 138638167        return parentNodeIndex;
 168    }
 169
 170    private int CreateParentForLeaves(int existingLeafIndex, int newLeafIndex)
 171    {
 13197172        TVolume combinedBounds = _nodePool[existingLeafIndex].Bounds.Union(_nodePool[newLeafIndex].Bounds);
 13197173        int oldParentIndex = _nodePool[existingLeafIndex].ParentIndex;
 13197174        int newParentIndex = AllocateNode(default!, combinedBounds, false);
 175
 13197176        ref SwiftBVHNode<TKey, TVolume> newParentNode = ref _nodePool[newParentIndex];
 13197177        newParentNode.ParentIndex = oldParentIndex;
 13197178        newParentNode.LeftChildIndex = existingLeafIndex;
 13197179        newParentNode.RightChildIndex = newLeafIndex;
 13197180        newParentNode.SubtreeSize = 1 + _nodePool[existingLeafIndex].SubtreeSize + _nodePool[newLeafIndex].SubtreeSize;
 181
 13197182        _nodePool[existingLeafIndex].ParentIndex = newParentIndex;
 13197183        _nodePool[newLeafIndex].ParentIndex = newParentIndex;
 184
 13197185        return newParentIndex;
 186    }
 187
 188    private void InsertIntoBestChild(int parentNodeIndex, int newNodeIndex)
 189    {
 138638190        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 138638191        if (ShouldInsertIntoLeftChild(parentNodeIndex, newNodeIndex))
 70201192            parentNode.LeftChildIndex = InsertIntoTree(parentNode.LeftChildIndex, newNodeIndex);
 193        else
 68437194            parentNode.RightChildIndex = InsertIntoTree(parentNode.RightChildIndex, newNodeIndex);
 68437195    }
 196
 197    private bool ShouldInsertIntoLeftChild(int parentNodeIndex, int newNodeIndex)
 198    {
 138638199        SwiftBVHNode<TKey, TVolume> parentNode = _nodePool[parentNodeIndex];
 138638200        SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parentNode.LeftChildIndex];
 138638201        SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parentNode.RightChildIndex];
 138638202        int leftSize = GetSubtreeSize(leftChild);
 138638203        int rightSize = GetSubtreeSize(rightChild);
 204
 138638205        if (IsSeverelyUnbalanced(leftSize, rightSize))
 12627206            return leftSize <= rightSize;
 207
 126011208        return ShouldInsertIntoLowerCostChild(
 126011209            leftChild,
 126011210            rightChild,
 126011211            leftSize,
 126011212            rightSize,
 126011213            _nodePool[newNodeIndex].Bounds);
 214    }
 215
 216    private static bool IsSeverelyUnbalanced(int leftSize, int rightSize)
 217    {
 138638218        int maxSize = Math.Max(leftSize, rightSize);
 138638219        int minSize = Math.Min(leftSize, rightSize);
 138638220        return maxSize > minSize * 2;
 221    }
 222
 223    private static bool ShouldInsertIntoLowerCostChild(
 224        SwiftBVHNode<TKey, TVolume> leftChild,
 225        SwiftBVHNode<TKey, TVolume> rightChild,
 226        int leftSize,
 227        int rightSize,
 228        TVolume newBounds)
 229    {
 126011230        long leftCost = leftChild.Bounds.GetCost(newBounds);
 126011231        long rightCost = rightChild.Bounds.GetCost(newBounds);
 232
 126011233        if (leftCost == rightCost)
 5699234            return leftSize <= rightSize;
 235
 120312236        return leftCost < rightCost;
 237    }
 238
 239    private void RefreshParentNode(int parentNodeIndex)
 240    {
 139127241        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 139127242        SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parentNode.LeftChildIndex];
 139127243        SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parentNode.RightChildIndex];
 244
 139127245        parentNode.Bounds = GetCombinedBounds(leftChild, rightChild);
 139127246        parentNode.SubtreeSize = 1 + GetSubtreeSize(leftChild) + GetSubtreeSize(rightChild);
 139127247    }
 248
 249    private static int GetSubtreeSize(SwiftBVHNode<TKey, TVolume> node)
 250    {
 555530251        return node.SubtreeSize;
 252    }
 253
 254    /// <summary>
 255    /// Inserts a value into the hash bucket for fast lookup.
 256    /// Handles collisions with linear probing.
 257    /// </summary>
 258    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 259    private void InsertIntoBuckets(TKey value, int nodeIndex)
 260    {
 13233261        _keyToNodeIndex.Insert(value, nodeIndex);
 13233262    }
 263
 264    /// <summary>
 265    /// Updates the bounding volume of a node and propagates changes up the tree.
 266    /// Ensures consistency in parent bounds and subtree sizes.
 267    /// </summary>
 268    public void UpdateEntryBounds(TKey value, TVolume newBounds)
 269    {
 7270        ChronicleGuard.ThrowIfNullGeneric(value, nameof(value));
 271
 7272        int index = _keyToNodeIndex.Find(value);
 8273        if (index == -1) return;
 274
 6275        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 7276        if (!node.IsAllocated) return; // Skip update if node has been removed
 277
 5278        TVolume oldBounds = node.Bounds;
 5279        if (oldBounds.BoundsEquals(newBounds))
 1280            return; // Skip unnecessary updates
 281
 4282        node.Bounds = newBounds;
 283
 284        // Propagate changes up the tree
 4285        int parentIndex = node.ParentIndex;
 7286        while (parentIndex != -1)
 287        {
 4288            ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 4289            SwiftBVHNode<TKey, TVolume> leftChild = _nodePool[parent.LeftChildIndex];
 4290            SwiftBVHNode<TKey, TVolume> rightChild = _nodePool[parent.RightChildIndex];
 291
 4292            TVolume newParentBounds = GetCombinedBounds(leftChild, rightChild);
 4293            if (parent.Bounds.BoundsEquals(newParentBounds))
 294                break; // No further updates needed
 295
 3296            parent.Bounds = newParentBounds;
 3297            parentIndex = parent.ParentIndex;
 298        }
 4299    }
 300
 301    /// <summary>
 302    /// Removes a value and its associated bounding volume from the BVH.
 303    /// Updates tree structure and clears hash bucket entries.
 304    /// </summary>
 305    public bool Remove(TKey value)
 306    {
 135307        ChronicleGuard.ThrowIfNullGeneric(value, nameof(value));
 308
 135309        int nodeIndex = _keyToNodeIndex.Find(value);
 137310        if (nodeIndex == -1) return false;
 311
 312        // If the node is the root and the only node, reset the BVH
 133313        if (nodeIndex == RootNodeIndex && _leafCount == 1)
 314        {
 2315            Clear();
 2316            return true;
 317        }
 318
 131319        RemoveFromBuckets(value); // Ensure the bucket is cleared before further operations
 320
 321        // Remove node and update tree structure
 131322        RemoveFromTree(nodeIndex);
 323
 131324        return true;
 325    }
 326
 327    /// <summary>
 328    /// Removes an entry from the hash buckets, resolving collisions as necessary.
 329    /// </summary>
 330    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 331    private void RemoveFromBuckets(TKey value)
 332    {
 131333        _keyToNodeIndex.Remove(value);
 131334    }
 335
 336    /// <summary>
 337    /// Removes a leaf node from the tree, collapses its parent, and propagates
 338    /// bound and subtree-size updates upward.  Every internal node is guaranteed
 339    /// to have exactly two children after this operation completes.
 340    /// </summary>
 341    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 342    private void RemoveFromTree(int nodeIndex)
 343    {
 131344        int parentIndex = _nodePool[nodeIndex].ParentIndex;
 345
 131346        int siblingIndex = ReleaseLeafAndParent(nodeIndex, parentIndex, out int grandParentIndex);
 131347        PromoteSiblingToGrandParent(siblingIndex, parentIndex, grandParentIndex);
 131348        if (grandParentIndex != -1)
 125349            RefreshAncestors(grandParentIndex);
 131350    }
 351
 352    private int ReleaseLeafAndParent(int nodeIndex, int parentIndex, out int grandParentIndex)
 353    {
 131354        ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 131355        int siblingIndex = parent.LeftChildIndex == nodeIndex
 131356            ? parent.RightChildIndex
 131357            : parent.LeftChildIndex;
 131358        grandParentIndex = parent.ParentIndex;
 359
 360        // Push parent before the leaf so that the leaf index sits on top of the
 361        // freelist stack and is reused first by the next allocation.
 131362        parent.Reset();
 131363        _freeIndices.Push(parentIndex);
 364
 131365        _leafCount--;
 131366        _nodePool[nodeIndex].Reset();
 131367        _freeIndices.Push(nodeIndex);
 368
 131369        return siblingIndex;
 370    }
 371
 372    private void PromoteSiblingToGrandParent(int siblingIndex, int parentIndex, int grandParentIndex)
 373    {
 131374        _nodePool[siblingIndex].ParentIndex = grandParentIndex;
 375
 131376        if (grandParentIndex == -1)
 377        {
 6378            _rootNodeIndex = siblingIndex;
 6379            return;
 380        }
 381
 125382        ref SwiftBVHNode<TKey, TVolume> grandParent = ref _nodePool[grandParentIndex];
 125383        if (grandParent.LeftChildIndex == parentIndex)
 65384            grandParent.LeftChildIndex = siblingIndex;
 385        else
 60386            grandParent.RightChildIndex = siblingIndex;
 60387    }
 388
 389    private void RefreshAncestors(int current)
 390    {
 614391        while (current != -1)
 392        {
 489393            RefreshParentNode(current);
 489394            current = _nodePool[current].ParentIndex;
 395        }
 125396    }
 397
 398    #endregion
 399
 400    #region Capacity Management
 401
 402    /// <summary>
 403    /// Ensures the BVH has sufficient capacity, resizing the node pool and buckets if needed.
 404    /// </summary>
 405    public void EnsureCapacity(int capacity)
 406    {
 2407        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 2408        if (capacity > _nodePool.Length)
 1409            Resize(capacity);
 2410    }
 411
 412    /// <summary>
 413    /// Resizes the internal node pool to accommodate additional nodes.
 414    /// Preserves existing nodes and reinitializes the expanded capacity.
 415    /// </summary>
 416    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 417    private void Resize(int newSize)
 418    {
 27419        SwiftBVHNode<TKey, TVolume>[] newArray = new SwiftBVHNode<TKey, TVolume>[newSize];
 27420        Array.Copy(_nodePool, 0, newArray, 0, _peakIndex);
 421
 70438422        for (int i = _peakIndex; i < newSize; i++)
 35192423            newArray[i].Reset(); // set default index lookup values
 424
 27425        _nodePool = newArray;
 426
 27427        ResizeBuckets(newSize);
 27428        SwiftCollectionDiagnostics.Shared.Info($"Resized BVH storage to {newSize} nodes.", _diagnosticSource);
 27429    }
 430
 431    /// <summary>
 432    /// Resizes and rehashes the hash buckets to maintain lookup efficiency.
 433    /// Rehashes existing nodes after resizing.
 434    /// </summary>
 435    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 436    private void ResizeBuckets(int newSize)
 437    {
 27438        _keyToNodeIndex.ResizeAndRehash(newSize, _peakIndex);
 27439    }
 440
 441    #endregion
 442
 443    #region Utility Methods
 444
 445    /// <summary>
 446    /// Gets the combined bounding volume of two child nodes.
 447    /// Handles cases where one or both children are missing.
 448    /// </summary>
 449    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 450    private static TVolume GetCombinedBounds(SwiftBVHNode<TKey, TVolume> leftChild, SwiftBVHNode<TKey, TVolume> rightChi
 451    {
 139131452        return leftChild.Bounds.Union(rightChild.Bounds);
 453    }
 454
 455    /// <summary>
 456    /// Queries the BVH for values whose bounding volumes intersect with the specified volume.
 457    /// Uses a stack-based approach for efficient traversal.
 458    /// </summary>
 459    public void Query(TVolume queryBounds, ICollection<TKey> results)
 460    {
 26461        ChronicleGuard.ThrowIfNull(results, nameof(results));
 462
 29463        if (RootNodeIndex == -1) return;
 464
 23465        SwiftIntStack nodeStack = _queryScratch.RentIntStack(_peakIndex + 1);
 23466        nodeStack.Push(RootNodeIndex);
 467
 21064468        while (nodeStack.Count > 0)
 469        {
 21043470            int index = nodeStack.Pop();
 21043471            QueryNode(index, queryBounds, results, nodeStack);
 472        }
 21473    }
 474
 475    private void QueryNode(int index, TVolume queryBounds, ICollection<TKey> results, SwiftIntStack nodeStack)
 476    {
 21043477        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 21043478        ThrowIfQueryNodeIsUnallocated(index, node);
 479
 21041480        if (!queryBounds.Intersects(node.Bounds))
 306481            return;
 482
 20735483        if (node.IsLeaf)
 484        {
 10225485            results.Add(node.Value);
 10225486            return;
 487        }
 488
 10510489        PushChildNodes(node, nodeStack);
 10510490    }
 491
 492    private static void PushChildNodes(SwiftBVHNode<TKey, TVolume> node, SwiftIntStack nodeStack)
 493    {
 10510494        nodeStack.Push(node.LeftChildIndex);
 10510495        nodeStack.Push(node.RightChildIndex);
 10510496    }
 497
 498    private static void ThrowIfQueryNodeIsUnallocated(int index, SwiftBVHNode<TKey, TVolume> node)
 499    {
 21043500        if (node.IsAllocated)
 21041501            return;
 502
 2503        SwiftCollectionDiagnostics.Shared.Error($"Encountered an unallocated node at index {index} during query traversa
 2504        throw new InvalidOperationException($"Encountered an unallocated node at index {index} during query traversal.")
 505    }
 506
 507    /// <summary>
 508    /// Finds the index of a node by its value in the BVH using hash buckets.
 509    /// Returns -1 if the value is not found.
 510    /// </summary>
 511    public int FindEntry(TKey value)
 512    {
 12513        ChronicleGuard.ThrowIfNullGeneric(value, nameof(value));
 12514        return _keyToNodeIndex.Find(value);
 515    }
 516
 517    /// <summary>
 518    /// Clears the BVH, resetting all nodes, buckets, and metadata.
 519    /// </summary>
 520    public void Clear()
 521    {
 5522        if (RootNodeIndex == -1) return;
 523
 208524        for (int i = 0; i < _peakIndex; i++)
 101525            _nodePool[i].Reset();
 526
 3527        _keyToNodeIndex.Clear();
 528
 3529        _freeIndices.Reset();
 530
 3531        _leafCount = 0;
 3532        _peakIndex = 0;
 3533        _rootNodeIndex = -1;
 3534    }
 535
 536    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 18528537    private TKey GetNodeValue(int index) => _nodePool[index].Value;
 538
 539    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 35132540    private bool IsLeafNode(int index) => _nodePool[index].IsLeaf;
 541
 542    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 543    private bool MatchesEntryKey(int index, TKey value)
 544    {
 285545        return _nodePool[index].IsLeaf && EqualityComparer<TKey>.Default.Equals(_nodePool[index].Value, value);
 546    }
 547
 548    #endregion
 549}
Generated by: ReportGenerator 5.5.12.0
11/05/2026 - 04:17:34
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)