cross.hh

Go to the documentation of this file.

#pragma once

#include <memory>

#include <boost/iterator/iterator_facade.hpp>

#include <vcsn/misc/tuple.hh>

namespace vcsn
{
  template <typename... Sequences>
  struct cross_sequences
  {
    using sequences_t = std::tuple<Sequences...>;

    template <std::size_t... I>
    using seq = vcsn::detail::index_sequence<I...>;

    static constexpr size_t size = sizeof...(Sequences);

    using indices_t = vcsn::detail::make_index_sequence<sizeof...(Sequences)>;

    template <typename Seq>
    using seq_t = std::remove_reference_t<Seq>;

    using value_type
      = std::tuple<typename seq_t<Sequences>::value_type...>;

    cross_sequences(sequences_t sequences)
      : sequences_(std::move(sequences))
    {}

    cross_sequences(Sequences... sequences)
      : sequences_(sequences...)
    {}

    using const_iterators_t
      = std::tuple<typename seq_t<Sequences>::const_iterator...>;

    using iterators_t
      = std::tuple<typename seq_t<Sequences>::iterator...>;

    template <typename ValueType,
              typename IteratorsType>
    struct cross_iterator
      : public boost::iterator_facade<
           cross_iterator<ValueType, IteratorsType>
         , ValueType
         , boost::forward_traversal_tag
         , ValueType // Reference.
        >
    {
      using iterators_type = IteratorsType;

      cross_iterator(const iterators_type& is,
                     const iterators_type& begins, const iterators_type& ends)
        : is_{is}
        , begins_{begins}
        , ends_{ends}
      {
        // If one of the ranges is empty, we are done already.
        if (empty())
          done_();
      }

      cross_iterator(const iterators_type& is, const iterators_type& ends)
        : cross_iterator{is, is, ends}
      {}

      template <typename OtherValue, typename OtherIterators>
      cross_iterator(cross_iterator<OtherValue, OtherIterators> const& that)
        : cross_iterator{that.is_, that.begins_, that.ends_}
      {}

      iterators_type is_;
      iterators_type begins_;
      iterators_type ends_;

      bool empty() const
      {
        return empty_(indices_t{});
      }

      void increment()
      {
        if (increment_() == -1)
          done_();
      }

      bool equal(const cross_iterator& that) const
      {
        return equal_(that, indices_t{});
      }

      value_type dereference() const
      {
        return dereference_(indices_t{});
      }

    private:
      friend class boost::iterator_core_access;

      template <std::size_t... I>
      bool empty_(seq<I...>) const
      {
        for (auto n: {(std::get<I>(begins_) == std::get<I>(ends_))...})
          if (n)
            return true;
        return false;
      }

      void done_()
      {
        is_ = ends_;
      }

      int increment_()
      {
        auto res = increment_(indices_t{});
        // Reset all the iterators that are before the first one that could
        // advance.
        if (res != -1)
          reset_up_to_(res);
        return res;
      }

      template <std::size_t... I>
      int increment_(seq<I...>)
      {
        int res = -1;
        using swallow = int[];
        (void) swallow
          {
            (res == -1
             && std::get<size-1-I>(is_) != std::get<size-1-I>(ends_)
             && ++std::get<size-1-I>(is_) != std::get<size-1-I>(ends_))
              ? res = size-1-I
              : 0
            ...
          };
        return res;
      }

      void reset_up_to_(int n)
      {
        reset_up_to_(n, indices_t{});
      }

      template <std::size_t... I>
      void reset_up_to_(size_t n, seq<I...>)
      {
        using swallow = int[];
        (void) swallow
          {
            (n < I
             && ((std::get<I>(is_) = std::get<I>(begins_)), true))...
          };
      }

      template <std::size_t... I>
      bool equal_(const cross_iterator& that, seq<I...>) const
      {
        for (auto n: {(std::get<I>(is_) == std::get<I>(that.is_))...})
          if (!n)
            return false;
        return true;
      }

      template <std::size_t... I>
      value_type dereference_(seq<I...>) const
      {
        return value_type{(*std::get<I>(is_))...};
      }
    };

    using iterator = cross_iterator<value_type, iterators_t>;

    using const_iterator = cross_iterator<const value_type, const_iterators_t>;

    const_iterator cbegin() const
    {
      auto res = cbegin_(indices_t{});
      return res;
    }

    const_iterator cend() const
    {
      return cend_(indices_t{});
    }

    const_iterator begin() const
    {
      return cbegin();
    }

    const_iterator end() const
    {
      return cend();
    }

    iterator begin()
    {
      auto res = begin_(indices_t{});
      return res;
    }

    iterator end()
    {
      return end_(indices_t{});
    }

    bool empty() const
    {
      return cbegin() == cend();
    }


  private:
    template <std::size_t... I>
    const_iterator cbegin_(seq<I...>) const
    {
      return {const_iterators_t{std::get<I>(sequences_).cbegin()...},
              const_iterators_t{std::get<I>(sequences_).cend()...}};
    }

    template <std::size_t... I>
    const_iterator cend_(seq<I...>) const
    {
      return {const_iterators_t{std::get<I>(sequences_).cend()...},
              const_iterators_t{std::get<I>(sequences_).cend()...}};
    }

    template <std::size_t... I>
    iterator begin_(seq<I...>)
    {
      return {iterators_t{std::get<I>(sequences_).begin()...},
              iterators_t{std::get<I>(sequences_).end()...}};
    }

    template <std::size_t... I>
    iterator end_(seq<I...>)
    {
      return {iterators_t{std::get<I>(sequences_).end()...},
              iterators_t{std::get<I>(sequences_).end()...}};
    }

    sequences_t sequences_;
  };

  template <typename... Sequences>
  cross_sequences<Sequences...>
  cross(Sequences&&... seqs)
  {
    return {std::forward<Sequences>(seqs)...};
  }

  template <typename... Sequences>
  cross_sequences<Sequences...>
  cross_tuple(const std::tuple<Sequences...>& seqs)
  {
    return {seqs};
  }
}