/* *****************************************************************************
* kblib is a general utility library for C++14 and C++17, intended to provide
* performant high-level abstractions and more expressive ways to do simple
* things.
*
* Copyright (c) 2021 killerbee
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
* ****************************************************************************/
/**
* @file
* @brief Provides multi_span.
*
* @author killerbee
* @date 2019-2021
* @copyright GNU General Public Licence v3.0
*/
#ifndef MULTI_SPAN_H
#define MULTI_SPAN_H
#include "tdecl.h"
#if KBLIB_USE_CXX17
# include
# include
# include
# include
# include
# include
# include
# include
namespace KBLIB_NS {
template
class multi_span;
namespace multi_impl {
template
using subspan_t = std::pair>;
template
class mulspan_iterator
: public boost::iterator_facade, T,
std::bidirectional_iterator_tag> {
public:
mulspan_iterator() = default;
mulspan_iterator(const multi_span& s)
: parent(&s) {
recalculate_cache();
}
mulspan_iterator(const multi_span& s, std::ptrdiff_t i)
: parent(&s)
, index(i) {}
private:
mulspan_iterator(const multi_span& s, std::ptrdiff_t i,
typename std::vector>::const_iterator r,
typename gsl::span::iterator p)
: parent(&s)
, index(i)
, pos_cache(cached_iterator{r, p}) {}
public:
template >>
mulspan_iterator(const mulspan_iterator&);
template >>
mulspan_iterator(mulspan_iterator&&);
private:
friend class boost::iterator_core_access;
auto recalculate_cache() const -> void {
if (! pos_cache) {
if (index == 0) {
pos_cache = {parent->spans.begin(),
parent->spans.front().second.begin()};
} else if (index == parent->size()) {
pos_cache
= {parent->spans.end(), parent->spans.back().second.begin()};
} else if (auto it = std::prev(parent->spans.end());
index >= it->first) {
pos_cache = {it, it->second.begin() + (index - it->first)};
} else {
// get the subspan before the first subspan starting after index
it = std::prev(std::upper_bound(
parent->spans.begin(), parent->spans.end(), index,
[](std::ptrdiff_t l, const subspan_t& r) {
return l < r.first;
}));
// calculate delta into that subspan
pos_cache = {it, it->second.begin() + (index - it->first)};
}
}
}
auto dereference() const noexcept -> T& {
recalculate_cache();
assert(index != parent->size());
return *pos_cache.value().pos;
}
template () == std::declval())>
auto equal(const mulspan_iterator& o) const noexcept -> bool {
return
// if both *this and o have caches,
/*(pos_cache and o.pos_cache)
//compare them
? pos_cache.value() == o.pos_cache.value()
//else, compare parent and index
:*/
std::tie(parent, index) == std::tie(o.parent, o.index);
}
auto increment() noexcept -> void {
++index;
if (pos_cache) {
++pos_cache.value().pos;
if (pos_cache.value().pos == pos_cache.value().subs->second.end()) {
++pos_cache.value().subs;
pos_cache.value().pos = pos_cache.value().subs->second.begin();
}
}
}
auto decrement() noexcept -> void {
--index;
if (pos_cache) {
if (pos_cache.value().pos
== pos_cache.value().subs->second.begin()) {
--pos_cache.value().subs;
pos_cache.value().pos = pos_cache.value().subs->second.end();
} else {
--pos_cache.value().pos;
}
}
}
auto advance(std::ptrdiff_t delta) noexcept -> void {
index += delta;
pos_cache = std::nullopt;
}
// enabled if T* is comparable with U*
template () == std::declval())>
auto distance_to(mulspan_iterator o) const noexcept -> std::ptrdiff_t {
return index - o.index;
}
const multi_span* parent{};
std::ptrdiff_t index{};
struct cached_iterator {
typename std::vector>::const_iterator subs;
typename gsl::span::iterator pos;
auto operator==(const cached_iterator& o) const noexcept -> bool {
return std::tie(subs, pos) == std::tie(o.subs, o.pos);
}
};
mutable std::optional pos_cache = std::nullopt;
friend class multi_span;
};
} // namespace multi_impl
template
class multi_span {
public:
using element_type = T;
using value_type = std::remove_cv;
using index_type = std::ptrdiff_t;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator = multi_impl::mulspan_iterator;
using const_iterator = multi_impl::mulspan_iterator;
using reverse_iterator = std::reverse_iterator;
using const_reverse_iterator = std::reverse_iterator;
multi_span() noexcept
: spans{{0, {}}} {}
template >>
multi_span(gsl::span o) noexcept
: spans{{0, o}, {o.size(), {}}} {}
template >>
multi_span(std::initializer_list> i_spans) noexcept {
index_type c
= std::accumulate(i_spans.begin(), i_spans.end(), index_type{0},
[this](int c, gsl::span s) {
spans.push_back({c, s});
return c + s.size();
});
spans.push_back({c, {}});
}
template ()), gsl::span>>>
multi_span(Iterator begin, Iterator end) noexcept {
index_type c = std::accumulate(begin, end, index_type{0},
[this](int c, gsl::span s) {
spans.push_back({c, s});
return c + s.size();
});
spans.push_back({c, {}});
}
template >>
multi_span(const multi_span&);
multi_span(const multi_span&) = default;
multi_span(multi_span&&) noexcept = default;
auto operator=(const multi_span&) -> multi_span& = default;
auto operator=(multi_span&&) noexcept -> multi_span& = default;
~multi_span() = default;
KBLIB_NODISCARD auto begin() noexcept -> iterator { return {*this}; }
KBLIB_NODISCARD auto begin() const noexcept -> const_iterator {
return {*this};
}
KBLIB_NODISCARD auto cbegin() const noexcept -> const_iterator {
return {*this};
}
KBLIB_NODISCARD auto end() noexcept -> iterator {
return {*this, size(), spans.end(), spans.back().second.begin()};
}
KBLIB_NODISCARD auto end() const noexcept -> const_iterator {
return {*this, size(), spans.end(), spans.back().second.begin()};
}
KBLIB_NODISCARD auto cend() const noexcept -> const_iterator {
return {*this, size(), spans.end(), spans.back().second.begin()};
}
KBLIB_NODISCARD auto rbegin() noexcept -> reverse_iterator {
return iterator{*this, size(), spans.end(), spans.back().second.begin()};
}
KBLIB_NODISCARD auto rbegin() const noexcept -> const_reverse_iterator {
return iterator{*this, size(), spans.end(), spans.back().second.begin()};
}
KBLIB_NODISCARD auto crbegin() const noexcept -> const_reverse_iterator {
return iterator{*this, size(), spans.end(), spans.back().second.begin()};
}
KBLIB_NODISCARD auto rend() noexcept -> reverse_iterator {
return iterator{*this};
}
KBLIB_NODISCARD auto rend() const noexcept -> const_reverse_iterator {
return iterator{*this};
}
KBLIB_NODISCARD auto crend() const noexcept -> const_reverse_iterator {
return iterator{*this};
}
KBLIB_NODISCARD reference operator[](index_type i) const {
return *iterator{*this, i};
}
// see invariant on spans
KBLIB_NODISCARD auto size() const noexcept -> index_type {
return spans.back().first;
}
KBLIB_NODISCARD auto empty() const noexcept -> bool {
return spans.back().first == 0;
}
auto diag(std::ostream& os) const noexcept -> void {
os << "Diagnostics: " << spans.size() << '\n';
for (auto& s : spans) {
os << &s << '\t' << s.first << ':' << s.second.size() << '\t';
os << s.second.data() << ',' << s.second.data() + s.second.size()
<< '\n';
}
}
// multi_span first(index_type count) const
// {
// }
// multi_span last(index_type count) const
// {
// }
// multi_span subspan(index_type offset, index_type count = -1) const
// {
// if (count == -1) {
// count = size() - offset;
// }
// }
private:
template
friend class multi_impl::mulspan_iterator;
// invariant: holds one extra value, {size, {}}
std::vector> spans;
};
} // namespace KBLIB_NS
#endif
#endif // MULTI_SPAN_H