cross.hh

Go to the documentation of this file.

#ifndef VCSN_MISC_CROSS_HH
# define VCSN_MISC_CROSS_HH

# include <boost/iterator/iterator_facade.hpp>

# include <vcsn/misc/raise.hh> // pass
# 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 = typename std::remove_reference<Seq>::type;

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

    cross_sequences(const sequences_t& sequences)
      : sequences_(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
        >
    {
      using iterators_type = IteratorsType;

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

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

      iterators_type is_;
      iterators_type begins_;
      iterators_type ends_;

      cross_iterator& operator++()
      {
        if (next_() == -1)
          done_();
        return *this;
      }

      bool operator!=(const cross_iterator& that) const
      {
        return not_equal_(that, indices_t{});
      }

      value_type operator*() const
      {
        return dereference_(indices_t{});
      }

    private:
      friend class boost::iterator_core_access;

      void done_()
      {
        is_ = ends_;
      }

      int next_()
      {
        auto res = next_(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 next_(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::next(std::get<size-1-I>(is_)) != std::get<size-1-I>(ends_))
              ? ++std::get<size-1-I>(is_), 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 not_equal_(const cross_iterator& that, seq<I...>) const
      {
        for (auto n: {(std::get<I>(is_) != std::get<I>(that.is_))...})
          if (n)
            return true;
        return false;
      }

      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{});
    }

  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};
  }
}

#endif // !VCSN_MISC_CROSS_HH