< 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: 432
Line coverage: 100%
Branch coverage
100%
Covered branches: 62
Total branches: 62
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%44100%
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 Chronicler.Diagnostics;
 12using SwiftCollections.Diagnostics;
 13using SwiftCollections.Utility;
 14
 15namespace SwiftCollections.Query;
 16
 17/// <summary>
 18/// Represents a mutable spatial hash that indexes keyed bounding volumes into deterministic integer grid cells.
 19/// </summary>
 20/// <typeparam name="TKey">The key used to identify each stored entry.</typeparam>
 21/// <typeparam name="TVolume">The volume type used for broad-phase registration and queries.</typeparam>
 22public class SwiftSpatialHash<TKey, TVolume>
 23    where TKey : notnull
 24    where TVolume : struct, IBoundVolume<TVolume>
 25{
 26    private const string _diagnosticSource = nameof(SwiftSpatialHash<TKey, TVolume>);
 27
 28    private readonly ISpatialHashCellMapper<TVolume> _cellMapper;
 29    private readonly QueryKeyIndexMap<TKey> _keyToEntryIndex;
 30    private readonly SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>> _cells;
 31    private readonly SwiftIntStack _freeEntries;
 32
 33    private SpatialHashEntry[] _entries;
 34    private int _peakCount;
 35    private int _count;
 36    private int _queryStamp;
 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    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper)
 1544        : this(capacity, cellMapper, SwiftSpatialHashOptions.Default)
 45    {
 1546    }
 47
 48    /// <summary>
 49    /// Initializes a new instance of the <see cref="SwiftSpatialHash{TKey, TVolume}"/> class.
 50    /// </summary>
 51    /// <param name="capacity">The initial entry capacity.</param>
 52    /// <param name="cellMapper">The mapper that projects volumes into deterministic cell coordinates.</param>
 53    /// <param name="options">Spatial hash query options.</param>
 1854    public SwiftSpatialHash(int capacity, ISpatialHashCellMapper<TVolume> cellMapper, SwiftSpatialHashOptions options)
 55    {
 1856        ChronicleGuard.ThrowIfNull(cellMapper, nameof(cellMapper));
 57
 1858        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 59
 1860        _cellMapper = cellMapper;
 1861        _keyToEntryIndex = new QueryKeyIndexMap<TKey>(capacity, MatchesEntryKey, IsAllocatedEntry, GetEntryKey);
 1862        _cells = new SwiftDictionary<SwiftSpatialHashCellIndex, SwiftList<int>>(capacity);
 1863        _freeEntries = new SwiftIntStack();
 1864        _entries = new SpatialHashEntry[capacity];
 1865        Options = options;
 1866    }
 67
 68    /// <summary>
 69    /// Gets the number of active entries stored in the spatial hash.
 70    /// </summary>
 371    public int Count => _count;
 72
 73    /// <summary>
 74    /// Gets the options used by this spatial hash.
 75    /// </summary>
 76    public SwiftSpatialHashOptions Options { get; }
 77
 78    /// <summary>
 79    /// Inserts a new entry or replaces the bounds of an existing key.
 80    /// </summary>
 81    /// <param name="key">The entry key.</param>
 82    /// <param name="bounds">The entry bounds.</param>
 83    /// <returns><c>true</c> when a new key was added; <c>false</c> when an existing key was replaced.</returns>
 84    public bool Insert(TKey key, TVolume bounds)
 85    {
 5986        ChronicleGuard.ThrowIfNull(key, nameof(key));
 87
 5988        int existingIndex = FindEntryIndex(key);
 5989        if (existingIndex >= 0)
 90        {
 191            UpdateEntryBounds(existingIndex, bounds);
 192            return false;
 93        }
 94
 5895        EnsureCapacity(_count + 1);
 96
 5897        int entryIndex = AllocateEntry(key, bounds);
 5898        AddEntryToCells(entryIndex, bounds);
 5899        _keyToEntryIndex.Insert(key, entryIndex);
 58100        _count++;
 58101        return true;
 102    }
 103
 104    /// <summary>
 105    /// Removes an entry from the spatial hash.
 106    /// </summary>
 107    /// <param name="key">The entry key.</param>
 108    /// <returns><c>true</c> when the key existed and was removed; otherwise, <c>false</c>.</returns>
 109    public bool Remove(TKey key)
 110    {
 4111        ChronicleGuard.ThrowIfNullGeneric(key, nameof(key));
 112
 4113        int entryIndex = FindEntryIndex(key);
 4114        if (entryIndex < 0)
 1115            return false;
 116
 3117        RemoveEntryFromCells(entryIndex, _entries[entryIndex].Bounds);
 3118        _keyToEntryIndex.Remove(key);
 3119        _entries[entryIndex].Reset();
 3120        _freeEntries.Push(entryIndex);
 3121        _count--;
 3122        return true;
 123    }
 124
 125    /// <summary>
 126    /// Updates the bounds for an existing entry.
 127    /// </summary>
 128    /// <param name="key">The entry key.</param>
 129    /// <param name="newBounds">The replacement bounds.</param>
 130    /// <returns><c>true</c> when the key existed; otherwise, <c>false</c>.</returns>
 131    public bool UpdateEntryBounds(TKey key, TVolume newBounds)
 132    {
 3133        ChronicleGuard.ThrowIfNullGeneric(key, nameof(key));
 134
 3135        int entryIndex = FindEntryIndex(key);
 3136        if (entryIndex < 0)
 1137            return false;
 138
 2139        return UpdateEntryBounds(entryIndex, newBounds);
 140    }
 141
 142    /// <summary>
 143    /// Determines whether the spatial hash contains the specified key.
 144    /// </summary>
 145    public bool Contains(TKey key)
 146    {
 4147        ChronicleGuard.ThrowIfNullGeneric(key, nameof(key));
 4148        return FindEntryIndex(key) >= 0;
 149    }
 150
 151    /// <summary>
 152    /// Attempts to retrieve the bounds registered for the supplied key.
 153    /// </summary>
 154    public bool TryGetBounds(TKey key, out TVolume bounds)
 155    {
 2156        ChronicleGuard.ThrowIfNullGeneric(key, nameof(key));
 157
 2158        int entryIndex = FindEntryIndex(key);
 2159        if (entryIndex < 0)
 160        {
 1161            bounds = default;
 1162            return false;
 163        }
 164
 1165        bounds = _entries[entryIndex].Bounds;
 1166        return true;
 167    }
 168
 169    /// <summary>
 170    /// Queries the spatial hash and returns only entries whose bounds intersect the supplied query volume.
 171    /// </summary>
 172    public void Query(TVolume queryBounds, ICollection<TKey> results)
 173    {
 15174        ChronicleGuard.ThrowIfNull(results, nameof(results));
 15175        ExecuteQuery(queryBounds, 0, true, results);
 15176    }
 177
 178    /// <summary>
 179    /// Queries the spatial hash using the supplied query volume plus the configured neighborhood padding.
 180    /// </summary>
 181    public void QueryNeighborhood(TVolume queryBounds, ICollection<TKey> results)
 182    {
 2183        ChronicleGuard.ThrowIfNull(results, nameof(results));
 2184        ExecuteQuery(queryBounds, Options.NeighborhoodPadding, false, results);
 2185    }
 186
 187    /// <summary>
 188    /// Collects every entry registered in one already-mapped spatial cell.
 189    /// </summary>
 190    protected void CollectCellCandidates(
 191        SwiftSpatialHashCellIndex cell,
 192        ICollection<TKey> results)
 193    {
 3194        ChronicleGuard.ThrowIfNull(results, nameof(results));
 2195        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 1196            return;
 197
 4198        for (int i = 0; i < entryIndices.Count; i++)
 1199            results.Add(_entries[entryIndices[i]].Key);
 1200    }
 201
 202    /// <summary>
 203    /// Ensures the spatial hash can store the specified number of entries without growing its entry storage.
 204    /// </summary>
 205    public void EnsureCapacity(int capacity)
 206    {
 58207        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 58208        if (capacity <= _entries.Length)
 53209            return;
 210
 5211        ResizeEntryStorage(capacity);
 5212    }
 213
 214    /// <summary>
 215    /// Removes all entries and cell registrations from the spatial hash.
 216    /// </summary>
 217    public void Clear()
 218    {
 2219        if (_count == 0)
 1220            return;
 221
 6222        for (int i = 0; i < _peakCount; i++)
 2223            _entries[i].Reset();
 224
 1225        _cells.Clear();
 1226        _keyToEntryIndex.Clear();
 1227        _freeEntries.Reset();
 1228        _peakCount = 0;
 1229        _count = 0;
 1230        _queryStamp = 0;
 1231    }
 232
 233    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 234    private int AllocateEntry(TKey key, TVolume bounds)
 235    {
 236        int entryIndex;
 58237        if (_freeEntries.Count > 0)
 1238            entryIndex = _freeEntries.Pop();
 239        else
 57240            entryIndex = _peakCount++;
 241
 58242        _entries[entryIndex].Key = key;
 58243        _entries[entryIndex].Bounds = bounds;
 58244        _entries[entryIndex].IsAllocated = true;
 58245        _entries[entryIndex].QueryStamp = 0;
 58246        return entryIndex;
 247    }
 248
 249    private bool UpdateEntryBounds(int entryIndex, TVolume newBounds)
 250    {
 3251        TVolume currentBounds = _entries[entryIndex].Bounds;
 3252        if (currentBounds.BoundsEquals(newBounds))
 1253            return true;
 254
 2255        RemoveEntryFromCells(entryIndex, currentBounds);
 2256        _entries[entryIndex].Bounds = newBounds;
 2257        AddEntryToCells(entryIndex, newBounds);
 2258        return true;
 259    }
 260
 261    private void ExecuteQuery(TVolume queryBounds, int padding, bool requireIntersection, ICollection<TKey> results)
 262    {
 17263        if (_count == 0)
 2264            return;
 265
 15266        int queryStamp = RentQueryStamp();
 15267        _cellMapper.GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCe
 268
 15269        long minX = Math.Max(int.MinValue, (long)minCell.X - padding);
 15270        long minY = Math.Max(int.MinValue, (long)minCell.Y - padding);
 15271        long minZ = Math.Max(int.MinValue, (long)minCell.Z - padding);
 15272        long maxX = Math.Min(int.MaxValue, (long)maxCell.X + padding);
 15273        long maxY = Math.Min(int.MaxValue, (long)maxCell.Y + padding);
 15274        long maxZ = Math.Min(int.MaxValue, (long)maxCell.Z + padding);
 275
 116276        for (long x = minX; x <= maxX; x++)
 277        {
 364278            for (long y = minY; y <= maxY; y++)
 279            {
 1264280                for (long z = minZ; z <= maxZ; z++)
 281                {
 493282                    var cell = new SwiftSpatialHashCellIndex((int)x, (int)y, (int)z);
 493283                    ProcessQueryCell(cell, queryBounds, queryStamp, requireIntersection, results);
 284                }
 285            }
 286        }
 15287    }
 288
 289    private void ProcessQueryCell(
 290        SwiftSpatialHashCellIndex cell,
 291        TVolume queryBounds,
 292        int queryStamp,
 293        bool requireIntersection,
 294        ICollection<TKey> results)
 295    {
 493296        if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 412297            return;
 298
 388299        for (int i = 0; i < entryIndices.Count; i++)
 113300            TryAddQueryResult(entryIndices[i], queryBounds, queryStamp, requireIntersection, results);
 81301    }
 302
 303    private void TryAddQueryResult(
 304        int entryIndex,
 305        TVolume queryBounds,
 306        int queryStamp,
 307        bool requireIntersection,
 308        ICollection<TKey> results)
 309    {
 113310        ref SpatialHashEntry entry = ref _entries[entryIndex];
 113311        if (entry.QueryStamp == queryStamp)
 63312            return;
 313
 50314        entry.QueryStamp = queryStamp;
 315
 50316        if (requireIntersection && !entry.Bounds.Intersects(queryBounds))
 1317            return;
 318
 49319        results.Add(entry.Key);
 49320    }
 321
 322    private void AddEntryToCells(int entryIndex, TVolume bounds)
 323    {
 60324        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 325
 280326        for (long x = minCell.X; x <= maxCell.X; x++)
 327        {
 416328            for (long y = minCell.Y; y <= maxCell.Y; y++)
 329            {
 764330                for (long z = minCell.Z; z <= maxCell.Z; z++)
 331                {
 254332                    var cell = new SwiftSpatialHashCellIndex((int)x, (int)y, (int)z);
 254333                    if (!_cells.TryGetValue(cell, out SwiftList<int> entryIndices))
 334                    {
 221335                        entryIndices = new SwiftList<int>(1);
 221336                        _cells[cell] = entryIndices;
 337                    }
 338
 254339                    entryIndices.Add(entryIndex);
 340                }
 341            }
 342        }
 60343    }
 344
 345    private void RemoveEntryFromCells(int entryIndex, TVolume bounds)
 346    {
 5347        _cellMapper.GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 348
 30349        for (long x = minCell.X; x <= maxCell.X; x++)
 350        {
 64351            for (long y = minCell.Y; y <= maxCell.Y; y++)
 352            {
 148353                for (long z = minCell.Z; z <= maxCell.Z; z++)
 354                {
 52355                    var cell = new SwiftSpatialHashCellIndex((int)x, (int)y, (int)z);
 52356                    RemoveEntryFromCell(cell, entryIndex);
 357                }
 358            }
 359        }
 5360    }
 361
 362    private void RemoveEntryFromCell(SwiftSpatialHashCellIndex cell, int entryIndex)
 363    {
 52364        SwiftList<int> entryIndices = _cells[cell];
 52365        RemoveEntryIndex(entryIndices, entryIndex);
 52366        if (entryIndices.Count == 0)
 51367            _cells.Remove(cell);
 52368    }
 369
 370    private static void RemoveEntryIndex(SwiftList<int> entryIndices, int entryIndex)
 371    {
 52372        entryIndices.RemoveAt(entryIndices.IndexOf(entryIndex));
 52373    }
 374
 375    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 376    private int FindEntryIndex(TKey key)
 377    {
 72378        return _keyToEntryIndex.Find(key);
 379    }
 380
 381    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 382    private void ResizeEntryStorage(int newCapacity)
 383    {
 5384        Array.Resize(ref _entries, newCapacity);
 5385        _cells.EnsureCapacity(newCapacity);
 5386        _keyToEntryIndex.ResizeAndRehash(newCapacity, _peakCount);
 5387        SwiftCollectionDiagnostics.Shared.Info($"Resized spatial hash entry storage to {newCapacity} entries.", _diagnos
 5388    }
 389
 390    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 391    private int RentQueryStamp()
 392    {
 15393        if (_queryStamp == int.MaxValue)
 394        {
 10395            for (int i = 0; i < _peakCount; i++)
 3396                _entries[i].QueryStamp = 0;
 397
 2398            _queryStamp = 0;
 2399            SwiftCollectionDiagnostics.Shared.Warn($"Query stamp overflow detected. Spatial hash query stamps were reset
 400        }
 401
 15402        return ++_queryStamp;
 403    }
 404
 405    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 406    private bool MatchesEntryKey(int index, TKey key)
 407    {
 12408        return EqualityComparer<TKey>.Default.Equals(_entries[index].Key, key);
 409    }
 410
 411    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31412    private bool IsAllocatedEntry(int index) => _entries[index].IsAllocated;
 413
 414    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31415    private TKey GetEntryKey(int index) => _entries[index].Key;
 416
 417    private struct SpatialHashEntry
 418    {
 419        public TKey Key;
 420        public TVolume Bounds;
 421        public int QueryStamp;
 422        public bool IsAllocated;
 423
 424        public void Reset()
 425        {
 5426            Key = default!;
 5427            Bounds = default;
 5428            QueryStamp = 0;
 5429            IsAllocated = false;
 5430        }
 431    }
 432}
Generated by: ReportGenerator 5.5.12.0
11/05/2026 - 04:17:34
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()