EnTT  3.7.0
sparse_set.hpp
1 #ifndef ENTT_ENTITY_SPARSE_SET_HPP
2 #define ENTT_ENTITY_SPARSE_SET_HPP
3 
4 
5 #include <iterator>
6 #include <utility>
7 #include <vector>
8 #include <memory>
9 #include <cstddef>
10 #include <type_traits>
11 #include "../config/config.h"
12 #include "../core/algorithm.hpp"
13 #include "entity.hpp"
14 #include "fwd.hpp"
15 
16 
17 namespace entt {
18 
19 
42 template<typename Entity>
44  static constexpr auto page_size = ENTT_PAGE_SIZE;
45 
47  using page_type = std::unique_ptr<Entity[]>;
48 
49  class sparse_set_iterator final {
50  friend class basic_sparse_set<Entity>;
51 
52  using packed_type = std::vector<Entity>;
53  using index_type = typename traits_type::difference_type;
54 
55  sparse_set_iterator(const packed_type &ref, const index_type idx) ENTT_NOEXCEPT
56  : packed{&ref}, index{idx}
57  {}
58 
59  public:
60  using difference_type = index_type;
61  using value_type = Entity;
62  using pointer = const value_type *;
63  using reference = const value_type &;
64  using iterator_category = std::random_access_iterator_tag;
65 
66  sparse_set_iterator() ENTT_NOEXCEPT = default;
67 
68  sparse_set_iterator & operator++() ENTT_NOEXCEPT {
69  return --index, *this;
70  }
71 
72  sparse_set_iterator operator++(int) ENTT_NOEXCEPT {
73  iterator orig = *this;
74  return ++(*this), orig;
75  }
76 
77  sparse_set_iterator & operator--() ENTT_NOEXCEPT {
78  return ++index, *this;
79  }
80 
81  sparse_set_iterator operator--(int) ENTT_NOEXCEPT {
82  sparse_set_iterator orig = *this;
83  return operator--(), orig;
84  }
85 
86  sparse_set_iterator & operator+=(const difference_type value) ENTT_NOEXCEPT {
87  index -= value;
88  return *this;
89  }
90 
91  sparse_set_iterator operator+(const difference_type value) const ENTT_NOEXCEPT {
92  sparse_set_iterator copy = *this;
93  return (copy += value);
94  }
95 
96  sparse_set_iterator & operator-=(const difference_type value) ENTT_NOEXCEPT {
97  return (*this += -value);
98  }
99 
100  sparse_set_iterator operator-(const difference_type value) const ENTT_NOEXCEPT {
101  return (*this + -value);
102  }
103 
104  difference_type operator-(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
105  return other.index - index;
106  }
107 
108  [[nodiscard]] reference operator[](const difference_type value) const {
109  const auto pos = size_type(index-value-1u);
110  return (*packed)[pos];
111  }
112 
113  [[nodiscard]] bool operator==(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
114  return other.index == index;
115  }
116 
117  [[nodiscard]] bool operator!=(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
118  return !(*this == other);
119  }
120 
121  [[nodiscard]] bool operator<(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
122  return index > other.index;
123  }
124 
125  [[nodiscard]] bool operator>(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
126  return index < other.index;
127  }
128 
129  [[nodiscard]] bool operator<=(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
130  return !(*this > other);
131  }
132 
133  [[nodiscard]] bool operator>=(const sparse_set_iterator &other) const ENTT_NOEXCEPT {
134  return !(*this < other);
135  }
136 
137  [[nodiscard]] pointer operator->() const {
138  const auto pos = size_type(index-1u);
139  return &(*packed)[pos];
140  }
141 
142  [[nodiscard]] reference operator*() const {
143  return *operator->();
144  }
145 
146  private:
147  const packed_type *packed;
148  index_type index;
149  };
150 
151  [[nodiscard]] auto page(const Entity entt) const ENTT_NOEXCEPT {
152  return size_type{(to_integral(entt) & traits_type::entity_mask) / page_size};
153  }
154 
155  [[nodiscard]] auto offset(const Entity entt) const ENTT_NOEXCEPT {
156  return size_type{to_integral(entt) & (page_size - 1)};
157  }
158 
159  [[nodiscard]] page_type & assure(const std::size_t pos) {
160  if(!(pos < sparse.size())) {
161  sparse.resize(pos+1);
162  }
163 
164  if(!sparse[pos]) {
165  sparse[pos].reset(new entity_type[page_size]);
166  // null is safe in all cases for our purposes
167  for(auto *first = sparse[pos].get(), *last = first + page_size; first != last; ++first) {
168  *first = null;
169  }
170  }
171 
172  return sparse[pos];
173  }
174 
175 protected:
177  virtual void swap_at(const std::size_t, const std::size_t) {}
178 
180  virtual void swap_and_pop(const std::size_t, void *) {}
181 
182 public:
184  using entity_type = Entity;
186  using size_type = std::size_t;
188  using iterator = sparse_set_iterator;
190  using reverse_iterator = const entity_type *;
191 
193  basic_sparse_set() = default;
194 
197 
199  virtual ~basic_sparse_set() = default;
200 
203 
212  void reserve(const size_type cap) {
213  packed.reserve(cap);
214  }
215 
221  [[nodiscard]] size_type capacity() const ENTT_NOEXCEPT {
222  return packed.capacity();
223  }
224 
226  void shrink_to_fit() {
227  // conservative approach
228  if(packed.empty()) {
229  sparse.clear();
230  }
231 
232  sparse.shrink_to_fit();
233  packed.shrink_to_fit();
234  }
235 
246  [[nodiscard]] size_type extent() const ENTT_NOEXCEPT {
247  return sparse.size() * page_size;
248  }
249 
260  [[nodiscard]] size_type size() const ENTT_NOEXCEPT {
261  return packed.size();
262  }
263 
268  [[nodiscard]] bool empty() const ENTT_NOEXCEPT {
269  return packed.empty();
270  }
271 
284  [[nodiscard]] const entity_type * data() const ENTT_NOEXCEPT {
285  return packed.data();
286  }
287 
297  [[nodiscard]] iterator begin() const ENTT_NOEXCEPT {
298  const typename traits_type::difference_type pos = packed.size();
299  return iterator{packed, pos};
300  }
301 
312  [[nodiscard]] iterator end() const ENTT_NOEXCEPT {
313  return iterator{packed, {}};
314  }
315 
326  [[nodiscard]] reverse_iterator rbegin() const ENTT_NOEXCEPT {
327  return packed.data();
328  }
329 
340  [[nodiscard]] reverse_iterator rend() const ENTT_NOEXCEPT {
341  return rbegin() + packed.size();
342  }
343 
350  [[nodiscard]] iterator find(const entity_type entt) const {
351  return contains(entt) ? --(end() - index(entt)) : end();
352  }
353 
359  [[nodiscard]] bool contains(const entity_type entt) const {
360  const auto curr = page(entt);
361  // testing against null permits to avoid accessing the packed array
362  return (curr < sparse.size() && sparse[curr] && sparse[curr][offset(entt)] != null);
363  }
364 
375  [[nodiscard]] size_type index(const entity_type entt) const {
376  ENTT_ASSERT(contains(entt));
377  return size_type{to_integral(sparse[page(entt)][offset(entt)])};
378  }
379 
385  [[nodiscard]] entity_type at(const size_type pos) const {
386  return pos < packed.size() ? packed[pos] : null;
387  }
388 
394  [[nodiscard]] entity_type operator[](const size_type pos) const {
395  ENTT_ASSERT(pos < packed.size());
396  return packed[pos];
397  }
398 
408  void emplace(const entity_type entt) {
409  ENTT_ASSERT(!contains(entt));
410  assure(page(entt))[offset(entt)] = entity_type{static_cast<typename traits_type::entity_type>(packed.size())};
411  packed.push_back(entt);
412  }
413 
425  template<typename It>
426  void insert(It first, It last) {
427  auto next = static_cast<typename traits_type::entity_type>(packed.size());
428  packed.insert(packed.end(), first, last);
429 
430  for(; first != last; ++first) {
431  ENTT_ASSERT(!contains(*first));
432  assure(page(*first))[offset(*first)] = entity_type{next++};
433  }
434  }
435 
446  void remove(const entity_type entt, void *ud = nullptr) {
447  ENTT_ASSERT(contains(entt));
448  auto &ref = sparse[page(entt)][offset(entt)];
449 
450  // last chance to use the entity for derived classes and mixins, if any
452 
453  const auto other = packed.back();
454  sparse[page(other)][offset(other)] = ref;
455  // if it looks weird, imagine what the subtle bugs it prevents are
456  ENTT_ASSERT((packed.back() = entt, true));
457  packed[size_type{to_integral(ref)}] = other;
458  ref = null;
459 
460  packed.pop_back();
461  }
462 
470  template<typename It>
471  void remove(It first, It last, void *ud = nullptr) {
472  for(; first != last; ++first) {
473  remove(*first, ud);
474  }
475  }
476 
490  void swap(const entity_type lhs, const entity_type rhs) {
491  const auto from = index(lhs);
492  const auto to = index(rhs);
493  std::swap(sparse[page(lhs)][offset(lhs)], sparse[page(rhs)][offset(rhs)]);
494  std::swap(packed[from], packed[to]);
495  swap_at(from, to);
496  }
497 
528  template<typename Compare, typename Sort = std_sort, typename... Args>
529  void sort_n(const size_type count, Compare compare, Sort algo = Sort{}, Args &&... args) {
530  ENTT_ASSERT(!(count > size()));
531 
532  algo(packed.rend() - count, packed.rend(), std::move(compare), std::forward<Args>(args)...);
533 
534  for(size_type pos{}; pos < count; ++pos) {
535  auto curr = pos;
536  auto next = index(packed[curr]);
537 
538  while(curr != next) {
539  const auto idx = index(packed[next]);
540  const auto entt = packed[curr];
541 
542  swap_at(next, idx);
543  sparse[page(entt)][offset(entt)] = entity_type{static_cast<typename traits_type::entity_type>(curr)};
544 
545  curr = next;
546  next = idx;
547  }
548  }
549  }
550 
563  template<typename Compare, typename Sort = std_sort, typename... Args>
564  void sort(Compare compare, Sort algo = Sort{}, Args &&... args) {
565  sort_n(size(), std::move(compare), std::move(algo), std::forward<Args>(args)...);
566  }
567 
583  void respect(const basic_sparse_set &other) {
584  const auto to = other.end();
585  auto from = other.begin();
586 
587  size_type pos = packed.size() - 1;
588 
589  while(pos && from != to) {
590  if(contains(*from)) {
591  if(*from != packed[pos]) {
592  swap(packed[pos], *from);
593  }
594 
595  --pos;
596  }
597 
598  ++from;
599  }
600  }
601 
606  void clear(void *ud = nullptr) ENTT_NOEXCEPT {
607  remove(begin(), end(), ud);
608  }
609 
610 private:
611  std::vector<page_type> sparse;
612  std::vector<entity_type> packed;
613 };
614 
615 
616 }
617 
618 
619 #endif
entt::basic_sparse_set::entity_type
Entity entity_type
Underlying entity identifier.
Definition: sparse_set.hpp:184
entt::operator==
constexpr bool operator==(const Entity &entity, const null_t &other) noexcept
Compares a null object and an entity identifier of any type.
Definition: entity.hpp:158
entt::basic_sparse_set::end
iterator end() const noexcept
Returns an iterator to the end.
Definition: sparse_set.hpp:312
entt::basic_sparse_set::basic_sparse_set
basic_sparse_set(basic_sparse_set &&)=default
Default move constructor.
entt::basic_sparse_set::~basic_sparse_set
virtual ~basic_sparse_set()=default
Default destructor.
entt::basic_sparse_set::sort_n
void sort_n(const size_type count, Compare compare, Sort algo=Sort{}, Args &&... args)
Sort the first count elements according to the given comparison function.
Definition: sparse_set.hpp:529
entt::to_integral
constexpr auto to_integral(const Entity entity) noexcept
Converts an entity type to its underlying type.
Definition: entity.hpp:93
entt::basic_sparse_set::reserve
void reserve(const size_type cap)
Increases the capacity of a sparse set.
Definition: sparse_set.hpp:212
entt::get
constexpr get_t< Type... > get
Variable template for lists of observed components.
Definition: utility.hpp:40
entt::operator+
constexpr type_list< Type..., Other... > operator+(type_list< Type... >, type_list< Other... >)
Concatenates multiple type lists.
Definition: type_traits.hpp:180
entt::basic_sparse_set::respect
void respect(const basic_sparse_set &other)
Sort entities according to their order in another sparse set.
Definition: sparse_set.hpp:583
entt::basic_sparse_set::remove
void remove(const entity_type entt, void *ud=nullptr)
Removes an entity from a sparse set.
Definition: sparse_set.hpp:446
entt::basic_sparse_set::operator[]
entity_type operator[](const size_type pos) const
Returns the entity at specified location, without bounds checking.
Definition: sparse_set.hpp:394
entt::basic_sparse_set::rend
reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
Definition: sparse_set.hpp:340
entt::basic_sparse_set::size
size_type size() const noexcept
Returns the number of elements in a sparse set.
Definition: sparse_set.hpp:260
entt::basic_sparse_set::clear
void clear(void *ud=nullptr) noexcept
Clears a sparse set.
Definition: sparse_set.hpp:606
entt::basic_sparse_set::extent
size_type extent() const noexcept
Returns the extent of a sparse set.
Definition: sparse_set.hpp:246
entt::basic_sparse_set::swap
void swap(const entity_type lhs, const entity_type rhs)
Swaps two entities in the internal packed array.
Definition: sparse_set.hpp:490
entt::basic_sparse_set::capacity
size_type capacity() const noexcept
Returns the number of elements that a sparse set has currently allocated space for.
Definition: sparse_set.hpp:221
entt::basic_sparse_set::swap_and_pop
virtual void swap_and_pop(const std::size_t, void *)
Attempts to remove an entity from the internal packed array.
Definition: sparse_set.hpp:180
entt::basic_sparse_set::iterator
sparse_set_iterator iterator
Random access iterator type.
Definition: sparse_set.hpp:188
entt::basic_sparse_set::shrink_to_fit
void shrink_to_fit()
Requests the removal of unused capacity.
Definition: sparse_set.hpp:226
entt
EnTT default namespace.
Definition: algorithm.hpp:13
entt::basic_sparse_set::rbegin
reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
Definition: sparse_set.hpp:326
entt::basic_sparse_set
Basic sparse set implementation.
Definition: sparse_set.hpp:43
entt::basic_sparse_set::begin
iterator begin() const noexcept
Returns an iterator to the beginning.
Definition: sparse_set.hpp:297
entt::basic_sparse_set::find
iterator find(const entity_type entt) const
Finds an entity.
Definition: sparse_set.hpp:350
entt::basic_sparse_set::at
entity_type at(const size_type pos) const
Returns the entity at specified location, with bounds checking.
Definition: sparse_set.hpp:385
entt::basic_sparse_set::size_type
std::size_t size_type
Unsigned integer type.
Definition: sparse_set.hpp:186
entt::basic_sparse_set::emplace
void emplace(const entity_type entt)
Assigns an entity to a sparse set.
Definition: sparse_set.hpp:408
entt::basic_sparse_set::empty
bool empty() const noexcept
Checks whether a sparse set is empty.
Definition: sparse_set.hpp:268
entt::basic_sparse_set::data
const entity_type * data() const noexcept
Direct access to the internal packed array.
Definition: sparse_set.hpp:284
entt::basic_sparse_set::insert
void insert(It first, It last)
Assigns one or more entities to a sparse set.
Definition: sparse_set.hpp:426
entt::basic_sparse_set::sort
void sort(Compare compare, Sort algo=Sort{}, Args &&... args)
Sort all elements according to the given comparison function.
Definition: sparse_set.hpp:564
entt::basic_sparse_set::basic_sparse_set
basic_sparse_set()=default
Default constructor.
entt::operator!=
bool operator!=(const basic_any< Len, Align > &lhs, const basic_any< Len, Align > &rhs) noexcept
Checks if two wrappers differ in their content.
Definition: any.hpp:348
entt::basic_sparse_set::index
size_type index(const entity_type entt) const
Returns the position of an entity in a sparse set.
Definition: sparse_set.hpp:375
entt::entt_traits
Entity traits.
Definition: entity.hpp:21
entt::basic_sparse_set::contains
bool contains(const entity_type entt) const
Checks if a sparse set contains an entity.
Definition: sparse_set.hpp:359
entt::basic_sparse_set::remove
void remove(It first, It last, void *ud=nullptr)
Removes multiple entities from a pool.
Definition: sparse_set.hpp:471
entt::basic_sparse_set< entity_type >::reverse_iterator
const entity_type * reverse_iterator
Reverse iterator type.
Definition: sparse_set.hpp:190
entt::basic_sparse_set::operator=
basic_sparse_set & operator=(basic_sparse_set &&)=default
Default move assignment operator.
entt::std_sort
Function object to wrap std::sort in a class type.
Definition: algorithm.hpp:24
entt::basic_sparse_set::swap_at
virtual void swap_at(const std::size_t, const std::size_t)
Swaps two entities in the internal packed array.
Definition: sparse_set.hpp:177