< 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
98%
Covered lines: 156
Uncovered lines: 3
Coverable lines: 159
Total lines: 412
Line coverage: 98.1%
Branch coverage
92%
Covered branches: 63
Total branches: 68
Branch coverage: 92.6%
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%
get_Options()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(...)75%4488.88%
ExecuteQuery(...)100%88100%
ProcessQueryCell(...)100%44100%
TryAddQueryResult(...)100%88100%
AddEntryToCells(...)100%88100%
RemoveEntryFromCells(...)100%66100%
RemoveEntryFromCell(...)75%4483.33%
RemoveEntryIndex(...)50%4480%
FindEntryIndex(...)100%11100%
ResizeEntryStorage(...)100%11100%
RentQueryStamp()100%44100%
MatchesEntryKey(...)50%22100%
IsAllocatedEntry(...)100%11100%
GetEntryKey(...)100%11100%
Reset()100%11100%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Runtime.CompilerServices;
 4
 5namespace SwiftCollections.Query;
 6
 7/// <summary>
 8/// Represents a mutable spatial hash that indexes keyed bounding volumes into deterministic integer grid cells.
 9/// </summary>
 10/// <typeparam name="TKey">The key used to identify each stored entry.</typeparam>
 11/// <typeparam name="TVolume">The volume type used for broad-phase registration and queries.</typeparam>
 12public class SwiftSpatialHash<TKey, TVolume>
 13    where TKey : notnull
 14    where TVolume : struct, IBoundVolume<TVolume>
 15{
 16    private const string _diagnosticSource = nameof(SwiftSpatialHash<TKey, TVolume>);
 17
 18    private readonly ISpatialHashCellMapper<TVolume> _cellMapper;
 19    private readonly QueryKeyIndexMap<TKey> _keyToEntryIndex;
 20    private readonly SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>> _cells;
 21    private readonly SwiftIntStack _freeEntries;
 22
 23    private SpatialHashEntry[] _entries;
 24    private int _peakCount;
 25    private int _count;
 26    private int _queryStamp;
 27
 28    /// <summary>
 29    /// Initializes a new instance of the <see cref="SwiftSpatialHash{TKey, TVolume}"/> class.
 30    /// </summary>
 31    /// <param name="capacity">The initial entry capacity.</param>
 32    /// <param name="cellMapper">The mapper that projects volumes into deterministic cell coordinates.</param>
 33    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper)
 1234        : this(capacity, cellMapper, SwiftSpatialHashOptions.Default)
 35    {
 1236    }
 37
 38    /// <summary>
 39    /// Initializes a new instance of the <see cref="SwiftSpatialHash{TKey, TVolume}"/> class.
 40    /// </summary>
 41    /// <param name="capacity">The initial entry capacity.</param>
 42    /// <param name="cellMapper">The mapper that projects volumes into deterministic cell coordinates.</param>
 43    /// <param name="options">Spatial hash query options.</param>
 1544    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper, SwiftSpatialHashOptions options)
 45    {
 1546        SwiftThrowHelper.ThrowIfNull(cellMapper, nameof(cellMapper));
 47
 1548        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 49
 1550        _cellMapper = cellMapper;
 1551        _keyToEntryIndex = new QueryKeyIndexMap<TKey>(capacity);
 1552        _cells = new SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>>(capacity);
 1553        _freeEntries = new SwiftIntStack();
 1554        _entries = new SpatialHashEntry[capacity];
 1555        Options = options;
 1556    }
 57
 58    /// <summary>
 59    /// Gets the number of active entries stored in the spatial hash.
 60    /// </summary>
 361    public int Count => _count;
 62
 63    /// <summary>
 64    /// Gets the options used by this spatial hash.
 65    /// </summary>
 266    public SwiftSpatialHashOptions Options { get; }
 67
 68    /// <summary>
 69    /// Inserts a new entry or replaces the bounds of an existing key.
 70    /// </summary>
 71    /// <param name="key">The entry key.</param>
 72    /// <param name="bounds">The entry bounds.</param>
 73    /// <returns><c>true</c> when a new key was added; <c>false</c> when an existing key was replaced.</returns>
 74    public bool Insert(TKey key, TVolume bounds)
 75    {
 5476        SwiftThrowHelper.ThrowIfNull(key, nameof(key));
 77
 5478        int existingIndex = FindEntryIndex(key);
 5479        if (existingIndex >= 0)
 80        {
 181            UpdateEntryBounds(existingIndex, bounds);
 182            return false;
 83        }
 84
 5385        EnsureCapacity(_count + 1);
 86
 5387        int entryIndex = AllocateEntry(key, bounds);
 5388        AddEntryToCells(entryIndex, bounds);
 5389        _keyToEntryIndex.Insert(key, entryIndex);
 5390        _count++;
 5391        return true;
 92    }
 93
 94    /// <summary>
 95    /// Removes an entry from the spatial hash.
 96    /// </summary>
 97    /// <param name="key">The entry key.</param>
 98    /// <returns><c>true</c> when the key existed and was removed; otherwise, <c>false</c>.</returns>
 99    public bool Remove(TKey key)
 100    {
 3101        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 102
 3103        int entryIndex = FindEntryIndex(key);
 3104        if (entryIndex < 0)
 1105            return false;
 106
 2107        RemoveEntryFromCells(entryIndex, _entries[entryIndex].Bounds);
 2108        _keyToEntryIndex.Remove(key, MatchesEntryKey, IsAllocatedEntry, GetEntryKey);
 2109        _entries[entryIndex].Reset();
 2110        _freeEntries.Push(entryIndex);
 2111        _count--;
 2112        return true;
 113    }
 114
 115    /// <summary>
 116    /// Updates the bounds for an existing entry.
 117    /// </summary>
 118    /// <param name="key">The entry key.</param>
 119    /// <param name="newBounds">The replacement bounds.</param>
 120    /// <returns><c>true</c> when the key existed; otherwise, <c>false</c>.</returns>
 121    public bool UpdateEntryBounds(TKey key, TVolume newBounds)
 122    {
 3123        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 124
 3125        int entryIndex = FindEntryIndex(key);
 3126        if (entryIndex < 0)
 1127            return false;
 128
 2129        return UpdateEntryBounds(entryIndex, newBounds);
 130    }
 131
 132    /// <summary>
 133    /// Determines whether the spatial hash contains the specified key.
 134    /// </summary>
 135    public bool Contains(TKey key)
 136    {
 2137        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 2138        return FindEntryIndex(key) >= 0;
 139    }
 140
 141    /// <summary>
 142    /// Attempts to retrieve the bounds registered for the supplied key.
 143    /// </summary>
 144    public bool TryGetBounds(TKey key, out TVolume bounds)
 145    {
 2146        SwiftThrowHelper.ThrowIfNullGeneric(key, nameof(key));
 147
 2148        int entryIndex = FindEntryIndex(key);
 2149        if (entryIndex < 0)
 150        {
 1151            bounds = default;
 1152            return false;
 153        }
 154
 1155        bounds = _entries[entryIndex].Bounds;
 1156        return true;
 157    }
 158
 159    /// <summary>
 160    /// Queries the spatial hash and returns only entries whose bounds intersect the supplied query volume.
 161    /// </summary>
 162    public void Query(TVolume queryBounds, ICollection<TKey> results)
 163    {
 13164        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 13165        ExecuteQuery(queryBounds, 0, true, results);
 13166    }
 167
 168    /// <summary>
 169    /// Queries the spatial hash using the supplied query volume plus the configured neighborhood padding.
 170    /// </summary>
 171    public void QueryNeighborhood(TVolume queryBounds, ICollection<TKey> results)
 172    {
 2173        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 2174        ExecuteQuery(queryBounds, Options.NeighborhoodPadding, false, results);
 2175    }
 176
 177    /// <summary>
 178    /// Ensures the spatial hash can store the specified number of entries without growing its entry storage.
 179    /// </summary>
 180    public void EnsureCapacity(int capacity)
 181    {
 53182        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 53183        if (capacity <= _entries.Length)
 49184            return;
 185
 4186        ResizeEntryStorage(capacity);
 4187    }
 188
 189    /// <summary>
 190    /// Removes all entries and cell registrations from the spatial hash.
 191    /// </summary>
 192    public void Clear()
 193    {
 2194        if (_count == 0)
 1195            return;
 196
 6197        for (int i = 0; i < _peakCount; i++)
 2198            _entries[i].Reset();
 199
 1200        _cells.Clear();
 1201        _keyToEntryIndex.Clear();
 1202        _freeEntries.Reset();
 1203        _peakCount = 0;
 1204        _count = 0;
 1205        _queryStamp = 0;
 1206    }
 207
 208    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 209    private int AllocateEntry(TKey key, TVolume bounds)
 210    {
 211        int entryIndex;
 53212        if (_freeEntries.Count > 0)
 1213            entryIndex = _freeEntries.Pop();
 214        else
 52215            entryIndex = _peakCount++;
 216
 53217        _entries[entryIndex].Key = key;
 53218        _entries[entryIndex].Bounds = bounds;
 53219        _entries[entryIndex].IsAllocated = true;
 53220        _entries[entryIndex].QueryStamp = 0;
 53221        return entryIndex;
 222    }
 223
 224    private bool UpdateEntryBounds(int entryIndex, TVolume newBounds)
 225    {
 3226        if (!_entries[entryIndex].IsAllocated)
 0227            return false;
 228
 3229        TVolume currentBounds = _entries[entryIndex].Bounds;
 3230        if (currentBounds.BoundsEquals(newBounds))
 1231            return true;
 232
 2233        RemoveEntryFromCells(entryIndex, currentBounds);
 2234        _entries[entryIndex].Bounds = newBounds;
 2235        AddEntryToCells(entryIndex, newBounds);
 2236        return true;
 237    }
 238
 239    private void ExecuteQuery(TVolume queryBounds, int padding, bool requireIntersection, ICollection<TKey> results)
 240    {
 15241        if (_count == 0)
 2242            return;
 243
 13244        int queryStamp = RentQueryStamp();
 13245        _cellMapper.GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCe
 246
 102247        for (int x = minCell.X - padding; x <= maxCell.X + padding; x++)
 248        {
 328249            for (int y = minCell.Y - padding; y <= maxCell.Y + padding; y++)
 250            {
 1168251                for (int z = minCell.Z - padding; z <= maxCell.Z + padding; z++)
 252                {
 458253                    var cell = new SwiftSpatialHashCellIndex(x, y, z);
 458254                    ProcessQueryCell(cell, queryBounds, queryStamp, requireIntersection, results);
 255                }
 256            }
 257        }
 13258    }
 259
 260    private void ProcessQueryCell(
 261        SwiftSpatialHashCellIndex cell,
 262        TVolume queryBounds,
 263        int queryStamp,
 264        bool requireIntersection,
 265        ICollection<TKey> results)
 266    {
 458267        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 380268            return;
 269
 376270        for (int i = 0; i < entryIndices.Count; i++)
 110271            TryAddQueryResult(entryIndices[i], queryBounds, queryStamp, requireIntersection, results);
 78272    }
 273
 274    private void TryAddQueryResult(
 275        int entryIndex,
 276        TVolume queryBounds,
 277        int queryStamp,
 278        bool requireIntersection,
 279        ICollection<TKey> results)
 280    {
 110281        ref SpatialHashEntry entry = ref _entries[entryIndex];
 110282        if (!entry.IsAllocated || entry.QueryStamp == queryStamp)
 63283            return;
 284
 47285        entry.QueryStamp = queryStamp;
 286
 47287        if (requireIntersection && !entry.Bounds.Intersects(queryBounds))
 1288            return;
 289
 46290        results.Add(entry.Key);
 46291    }
 292
 293    private void AddEntryToCells(int entryIndex, TVolume bounds)
 294    {
 55295        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 296
 260297        for (int x = minCell.X; x <= maxCell.X; x++)
 298        {
 396299            for (int y = minCell.Y; y <= maxCell.Y; y++)
 300            {
 744301                for (int z = minCell.Z; z <= maxCell.Z; z++)
 302                {
 249303                    var cell = new SwiftSpatialHashCellIndex(x, y, z);
 249304                    if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 305                    {
 217306                        entryIndices = new SwiftList<int>(1);
 217307                        _cells[cell] = entryIndices;
 308                    }
 309
 249310                    entryIndices.Add(entryIndex);
 311                }
 312            }
 313        }
 55314    }
 315
 316    private void RemoveEntryFromCells(int entryIndex, TVolume bounds)
 317    {
 4318        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 319
 26320        for (int x = minCell.X; x <= maxCell.X; x++)
 321        {
 60322            for (int y = minCell.Y; y <= maxCell.Y; y++)
 323            {
 144324                for (int z = minCell.Z; z <= maxCell.Z; z++)
 325                {
 51326                    var cell = new SwiftSpatialHashCellIndex(x, y, z);
 51327                    RemoveEntryFromCell(cell, entryIndex);
 328                }
 329            }
 330        }
 4331    }
 332
 333    private void RemoveEntryFromCell(SwiftSpatialHashCellIndex cell, int entryIndex)
 334    {
 51335        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 0336            return;
 337
 51338        RemoveEntryIndex(entryIndices, entryIndex);
 51339        if (entryIndices.Count == 0)
 51340            _cells.Remove(cell);
 51341    }
 342
 343    private static void RemoveEntryIndex(SwiftList<int> entryIndices, int entryIndex)
 344    {
 102345        for (int i = 0; i < entryIndices.Count; i++)
 346        {
 51347            if (entryIndices[i] != entryIndex)
 348                continue;
 349
 51350            entryIndices.RemoveAt(i);
 51351            return;
 352        }
 0353    }
 354
 355    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 356    private int FindEntryIndex(TKey key)
 357    {
 64358        return _keyToEntryIndex.Find(key, MatchesEntryKey);
 359    }
 360
 361    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 362    private void ResizeEntryStorage(int newCapacity)
 363    {
 4364        Array.Resize(ref _entries, newCapacity);
 4365        _cells.EnsureCapacity(newCapacity);
 4366        _keyToEntryIndex.ResizeAndRehash(newCapacity, _peakCount, IsAllocatedEntry, GetEntryKey);
 4367        QueryCollectionDiagnostics.WriteInfo(_diagnosticSource, $"Resized spatial hash entry storage to {newCapacity} en
 4368    }
 369
 370    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 371    private int RentQueryStamp()
 372    {
 13373        if (_queryStamp == int.MaxValue)
 374        {
 4375            for (int i = 0; i < _peakCount; i++)
 1376                _entries[i].QueryStamp = 0;
 377
 1378            _queryStamp = 0;
 1379            QueryCollectionDiagnostics.WriteWarning(_diagnosticSource, "Query stamp overflow detected. Spatial hash quer
 380        }
 381
 13382        return ++_queryStamp;
 383    }
 384
 385    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 386    private bool MatchesEntryKey(int index, TKey key)
 387    {
 9388        return _entries[index].IsAllocated && EqualityComparer<TKey>.Default.Equals(_entries[index].Key, key);
 389    }
 390
 391    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 30392    private bool IsAllocatedEntry(int index) => _entries[index].IsAllocated;
 393
 394    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 30395    private TKey GetEntryKey(int index) => _entries[index].Key;
 396
 397    private struct SpatialHashEntry
 398    {
 399        public TKey Key;
 400        public TVolume Bounds;
 401        public int QueryStamp;
 402        public bool IsAllocated;
 403
 404        public void Reset()
 405        {
 4406            Key = default!;
 4407            Bounds = default;
 4408            QueryStamp = 0;
 4409            IsAllocated = false;
 4410        }
 411    }
 412}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 03:35:54
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()
get_Options()
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()