component.hxx 21.8 KB
Newer Older
1
2
#pragma once

3
#include <concurrentqueue.h>
4

Florian Oetke's avatar
Florian Oetke committed
5
#ifndef MIRRAGE_ECS_COMPONENT_INCLUDED
6
7
8
#include "component.hpp"
#endif

9
namespace mirrage::ecs {
10
11

	class Sparse_index_policy {
Florian Oetke's avatar
Florian Oetke committed
12
13
		using Table = tsl::robin_map<Entity_id, Component_index>;

14
15
16
17
18
19
20
	  public:
		void attach(Entity_id, Component_index);
		void detach(Entity_id);
		void shrink_to_fit();
		auto find(Entity_id) const -> util::maybe<Component_index>;
		void clear();

Florian Oetke's avatar
Florian Oetke committed
21
22
23
24
25
26
27
28
29
		auto begin() const { return _table.begin(); }
		auto end() const { return _table.end(); }

		static constexpr bool sorted_iteration_supported = false;

		using iterator = Table::const_iterator;
		// sorted_begin()
		// sorted_end()

30
	  private:
Florian Oetke's avatar
Florian Oetke committed
31
		Table _table;
32
	};
Florian Oetke's avatar
Florian Oetke committed
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

	namespace detail {
		class Compact_index_policy_iterator {
		  public:
			using Value_iterator = std::vector<Component_index>::const_iterator;

			using iterator_category = std::input_iterator_tag;
			using value_type        = std::tuple<Entity_id, Component_index>;
			using difference_type   = std::int_fast32_t;
			using reference         = value_type;
			using pointer           = value_type*;

			Compact_index_policy_iterator() = default;
			Compact_index_policy_iterator(difference_type index, Value_iterator value)
			  : _index(index), _value(value)
			{
			}

			value_type  operator*() noexcept { return *get(); }
			value_type* operator->() noexcept { return get(); }
			value_type* get() noexcept
			{
				_last_value = std::tie(_index, *_value);
				return &_last_value;
			}

			auto operator+=(difference_type n) -> auto&
			{
				_index += n;
				_value += n;
				return *this;
			}
			auto operator-=(difference_type n) -> auto&
			{
				_index -= n;
				_value -= n;
				return *this;
			}

			auto operator[](difference_type i) -> value_type
			{
				auto x = *this;
				x += i;
				return *x;
			}

			auto operator++() -> auto&
			{
				*this += 1;
				return *this;
			}
			auto operator++(int)
			{
				auto self = *this;
				++(*this);
				return self;
			}
			auto operator--() -> auto&
			{
				*this -= 1;
				return *this;
			}

			auto operator--(int)
			{
				auto self = *this;
				--(*this);
				return self;
			}

			friend auto operator-(const Compact_index_policy_iterator& lhs,
			                      const Compact_index_policy_iterator& rhs) noexcept
			{
				return lhs._index - rhs._index;
			}
			friend auto operator+(Compact_index_policy_iterator iter, difference_type offset)
			{
				iter += offset;
				return iter;
			}
			friend auto operator+(difference_type offset, Compact_index_policy_iterator iter)
			{
				iter += offset;
				return iter;
			}
			friend auto operator-(Compact_index_policy_iterator iter, difference_type offset)
			{
				iter -= offset;
				return iter;
			}

			friend auto operator<(const Compact_index_policy_iterator& lhs,
			                      const Compact_index_policy_iterator& rhs) noexcept
			{
				return lhs._index < rhs._index;
			}
			friend auto operator>(const Compact_index_policy_iterator& lhs,
			                      const Compact_index_policy_iterator& rhs) noexcept
			{
				return lhs._index > rhs._index;
			}
			friend auto operator<=(const Compact_index_policy_iterator& lhs,
			                       const Compact_index_policy_iterator& rhs) noexcept
			{
				return lhs._index <= rhs._index;
			}
			friend auto operator>=(const Compact_index_policy_iterator& lhs,
			                       const Compact_index_policy_iterator& rhs) noexcept
			{
				return lhs._index >= rhs._index;
			}
			friend auto operator==(const Compact_index_policy_iterator& lhs,
			                       const Compact_index_policy_iterator& rhs) noexcept
			{
				return lhs._index == rhs._index;
			}
			friend auto operator!=(const Compact_index_policy_iterator& lhs,
			                       const Compact_index_policy_iterator& rhs) noexcept
			{
				return !(lhs == rhs);
			}

		  private:
			difference_type _index = 0;
			Value_iterator  _value;
			value_type      _last_value;
		};
	} // namespace detail

162
	class Compact_index_policy {
163
	  public:
Florian Oetke's avatar
Florian Oetke committed
164
165
		using iterator = detail::Compact_index_policy_iterator;

166
167
168
169
170
171
172
		Compact_index_policy();
		void attach(Entity_id, Component_index);
		void detach(Entity_id);
		void shrink_to_fit();
		auto find(Entity_id) const -> util::maybe<Component_index>;
		void clear();

Florian Oetke's avatar
Florian Oetke committed
173
174
175
176
177
178
179
180
		static constexpr bool sorted_iteration_supported = true;

		auto sorted_begin() const -> iterator { return {0, _table.begin()}; }
		auto sorted_end() const -> iterator { return {std::int_fast32_t(_table.size()), _table.end()}; }

		auto begin() const { return sorted_begin(); }
		auto end() const { return sorted_end(); }

181
182
	  private:
		std::vector<Component_index> _table;
183
184
	};

Florian Oetke's avatar
Florian Oetke committed
185
186
187
188
189
190
191
192
193
194
195
196
197
198
	template <class Storage_policy>
	class Pool_based_index_policy {
	  public:
		Pool_based_index_policy(Storage_policy& pool) : _pool(&pool) {}
		void attach(Entity_id, Component_index) {}
		void detach(Entity_id) {}
		void shrink_to_fit() {}
		auto find(Entity_id entity) const -> util::maybe<Component_index> { return _pool->find(entity); }
		void clear() {}

		using iterator                                   = typename Storage_policy::iterator;
		static constexpr bool sorted_iteration_supported = false;
		// sorted_begin()
		// sorted_end()
199

Florian Oetke's avatar
Florian Oetke committed
200
201
		auto begin() { return _pool->begin(); }
		auto end() { return _pool->end(); }
202

Florian Oetke's avatar
Florian Oetke committed
203
204
	  private:
		Storage_policy* _pool;
205
206
207
	};


Florian Oetke's avatar
Florian Oetke committed
208
209
210
211
212
	namespace detail {
		template <class T, typename = void>
		struct Pool_storage_policy_sort {
			static constexpr bool sorted = false;
		};
Florian Oetke's avatar
Florian Oetke committed
213

214
		// FIXME: sorted pool returns/erases the wrong values under heavy contention
Florian Oetke's avatar
Florian Oetke committed
215
216
217
		template <class T>
		struct Pool_storage_policy_sort<T, util::void_t<decltype(T::sort_key), decltype(T::sort_key_index)>> {
			static constexpr bool sorted                   = true;
218
			static constexpr auto sort_key                 = T::sort_key();
Florian Oetke's avatar
Florian Oetke committed
219
220
			static constexpr auto sort_key_constructor_idx = T::sort_key_index;
		};
Florian Oetke's avatar
Florian Oetke committed
221

Florian Oetke's avatar
Florian Oetke committed
222
223
224
225
226
227
228
229
230
		template <class T, std::size_t Holes>
		struct Pool_storage_policy_value_traits : Pool_storage_policy_sort<T> {
			static constexpr int_fast32_t max_free = Holes;
		};
	} // namespace detail



	template <std::size_t Chunk_size, std::size_t Holes, class T>
231
	class Pool_storage_policy {
Florian Oetke's avatar
Florian Oetke committed
232
233
		using pool_t =
		        util::pool<T, Chunk_size, detail::Pool_storage_policy_value_traits<T, Holes>, Component_index>;
234

235
	  public:
Florian Oetke's avatar
Florian Oetke committed
236
237
		static constexpr auto is_sorted = pool_t::sorted;

238
		using iterator = typename pool_t::iterator;
239

Florian Oetke's avatar
Florian Oetke committed
240
241
		template <typename F, class... Args>
		auto emplace(F&& relocate, Args&&... args) -> std::tuple<T&, Component_index>
242
		{
Florian Oetke's avatar
Florian Oetke committed
243
			return _pool.emplace(relocate, std::forward<Args>(args)...);
244
		}
245

246
		void replace(Component_index idx, T&& new_element) { _pool.replace(idx, std::move(new_element)); }
247

248
		template <typename F>
249
250
		void erase(Component_index idx, F&& relocate)
		{
251
252
			_pool.erase(idx, std::forward<F>(relocate));
		}
253

254
		void clear() { _pool.clear(); }
255

256
		template <typename F>
257
258
		void shrink_to_fit(F&& relocate)
		{
259
260
			_pool.shrink_to_fit(std::forward<F>(relocate));
		}
261

262
		auto get(Component_index idx) -> T& { return _pool.get(idx); }
263

264
265
266
267
268
		auto begin() noexcept -> iterator { return _pool.begin(); }
		auto end() noexcept -> iterator { return _pool.end(); }
		auto size() const -> Component_index { return _pool.size(); }
		auto empty() const -> bool { return _pool.empty(); }

Florian Oetke's avatar
Florian Oetke committed
269
		template <class Key,
270
		          class = std::enable_if_t<std::is_same_v<Key, decltype(std::declval<T>().*T::sort_key())>>>
Florian Oetke's avatar
Florian Oetke committed
271
272
273
274
275
		auto find(const Key& key)
		{
			return _pool.find(key);
		}

276
277
	  private:
		pool_t _pool;
278
279
280
	};


Florian Oetke's avatar
Florian Oetke committed
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
	template <class T>
	class Void_storage_policy {
	  public:
		static constexpr auto is_sorted = false;

		/// dummy returned by all calls. Can be mutable because it doesn't contain any state
		static T dummy_instance;

		using iterator = T*;

		template <typename F, class... Args>
		auto emplace(F&&, Args&&...) -> std::tuple<T&, Component_index>
		{
			_size++;
			return {dummy_instance, 0};
		}

		void replace(Component_index, T&&) {}

		template <typename F>
		void erase(Component_index, F&&)
		{
			_size--;
		}

		void clear() { _size = 0; }

		template <typename F>
		void shrink_to_fit(F&&)
		{
		}

		auto get(Component_index) -> T& { return dummy_instance; }

		auto begin() noexcept -> iterator
		{
			static_assert(util::dependent_false<T>(), "Iteration is not supported by Void_storage_policy.");
			return &dummy_instance;
		}
		auto end() noexcept -> iterator
		{
			static_assert(util::dependent_false<T>(), "Iteration is not supported by Void_storage_policy.");
			return &dummy_instance + 1;
		}
325
		auto size() const -> Component_index { return static_cast<Component_index>(_size); }
Florian Oetke's avatar
Florian Oetke committed
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
		auto empty() const -> bool { return _size == 0; }

	  private:
		std::size_t _size = 0;
	};

	template <class T>
	T Void_storage_policy<T>::dummy_instance;


	namespace detail {
		template <class Index, class Storage>
		auto index_constructor_arg(Storage& storage)
		{
			if constexpr(std::is_constructible_v<Index, Storage&>) {
				return Index(storage);
			} else {
				return Index();
			}
		}
	} // namespace detail
347

348
	template <class T>
349
350
351
352
353
	class Component_container : public Component_container_base {
		friend class Entity_manager;
		friend void load(sf2::JsonDeserializer& s, Entity_handle& e);
		friend void save(sf2::JsonSerializer& s, const Entity_handle& e);

354
	  public:
Florian Oetke's avatar
Florian Oetke committed
355
356
		Component_container(Entity_manager& m)
		  : _storage(), _index(detail::index_constructor_arg<typename T::index_policy>(_storage)), _manager(m)
357
		{
Florian Oetke's avatar
Florian Oetke committed
358
			T::_check_type_invariants();
359
360
361
362
			_index.clear();
		}

		auto value_type() const noexcept -> Component_type override { return component_type_id<T>(); }
363

364
	  protected:
365
366
		void restore(Entity_handle owner, Deserializer& deserializer) override
		{
Florian Oetke's avatar
Florian Oetke committed
367
368
369
370
			if constexpr(std::is_constructible_v<T, Entity_handle, Entity_manager&>) {
				auto entity_id = get_entity_id(owner, _manager);
				if(entity_id == invalid_entity_id) {
					MIRRAGE_FAIL("emplace_or_find_now of component from invalid/deleted entity");
371
372
				}

Florian Oetke's avatar
Florian Oetke committed
373
374
375
376
377
378
379
380
381
				auto& comp = [&]() -> T& {
					auto comp_idx = _index.find(entity_id);
					if(comp_idx.is_some()) {
						return _storage.get(comp_idx.get_or_throw());
					}

					auto relocator = [&](auto, auto& comp, auto new_idx) {
						_index.attach(comp.owner_handle().id(), new_idx);
					};
Florian Oetke's avatar
Florian Oetke committed
382

Florian Oetke's avatar
Florian Oetke committed
383
384
385
386
					auto comp = _storage.emplace(relocator, owner, _manager);
					_index.attach(entity_id, std::get<1>(comp));
					return std::get<0>(comp);
				}();
387

Florian Oetke's avatar
Florian Oetke committed
388
389
390
391
392
393
394
395
				load_component(deserializer, comp);

			} else {
				(void) owner;
				(void) deserializer;
				MIRRAGE_FAIL("Tried to load component " << T::name()
				                                        << " that has no two-argument constructor!");
			}
396
		}
397

398
399
		bool save(Entity_handle owner, Serializer& serializer) override
		{
400
401
402
403
404
405
			return find(owner).process(false, [&](T& comp) {
				serializer.write_value(T::name_save_as());
				save_component(serializer, comp);
				return true;
			});
		}
406

407
408
		void clear() override
		{
409
410
411
412
413
414
415
416
417
418
419
			_queued_deletions  = Queue<Entity_handle>{}; // clear by moving a new queue into the old
			_queued_insertions = Queue<Insertion>{};     // clear by moving a new queue into the old
			_index.clear();
			_storage.clear();
			_unoptimized_deletes = 0;
			_index.shrink_to_fit();
			_storage.shrink_to_fit([&](auto, auto& comp, auto new_idx) {
				_index.attach(comp.owner_handle().id(), new_idx);
			});
		}

420
421
		void process_queued_actions() override
		{
422
423
			process_deletions();
			process_insertions();
424

425
			if(_unoptimized_deletes > 32) {
426
427
428
429
				_unoptimized_deletes = 0;
				_storage.shrink_to_fit([&](auto, auto& comp, auto new_idx) {
					_index.attach(comp.owner_handle().id(), new_idx);
				});
Florian Oetke's avatar
Florian Oetke committed
430
				_index.shrink_to_fit();
431
			}
432
		}
433

434
435
		void process_deletions()
		{
436
437
438
439
440
441
442
443
444
			std::array<Entity_handle, 16> deletions_buffer;

			do {
				std::size_t deletions =
				        _queued_deletions.try_dequeue_bulk(deletions_buffer.data(), deletions_buffer.size());
				if(deletions > 0) {
					for(auto i = 0ull; i < deletions; i++) {
						auto entity_id = get_entity_id(deletions_buffer[i], _manager);
						if(entity_id == invalid_entity_id) {
445
446
447
							LOG(plog::warning)
							        << "Discard delete of component " << T::name()
							        << " from invalid/deleted entity: " << entity_name(deletions_buffer[i]);
448
449
							continue;
						}
450

451
452
453
454
						auto comp_idx_mb = _index.find(entity_id);
						if(!comp_idx_mb) {
							continue;
						}
455

456
457
						auto comp_idx = comp_idx_mb.get_or_throw();
						_index.detach(entity_id);
458

Florian Oetke's avatar
Florian Oetke committed
459
460
461
462
463
						_storage.erase(comp_idx, [&](auto, auto& comp, auto new_idx) {
							auto entity_id = get_entity_id(comp.owner_handle(), _manager);
							_index.attach(entity_id, new_idx);
						});
						_unoptimized_deletes++;
464
					}
465
466
467
468
469
				} else {
					break;
				}
			} while(true);
		}
470
471
		void process_insertions()
		{
472
473
474
475
476
477
478
479
480
			std::array<Insertion, 8> insertions_buffer;

			do {
				std::size_t insertions = _queued_insertions.try_dequeue_bulk(insertions_buffer.data(),
				                                                             insertions_buffer.size());
				if(insertions > 0) {
					for(auto i = 0ull; i < insertions; i++) {
						auto entity_id = get_entity_id(std::get<1>(insertions_buffer[i]), _manager);
						if(entity_id == invalid_entity_id) {
481
482
483
							LOG(plog::warning)
							        << "Discard insertion of component from invalid/deleted entity: "
							        << entity_name(std::get<1>(insertions_buffer[i]));
484
							continue;
485
						}
486

Florian Oetke's avatar
Florian Oetke committed
487
488
489
490
						auto relocator = [&](auto, auto& comp, auto new_idx) {
							_index.attach(comp.owner_handle().id(), new_idx);
						};
						auto comp = _storage.emplace(relocator, std::move(std::get<0>(insertions_buffer[i])));
491
						_index.attach(entity_id, std::get<1>(comp));
492
					}
493
494
495
496
497
				} else {
					break;
				}
			} while(true);
		}
498

499
	  public:
Florian Oetke's avatar
Florian Oetke committed
500
501
502
		using iterator       = typename T::storage_policy::iterator;
		using component_type = T;

503
		template <typename F, typename... Args>
504
505
		void emplace(F&& init, Entity_handle owner, Args&&... args)
		{
506
			MIRRAGE_INVARIANT(owner != invalid_entity, "emplace on invalid entity");
507
508
509

			// construct T inplace inside the pair to avoid additional move
			auto inst = Insertion(std::piecewise_construct,
Florian Oetke's avatar
Florian Oetke committed
510
			                      std::forward_as_tuple(owner, _manager, std::forward<Args>(args)...),
511
512
513
514
			                      std::forward_as_tuple(owner));
			std::forward<F>(init)(inst.first);
			_queued_insertions.enqueue(std::move(inst));
		}
515

516
517
		void erase(Entity_handle owner) override
		{
518
			MIRRAGE_INVARIANT(owner, "erase on invalid entity");
519
520
			_queued_deletions.enqueue(owner);
		}
521

522
523
		auto find(Entity_handle owner) -> util::maybe<T&>
		{
524
			auto entity_id = get_entity_id(owner, _manager);
525

526
527
528
			return _index.find(entity_id).process(
			        util::maybe<T&>(), [&](auto comp_idx) { return util::justPtr(&_storage.get(comp_idx)); });
		}
529
530
		auto has(Entity_handle owner) const -> bool
		{
531
			auto entity_id = get_entity_id(owner, _manager);
532

533
534
			return _index.find(entity_id).is_some();
		}
535

536
537
538
539
		auto begin() noexcept { return _storage.begin(); }
		auto end() noexcept { return _storage.end(); }
		auto size() const noexcept { return _storage.size(); }
		auto empty() const noexcept { return _storage.empty(); }
540

Florian Oetke's avatar
Florian Oetke committed
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560

		auto unsafe_find(Entity_id entity_id) -> util::maybe<T&>
		{
			return _index.find(entity_id).process(
			        util::maybe<T&>(), [&](auto comp_idx) { return util::justPtr(&_storage.get(comp_idx)); });
		}

		static constexpr auto sorted_iteration_supported =
		        T::storage_policy::is_sorted || T::index_policy::sorted_iteration_supported;

		template <class ComponentContainer>
		friend auto detail::container_begin(ComponentContainer&)
		        -> Sorted_component_iterator<typename ComponentContainer::component_type>;

		template <class ComponentContainer>
		friend auto detail::container_end(ComponentContainer&)
		        -> Sorted_component_iterator<typename ComponentContainer::component_type>;

		template <class>
		friend class Sorted_component_iterator;
561

562
563
	  private:
		using Insertion = std::pair<T, Entity_handle>;
564

565
566
		template <class E>
		using Queue = moodycamel::ConcurrentQueue<E>;
567

568
		typename T::storage_policy _storage;
Florian Oetke's avatar
Florian Oetke committed
569
		typename T::index_policy   _index;
570

571
572
573
574
575
		Entity_manager&      _manager;
		Queue<Entity_handle> _queued_deletions;
		Queue<Insertion>     _queued_insertions;
		int                  _unoptimized_deletes = 0;
	};
Florian Oetke's avatar
Florian Oetke committed
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603


	template <class T>
	class Sorted_component_iterator {
	  public:
		static constexpr auto pool_based = T::storage_policy::is_sorted;
		using wrapped_iterator           = std::conditional_t<pool_based,
                                                    typename T::storage_policy::iterator,
                                                    typename T::index_policy::iterator>;

		using iterator_category = std::input_iterator_tag;
		using value_type        = std::tuple<Entity_id, T*>;
		using difference_type   = std::int_fast32_t;
		using reference         = value_type;
		using pointer           = value_type*;

		Sorted_component_iterator() : _container(nullptr), _iterator() {}
		Sorted_component_iterator(typename T::Pool* container, wrapped_iterator iterator)
		  : _container(container), _iterator(std::move(iterator))
		{
		}

		value_type  operator*() noexcept { return *get(); }
		value_type* operator->() noexcept { return get(); }
		value_type* get() noexcept
		{
			if constexpr(pool_based) {
				auto& component = *_iterator;
604
				_last_value     = value_type{(component.*T::sort_key()).id(), &component};
Florian Oetke's avatar
Florian Oetke committed
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
			} else {
				auto&& [entity, idx] = *_iterator;
				_last_value          = value_type{entity, &_container->_storage.get(idx)};
			}

			return &_last_value;
		}

		auto operator+=(difference_type n) -> auto&
		{
			_iterator += n;
			return *this;
		}
		auto operator-=(difference_type n) -> auto&
		{
			_iterator -= n;
			return *this;
		}

		auto operator[](difference_type i) -> value_type { return _iterator[i]; }

		auto operator++() -> auto&
		{
			++_iterator;
			return *this;
		}
		auto operator++(int)
		{
			auto self = *this;
			++(*this);
			return self;
		}
		auto operator--() -> auto&
		{
			--_iterator;
			return *this;
		}

		auto operator--(int)
		{
			auto self = *this;
			--(*this);
			return self;
		}

		friend auto operator-(const Sorted_component_iterator& lhs,
		                      const Sorted_component_iterator& rhs) noexcept
		{
			return lhs._iterator - rhs._iterator;
		}
		friend auto operator+(Sorted_component_iterator iter, difference_type offset)
		{
			iter += offset;
			return iter;
		}
		friend auto operator+(difference_type offset, Sorted_component_iterator iter)
		{
			iter += offset;
			return iter;
		}
		friend auto operator-(Sorted_component_iterator iter, difference_type offset)
		{
			iter -= offset;
			return iter;
		}

		friend auto operator<(const Sorted_component_iterator& lhs,
		                      const Sorted_component_iterator& rhs) noexcept
		{
			return lhs._iterator < rhs._iterator;
		}
		friend auto operator>(const Sorted_component_iterator& lhs,
		                      const Sorted_component_iterator& rhs) noexcept
		{
			return lhs._iterator > rhs._iterator;
		}
		friend auto operator<=(const Sorted_component_iterator& lhs,
		                       const Sorted_component_iterator& rhs) noexcept
		{
			return lhs._iterator <= rhs._iterator;
		}
		friend auto operator>=(const Sorted_component_iterator& lhs,
		                       const Sorted_component_iterator& rhs) noexcept
		{
			return lhs._iterator >= rhs._iterator;
		}
		friend auto operator==(const Sorted_component_iterator& lhs,
		                       const Sorted_component_iterator& rhs) noexcept
		{
			return lhs._iterator == rhs._iterator;
		}
		friend auto operator!=(const Sorted_component_iterator& lhs,
		                       const Sorted_component_iterator& rhs) noexcept
		{
			return !(lhs == rhs);
		}

	  private:
		typename T::Pool* _container;
		wrapped_iterator  _iterator;
		value_type        _last_value;
	};

	namespace detail {
		template <class ComponentContainer>
		auto container_begin(ComponentContainer& container)
		        -> Sorted_component_iterator<typename ComponentContainer::component_type>
		{

			if constexpr(ComponentContainer::component_type::storage_policy::is_sorted) {
				return Sorted_component_iterator<typename ComponentContainer::component_type>(
				        &container, container._storage.begin());

			} else if constexpr(ComponentContainer::component_type::index_policy::sorted_iteration_supported) {
				return Sorted_component_iterator<typename ComponentContainer::component_type>(
				        &container, container._index.sorted_begin());

			} else {
				return Sorted_component_iterator<typename ComponentContainer::component_type>(
				        &container, container._index.begin());
			}
		}

		template <class ComponentContainer>
		auto container_end(ComponentContainer& container)
		        -> Sorted_component_iterator<typename ComponentContainer::component_type>
		{
			if constexpr(ComponentContainer::component_type::storage_policy::is_sorted) {
				return Sorted_component_iterator<typename ComponentContainer::component_type>(
				        &container, container._storage.end());
			} else if constexpr(ComponentContainer::component_type::index_policy::sorted_iteration_supported) {
				return Sorted_component_iterator<typename ComponentContainer::component_type>(
				        &container, container._index.sorted_end());
			} else {
				return Sorted_component_iterator<typename ComponentContainer::component_type>(
				        &container, container._index.end());
			}
		}
	} // namespace detail

	template <class ComponentContainer, typename>
	auto sorted_begin(ComponentContainer& container)
	        -> Sorted_component_iterator<typename ComponentContainer::component_type>
	{
		static_assert(ComponentContainer::sorted_iteration_supported,
		              "Sorted iteration is not supported by this component type!");

		return detail::container_begin(container);
	}

	template <class ComponentContainer, typename>
	auto sorted_end(ComponentContainer& container)
	        -> Sorted_component_iterator<typename ComponentContainer::component_type>
	{
		static_assert(ComponentContainer::sorted_iteration_supported,
		              "Sorted iteration is not supported by this component type!");

		return detail::container_end(container);
	}

765
} // namespace mirrage::ecs