sparse_set.hpp

Go to the documentation of this file.

#pragma once
 
#include <helios/assert.hpp>
 
#include <algorithm>
#include <concepts>
#include <cstddef>
#include <limits>
#include <memory>
#include <memory_resource>
#include <span>
#include <string_view>
#include <type_traits>
#include <vector>
 
namespace helios::container {
 
/**
 * @brief A sparse set data structure for efficient mapping of sparse indices to
 * dense storage of values.
 * @details SparseSet provides O(1) insertion, deletion, and lookup operations
 * using two arrays:
 * - sparse: maps element indices to dense indices
 * - dense: stores packed values of type T in contiguous memory
 *
 * The data structure is particularly useful for managing sparse collections
 * where indices may have large gaps but you want cache-friendly iteration over
 * existing values.
 *
 * Memory complexity: O(max_index + num_elements)
 * Time complexity: O(1) for all operations (amortized for insertions)
 *
 * @tparam T Type of values stored in the dense array
 * @tparam IndexType Type used for element indices (default: size_t)
 * @tparam Allocator Allocator type for memory management (default:
 * std::allocator<T>)
 */
template <typename T, typename IndexType = size_t,
          typename Allocator = std::allocator<T>>
class SparseSet {
private:
  using DenseIndexType = IndexType;
  using SparseAllocator = typename std::allocator_traits<
      Allocator>::template rebind_alloc<DenseIndexType>;
  using DenseAllocator = Allocator;
  using ReverseMapAllocator = typename std::allocator_traits<
      Allocator>::template rebind_alloc<IndexType>;
 
  using SparseContainerType = std::vector<DenseIndexType, SparseAllocator>;
  using DenseContainerType = std::vector<T, DenseAllocator>;
  using ReverseMapContainerType = std::vector<IndexType, ReverseMapAllocator>;
 
public:
  using value_type = T;
  using index_type = IndexType;
  using dense_index_type = DenseIndexType;
  using size_type = size_t;
  using reference = T&;
  using const_reference = const T&;
  using pointer = T*;
  using const_pointer = const T*;
  using allocator_type = Allocator;
 
  using iterator = typename DenseContainerType::iterator;
  using const_iterator = typename DenseContainerType::const_iterator;
  using reverse_iterator = typename DenseContainerType::reverse_iterator;
  using const_reverse_iterator =
      typename DenseContainerType::const_reverse_iterator;
 
  static constexpr IndexType kInvalidIndex =
      std::numeric_limits<IndexType>::max();
  static constexpr DenseIndexType kInvalidDenseIndex =
      std::numeric_limits<DenseIndexType>::max();
 
  /**
   * @brief Default constructor.
   * @details Creates an empty sparse set.
   * Exception safety: No-throw guarantee if `T` and `Allocator` are nothrow
   * default constructible.
   */
  constexpr SparseSet() noexcept(
      std::is_nothrow_default_constructible_v<Allocator>) = default;
 
  /**
   * @brief Constructor with custom allocator.
   * @details Creates an empty sparse set with the specified allocator.
   * Exception safety: Basic guarantee.
   * @param alloc The allocator to use for memory management
   * @throws May throw if allocator copy constructor throws
   */
  explicit SparseSet(const Allocator& alloc) noexcept(
      noexcept(SparseAllocator(alloc)))
      : sparse_(SparseAllocator(alloc)),
        dense_(alloc),
        reverse_map_(ReverseMapAllocator(alloc)) {}
 
  /**
   * @brief Constructor with PMR memory resource.
   * @details Enabled only when `Allocator` is constructible from
   * `std::pmr::memory_resource*`.
   * @param resource Memory resource used to construct allocator
   */
  explicit SparseSet(std::pmr::memory_resource* resource) noexcept(
      std::is_nothrow_constructible_v<Allocator, std::pmr::memory_resource*>)
    requires std::constructible_from<Allocator, std::pmr::memory_resource*>
      : SparseSet(Allocator{resource}) {}
 
  SparseSet(std::nullptr_t) = delete;
 
  /**
   * @brief Copy constructor.
   * @details Creates a copy of another sparse set.
   * Exception safety: Strong guarantee.
   * @param other The sparse set to copy from
   * @throws May throw if `T` copy constructor or memory allocation fails
   */
  constexpr SparseSet(const SparseSet& other) = default;
  /**
   * @brief Move constructor.
   * @details Transfers ownership of resources from other sparse set.
   * Exception safety: No-throw guarantee.
   */
  constexpr SparseSet(SparseSet&&) noexcept = default;
 
  /**
   * @brief Destructor.
   * @details Destroys the sparse set and releases all memory.
   */
  constexpr ~SparseSet() = default;
 
  /**
   * @brief Copy assignment operator.
   * @details Assigns the contents of another sparse set to this one.
   * Exception safety: Strong guarantee.
   * @param other The sparse set to copy from
   * @return Reference to this sparse set
   * @throws May throw if `T` copy assignment or memory allocation fails
   */
  constexpr SparseSet& operator=(const SparseSet& other) = default;
 
  /**
   * @brief Move assignment operator.
   * @details Transfers ownership of resources from other sparse set.
   * Exception safety: No-throw guarantee.
   * @return Reference to this sparse set
   */
  constexpr SparseSet& operator=(SparseSet&&) noexcept = default;
 
  /**
   * @brief Clears the set, removing all elements.
   * @details Removes all values from the set.
   * The sparse array is reset to invalid indices but its capacity is preserved
   * for performance. Time complexity: O(sparse_capacity). Exception safety:
   * No-throw guarantee.
   */
  constexpr void Clear() noexcept;
 
  /**
   * @brief Inserts a value at the specified index (copy version).
   * @details Adds the specified value to the set at the given index if it's not
   * already present. If the index already exists, the existing value is
   * replaced. The sparse array will be resized if necessary to accommodate the
   * index. Time complexity: O(1) amortized (O(index) worst case if sparse array
   * needs resizing). Exception safety: Strong guarantee.
   * @warning Triggers assertion if index is invalid or negative
   * @param index The index to insert at
   * @param value The value to move insert
   * @return The dense index where the value was stored
   * @throws std::bad_alloc If memory allocation fails during sparse array
   * resize or dense array growth
   */
  constexpr DenseIndexType Insert(IndexType index, const T& value);
 
  /**
   * @brief Inserts a value at the specified index (move version).
   * @details Adds the specified value to the set at the given index if it's not
   * already present. If the index already exists, the existing value is
   * replaced. The sparse array will be resized if necessary to accommodate the
   * index. Time complexity: O(1) amortized (O(index) worst case if sparse array
   * needs resizing). Exception safety: Strong guarantee.
   * @warning Triggers assertion if index is invalid or negative
   * @param index The index to insert at
   * @param value The value to copy insert
   * @return The dense index where the value was stored
   * @throws std::bad_alloc If memory allocation fails during sparse array
   * resize or dense array growth
   */
  constexpr DenseIndexType Insert(IndexType index, T&& value);
 
  /**
   * @brief Constructs a value in-place at the specified index.
   * @details Constructs a value directly in the dense array at the given index.
   * If the index already exists, the existing value is replaced.
   * The sparse array will be resized if necessary to accommodate the index.
   * Time complexity: O(1) amortized (O(index) worst case if sparse array needs
   * resizing). Exception safety: Strong guarantee.
   * @warning Triggers assertion if index is invalid or negative.
   * @param index The index to insert at
   * @param args Arguments to forward to T's constructor
   * @return The dense index where the value was stored
   * @throws std::bad_alloc If memory allocation fails during sparse array
   * resize or dense array growth
   */
  template <typename... Args>
  constexpr DenseIndexType Emplace(IndexType index, Args&&... args);
 
  /**
   * @brief Removes an index from the set.
   * @details Removes the specified index from the set using swap-and-pop
   * technique to maintain dense packing. The last element in the dense array is
   * moved to fill the gap left by the removed element. Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @warning Triggers assertion if index is invalid, negative, or doesn't
   * exist.
   * @param index The index to remove
   */
  constexpr void Remove(IndexType index) noexcept;
 
  /**
   * @brief Reserves space for at least n elements in the dense array.
   * @details Ensures that the dense array can hold at least n elements without
   * triggering a reallocation. Does not affect the sparse array capacity. Time
   * complexity: O(1) if no reallocation, O(Size()) if reallocation occurs.
   * Exception safety: Strong guarantee.
   * @warning Triggers assertion if n is negative.
   * @param n The minimum capacity to reserve
   * @throws std::bad_alloc If memory allocation fails
   */
  constexpr void Reserve(size_type n) { dense_.reserve(n); }
 
  /**
   * @brief Reserves space for indices up to max_index in the sparse array.
   * @details Ensures that the sparse array can accommodate indices up to
   * max_index without triggering a reallocation. Time complexity: O(1) if no
   * reallocation, O(max_index) if reallocation occurs. Exception safety: Strong
   * guarantee.
   * @warning Triggers assertion if max_index is invalid or negative.
   * @param max_index The maximum index to accommodate
   * @throws std::bad_alloc If memory allocation fails
   */
  constexpr void ReserveSparse(IndexType max_index);
 
  /**
   * @brief Shrinks the capacity of both arrays to fit their current size.
   * @details Reduces memory usage by shrinking both the dense and sparse arrays
   * to their minimum required size. Time complexity: O(Size() + SparseSize()).
   * Exception safety: Strong guarantee.
   * @throws std::bad_alloc If memory allocation fails during shrinking
   */
  constexpr void ShrinkToFit();
 
  /**
   * @brief Gets the value at the specified index.
   * @details Returns a reference to the value stored at the given index.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @warning Triggers assertion if index is invalid, negative, or doesn't
   * exist.
   * @param index The index to access
   * @return Reference to the value at the specified index
   */
  [[nodiscard]] constexpr T& Get(IndexType index) noexcept;
 
  /**
   * @brief Gets the value at the specified index (const version).
   * @details Returns a const reference to the value stored at the given index.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @warning Triggers assertion if index is invalid, negative, or doesn't
   * exist.
   * @param index The index to access
   * @return Const reference to the value at the specified index
   */
  [[nodiscard]] constexpr const T& Get(IndexType index) const noexcept;
 
  /**
   * @brief Gets the value at the specified dense index.
   * @details Returns a reference to the value stored at the given dense
   * position. Time complexity: O(1). Exception safety: No-throw guarantee.
   * @warning Triggers assertion if dense_index is invalid, negative, or out of
   * bounds.
   * @param dense_index The dense position to access
   * @return Reference to the value at the specified dense position
   */
  [[nodiscard]] constexpr T& GetByDenseIndex(
      DenseIndexType dense_index) noexcept;
 
  /**
   * @brief Gets the value at the specified dense index (const version).
   * @details Returns a const reference to the value stored at the given dense
   * position. Time complexity: O(1). Exception safety: No-throw guarantee.
   * @warning Triggers assertion if dense_index is invalid, negative, or out of
   * bounds.
   * @param dense_index The dense position to access
   * @return Const reference to the value at the specified dense position
   */
  [[nodiscard]] constexpr const T& GetByDenseIndex(
      DenseIndexType dense_index) const noexcept;
 
  /**
   * @brief Tries to get the value at the specified index.
   * @details Returns a pointer to the value stored at the given index, or
   * nullptr if the index doesn't exist. Time complexity: O(1). Exception
   * safety: No-throw guarantee.
   * @param index The index to access
   * @return Pointer to the value at the specified index, or nullptr if index
   * doesn't exist
   */
  [[nodiscard]] constexpr T* TryGet(IndexType index) noexcept;
 
  /**
   * @brief Tries to get the value at the specified index (const version).
   * @details Returns a pointer to the value stored at the given index, or
   * nullptr if the index doesn't exist. Time complexity: O(1). Exception
   * safety: No-throw guarantee.
   * @param index The index to access
   * @return Pointer to the value at the specified index, or nullptr if index
   * doesn't exist
   */
  [[nodiscard]] constexpr const T* TryGet(IndexType index) const noexcept;
 
  /**
   * @brief Swaps the contents of this sparse set with another.
   * @details Efficiently swaps all data between two sparse sets.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @param other The sparse set to swap with
   */
  constexpr void Swap(SparseSet& other) noexcept;
 
  /**
   * @brief Non-member swap function for `SparseSet`.
   * @details Provides a non-member swap function to enable ADL and
   * compatibility with standard algorithms. Time complexity: O(1). Exception
   * safety: No-throw guarantee.
   * @param lhs First sparse set
   * @param rhs Second sparse set
   */
  friend constexpr void swap(SparseSet& lhs, SparseSet& rhs) noexcept {
    lhs.Swap(rhs);
  }
 
  /**
   * @brief Checks if two sparse sets are equal.
   * @details Two sparse sets are equal if they contain the same index-value
   * pairs. Time complexity: O(`Size()` + `other.Size()`). Exception safety:
   * No-throw guarantee.
   * @param other The sparse set to compare with
   * @return True if both sets contain the same index-value pairs
   */
  [[nodiscard]] bool operator==(const SparseSet& other) const noexcept
    requires std::equality_comparable<T>;
 
  /**
   * @brief Checks if the set is empty.
   * @details Returns true if no values are stored in the set.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @return True if the set contains no elements, false otherwise
   */
  [[nodiscard]] constexpr bool Empty() const noexcept { return dense_.empty(); }
 
  /**
   * @brief Checks if an index value is valid for this sparse set.
   * @details Returns true if the index is not the reserved invalid value.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @param index The index to validate
   * @return True if the index is valid, false if it's the reserved invalid
   * value
   */
  [[nodiscard]] static constexpr bool IsValidIndex(IndexType index) noexcept {
    return index != kInvalidIndex;
  }
 
  /**
   * @brief Checks if an index exists in the set.
   * @details Performs a comprehensive check to ensure the index is valid and
   * exists in the set. Time complexity: O(1). Exception safety: No-throw
   * guarantee.
   * @warning Triggers assertion if index is invalid or negative.
   * @param index The index to check
   * @return True if the index exists in the set, false otherwise
   */
  [[nodiscard]] constexpr bool Contains(IndexType index) const noexcept;
 
  /**
   * @brief Returns the allocator associated with the container.
   * @details Gets the allocator used for the dense array.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @return Copy of the allocator
   */
  [[nodiscard]] constexpr allocator_type GetAllocator() const noexcept {
    return dense_.get_allocator();
  }
 
  /**
   * @brief Gets the dense index for a given index.
   * @details Returns the position of the value in the dense array for the
   * specified index. Time complexity: O(1). Exception safety: No-throw
   * guarantee.
   * @warning Triggers assertion if index is invalid, negative, or doesn't
   * exist.
   * @param index The index to look up
   * @return The dense index
   */
  [[nodiscard]] constexpr DenseIndexType GetDenseIndex(
      IndexType index) const noexcept;
 
  /**
   * @brief Returns the number of values in the set.
   * @details Returns the count of values currently stored in the set.
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @return The number of values in the set
   */
  [[nodiscard]] constexpr size_type Size() const noexcept {
    return dense_.size();
  }
 
  /**
   * @brief Returns the maximum possible size of the set.
   * @details Returns the theoretical maximum number of elements the set can
   * hold. Time complexity: O(1). Exception safety: No-throw guarantee.
   * @return The maximum possible size
   */
  [[nodiscard]] constexpr size_type MaxSize() const noexcept {
    return dense_.max_size();
  }
 
  /**
   * @brief Returns the capacity of the dense array.
   * @details Returns the number of elements that can be stored in the dense
   * array without triggering a reallocation. Time complexity: O(1). Exception
   * safety: No-throw guarantee.
   * @return The capacity of the dense array
   */
  [[nodiscard]] constexpr size_type Capacity() const noexcept {
    return dense_.capacity();
  }
 
  /**
   * @brief Returns the capacity of the sparse array.
   * @details Returns the maximum index that can be stored without triggering a
   * sparse array reallocation. Time complexity: O(1). Exception safety:
   * No-throw guarantee.
   * @return The capacity of the sparse array
   */
  [[nodiscard]] constexpr size_type SparseCapacity() const noexcept {
    return sparse_.capacity();
  }
 
  /**
   * @brief Returns a writable span of the packed values.
   * @details Provides direct access to the densely packed values in the order
   * they were inserted (with removal gaps filled by later insertions).
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @return A span containing all values in the set
   */
  [[nodiscard]] constexpr auto Data() noexcept -> std::span<T> {
    return dense_;
  }
 
  /**
   * @brief Returns a read-only span of the packed values.
   * @details Provides direct access to the densely packed values in the order
   * they were inserted (with removal gaps filled by later insertions).
   * Time complexity: O(1).
   * Exception safety: No-throw guarantee.
   * @return A span containing all values in the set
   */
  [[nodiscard]] constexpr auto Data() const noexcept -> std::span<const T> {
    return dense_;
  }
 
  [[nodiscard]] constexpr iterator begin() noexcept { return dense_.begin(); }
  [[nodiscard]] constexpr const_iterator begin() const noexcept {
    return dense_.begin();
  }
  [[nodiscard]] constexpr const_iterator cbegin() const noexcept {
    return dense_.cbegin();
  }
 
  [[nodiscard]] constexpr iterator end() noexcept { return dense_.end(); }
  [[nodiscard]] constexpr const_iterator end() const noexcept {
    return dense_.end();
  }
  [[nodiscard]] constexpr const_iterator cend() const noexcept {
    return dense_.cend();
  }
 
  [[nodiscard]] constexpr reverse_iterator rbegin() noexcept {
    return dense_.rbegin();
  }
  [[nodiscard]] constexpr const_reverse_iterator rbegin() const noexcept {
    return dense_.rbegin();
  }
  [[nodiscard]] constexpr const_reverse_iterator crbegin() const noexcept {
    return dense_.crbegin();
  }
 
  [[nodiscard]] constexpr reverse_iterator rend() noexcept {
    return dense_.rend();
  }
  [[nodiscard]] constexpr const_reverse_iterator rend() const noexcept {
    return dense_.rend();
  }
  [[nodiscard]] constexpr const_reverse_iterator crend() const noexcept {
    return dense_.crend();
  }
 
private:
  SparseContainerType sparse_;           ///< Maps index -> dense index
  DenseContainerType dense_;             ///< Packed values in insertion order
  ReverseMapContainerType reverse_map_;  ///< Maps dense index -> original index
                                         ///< for efficient removal
};
 
template <typename T, typename IndexType, typename Allocator>
constexpr void SparseSet<T, IndexType, Allocator>::Clear() noexcept {
  dense_.clear();
  reverse_map_.clear();
  std::ranges::fill(sparse_, kInvalidDenseIndex);
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr auto SparseSet<T, IndexType, Allocator>::Insert(IndexType index,
                                                          const T& value)
    -> DenseIndexType {
  HELIOS_ASSERT(IsValidIndex(index),
                "Failed to insert value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to insert value: index cannot be negative!");
  }
 
  // Check if index already exists and replace the value
  if (Contains(index)) {
    const DenseIndexType dense_index = sparse_[index];
    dense_[dense_index] = value;
    return dense_index;
  }
 
  // Ensure sparse array can accommodate this index
  if (index >= sparse_.size()) {
    sparse_.resize(index + 1, kInvalidDenseIndex);
  }
 
  const auto dense_index = static_cast<DenseIndexType>(dense_.size());
  dense_.push_back(value);
  reverse_map_.push_back(index);
  sparse_[index] = dense_index;
 
  return dense_index;
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr auto SparseSet<T, IndexType, Allocator>::Insert(IndexType index,
                                                          T&& value)
    -> DenseIndexType {
  HELIOS_ASSERT(IsValidIndex(index),
                "Failed to insert value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to insert value: index cannot be negative!");
  }
 
  // Check if index already exists and replace the value
  if (Contains(index)) {
    const DenseIndexType dense_index = sparse_[index];
    dense_[dense_index] = std::move(value);
    return dense_index;
  }
 
  // Ensure sparse array is large enough
  if (static_cast<size_type>(index) >= sparse_.size()) {
    sparse_.resize(static_cast<size_type>(index) + 1, kInvalidDenseIndex);
  }
 
  const auto dense_index = static_cast<DenseIndexType>(dense_.size());
  sparse_[index] = dense_index;
  dense_.push_back(std::move(value));
  reverse_map_.push_back(index);
 
  return dense_index;
}
 
template <typename T, typename IndexType, typename Allocator>
template <typename... Args>
constexpr auto SparseSet<T, IndexType, Allocator>::Emplace(IndexType index,
                                                           Args&&... args)
    -> DenseIndexType {
  HELIOS_ASSERT(IsValidIndex(index),
                "Failed to emplace value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to emplace value: index cannot be negative!");
  }
 
  // Check if index already exists and replace the value
  if (Contains(index)) {
    const DenseIndexType dense_index = sparse_[index];
    dense_[dense_index] = T(std::forward<Args>(args)...);
    return dense_index;
  }
 
  // Ensure sparse array is large enough
  if (static_cast<size_type>(index) >= sparse_.size()) {
    sparse_.resize(static_cast<size_type>(index) + 1, kInvalidDenseIndex);
  }
 
  const auto dense_index = static_cast<DenseIndexType>(dense_.size());
  sparse_[index] = dense_index;
  dense_.emplace_back(std::forward<Args>(args)...);
  reverse_map_.push_back(index);
 
  return dense_index;
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr void SparseSet<T, IndexType, Allocator>::Remove(
    IndexType index) noexcept {
  HELIOS_ASSERT(IsValidIndex(index),
                "Failed to remove value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to remove value: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index),
                "Failed to remove value: index does not exist!");
 
  const DenseIndexType dense_index = sparse_[index];
  const auto last_dense_index = static_cast<DenseIndexType>(dense_.size() - 1);
 
  if (dense_index != last_dense_index) {
    // Swap with last element to maintain dense packing
    const IndexType last_index = reverse_map_[last_dense_index];
    dense_[dense_index] = std::move(dense_[last_dense_index]);
    reverse_map_[dense_index] = last_index;
    sparse_[last_index] = dense_index;
  }
 
  dense_.pop_back();
  reverse_map_.pop_back();
  sparse_[index] = kInvalidDenseIndex;
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr void SparseSet<T, IndexType, Allocator>::ReserveSparse(
    IndexType max_index) {
  HELIOS_ASSERT(IsValidIndex(max_index),
                "Failed to reserve sparse: max_index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(max_index >= 0,
                  "Failed to reserve sparse: max_index cannot be negative!");
  }
  if (static_cast<size_type>(max_index) + 1 > sparse_.size()) {
    sparse_.resize(static_cast<size_type>(max_index) + 1, kInvalidDenseIndex);
  }
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr void SparseSet<T, IndexType, Allocator>::ShrinkToFit() {
  dense_.shrink_to_fit();
  reverse_map_.shrink_to_fit();
 
  // Find the maximum index in use to determine minimum sparse size needed
  if (reverse_map_.empty()) {
    sparse_.clear();
  } else {
    const IndexType max_index = *std::ranges::max_element(reverse_map_);
    sparse_.resize(static_cast<size_type>(max_index) + 1);
  }
  sparse_.shrink_to_fit();
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr T& SparseSet<T, IndexType, Allocator>::Get(IndexType index) noexcept {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to get value: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index), "Failed to get value: index does not exist!");
  return dense_[sparse_[index]];
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr const T& SparseSet<T, IndexType, Allocator>::Get(
    IndexType index) const noexcept {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to get value: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index), "Failed to get value: index does not exist!");
  return dense_[sparse_[index]];
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr T& SparseSet<T, IndexType, Allocator>::GetByDenseIndex(
    DenseIndexType dense_index) noexcept {
  HELIOS_ASSERT(dense_index != kInvalidDenseIndex,
                "Failed to get value: dense_index is invalid!");
  if constexpr (std::is_signed_v<DenseIndexType>) {
    HELIOS_ASSERT(dense_index >= 0,
                  "Failed to get value: dense_index cannot be negative!");
  }
  HELIOS_ASSERT(dense_index < dense_.size(),
                "Failed to get value: dense_index is out of bounds!");
  return dense_[dense_index];
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr const T& SparseSet<T, IndexType, Allocator>::GetByDenseIndex(
    DenseIndexType dense_index) const noexcept {
  HELIOS_ASSERT(dense_index != kInvalidDenseIndex,
                "Failed to get value: dense_index is invalid!");
  if constexpr (std::is_signed_v<DenseIndexType>) {
    HELIOS_ASSERT(dense_index >= 0,
                  "Failed to get value: dense_index cannot be negative!");
  }
  HELIOS_ASSERT(dense_index < dense_.size(),
                "Failed to get value: dense_index is out of bounds!");
  return dense_[dense_index];
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr T* SparseSet<T, IndexType, Allocator>::TryGet(
    IndexType index) noexcept {
  HELIOS_ASSERT(index != kInvalidIndex,
                "Failed to try get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to try get value: index cannot be negative!");
  }
 
  if (!Contains(index)) {
    return nullptr;
  }
  return &dense_[sparse_[index]];
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr const T* SparseSet<T, IndexType, Allocator>::TryGet(
    IndexType index) const noexcept {
  HELIOS_ASSERT(index != kInvalidIndex,
                "Failed to get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to try get value: index cannot be negative!");
  }
 
  if (!Contains(index)) {
    return nullptr;
  }
  return &dense_[sparse_[index]];
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr void SparseSet<T, IndexType, Allocator>::Swap(
    SparseSet& other) noexcept {
  std::swap(sparse_, other.sparse_);
  std::swap(dense_, other.dense_);
  std::swap(reverse_map_, other.reverse_map_);
}
 
template <typename T, typename IndexType, typename Allocator>
inline bool SparseSet<T, IndexType, Allocator>::operator==(
    const SparseSet& other) const noexcept
  requires std::equality_comparable<T>
{
  if (Size() != other.Size()) {
    return false;
  }
 
  for (size_type i = 0; i < dense_.size(); ++i) {
    const IndexType index = reverse_map_[i];
    if (!other.Contains(index) || dense_[i] != other.Get(index)) {
      return false;
    }
  }
 
  return true;
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr bool SparseSet<T, IndexType, Allocator>::Contains(
    IndexType index) const noexcept {
  HELIOS_ASSERT(IsValidIndex(index),
                "Failed to check if set contains index: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(
        index >= 0,
        "Failed to check if set contains index: index cannot be negative!");
  }
  return static_cast<size_type>(index) < sparse_.size() &&
         sparse_[index] != kInvalidDenseIndex &&
         static_cast<size_type>(sparse_[index]) < dense_.size() &&
         static_cast<size_type>(sparse_[index]) < reverse_map_.size() &&
         reverse_map_[sparse_[index]] == index;
}
 
template <typename T, typename IndexType, typename Allocator>
constexpr auto SparseSet<T, IndexType, Allocator>::GetDenseIndex(
    IndexType index) const noexcept -> DenseIndexType {
  HELIOS_ASSERT(IsValidIndex(index),
                "Failed to get dense index: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0,
                  "Failed to get dense index: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index),
                "Failed to get dense index: index does not exist!");
  return sparse_[index];
}
 
template <typename T, typename IndexType = size_t>
using PmrSparseSet =
    SparseSet<T, IndexType, std::pmr::polymorphic_allocator<T>>;
 
}  // namespace helios::container