< 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: 164
Uncovered lines: 0
Coverable lines: 164
Total lines: 431
Line coverage: 100%
Branch coverage
100%
Covered branches: 64
Total branches: 64
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%
CollectCellCandidates(...)100%44100%
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 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 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>
 2953    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper, SwiftSpatialHashOptions options)
 54    {
 2955        SwiftThrowHelper.ThrowIfNull(cellMapper, nameof(cellMapper));
 56
 2957        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 58
 2959        _cellMapper = cellMapper;
 2960        _keyToEntryIndex = new QueryKeyIndexMap<TKey>(capacity, MatchesEntryKey, IsAllocatedEntry, GetEntryKey);
 2961        _cells = new SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>>(capacity);
 2962        _freeEntries = new SwiftIntStack();
 2963        _entries = new SpatialHashEntry[capacity];
 2964        Options = options;
 2965    }
 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    {
 6985        SwiftThrowHelper.ThrowIfNull(key, nameof(key));
 86
 6987        int existingIndex = FindEntryIndex(key);
 6988        if (existingIndex >= 0)
 89        {
 190            UpdateEntryBounds(existingIndex, bounds);
 191            return false;
 92        }
 93
 6894        EnsureCapacity(_count + 1);
 95
 6896        int entryIndex = AllocateEntry(key, bounds);
 6897        AddEntryToCells(entryIndex, bounds);
 6898        _keyToEntryIndex.Insert(key, entryIndex);
 6899        _count++;
 68100        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    {
 6110        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 111
 6112        int entryIndex = FindEntryIndex(key);
 6113        if (entryIndex < 0)
 1114            return false;
 115
 5116        RemoveEntryFromCells(entryIndex, _entries[entryIndex].Bounds);
 5117        _keyToEntryIndex.Remove(key);
 5118        _entries[entryIndex].Reset();
 5119        _freeEntries.Push(entryIndex);
 5120        _count--;
 5121        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    {
 21173        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 21174        ExecuteQuery(queryBounds, 0, true, results);
 21175    }
 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    {
 4182        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 4183        ExecuteQuery(queryBounds, Options.NeighborhoodPadding, false, results);
 4184    }
 185
 186    /// <summary>
 187    /// Collects every entry registered in one already-mapped spatial cell.
 188    /// </summary>
 189    protected void CollectCellCandidates(
 190        SwiftSpatialHashCellIndex cell,
 191        ICollection<TKey> results)
 192    {
 8193        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 7194        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 1195            return;
 196
 26197        for (int i = 0; i < entryIndices.Count; i++)
 7198            results.Add(_entries[entryIndices[i]].Key);
 6199    }
 200
 201    /// <summary>
 202    /// Ensures the spatial hash can store the specified number of entries without growing its entry storage.
 203    /// </summary>
 204    public void EnsureCapacity(int capacity)
 205    {
 68206        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 68207        if (capacity <= _entries.Length)
 63208            return;
 209
 5210        ResizeEntryStorage(capacity);
 5211    }
 212
 213    /// <summary>
 214    /// Removes all entries and cell registrations from the spatial hash.
 215    /// </summary>
 216    public void Clear()
 217    {
 2218        if (_count == 0)
 1219            return;
 220
 6221        for (int i = 0; i < _peakCount; i++)
 2222            _entries[i].Reset();
 223
 1224        _cells.Clear();
 1225        _keyToEntryIndex.Clear();
 1226        _freeEntries.Reset();
 1227        _peakCount = 0;
 1228        _count = 0;
 1229        _queryStamp = 0;
 1230    }
 231
 232    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 233    private int AllocateEntry(TKey key, TVolume bounds)
 234    {
 235        int entryIndex;
 68236        if (_freeEntries.Count > 0)
 1237            entryIndex = _freeEntries.Pop();
 238        else
 67239            entryIndex = _peakCount++;
 240
 68241        _entries[entryIndex].Key = key;
 68242        _entries[entryIndex].Bounds = bounds;
 68243        _entries[entryIndex].IsAllocated = true;
 68244        _entries[entryIndex].QueryStamp = 0;
 68245        return entryIndex;
 246    }
 247
 248    private bool UpdateEntryBounds(int entryIndex, TVolume newBounds)
 249    {
 3250        TVolume currentBounds = _entries[entryIndex].Bounds;
 3251        if (currentBounds.BoundsEquals(newBounds))
 1252            return true;
 253
 2254        RemoveEntryFromCells(entryIndex, currentBounds);
 2255        _entries[entryIndex].Bounds = newBounds;
 2256        AddEntryToCells(entryIndex, newBounds);
 2257        return true;
 258    }
 259
 260    private void ExecuteQuery(TVolume queryBounds, int padding, bool requireIntersection, ICollection<TKey> results)
 261    {
 25262        if (_count == 0)
 4263            return;
 264
 21265        int queryStamp = RentQueryStamp();
 21266        _cellMapper.GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCe
 267
 21268        long minX = Math.Max(int.MinValue, (long)minCell.X - padding);
 21269        long minY = Math.Max(int.MinValue, (long)minCell.Y - padding);
 21270        long minZ = Math.Max(int.MinValue, (long)minCell.Z - padding);
 21271        long maxX = Math.Min(int.MaxValue, (long)maxCell.X + padding);
 21272        long maxY = Math.Min(int.MaxValue, (long)maxCell.Y + padding);
 21273        long maxZ = Math.Min(int.MaxValue, (long)maxCell.Z + padding);
 274
 148275        for (long x = minX; x <= maxX; x++)
 276        {
 420277            for (long y = minY; y <= maxY; y++)
 278            {
 1368279                for (long z = minZ; z <= maxZ; z++)
 280                {
 527281                    var cell = new SwiftSpatialHashCellIndex((int)x, (int)y, (int)z);
 527282                    ProcessQueryCell(cell, queryBounds, queryStamp, requireIntersection, results);
 283                }
 284            }
 285        }
 21286    }
 287
 288    private void ProcessQueryCell(
 289        SwiftSpatialHashCellIndex cell,
 290        TVolume queryBounds,
 291        int queryStamp,
 292        bool requireIntersection,
 293        ICollection<TKey> results)
 294    {
 527295        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 426296            return;
 297
 468298        for (int i = 0; i < entryIndices.Count; i++)
 133299            TryAddQueryResult(entryIndices[i], queryBounds, queryStamp, requireIntersection, results);
 101300    }
 301
 302    private void TryAddQueryResult(
 303        int entryIndex,
 304        TVolume queryBounds,
 305        int queryStamp,
 306        bool requireIntersection,
 307        ICollection<TKey> results)
 308    {
 133309        ref SpatialHashEntry entry = ref _entries[entryIndex];
 133310        if (entry.QueryStamp == queryStamp)
 77311            return;
 312
 56313        entry.QueryStamp = queryStamp;
 314
 56315        if (requireIntersection && !entry.Bounds.Intersects(queryBounds))
 1316            return;
 317
 55318        results.Add(entry.Key);
 55319    }
 320
 321    private void AddEntryToCells(int entryIndex, TVolume bounds)
 322    {
 70323        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 324
 328325        for (long x = minCell.X; x <= maxCell.X; x++)
 326        {
 500327            for (long y = minCell.Y; y <= maxCell.Y; y++)
 328            {
 980329                for (long z = minCell.Z; z <= maxCell.Z; z++)
 330                {
 334331                    var cell = new SwiftSpatialHashCellIndex((int)x, (int)y, (int)z);
 334332                    if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 333                    {
 300334                        entryIndices = new SwiftList<int>(1);
 300335                        _cells[cell] = entryIndices;
 336                    }
 337
 334338                    entryIndices.Add(entryIndex);
 339                }
 340            }
 341        }
 70342    }
 343
 344    private void RemoveEntryFromCells(int entryIndex, TVolume bounds)
 345    {
 7346        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 347
 38348        for (long x = minCell.X; x <= maxCell.X; x++)
 349        {
 72350            for (long y = minCell.Y; y <= maxCell.Y; y++)
 351            {
 156352                for (long z = minCell.Z; z <= maxCell.Z; z++)
 353                {
 54354                    var cell = new SwiftSpatialHashCellIndex((int)x, (int)y, (int)z);
 54355                    RemoveEntryFromCell(cell, entryIndex);
 356                }
 357            }
 358        }
 7359    }
 360
 361    private void RemoveEntryFromCell(SwiftSpatialHashCellIndex cell, int entryIndex)
 362    {
 54363        SwiftList<int> entryIndices = _cells[cell];
 54364        RemoveEntryIndex(entryIndices, entryIndex);
 54365        if (entryIndices.Count == 0)
 53366            _cells.Remove(cell);
 54367    }
 368
 369    private static void RemoveEntryIndex(SwiftList<int> entryIndices, int entryIndex)
 370    {
 54371        entryIndices.RemoveAt(entryIndices.IndexOf(entryIndex));
 54372    }
 373
 374    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 375    private int FindEntryIndex(TKey key)
 376    {
 84377        return _keyToEntryIndex.Find(key);
 378    }
 379
 380    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 381    private void ResizeEntryStorage(int newCapacity)
 382    {
 5383        Array.Resize(ref _entries, newCapacity);
 5384        _cells.EnsureCapacity(newCapacity);
 5385        _keyToEntryIndex.ResizeAndRehash(newCapacity, _peakCount);
 5386        SwiftCollectionDiagnostics.Shared.Info($"Resized spatial hash entry storage to {newCapacity} entries.", _diagnos
 5387    }
 388
 389    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 390    private int RentQueryStamp()
 391    {
 21392        if (_queryStamp == int.MaxValue)
 393        {
 10394            for (int i = 0; i < _peakCount; i++)
 3395                _entries[i].QueryStamp = 0;
 396
 2397            _queryStamp = 0;
 2398            SwiftCollectionDiagnostics.Shared.Warn($"Query stamp overflow detected. Spatial hash query stamps were reset
 399        }
 400
 21401        return ++_queryStamp;
 402    }
 403
 404    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 405    private bool MatchesEntryKey(int index, TKey key)
 406    {
 16407        return EqualityComparer<TKey>.Default.Equals(_entries[index].Key, key);
 408    }
 409
 410    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31411    private bool IsAllocatedEntry(int index) => _entries[index].IsAllocated;
 412
 413    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31414    private TKey GetEntryKey(int index) => _entries[index].Key;
 415
 416    private struct SpatialHashEntry
 417    {
 418        public TKey Key;
 419        public TVolume Bounds;
 420        public int QueryStamp;
 421        public bool IsAllocated;
 422
 423        public void Reset()
 424        {
 7425            Key = default!;
 7426            Bounds = default;
 7427            QueryStamp = 0;
 7428            IsAllocated = false;
 7429        }
 430    }
 431}
Generated by: ReportGenerator 5.5.11.0
08/05/2026 - 03:54:48
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>)
CollectCellCandidates(SwiftCollections.Query.SwiftSpatialHashCellIndex,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()