< 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
94%
Covered lines: 220
Uncovered lines: 13
Coverable lines: 233
Total lines: 587
Line coverage: 94.4%
Branch coverage
86%
Covered branches: 83
Total branches: 96
Branch coverage: 86.4%
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%
GetInsertionCost(...)50%2266.66%
RefreshParentNode(...)100%11100%
GetNodeOrDefault(...)50%2266.66%
GetSubtreeSize(...)50%2266.66%
InsertIntoBuckets(...)100%11100%
UpdateEntryBounds(...)78.57%1414100%
Remove(...)100%66100%
RemoveFromBuckets(...)100%11100%
RemoveFromTree(...)75%4477.77%
RemoveRootLeaf(...)100%210%
ReleaseLeafAndParent(...)100%22100%
PromoteSiblingToGrandParent(...)100%66100%
RefreshAncestors(...)100%22100%
EnsureCapacity(...)100%22100%
Resize(...)100%22100%
ResizeBuckets(...)100%11100%
GetCombinedBounds(...)33.33%14640%
Query(...)100%44100%
QueryNode(...)100%44100%
PushChildNodes(...)100%44100%
ThrowIfQueryNodeIsUnallocated(...)100%22100%
FindEntry(...)100%11100%
Clear()75%44100%
GetNodeValue(...)100%11100%
IsLeafNode(...)100%11100%
IsAllocatedLeafNode(...)50%22100%
MatchesEntryKey(...)100%22100%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Runtime.CompilerServices;
 4
 5namespace SwiftCollections.Query;
 6
 7/// <summary>
 8/// Represents a Bounding Volume Hierarchy (BVH) optimized for spatial queries.
 9/// </summary>
 10/// <remarks>
 11/// <para>
 12/// This class is not thread-safe. Concurrent access from multiple threads must be
 13/// serialized externally (e.g., with a lock or by limiting access to a single thread).
 14/// </para>
 15/// </remarks>
 16public class SwiftBVH<TKey, TVolume>
 17    where TKey : notnull
 18    where TVolume : struct, IBoundVolume<TVolume>
 19{
 20    #region Static & Constants
 21
 22    private const string _diagnosticSource = nameof(SwiftBVH<TKey, TVolume>);
 23
 24    #endregion
 25
 26    #region Fields
 27
 28    private SwiftBVHNode<TKey, TVolume>[] _nodePool;
 29    private int _peakIndex;
 30    private int _leafCount;
 31
 32    private readonly QueryKeyIndexMap<TKey> _keyToNodeIndex;
 3733    private readonly QueryTraversalScratch _queryScratch = new();
 34
 3735    private readonly SwiftIntStack _freeIndices = new();
 36
 37    private int _rootNodeIndex;
 38
 39    #endregion
 40
 41    #region Constructor
 42
 43    /// <summary>
 44    /// Initializes a new instance of the <see cref="SwiftBVH{TKey, TVolume}"/> class with the specified capacity.
 45    /// </summary>
 3746    public SwiftBVH(int capacity)
 47    {
 3748        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 3749        _nodePool = new SwiftBVHNode<TKey, TVolume>[capacity].Populate(() =>
 1888450            new SwiftBVHNode<TKey, TVolume>() { ParentIndex = -1, LeftChildIndex = -1, RightChildIndex = -1 });
 3751        _keyToNodeIndex = new QueryKeyIndexMap<TKey>(capacity);
 52
 3753        _rootNodeIndex = -1;
 54
 3755        _freeIndices = new SwiftIntStack(SwiftIntStack.DefaultCapacity);
 3756    }
 57
 58    #endregion
 59
 60    #region Properties
 61
 62    /// <summary>
 63    /// Gets the underlying pool of nodes used in the BVH.
 64    /// </summary>
 805265    public SwiftBVHNode<TKey, TVolume>[] NodePool => _nodePool;
 66
 67    /// <summary>
 68    /// Gets the root node of the BVH.
 69    /// </summary>
 670    public SwiftBVHNode<TKey, TVolume> RootNode => _rootNodeIndex >= 0 && _nodePool[_rootNodeIndex].IsAllocated
 671        ? _nodePool[_rootNodeIndex]
 672        : SwiftBVHNode<TKey, TVolume>.Default;
 73
 74    /// <summary>
 75    /// Gets the index of the root node in the BVH.
 76    /// </summary>
 19177    public int RootNodeIndex => _rootNodeIndex;
 78
 79    /// <summary>
 80    /// Gets the total number of leaf nodes in the BVH.
 81    /// </summary>
 482    public int Count => _leafCount;
 83
 84    #endregion
 85
 86    #region Collection Manipulation
 87
 88    /// <summary>
 89    /// Allocates a new node with the specified value, bounds, and leaf status.
 90    /// Reuses indices from the freelist when available.
 91    /// </summary>
 92    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 93    private int AllocateNode(TKey value, TVolume bounds, bool isLeaf)
 94    {
 95        int index;
 96
 97        // Check if there are any reusable indices in the freelist
 2642998        if (_freeIndices.Count > 0)
 499            index = _freeIndices.Pop(); // Reuse an available index
 100        else
 101        {
 26425102            if (_peakIndex + 1 >= _nodePool.Length)
 25103                Resize(_nodePool.Length * 2);
 104
 105            // Allocate a new index if freelist is empty
 26425106            index = _peakIndex++;
 107        }
 108
 26429109        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 26429110        node.Reset(); // Explicit reset
 26429111        node.MyIndex = index;
 26429112        node.Value = value;
 26429113        node.Bounds = bounds;
 114
 26429115        if (isLeaf)
 116        {
 13232117            node.IsLeaf = isLeaf;
 13232118            node.SubtreeSize = 1;
 13232119            _leafCount++;
 120        }
 121
 26429122        node.IsAllocated = true;
 123
 26429124        return index;
 125    }
 126
 127    /// <summary>
 128    /// Inserts a bounding volume with an associated value into the BVH.
 129    /// Ensures tree balance and updates hash buckets.
 130    /// </summary>
 131    public bool Insert(TKey value, TVolume bounds)
 132    {
 13232133        int newNodeIndex = AllocateNode(value, bounds, true); // Allocate new node as a leaf
 13232134        _rootNodeIndex = InsertIntoTree(_rootNodeIndex, newNodeIndex);
 13232135        InsertIntoBuckets(value, newNodeIndex);
 13232136        return true;
 137    }
 138
 139    /// <summary>
 140    /// Inserts a node into the tree while maintaining tree balance.
 141    /// Adjusts parent-child relationships as necessary.
 142    /// </summary>
 143    [MethodImpl(MethodImplOptions.NoInlining)]
 144    private int InsertIntoTree(int parentNodeIndex, int newNodeIndex)
 145    {
 151862146        if (parentNodeIndex < 0 || !_nodePool[parentNodeIndex].IsAllocated)
 35147            return newNodeIndex;
 148
 151827149        if (_nodePool[parentNodeIndex].IsLeaf)
 13197150            return CreateParentForLeaves(parentNodeIndex, newNodeIndex);
 151
 138630152        InsertIntoBestChild(parentNodeIndex, newNodeIndex);
 138630153        RefreshParentNode(parentNodeIndex);
 138630154        return parentNodeIndex;
 155    }
 156
 157    private int CreateParentForLeaves(int existingLeafIndex, int newLeafIndex)
 158    {
 13197159        TVolume combinedBounds = _nodePool[existingLeafIndex].Bounds.Union(_nodePool[newLeafIndex].Bounds);
 13197160        int oldParentIndex = _nodePool[existingLeafIndex].ParentIndex;
 13197161        int newParentIndex = AllocateNode(default!, combinedBounds, false);
 162
 13197163        ref SwiftBVHNode<TKey, TVolume> newParentNode = ref _nodePool[newParentIndex];
 13197164        newParentNode.ParentIndex = oldParentIndex;
 13197165        newParentNode.LeftChildIndex = existingLeafIndex;
 13197166        newParentNode.RightChildIndex = newLeafIndex;
 13197167        newParentNode.SubtreeSize = 1 + _nodePool[existingLeafIndex].SubtreeSize + _nodePool[newLeafIndex].SubtreeSize;
 168
 13197169        _nodePool[existingLeafIndex].ParentIndex = newParentIndex;
 13197170        _nodePool[newLeafIndex].ParentIndex = newParentIndex;
 171
 13197172        return newParentIndex;
 173    }
 174
 175    private void InsertIntoBestChild(int parentNodeIndex, int newNodeIndex)
 176    {
 138630177        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 138630178        if (ShouldInsertIntoLeftChild(parentNodeIndex, newNodeIndex))
 70153179            parentNode.LeftChildIndex = InsertIntoTree(parentNode.LeftChildIndex, newNodeIndex);
 180        else
 68477181            parentNode.RightChildIndex = InsertIntoTree(parentNode.RightChildIndex, newNodeIndex);
 68477182    }
 183
 184    private bool ShouldInsertIntoLeftChild(int parentNodeIndex, int newNodeIndex)
 185    {
 138630186        SwiftBVHNode<TKey, TVolume> parentNode = _nodePool[parentNodeIndex];
 138630187        SwiftBVHNode<TKey, TVolume> leftChild = GetNodeOrDefault(parentNode.LeftChildIndex);
 138630188        SwiftBVHNode<TKey, TVolume> rightChild = GetNodeOrDefault(parentNode.RightChildIndex);
 138630189        int leftSize = GetSubtreeSize(leftChild);
 138630190        int rightSize = GetSubtreeSize(rightChild);
 191
 138630192        if (IsSeverelyUnbalanced(leftSize, rightSize))
 12624193            return leftSize <= rightSize;
 194
 126006195        return ShouldInsertIntoLowerCostChild(
 126006196            parentNode,
 126006197            leftChild,
 126006198            rightChild,
 126006199            leftSize,
 126006200            rightSize,
 126006201            _nodePool[newNodeIndex].Bounds);
 202    }
 203
 204    private static bool IsSeverelyUnbalanced(int leftSize, int rightSize)
 205    {
 138630206        int maxSize = Math.Max(leftSize, rightSize);
 138630207        int minSize = Math.Min(leftSize, rightSize);
 138630208        return maxSize > minSize * 2;
 209    }
 210
 211    private static bool ShouldInsertIntoLowerCostChild(
 212        SwiftBVHNode<TKey, TVolume> parentNode,
 213        SwiftBVHNode<TKey, TVolume> leftChild,
 214        SwiftBVHNode<TKey, TVolume> rightChild,
 215        int leftSize,
 216        int rightSize,
 217        TVolume newBounds)
 218    {
 126006219        long leftCost = GetInsertionCost(parentNode.LeftChildIndex, leftChild, newBounds);
 126006220        long rightCost = GetInsertionCost(parentNode.RightChildIndex, rightChild, newBounds);
 221
 126006222        if (leftCost == rightCost)
 5801223            return leftSize <= rightSize;
 224
 120205225        return leftCost < rightCost;
 226    }
 227
 228    private static long GetInsertionCost(int childIndex, SwiftBVHNode<TKey, TVolume> child, TVolume newBounds)
 229    {
 252012230        if (childIndex == -1)
 0231            return 0L;
 232
 252012233        return child.Bounds.GetCost(newBounds);
 234    }
 235
 236    private void RefreshParentNode(int parentNodeIndex)
 237    {
 139119238        ref SwiftBVHNode<TKey, TVolume> parentNode = ref _nodePool[parentNodeIndex];
 139119239        SwiftBVHNode<TKey, TVolume> leftChild = GetNodeOrDefault(parentNode.LeftChildIndex);
 139119240        SwiftBVHNode<TKey, TVolume> rightChild = GetNodeOrDefault(parentNode.RightChildIndex);
 241
 139119242        parentNode.Bounds = GetCombinedBounds(leftChild, rightChild);
 139119243        parentNode.SubtreeSize = 1 + GetSubtreeSize(leftChild) + GetSubtreeSize(rightChild);
 139119244    }
 245
 246    private SwiftBVHNode<TKey, TVolume> GetNodeOrDefault(int nodeIndex)
 247    {
 555498248        if (nodeIndex == -1)
 0249            return SwiftBVHNode<TKey, TVolume>.Default;
 250
 555498251        return _nodePool[nodeIndex];
 252    }
 253
 254    private static int GetSubtreeSize(SwiftBVHNode<TKey, TVolume> node)
 255    {
 555498256        if (!node.IsAllocated)
 0257            return 0;
 258
 555498259        return node.SubtreeSize;
 260    }
 261
 262    /// <summary>
 263    /// Inserts a value into the hash bucket for fast lookup.
 264    /// Handles collisions with linear probing.
 265    /// </summary>
 266    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 267    private void InsertIntoBuckets(TKey value, int nodeIndex)
 268    {
 13232269        _keyToNodeIndex.Insert(value, nodeIndex);
 13232270    }
 271
 272    /// <summary>
 273    /// Updates the bounding volume of a node and propagates changes up the tree.
 274    /// Ensures consistency in parent bounds and subtree sizes.
 275    /// </summary>
 276    public void UpdateEntryBounds(TKey value, TVolume newBounds)
 277    {
 5278        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 279
 5280        int index = _keyToNodeIndex.Find(value, MatchesEntryKey);
 5281        if (index == -1) return;
 282
 5283        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 6284        if (!node.IsAllocated) return; // Skip update if node has been removed
 285
 4286        TVolume oldBounds = node.Bounds;
 4287        if (oldBounds.BoundsEquals(newBounds))
 1288            return; // Skip unnecessary updates
 289
 3290        node.Bounds = newBounds;
 291
 292        // Propagate changes up the tree
 3293        int parentIndex = node.ParentIndex;
 6294        while (parentIndex != -1)
 295        {
 3296            ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 3297            SwiftBVHNode<TKey, TVolume> leftChild = parent.HasLeftChild
 3298                ? _nodePool[parent.LeftChildIndex]
 3299                : SwiftBVHNode<TKey, TVolume>.Default;
 3300            SwiftBVHNode<TKey, TVolume> rightChild = parent.HasRightChild
 3301                ? _nodePool[parent.RightChildIndex]
 3302                : SwiftBVHNode<TKey, TVolume>.Default;
 303
 3304            TVolume newParentBounds = GetCombinedBounds(leftChild, rightChild);
 3305            if (parent.Bounds.BoundsEquals(newParentBounds))
 306                break; // No further updates needed
 307
 3308            parent.Bounds = newParentBounds;
 3309            parentIndex = parent.ParentIndex;
 310        }
 3311    }
 312
 313    /// <summary>
 314    /// Removes a value and its associated bounding volume from the BVH.
 315    /// Updates tree structure and clears hash bucket entries.
 316    /// </summary>
 317    public bool Remove(TKey value)
 318    {
 135319        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 320
 135321        int nodeIndex = _keyToNodeIndex.Find(value, MatchesEntryKey);
 137322        if (nodeIndex == -1) return false;
 323
 324        // If the node is the root and the only node, reset the BVH
 133325        if (nodeIndex == RootNodeIndex && _leafCount == 1)
 326        {
 2327            Clear();
 2328            return true;
 329        }
 330
 131331        RemoveFromBuckets(value); // Ensure the bucket is cleared before further operations
 332
 333        // Remove node and update tree structure
 131334        RemoveFromTree(nodeIndex);
 335
 131336        return true;
 337    }
 338
 339    /// <summary>
 340    /// Removes an entry from the hash buckets, resolving collisions as necessary.
 341    /// </summary>
 342    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 343    private void RemoveFromBuckets(TKey value)
 344    {
 131345        _keyToNodeIndex.Remove(value, MatchesEntryKey, IsAllocatedLeafNode, GetNodeValue);
 131346    }
 347
 348    /// <summary>
 349    /// Removes a leaf node from the tree, collapses its parent, and propagates
 350    /// bound and subtree-size updates upward.  Every internal node is guaranteed
 351    /// to have exactly two children after this operation completes.
 352    /// </summary>
 353    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 354    private void RemoveFromTree(int nodeIndex)
 355    {
 131356        int parentIndex = _nodePool[nodeIndex].ParentIndex;
 357
 131358        if (parentIndex == -1)
 359        {
 0360            RemoveRootLeaf(nodeIndex);
 0361            return;
 362        }
 363
 131364        int siblingIndex = ReleaseLeafAndParent(nodeIndex, parentIndex, out int grandParentIndex);
 131365        PromoteSiblingToGrandParent(siblingIndex, parentIndex, grandParentIndex);
 131366        if (grandParentIndex != -1)
 125367            RefreshAncestors(grandParentIndex);
 131368    }
 369
 370    private void RemoveRootLeaf(int nodeIndex)
 371    {
 0372        _leafCount--;
 0373        _nodePool[nodeIndex].Reset();
 0374        _freeIndices.Push(nodeIndex);
 0375        _rootNodeIndex = -1;
 0376    }
 377
 378    private int ReleaseLeafAndParent(int nodeIndex, int parentIndex, out int grandParentIndex)
 379    {
 131380        ref SwiftBVHNode<TKey, TVolume> parent = ref _nodePool[parentIndex];
 131381        int siblingIndex = parent.LeftChildIndex == nodeIndex
 131382            ? parent.RightChildIndex
 131383            : parent.LeftChildIndex;
 131384        grandParentIndex = parent.ParentIndex;
 385
 386        // Push parent before the leaf so that the leaf index sits on top of the
 387        // freelist stack and is reused first by the next allocation.
 131388        parent.Reset();
 131389        _freeIndices.Push(parentIndex);
 390
 131391        _leafCount--;
 131392        _nodePool[nodeIndex].Reset();
 131393        _freeIndices.Push(nodeIndex);
 394
 131395        return siblingIndex;
 396    }
 397
 398    private void PromoteSiblingToGrandParent(int siblingIndex, int parentIndex, int grandParentIndex)
 399    {
 131400        if (siblingIndex != -1)
 131401            _nodePool[siblingIndex].ParentIndex = grandParentIndex;
 402
 131403        if (grandParentIndex == -1)
 404        {
 6405            _rootNodeIndex = siblingIndex;
 6406            return;
 407        }
 408
 125409        ref SwiftBVHNode<TKey, TVolume> grandParent = ref _nodePool[grandParentIndex];
 125410        if (grandParent.LeftChildIndex == parentIndex)
 65411            grandParent.LeftChildIndex = siblingIndex;
 412        else
 60413            grandParent.RightChildIndex = siblingIndex;
 60414    }
 415
 416    private void RefreshAncestors(int current)
 417    {
 614418        while (current != -1)
 419        {
 489420            RefreshParentNode(current);
 489421            current = _nodePool[current].ParentIndex;
 422        }
 125423    }
 424
 425    #endregion
 426
 427    #region Capacity Management
 428
 429    /// <summary>
 430    /// Ensures the BVH has sufficient capacity, resizing the node pool and buckets if needed.
 431    /// </summary>
 432    public void EnsureCapacity(int capacity)
 433    {
 2434        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 2435        if (capacity > _nodePool.Length)
 1436            Resize(capacity);
 2437    }
 438
 439    /// <summary>
 440    /// Resizes the internal node pool to accommodate additional nodes.
 441    /// Preserves existing nodes and reinitializes the expanded capacity.
 442    /// </summary>
 443    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 444    private void Resize(int newSize)
 445    {
 26446        SwiftBVHNode<TKey, TVolume>[] newArray = new SwiftBVHNode<TKey, TVolume>[newSize];
 26447        Array.Copy(_nodePool, 0, newArray, 0, _peakIndex);
 448
 70432449        for (int i = _peakIndex; i < newSize; i++)
 35190450            newArray[i].Reset(); // set default index lookup values
 451
 26452        _nodePool = newArray;
 453
 26454        ResizeBuckets(newSize);
 26455        QueryCollectionDiagnostics.WriteInfo(_diagnosticSource, $"Resized BVH storage to {newSize} nodes.");
 26456    }
 457
 458    /// <summary>
 459    /// Resizes and rehashes the hash buckets to maintain lookup efficiency.
 460    /// Rehashes existing nodes after resizing.
 461    /// </summary>
 462    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 463    private void ResizeBuckets(int newSize)
 464    {
 26465        _keyToNodeIndex.ResizeAndRehash(newSize, _peakIndex, IsLeafNode, GetNodeValue);
 26466    }
 467
 468    #endregion
 469
 470    #region Utility Methods
 471
 472    /// <summary>
 473    /// Gets the combined bounding volume of two child nodes.
 474    /// Handles cases where one or both children are missing.
 475    /// </summary>
 476    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 477    private static TVolume GetCombinedBounds(SwiftBVHNode<TKey, TVolume> leftChild, SwiftBVHNode<TKey, TVolume> rightChi
 478    {
 139122479        if (leftChild.IsAllocated && rightChild.IsAllocated)
 139122480            return leftChild.Bounds.Union(rightChild.Bounds);
 0481        if (leftChild.IsAllocated)
 0482            return leftChild.Bounds;
 0483        return rightChild.Bounds;
 484    }
 485
 486    /// <summary>
 487    /// Queries the BVH for values whose bounding volumes intersect with the specified volume.
 488    /// Uses a stack-based approach for efficient traversal.
 489    /// </summary>
 490    public void Query(TVolume queryBounds, ICollection<TKey> results)
 491    {
 25492        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 493
 28494        if (RootNodeIndex == -1) return;
 495
 22496        SwiftIntStack nodeStack = _queryScratch.RentIntStack(_peakIndex + 1);
 22497        nodeStack.Push(RootNodeIndex);
 498
 21063499        while (nodeStack.Count > 0)
 500        {
 21042501            int index = nodeStack.Pop();
 21042502            QueryNode(index, queryBounds, results, nodeStack);
 503        }
 21504    }
 505
 506    private void QueryNode(int index, TVolume queryBounds, ICollection<TKey> results, SwiftIntStack nodeStack)
 507    {
 21042508        ref SwiftBVHNode<TKey, TVolume> node = ref _nodePool[index];
 21042509        ThrowIfQueryNodeIsUnallocated(index, node);
 510
 21041511        if (!queryBounds.Intersects(node.Bounds))
 306512            return;
 513
 20735514        if (node.IsLeaf)
 515        {
 10225516            results.Add(node.Value);
 10225517            return;
 518        }
 519
 10510520        PushChildNodes(node, nodeStack);
 10510521    }
 522
 523    private static void PushChildNodes(SwiftBVHNode<TKey, TVolume> node, SwiftIntStack nodeStack)
 524    {
 10510525        if (node.HasLeftChild)
 10510526            nodeStack.Push(node.LeftChildIndex);
 10510527        if (node.HasRightChild)
 10510528            nodeStack.Push(node.RightChildIndex);
 10510529    }
 530
 531    private static void ThrowIfQueryNodeIsUnallocated(int index, SwiftBVHNode<TKey, TVolume> node)
 532    {
 21042533        if (node.IsAllocated)
 21041534            return;
 535
 1536        QueryCollectionDiagnostics.WriteError(
 1537            _diagnosticSource,
 1538            $"Encountered an unallocated node at index {index} during query traversal.");
 1539        throw new InvalidOperationException($"Encountered an unallocated node at index {index} during query traversal.")
 540    }
 541
 542    /// <summary>
 543    /// Finds the index of a node by its value in the BVH using hash buckets.
 544    /// Returns -1 if the value is not found.
 545    /// </summary>
 546    public int FindEntry(TKey value)
 547    {
 11548        SwiftThrowHelper.ThrowIfNullGeneric(value, nameof(value));
 11549        return _keyToNodeIndex.Find(value, MatchesEntryKey);
 550    }
 551
 552    /// <summary>
 553    /// Clears the BVH, resetting all nodes, buckets, and metadata.
 554    /// </summary>
 555    public void Clear()
 556    {
 3557        if (RootNodeIndex == -1) return;
 558
 208559        for (int i = 0; i < _peakIndex; i++)
 101560            _nodePool[i].Reset();
 561
 3562        _keyToNodeIndex.Clear();
 563
 3564        _freeIndices.Reset();
 565
 3566        _leafCount = 0;
 3567        _peakIndex = 0;
 3568        _rootNodeIndex = -1;
 3569    }
 570
 571    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 18528572    private TKey GetNodeValue(int index) => _nodePool[index].Value;
 573
 574    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 35132575    private bool IsLeafNode(int index) => _nodePool[index].IsLeaf;
 576
 577    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 950578    private bool IsAllocatedLeafNode(int index) => _nodePool[index].IsLeaf && _nodePool[index].IsAllocated;
 579
 580    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 581    private bool MatchesEntryKey(int index, TKey value)
 582    {
 284583        return _nodePool[index].IsLeaf && EqualityComparer<TKey>.Default.Equals(_nodePool[index].Value, value);
 584    }
 585
 586    #endregion
 587}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 03:35:54
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>,SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>,System.Int32,System.Int32,TVolume)
GetInsertionCost(System.Int32,SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>,TVolume)
RefreshParentNode(System.Int32)
GetNodeOrDefault(System.Int32)
GetSubtreeSize(SwiftCollections.Query.SwiftBVHNode`2<TKey,TVolume>)
InsertIntoBuckets(TKey,System.Int32)
UpdateEntryBounds(TKey,TVolume)
Remove(TKey)
RemoveFromBuckets(TKey)
RemoveFromTree(System.Int32)
RemoveRootLeaf(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)
IsAllocatedLeafNode(System.Int32)
MatchesEntryKey(System.Int32,TKey)