4 #include "kblib/kblib.h" 74 template <
typename T,
bool SaveNext>
84 template <
typename Ti>
85 el_impl(Ti&& v,
bool var, [[maybe_unused]] std::ptrdiff_t _)
86 : val(std::forward(v)), variadic(var) {}
95 std::ptrdiff_t dist{};
100 std::ptrdiff_t dist_var;
101 std::ptrdiff_t dist_nvar;
104 template <
typename T,
bool I>
105 using element = std::variant<tombstone_t, el_impl<T, I>,
backref_t>;
107 enum class fda_policy : unsigned {
113 [[nodiscard]] constexpr fda_policy operator|(fda_policy l,
114 fda_policy r) noexcept {
116 return static_cast<fda_policy
>(etoi(l) | etoi(r));
119 [[nodiscard]] constexpr fda_policy operator&(fda_policy l,
120 fda_policy r) noexcept {
122 return static_cast<fda_policy
>(etoi(l) & etoi(r));
125 template <
typename T,
typename BI>
131 using difference_type = std::ptrdiff_t;
132 using value_type = T;
134 using reference = T&;
135 using iterator_category = std::bidirectional_iterator_tag;
140 [[nodiscard]] reference operator*() {
return std::get<live_type>(*_p).val; }
141 [[nodiscard]] pointer operator->() {
return &std::get<live_type>(*_p).val; }
144 _p += std::get<live_type>(*_p).next;
158 [](backref_t d) {
return d.dist_nvar; });
167 template <
typename T1,
typename BI1>
169 std::swap(a._p, b._p);
172 template <
typename T1,
typename BI1>
175 template <
typename T1,
typename BI1>
178 [[nodiscard]]
auto get()
const noexcept {
179 return &
static_cast<const std::decay_t<decltype(*_p)>&
>(*_p);
183 template <
typename T1, fda_policy policy,
typename Alloc>
188 inline namespace comp {
190 template <
typename T1,
typename BI1>
196 template <
typename T1,
typename BI1>
202 template <
typename T1,
typename BI1>
203 [[nodiscard]]
bool operator<(const f_iterator<T1, BI1> a,
208 template <
typename T1,
typename BI1>
214 template <
typename T1,
typename BI1>
220 template <
typename T1,
typename BI1>
221 [[nodiscard]]
bool operator<=(const f_iterator<T1, BI1> a,
228 template <
typename P>
233 operator bool()
const noexcept {
return ptr; }
235 template <
typename P>
236 std::ostream& operator<<(std::ostream& os, const info_t<P>& i) {
237 return os <<
"{ptr: " << i.ptr <<
", idx: " << i.idx
238 <<
", variadic: " << i.variadic <<
"}";
241 template <
typename T, fda_policy policy = fda_policy::Default,
242 typename Alloc =
void>
244 constexpr
static bool AllowIteration =
245 (policy & fda_policy::DenyIteration) != fda_policy::DenyIteration;
246 constexpr
static bool DoShadow =
247 (policy & fda_policy::NV_Shadow_V) == fda_policy::NV_Shadow_V;
251 using size_type = std::size_t;
252 using index_type = std::ptrdiff_t;
253 using difference_type = index_type;
256 std::is_same_v<T, std::remove_reference_t<std::remove_cv_t<T>>>);
257 using value_type = T;
258 using reference = value_type&;
259 using const_reference =
const T&;
263 using const_pointer =
const T*;
265 using element_type = element<value_type, AllowIteration>;
269 using allocator_type =
270 std::conditional_t<std::is_void_v<Alloc>, std::allocator<element_type>,
274 using BC = std::vector<element_type, allocator_type>;
277 static constexpr index_type npos =
278 std::numeric_limits<difference_type>::max() / 2;
281 std::conditional_t<AllowIteration,
283 using const_iterator = std::conditional_t<
287 using reverse_iterator =
288 std::conditional_t<AllowIteration, std::reverse_iterator<iterator>,
290 using const_reverse_iterator =
291 std::conditional_t<AllowIteration, std::reverse_iterator<const_iterator>,
309 falldown_array& operator=(std::initializer_list<el_val> v) { assign(v); }
311 allocator_type get_allocator()
const {
return backing.get_allocator(); }
313 void assign(std::initializer_list<el_val> v) {
316 set(e.idx, e.var, e.val);
319 auto set(index_type idx,
bool variadic, const_reference val) noexcept(
320 std::is_nothrow_copy_constructible_v<value_type>) {
321 return emplace(idx, variadic, val);
324 template <
typename... Args>
325 auto emplace(index_type idx,
bool variadic, Args&&... args) noexcept(
326 std::is_nothrow_constructible_v<value_type, Args...>) {
330 if (idx > static_cast<difference_type>(backing.size()) - 2) {
331 const auto start_adjusting =
332 static_cast<index_type
>(backing.size()) - 1;
333 backing.resize(idx + 2);
334 if (start_adjusting >= 0) {
335 propagate_ref_end(start_adjusting);
340 const typename BC::iterator pos = backing.begin() + idx;
341 bool need_adjust = !(std::holds_alternative<live_type>(*pos) &&
342 (std::get<live_type>(*pos).variadic == variadic));
346 live_type{value_type(std::forward<Args...>(args...)), variadic, 0};
347 propagate_ref_mid(idx);
349 std::get<live_type>(*pos).val =
350 value_type(std::forward<Args...>(args...));
353 _first = std::min(_first, idx);
354 _size = std::count_if(backing.begin() + _first, backing.end(),
355 [](
const element_type& e) {
356 return std::holds_alternative<live_type>(e);
361 if constexpr (AllowIteration) {
362 return iterator{pos};
368 [[nodiscard]] size_type size()
const noexcept {
return _size; }
369 [[nodiscard]] size_type capacity()
const noexcept {
370 return backing.capacity();
372 [[nodiscard]] size_type empty()
const noexcept {
return backing.empty(); }
373 [[nodiscard]] size_type max_size()
const noexcept {
374 return std::min(backing.max_size(),
static_cast<size_type
>(npos) - 1);
377 void reserve(size_type s) { backing.reserve(s); }
378 void shrink_to_fit() { backing.shrink_to_fit(); }
380 void clear() noexcept {
386 const_reference operator[](index_type idx)
const noexcept(
false) {
388 const auto pos = adjust_down<false>(
390 std::min(idx, static_cast<index_type>(backing.size()) - 1));
391 return std::get<live_type>(*pos).val;
393 reference operator[](index_type idx) noexcept(
false) {
395 const auto pos = adjust_down<false>(
397 std::min(idx, static_cast<index_type>(backing.size()) - 1));
398 return std::get<live_type>(*pos).val;
402 const auto pos = adjust_down<true>(
404 std::min(idx, static_cast<index_type>(backing.size()) - 1));
405 if (
auto p = std::get_if<live_type>(&*pos)) {
406 return {&p->val, pos - backing.begin(), p->variadic};
408 return {
nullptr, pos - backing.begin(),
false};
413 const auto pos = adjust_down<true>(
415 std::min(idx, static_cast<index_type>(backing.size()) - 1));
416 if (
auto p = std::get_if<live_type>(&*pos)) {
417 return {&p->val, pos - backing.begin(), p->variadic};
419 return {
nullptr, pos - backing.begin(),
false};
423 pointer
get(index_type idx) noexcept {
return info(idx).ptr; }
425 const_pointer
get(index_type idx)
const noexcept {
return info(idx).ptr; }
427 iterator begin() noexcept {
return iterator{backing.begin() + _first}; }
428 iterator end() noexcept {
return iterator{backing.end()}; }
429 const_iterator begin()
const noexcept {
430 return iterator{backing.begin() + _first};
432 const_iterator end()
const noexcept {
return iterator{backing.end()}; }
434 reverse_iterator rbegin() noexcept {
435 return std::make_reverse_iterator(iterator{backing.end()});
437 reverse_iterator rend() noexcept {
438 return std::make_reverse_iterator(iterator{backing.begin() + _first});
440 const_reverse_iterator rbegin()
const noexcept {
441 return std::make_reverse_iterator(iterator{backing.end()});
443 const_reverse_iterator rend()
const noexcept {
444 return std::make_reverse_iterator(iterator{backing.begin() + _first});
447 const_iterator cbegin()
const noexcept {
448 return const_iterator{backing.begin() + _first};
450 const_iterator cend()
const noexcept {
451 return const_iterator{backing.end()};
453 const_reverse_iterator crbegin()
const noexcept {
454 return std::make_reverse_iterator(const_iterator{backing.end()});
456 const_reverse_iterator crend()
const noexcept {
457 return std::make_reverse_iterator(
458 const_iterator{backing.begin() + _first});
465 swap(a.backing, b.backing);
466 swap(a._first, b._first);
467 swap(a._size, b._size);
479 template <
typename F>
480 struct extract_arg_from;
481 template <
typename R,
typename Arg>
482 struct extract_arg_from<R (*)(Arg)> {
485 template <
typename F>
486 struct extract_ret_from;
487 template <
typename R,
typename Arg>
488 struct extract_ret_from<R (*)(Arg)> {
492 template <
typename... Fs>
493 struct Funs : Funs<Fs>... {};
494 template <
typename F>
496 using arg =
typename extract_arg_from<F>::type;
497 using ret =
typename extract_ret_from<F>::type;
498 ret operator()(arg a) {
return f(a); }
502 template <
bool nothrow>
503 static typename BC::iterator
504 adjust_down(
typename BC::iterator pos) noexcept(nothrow) {
505 static_assert(std::is_invocable_v<Funs<
void (*)(
int)>,
int>);
506 static_assert(kblib::detail::v_invocable_with_all_v<
508 void (*)(backref_t)>,
510 return kblib::visit2(
513 if constexpr (nothrow) {
516 throw std::out_of_range(
"");
520 [&](backref_t d) {
return pos - d.dist_var; });
525 void propagate_ref_end(index_type start) noexcept {
526 const auto start_pos = backing.begin() + start;
527 const auto end = backing.end();
528 auto [count, variadic] = scan_backward_for_last_var(start + 1);
529 auto dist_nvar = scan_backward_for_last_entry(start + 1);
530 for (
auto it = start_pos + 1;
531 it != end && !std::holds_alternative<live_type>(*it); ++it) {
533 *it = backref_t{count, dist_nvar};
544 void propagate_ref_mid(index_type start) noexcept {
545 const typename BC::iterator pos = backing.begin() + start;
547 assert(start >= 0 and kblib::to_unsigned(start) < backing.size());
548 assert(std::holds_alternative<live_type>(*pos));
549 auto& reference = std::get<live_type>(*pos);
551 propagate_ref_end(start);
552 if constexpr (AllowIteration) {
553 reference.next = scan_forward_for_next_entry(start + 1) - start;
554 if (reference.next + start == kblib::to_signed(backing.size())) {
555 reference.next = npos;
557 auto last = scan_backward_for_last_entry(start - 1);
559 std::get<live_type>(backing[last]).next = (start - last);
573 std::pair<difference_type, bool>
574 scan_backward_for_last_var(index_type start)
const noexcept {
575 const typename BC::const_iterator pos = backing.begin() + start,
576 begin = backing.begin();
577 std::optional<difference_type> nvar_pos;
580 difference_type steps = 0;
583 if (
auto p = std::get_if<live_type>(&*it)) {
584 if constexpr (DoShadow) {
585 return {steps, p->variadic};
588 return {steps,
true};
589 }
else if (!nvar_pos) {
590 nvar_pos.emplace(steps);
593 }
else if (
auto p = std::get_if<backref_t>(&*it)) {
594 return {steps + p->dist_var,
true};
595 }
else if (
auto p = std::get_if<tombstone_t>(&*it)) {
597 return {*nvar_pos,
false};
599 return {steps + p->dist,
false};
601 }
while (--it != begin);
603 return {*nvar_pos,
false};
605 return {start,
false};
611 index_type scan_forward_for_next_entry(index_type start)
const noexcept {
612 return kblib::find_in_if(backing.begin() + start, backing.end(),
613 [](
const element_type& el) {
614 return std::holds_alternative<live_type>(el);
619 index_type scan_backward_for_last_entry(index_type start)
const noexcept {
621 return kblib::find_last_in_if(
622 backing.begin(), backing.begin() + start + 1,
623 [](
const element_type& el) {
624 return std::holds_alternative<live_type>(el);
644 void assert_conditions() noexcept {
646 std::cerr <<
"--------\n";
647 if (!backing.empty()) {
650 index_type counter{};
651 index_type toNext{_first};
652 [[maybe_unused]] index_type idx = 0;
653 for (
const auto& el : backing) {
654 std::cerr << idx++ <<
" b: -" << counter <<
" n: " << toNext
655 <<
" v: " << var <<
" | ";
663 std::cerr <<
'[' << e.val <<
',' 664 << (e.variadic ?
'T' :
'F');
665 if constexpr (AllowIteration) {
666 std::cerr <<
',' << e.next;
669 if constexpr (DoShadow) {
682 std::cerr <<
"b -" << b.dist_var <<
'\n';
683 assert(b.dist_var == counter);
690 assert(!std::holds_alternative<live_type>(backing.back()));
696 index_type _first{npos};
703 #endif // FDA_H_INCLUDED