multi_span.h

Go to the documentation of this file.

/* *****************************************************************************
 * 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 <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef MULTI_SPAN_H
#define MULTI_SPAN_H
 
#include "tdecl.h"
#include <algorithm>
#include <vector>
 
#if KBLIB_USE_CXX17
 
#  include <tuple>
#  include <optional>
#  include <ostream>
#  include <type_traits>
#  include <utility>
 
#  include <boost/iterator.hpp>
#  include <boost/iterator/iterator_facade.hpp>
#  if __cpp_lib_span >= 202002L
#     include <span>
#  else
#     include <gsl/gsl>
#  endif
 
namespace KBLIB_NS {
#  if __cpp_lib_span >= 202002L
 
using std::span;
#  else
using gsl::span;
#  endif
 
template <typename T>
class multi_span;
 
namespace multi_impl {
 
   template <typename T>
   using subspan_t = std::pair<std::ptrdiff_t, span<T>>;
 
   template <typename T>
   class mulspan_iterator
       : public boost::iterator_facade<mulspan_iterator<T>, T,
                                       std::bidirectional_iterator_tag> {
    public:
      mulspan_iterator() = default;
      mulspan_iterator(const multi_span<T>& s)
          : parent(&s) {
         recalculate_cache();
      }
      mulspan_iterator(const multi_span<T>& s, std::ptrdiff_t i)
          : parent(&s)
          , index(i) {}
 
    private:
      mulspan_iterator(const multi_span<T>& s, std::ptrdiff_t i,
                       typename std::vector<subspan_t<T>>::const_iterator r,
                       typename span<T>::iterator p)
          : parent(&s)
          , index(i)
          , pos_cache(cached_iterator{r, p}) {}
 
    public:
      template <typename U,
                typename
                = std::enable_if_t<std::is_convertible_v<U (*)[], T (*)[]>>>
      mulspan_iterator(const mulspan_iterator<U>&);
      template <typename U,
                typename
                = std::enable_if_t<std::is_convertible_v<U (*)[], T (*)[]>>>
      mulspan_iterator(mulspan_iterator<U>&&);
 
    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<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 <typename U,
                typename = decltype(std::declval<T*>() == std::declval<U*>())>
      auto equal(const mulspan_iterator<U>& 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 <typename U,
                typename = decltype(std::declval<T*>() == std::declval<U*>())>
      auto distance_to(mulspan_iterator<U> o) const noexcept -> std::ptrdiff_t {
         return index - o.index;
      }
 
      const multi_span<T>* parent{};
      std::ptrdiff_t index{};
      struct cached_iterator {
         typename std::vector<multi_impl::subspan_t<T>>::const_iterator subs;
         typename span<T>::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<cached_iterator> pos_cache = std::nullopt;
 
      friend class multi_span<T>;
   };
 
} // namespace multi_impl
 
template <typename T>
class multi_span {
 public:
   using element_type = T;
   using value_type = std::remove_cv<T>;
   using index_type = std::ptrdiff_t;
   using difference_type = std::ptrdiff_t;
   using pointer = T*;
   using reference = T&;
   using iterator = multi_impl::mulspan_iterator<T>;
   using const_iterator = multi_impl::mulspan_iterator<const T>;
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
   multi_span() noexcept
       : spans{{0, {}}} {}
   template <typename U,
             typename
             = std::enable_if_t<std::is_convertible_v<U (*)[], T (*)[]>>>
   multi_span(span<U> o) noexcept
       : spans{{0, o}, {o.size(), {}}} {}
   template <typename U,
             typename
             = std::enable_if_t<std::is_convertible_v<U (*)[], T (*)[]>>>
   multi_span(std::initializer_list<span<U>> i_spans) noexcept {
      index_type c = std::accumulate(i_spans.begin(), i_spans.end(),
                                     index_type{0}, [this](int c, span<U> s) {
                                        spans.push_back({c, s});
                                        return c + s.size();
                                     });
      spans.push_back({c, {}});
   }
   template <typename Iterator,
             typename = std::enable_if_t<std::is_convertible_v<
                 decltype(*std::declval<Iterator>()), span<T>>>>
   multi_span(Iterator begin, Iterator end) noexcept {
      index_type c = std::accumulate(begin, end, index_type{0},
                                     [this](int c, span<T> s) {
                                        spans.push_back({c, s});
                                        return c + s.size();
                                     });
      spans.push_back({c, {}});
   }
 
   template <typename U,
             typename
             = std::enable_if_t<std::is_convertible_v<U (*)[], T (*)[]>>>
   multi_span(const multi_span<U>&);
 
   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<T> first(index_type count) const
   // {
 
   // }
   // multi_span<T> last(index_type count) const
   // {
 
   // }
   // multi_span<T> subspan(index_type offset, index_type count = -1) const
   // {
   // if (count == -1) {
   // count = size() - offset;
   // }
 
   // }
 private:
   template <typename U>
   friend class multi_impl::mulspan_iterator;
   // invariant: holds one extra value, {size, {}}
   std::vector<multi_impl::subspan_t<T>> spans;
};
 
} // namespace KBLIB_NS
 
#endif
 
#endif // MULTI_SPAN_H