< Summary

Information
Class: SwiftCollections.Query.SwiftSpatialHash<T1, T2>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Query/SpatialHash/SwiftSpatialHash.cs
Line coverage
100%
Covered lines: 152
Uncovered lines: 0
Coverable lines: 152
Total lines: 409
Line coverage: 100%
Branch coverage
100%
Covered branches: 60
Total branches: 60
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%11100%
.ctor(...)100%11100%
get_Count()100%11100%
Insert(...)100%22100%
Remove(...)100%22100%
UpdateEntryBounds(...)100%22100%
Contains(...)100%11100%
TryGetBounds(...)100%22100%
Query(...)100%11100%
QueryNeighborhood(...)100%11100%
EnsureCapacity(...)100%22100%
Clear()100%44100%
AllocateEntry(...)100%22100%
UpdateEntryBounds(...)100%22100%
ExecuteQuery(...)100%88100%
ProcessQueryCell(...)100%44100%
TryAddQueryResult(...)100%66100%
AddEntryToCells(...)100%88100%
RemoveEntryFromCells(...)100%66100%
RemoveEntryFromCell(...)100%22100%
RemoveEntryIndex(...)100%11100%
FindEntryIndex(...)100%11100%
ResizeEntryStorage(...)100%22100%
RentQueryStamp()100%66100%
MatchesEntryKey(...)100%11100%
IsAllocatedEntry(...)100%11100%
GetEntryKey(...)100%11100%
Reset()100%11100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Query/SpatialHash/SwiftSpatialHash.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftSpatialHash.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 mutable spatial hash that indexes keyed bounding volumes into deterministic integer grid cells.
 18/// </summary>
 19/// <typeparam name="TKey">The key used to identify each stored entry.</typeparam>
 20/// <typeparam name="TVolume">The volume type used for broad-phase registration and queries.</typeparam>
 21public class SwiftSpatialHash<TKey, TVolume>
 22    where TKey : notnull
 23    where TVolume : struct, IBoundVolume<TVolume>
 24{
 25    private const string _diagnosticSource = nameof(SwiftSpatialHash<TKey, TVolume>);
 26
 27    private readonly ISpatialHashCellMapper<TVolume> _cellMapper;
 28    private readonly QueryKeyIndexMap<TKey> _keyToEntryIndex;
 29    private readonly SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>> _cells;
 30    private readonly SwiftIntStack _freeEntries;
 31
 32    private SpatialHashEntry[] _entries;
 33    private int _peakCount;
 34    private int _count;
 35    private int _queryStamp;
 36
 37    /// <summary>
 38    /// Initializes a new instance of the <see cref="SwiftSpatialHash{TKey, TVolume}"/> class.
 39    /// </summary>
 40    /// <param name="capacity">The initial entry capacity.</param>
 41    /// <param name="cellMapper">The mapper that projects volumes into deterministic cell coordinates.</param>
 42    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper)
 1443        : this(capacity, cellMapper, SwiftSpatialHashOptions.Default)
 44    {
 1445    }
 46
 47    /// <summary>
 48    /// Initializes a new instance of the <see cref="SwiftSpatialHash{TKey, TVolume}"/> class.
 49    /// </summary>
 50    /// <param name="capacity">The initial entry capacity.</param>
 51    /// <param name="cellMapper">The mapper that projects volumes into deterministic cell coordinates.</param>
 52    /// <param name="options">Spatial hash query options.</param>
 1953    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper, SwiftSpatialHashOptions options)
 54    {
 1955        SwiftThrowHelper.ThrowIfNull(cellMapper, nameof(cellMapper));
 56
 1957        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 58
 1959        _cellMapper = cellMapper;
 1960        _keyToEntryIndex = new QueryKeyIndexMap<TKey>(capacity);
 1961        _cells = new SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>>(capacity);
 1962        _freeEntries = new SwiftIntStack();
 1963        _entries = new SpatialHashEntry[capacity];
 1964        Options = options;
 1965    }
 66
 67    /// <summary>
 68    /// Gets the number of active entries stored in the spatial hash.
 69    /// </summary>
 370    public int Count => _count;
 71
 72    /// <summary>
 73    /// Gets the options used by this spatial hash.
 74    /// </summary>
 75    public SwiftSpatialHashOptions Options { get; }
 76
 77    /// <summary>
 78    /// Inserts a new entry or replaces the bounds of an existing key.
 79    /// </summary>
 80    /// <param name="key">The entry key.</param>
 81    /// <param name="bounds">The entry bounds.</param>
 82    /// <returns><c>true</c> when a new key was added; <c>false</c> when an existing key was replaced.</returns>
 83    public bool Insert(TKey key, TVolume bounds)
 84    {
 6085        SwiftThrowHelper.ThrowIfNull(key, nameof(key));
 86
 6087        int existingIndex = FindEntryIndex(key);
 6088        if (existingIndex >= 0)
 89        {
 190            UpdateEntryBounds(existingIndex, bounds);
 191            return false;
 92        }
 93
 5994        EnsureCapacity(_count + 1);
 95
 5996        int entryIndex = AllocateEntry(key, bounds);
 5997        AddEntryToCells(entryIndex, bounds);
 5998        _keyToEntryIndex.Insert(key, entryIndex);
 5999        _count++;
 59100        return true;
 101    }
 102
 103    /// <summary>
 104    /// Removes an entry from the spatial hash.
 105    /// </summary>
 106    /// <param name="key">The entry key.</param>
 107    /// <returns><c>true</c> when the key existed and was removed; otherwise, <c>false</c>.</returns>
 108    public bool Remove(TKey key)
 109    {
 4110        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 111
 4112        int entryIndex = FindEntryIndex(key);
 4113        if (entryIndex < 0)
 1114            return false;
 115
 3116        RemoveEntryFromCells(entryIndex, _entries[entryIndex].Bounds);
 3117        _keyToEntryIndex.Remove(key, MatchesEntryKey, IsAllocatedEntry, GetEntryKey);
 3118        _entries[entryIndex].Reset();
 3119        _freeEntries.Push(entryIndex);
 3120        _count--;
 3121        return true;
 122    }
 123
 124    /// <summary>
 125    /// Updates the bounds for an existing entry.
 126    /// </summary>
 127    /// <param name="key">The entry key.</param>
 128    /// <param name="newBounds">The replacement bounds.</param>
 129    /// <returns><c>true</c> when the key existed; otherwise, <c>false</c>.</returns>
 130    public bool UpdateEntryBounds(TKey key, TVolume newBounds)
 131    {
 3132        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 133
 3134        int entryIndex = FindEntryIndex(key);
 3135        if (entryIndex < 0)
 1136            return false;
 137
 2138        return UpdateEntryBounds(entryIndex, newBounds);
 139    }
 140
 141    /// <summary>
 142    /// Determines whether the spatial hash contains the specified key.
 143    /// </summary>
 144    public bool Contains(TKey key)
 145    {
 4146        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 4147        return FindEntryIndex(key) >= 0;
 148    }
 149
 150    /// <summary>
 151    /// Attempts to retrieve the bounds registered for the supplied key.
 152    /// </summary>
 153    public bool TryGetBounds(TKey key, out TVolume bounds)
 154    {
 2155        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 156
 2157        int entryIndex = FindEntryIndex(key);
 2158        if (entryIndex < 0)
 159        {
 1160            bounds = default;
 1161            return false;
 162        }
 163
 1164        bounds = _entries[entryIndex].Bounds;
 1165        return true;
 166    }
 167
 168    /// <summary>
 169    /// Queries the spatial hash and returns only entries whose bounds intersect the supplied query volume.
 170    /// </summary>
 171    public void Query(TVolume queryBounds, ICollection<TKey> results)
 172    {
 17173        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 17174        ExecuteQuery(queryBounds, 0, true, results);
 17175    }
 176
 177    /// <summary>
 178    /// Queries the spatial hash using the supplied query volume plus the configured neighborhood padding.
 179    /// </summary>
 180    public void QueryNeighborhood(TVolume queryBounds, ICollection<TKey> results)
 181    {
 2182        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 2183        ExecuteQuery(queryBounds, Options.NeighborhoodPadding, false, results);
 2184    }
 185
 186    /// <summary>
 187    /// Ensures the spatial hash can store the specified number of entries without growing its entry storage.
 188    /// </summary>
 189    public void EnsureCapacity(int capacity)
 190    {
 59191        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 59192        if (capacity <= _entries.Length)
 54193            return;
 194
 5195        ResizeEntryStorage(capacity);
 5196    }
 197
 198    /// <summary>
 199    /// Removes all entries and cell registrations from the spatial hash.
 200    /// </summary>
 201    public void Clear()
 202    {
 2203        if (_count == 0)
 1204            return;
 205
 6206        for (int i = 0; i < _peakCount; i++)
 2207            _entries[i].Reset();
 208
 1209        _cells.Clear();
 1210        _keyToEntryIndex.Clear();
 1211        _freeEntries.Reset();
 1212        _peakCount = 0;
 1213        _count = 0;
 1214        _queryStamp = 0;
 1215    }
 216
 217    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 218    private int AllocateEntry(TKey key, TVolume bounds)
 219    {
 220        int entryIndex;
 59221        if (_freeEntries.Count > 0)
 1222            entryIndex = _freeEntries.Pop();
 223        else
 58224            entryIndex = _peakCount++;
 225
 59226        _entries[entryIndex].Key = key;
 59227        _entries[entryIndex].Bounds = bounds;
 59228        _entries[entryIndex].IsAllocated = true;
 59229        _entries[entryIndex].QueryStamp = 0;
 59230        return entryIndex;
 231    }
 232
 233    private bool UpdateEntryBounds(int entryIndex, TVolume newBounds)
 234    {
 3235        TVolume currentBounds = _entries[entryIndex].Bounds;
 3236        if (currentBounds.BoundsEquals(newBounds))
 1237            return true;
 238
 2239        RemoveEntryFromCells(entryIndex, currentBounds);
 2240        _entries[entryIndex].Bounds = newBounds;
 2241        AddEntryToCells(entryIndex, newBounds);
 2242        return true;
 243    }
 244
 245    private void ExecuteQuery(TVolume queryBounds, int padding, bool requireIntersection, ICollection<TKey> results)
 246    {
 19247        if (_count == 0)
 2248            return;
 249
 17250        int queryStamp = RentQueryStamp();
 17251        _cellMapper.GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCe
 252
 128253        for (int x = minCell.X - padding; x <= maxCell.X + padding; x++)
 254        {
 388255            for (int y = minCell.Y - padding; y <= maxCell.Y + padding; y++)
 256            {
 1312257                for (int z = minCell.Z - padding; z <= maxCell.Z + padding; z++)
 258                {
 509259                    var cell = new SwiftSpatialHashCellIndex(x, y, z);
 509260                    ProcessQueryCell(cell, queryBounds, queryStamp, requireIntersection, results);
 261                }
 262            }
 263        }
 17264    }
 265
 266    private void ProcessQueryCell(
 267        SwiftSpatialHashCellIndex cell,
 268        TVolume queryBounds,
 269        int queryStamp,
 270        bool requireIntersection,
 271        ICollection<TKey> results)
 272    {
 509273        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 412274            return;
 275
 452276        for (int i = 0; i < entryIndices.Count; i++)
 129277            TryAddQueryResult(entryIndices[i], queryBounds, queryStamp, requireIntersection, results);
 97278    }
 279
 280    private void TryAddQueryResult(
 281        int entryIndex,
 282        TVolume queryBounds,
 283        int queryStamp,
 284        bool requireIntersection,
 285        ICollection<TKey> results)
 286    {
 129287        ref SpatialHashEntry entry = ref _entries[entryIndex];
 129288        if (entry.QueryStamp == queryStamp)
 77289            return;
 290
 52291        entry.QueryStamp = queryStamp;
 292
 52293        if (requireIntersection && !entry.Bounds.Intersects(queryBounds))
 1294            return;
 295
 51296        results.Add(entry.Key);
 51297    }
 298
 299    private void AddEntryToCells(int entryIndex, TVolume bounds)
 300    {
 61301        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 302
 292303        for (int x = minCell.X; x <= maxCell.X; x++)
 304        {
 464305            for (int y = minCell.Y; y <= maxCell.Y; y++)
 306            {
 944307                for (int z = minCell.Z; z <= maxCell.Z; z++)
 308                {
 325309                    var cell = new SwiftSpatialHashCellIndex(x, y, z);
 325310                    if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 311                    {
 292312                        entryIndices = new SwiftList<int>(1);
 292313                        _cells[cell] = entryIndices;
 314                    }
 315
 325316                    entryIndices.Add(entryIndex);
 317                }
 318            }
 319        }
 61320    }
 321
 322    private void RemoveEntryFromCells(int entryIndex, TVolume bounds)
 323    {
 5324        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 325
 30326        for (int x = minCell.X; x <= maxCell.X; x++)
 327        {
 64328            for (int y = minCell.Y; y <= maxCell.Y; y++)
 329            {
 148330                for (int z = minCell.Z; z <= maxCell.Z; z++)
 331                {
 52332                    var cell = new SwiftSpatialHashCellIndex(x, y, z);
 52333                    RemoveEntryFromCell(cell, entryIndex);
 334                }
 335            }
 336        }
 5337    }
 338
 339    private void RemoveEntryFromCell(SwiftSpatialHashCellIndex cell, int entryIndex)
 340    {
 52341        SwiftList<int> entryIndices = _cells[cell];
 52342        RemoveEntryIndex(entryIndices, entryIndex);
 52343        if (entryIndices.Count == 0)
 51344            _cells.Remove(cell);
 52345    }
 346
 347    private static void RemoveEntryIndex(SwiftList<int> entryIndices, int entryIndex)
 348    {
 52349        entryIndices.RemoveAt(entryIndices.IndexOf(entryIndex));
 52350    }
 351
 352    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 353    private int FindEntryIndex(TKey key)
 354    {
 73355        return _keyToEntryIndex.Find(key, MatchesEntryKey);
 356    }
 357
 358    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 359    private void ResizeEntryStorage(int newCapacity)
 360    {
 5361        Array.Resize(ref _entries, newCapacity);
 5362        _cells.EnsureCapacity(newCapacity);
 5363        _keyToEntryIndex.ResizeAndRehash(newCapacity, _peakCount, IsAllocatedEntry, GetEntryKey);
 5364        SwiftCollectionDiagnostics.Shared.Info($"Resized spatial hash entry storage to {newCapacity} entries.", _diagnos
 5365    }
 366
 367    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 368    private int RentQueryStamp()
 369    {
 17370        if (_queryStamp == int.MaxValue)
 371        {
 10372            for (int i = 0; i < _peakCount; i++)
 3373                _entries[i].QueryStamp = 0;
 374
 2375            _queryStamp = 0;
 2376            SwiftCollectionDiagnostics.Shared.Warn($"Query stamp overflow detected. Spatial hash query stamps were reset
 377        }
 378
 17379        return ++_queryStamp;
 380    }
 381
 382    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 383    private bool MatchesEntryKey(int index, TKey key)
 384    {
 12385        return EqualityComparer<TKey>.Default.Equals(_entries[index].Key, key);
 386    }
 387
 388    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31389    private bool IsAllocatedEntry(int index) => _entries[index].IsAllocated;
 390
 391    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31392    private TKey GetEntryKey(int index) => _entries[index].Key;
 393
 394    private struct SpatialHashEntry
 395    {
 396        public TKey Key;
 397        public TVolume Bounds;
 398        public int QueryStamp;
 399        public bool IsAllocated;
 400
 401        public void Reset()
 402        {
 5403            Key = default!;
 5404            Bounds = default;
 5405            QueryStamp = 0;
 5406            IsAllocated = false;
 5407        }
 408    }
 409}
Generated by: ReportGenerator 5.5.10.0
07/01/2026 - 04:31:31
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Int32,SwiftCollections.Query.ISpatialHashCellMapper`1<TVolume>)
.ctor(System.Int32,SwiftCollections.Query.ISpatialHashCellMapper`1<TVolume>,SwiftCollections.Query.SwiftSpatialHashOptions)
get_Count()
Insert(TKey,TVolume)
Remove(TKey)
UpdateEntryBounds(TKey,TVolume)
Contains(TKey)
TryGetBounds(TKey,TVolume&)
Query(TVolume,System.Collections.Generic.ICollection`1<TKey>)
QueryNeighborhood(TVolume,System.Collections.Generic.ICollection`1<TKey>)
EnsureCapacity(System.Int32)
Clear()
AllocateEntry(TKey,TVolume)
UpdateEntryBounds(System.Int32,TVolume)
ExecuteQuery(TVolume,System.Int32,System.Boolean,System.Collections.Generic.ICollection`1<TKey>)
ProcessQueryCell(SwiftCollections.Query.SwiftSpatialHashCellIndex,TVolume,System.Int32,System.Boolean,System.Collections.Generic.ICollection`1<TKey>)
TryAddQueryResult(System.Int32,TVolume,System.Int32,System.Boolean,System.Collections.Generic.ICollection`1<TKey>)
AddEntryToCells(System.Int32,TVolume)
RemoveEntryFromCells(System.Int32,TVolume)
RemoveEntryFromCell(SwiftCollections.Query.SwiftSpatialHashCellIndex,System.Int32)
RemoveEntryIndex(SwiftCollections.SwiftList`1<System.Int32>,System.Int32)
FindEntryIndex(TKey)
ResizeEntryStorage(System.Int32)
RentQueryStamp()
MatchesEntryKey(System.Int32,TKey)
IsAllocatedEntry(System.Int32)
GetEntryKey(System.Int32)
Reset()