sparse_set.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: MIT
#ifndef LIBSBX_SPARSE_SET_HPP_
#define LIBSBX_SPARSE_SET_HPP_
 
#include <memory>
#include <vector>
#include <unordered_map>
#include <type_traits>
#include <utility>
#include <iterator>
#include <algorithm>
#include <functional>
 
#include <libsbx/utility/assert.hpp>
#include <libsbx/utility/fast_mod.hpp>
#include <libsbx/utility/algorithm.hpp>
#include <libsbx/utility/hashed_string.hpp>
 
#include <libsbx/memory/concepts.hpp>
 
#include <libsbx/ecs/detail/sparse_set_iterator.hpp>
 
namespace sbx::ecs {
 
enum class deletion_policy : std::uint8_t {
  swap_and_pop = 0u,
  in_place = 1u,
  swap_only = 2u,
  unspecified = swap_and_pop
}; // enum class deletion_policy
 
template<typename Entity, memory::allocator_for<Entity> Allocator = std::allocator<Entity>>
class basic_sparse_set {
 
  using allocator_traits = std::allocator_traits<Allocator>;
  using entity_traits = ecs::entity_traits<Entity>;
 
  using dense_storage_type = std::vector<Entity, Allocator>;
  using sparse_storage_type = std::vector<typename allocator_traits::pointer, typename allocator_traits::rebind_alloc<typename allocator_traits::pointer>>;
 
  inline static constexpr auto max_size = static_cast<std::size_t>(entity_traits::to_entity(null_entity));
 
public:
 
  using allocator_type = Allocator;
  using entity_type = entity_traits::value_type;
  using version_type = entity_traits::version_type;
  using pointer = typename dense_storage_type::pointer;
  using const_pointer = typename dense_storage_type::const_pointer;
  using reference = typename dense_storage_type::reference;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using iterator = detail::sparse_set_iterator<dense_storage_type>;
  using const_iterator = iterator;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
  basic_sparse_set(const deletion_policy policy = deletion_policy::unspecified, const allocator_type& allocator = allocator_type{});
 
  basic_sparse_set(const basic_sparse_set& other) = delete;
 
  basic_sparse_set(basic_sparse_set&& other) noexcept;
 
  basic_sparse_set(basic_sparse_set&& other, const allocator_type& allocator);
 
  virtual ~basic_sparse_set();
 
  auto operator=(const basic_sparse_set& other) -> basic_sparse_set& = delete;
 
  auto operator=(basic_sparse_set&& other) noexcept -> basic_sparse_set&;
 
  auto swap(basic_sparse_set& other) noexcept -> void;
 
  [[nodiscard]] constexpr auto get_allocator() const noexcept -> allocator_type;
 
  [[nodiscard]] auto policy() const noexcept -> deletion_policy;
 
  [[nodiscard]] auto free_list() const noexcept -> size_type;
 
  virtual void reserve(const size_type capacity);
 
  [[nodiscard]] virtual auto capacity() const noexcept -> size_type;
 
  [[nodiscard]] auto extent() const noexcept -> size_type;
 
  [[nodiscard]] auto size() const noexcept -> size_type;
 
  [[nodiscard]] auto is_empty() const noexcept -> bool;
 
  [[nodiscard]] auto is_contiguous() const noexcept -> bool;
 
  [[nodiscard]] auto data() const noexcept -> const_pointer;
 
  [[nodiscard]] auto data() noexcept -> pointer;
 
  auto bump(const entity_type entity) -> version_type;
 
  [[nodiscard]] auto begin() const noexcept -> iterator;
 
  [[nodiscard]] auto cbegin() const noexcept -> const_iterator;
 
  [[nodiscard]] auto end() const noexcept -> iterator;
 
  [[nodiscard]] auto cend() const noexcept -> const_iterator;
 
  [[nodiscard]] bool contains(const entity_type entity) const noexcept;
 
  [[nodiscard]] auto current(const entity_type entity) const noexcept -> version_type;
 
  [[nodiscard]] auto find(const entity_type entity) const noexcept -> const_iterator;
 
  [[nodiscard]] auto index(const entity_type entity) const noexcept -> size_type;
 
  auto erase(const entity_type entity) -> void;
 
  auto remove(const entity_type entity) -> bool;
 
  template<typename Compare, typename Sort = utility::std_sort, typename... Args>
  auto sort(Compare compare, Sort sort = Sort{}, Args&&... args) -> void;
 
  template<typename Compare, typename Sort = utility::std_sort, typename... Args>
  auto sort_n(const size_type length, Compare compare, Sort sort = Sort{}, Args&&... args) -> void;
 
  auto clear() -> void;
 
  auto invoke(const utility::hashed_string& tag, const entity_type entity) -> void;
 
protected:
 
  using basic_iterator = iterator;
 
  virtual auto call(const utility::hashed_string& tag, const entity_type entity) -> void;
 
  void swap_only(const basic_iterator iterator);
 
  auto swap_and_pop(const basic_iterator iterator) -> void;
 
  auto in_place_pop(const basic_iterator iterator) -> void;
 
  virtual auto pop(basic_iterator first, basic_iterator last) -> void;
 
  virtual auto pop_all() -> void;
 
  virtual auto try_emplace(const entity_type entity, const bool force_back) -> basic_iterator;
 
private:
 
  [[nodiscard]] virtual auto get_at(const std::size_t) const -> const void*;
 
  virtual auto _swap_or_move(const std::size_t from, const std::size_t to) -> void;
 
  [[nodiscard]] auto _policy_to_head() const noexcept -> size_type;
 
  [[nodiscard]] auto _entity_to_position(const entity_type entity) const noexcept;
 
  [[nodiscard]] auto _position_to_page(const size_type position) const noexcept;
 
  [[nodiscard]] auto _sparse_pointer(const entity_type entity) const -> pointer;
 
  [[nodiscard]] auto _sparse_reference(const entity_type entity) const -> reference;
 
  void _release_sparse_pages();
 
  [[nodiscard]] auto _to_iterator(const entity_type entity) const noexcept -> iterator;
 
  [[nodiscard]] auto _assure_at_least(const entity_type entity) -> reference;
 
  auto _swap_at(const size_type lhs, const size_type rhs) -> void;
 
  dense_storage_type _dense;
  sparse_storage_type _sparse;
  deletion_policy _policy;
  size_type _head;
 
}; // class basic_sparse_set
 
} // namespace sbx::ecs
 
#include <libsbx/ecs/sparse_set.ipp>
 
#endif // LIBSBX_SPARSE_SET_HPP_