ranges.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2023-2025 James D. Mitchell
//
// 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 <http://www.gnu.org/licenses/>.
//
 
// This file contains declarations of some ranges (in the sense of rx-ranges)
// that augment those in rx-ranges.
 
#ifndef LIBSEMIGROUPS_RANGES_HPP_
#define LIBSEMIGROUPS_RANGES_HPP_
 
#include <algorithm>    // for is_sorted
#include <cstddef>      // for size_t
#include <functional>   // for less
#include <ostream>      // for operator<<, ostream
#include <random>       // for mt19937, random_device, uniform_int_distribution
#include <type_traits>  // for enable_if_t
#include <utility>      // for forward
 
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wshadow"
#pragma GCC diagnostic ignored "-Winline"
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#include <rx/ranges.hpp>  // for count, iterator_range
#pragma GCC diagnostic pop
 
#include "config.hpp"  // for LIBSEMIGROUPS_PARSED_BY_DOXYGEN
 
#include "detail/fmt.hpp"     // for fmt::join
#include "detail/string.hpp"  // for detail::to_string
 
namespace libsemigroups {


  // Custom ranges

  // TODO(2) this should be able to emit any number of random items not only
  // one.
  struct Random {
    Random() = default;

    Random(Random const&) = default;

    Random(Random&&) = default;

    Random& operator=(Random const&) = default;

    Random& operator=(Random&&) = default;
 
    template <typename InputRange>
    struct Range {
      using output_type = typename InputRange::output_type;
 
      // TODO(1) this is probably not correct, should depend on InputRange
      static constexpr bool is_finite = rx::is_finite_v<InputRange>;
      // TODO(1) this is probably not correct, should depend on InputRange
      static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
 
      bool                _at_end;
      InputRange          _input;
      mutable output_type _val;
      mutable bool        _val_set;
 
      explicit constexpr Range(InputRange&& input) noexcept
          : _at_end(false), _input(std::move(input)), _val(), _val_set(false) {}
 
      [[nodiscard]] output_type get() const noexcept;
 
      constexpr void next() noexcept {
        _at_end = true;
      }
 
      [[nodiscard]] constexpr bool at_end() const noexcept {
        return _at_end;
      }
 
      [[nodiscard]] constexpr size_t size_hint() const noexcept {
        if (!at_end()) {
          return 1;
        } else {
          return 0;
        }
      }
    };
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    template <typename InputRange>
    [[nodiscard]] constexpr auto operator()(InputRange&& input) const {
      using Inner = rx::get_range_type_t<InputRange>;
      return Range<Inner>(std::forward<InputRange>(input));
    }
#endif  // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
  };

  // Comparison functions

  template <typename Range, typename Compare>
  bool is_sorted(Range r, Compare&& comp);

  template <typename Range>
  bool is_sorted(Range r) {
    return std::is_sorted(r, std::less<>());
  }

  template <typename Range1, typename Range2>
  bool equal(Range1 r1, Range2 r2);

  template <typename Range1, typename Range2>
  bool lexicographical_compare(Range1 r1, Range2 r2);

  template <typename Range1, typename Range2>
  bool shortlex_compare(Range1 r1, Range2 r2);
 
  // TODO(1) recursive_path_compare?

  // Custom combinators

  template <typename S, typename T>
  auto chain(S const& x, T const& y) {
    return rx::chain(rx::iterator_range(x.cbegin(), x.cend()),
                     rx::iterator_range(y.cbegin(), y.cend()));
  }

  template <typename T>
  auto enumerate(T const& thing) {
    return rx::enumerate(rx::iterator_range(thing));
  }

  // String representation

  template <typename Range,
            typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
  std::ostream& operator<<(std::ostream& os, Range r);
 
}  // namespace libsemigroups
 
#include "ranges.tpp"
 
#endif  // LIBSEMIGROUPS_RANGES_HPP_