order.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2025 James D. Mitchell + James W. Swent
//
// 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 the declarations of several functions and structs
// defining linear orders on words.
 
// TODO
// * dry it out
// * noexcept
 
#ifndef LIBSEMIGROUPS_ORDER_HPP_
#define LIBSEMIGROUPS_ORDER_HPP_
 
#include <algorithm>         // for std::find_if, std::lexicographical_compare
#include <cstddef>           // for size_t
#include <cstdint>           // for uint8_t
#include <initializer_list>  // for initializer_list
#include <iterator>          // for distance
#include <numeric>           // for accumulate
#include <type_traits>       // for enable_if_t
#include <utility>           // for move
#include <vector>            // for vector
 
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "ranges.hpp"     // for shortlex_compare
 
namespace libsemigroups {
  enum class Order : uint8_t {
    none = 0,

    shortlex,

    lex,

    recursive
 
    // wreath TODO(later)
  };


  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool lexicographical_compare(Thing const& x, Thing const& y) {
    return std::lexicographical_compare(
        x.cbegin(), x.cend(), y.cbegin(), y.cend());
  }

  template <typename Thing>
  [[nodiscard]] bool lexicographical_compare(Thing* const x, Thing* const y) {
    return std::lexicographical_compare(
        x->cbegin(), x->cend(), y->cbegin(), y->cend());
  }

  struct LexicographicalCompare {
    template <typename Thing>
    [[nodiscard]] bool operator()(Thing const& x, Thing const& y) const {
      return lexicographical_compare(x, y);
    }

    // TODO(v4) is this really necessary?
    template <typename T>
    [[nodiscard]] bool operator()(std::initializer_list<T> x,
                                  std::initializer_list<T> y) const {
      return std::lexicographical_compare(
          x.begin(), x.end(), y.begin(), y.end());
    }

    // TODO(v4) remove this?
    template <typename Iterator>
    [[nodiscard]] bool operator()(Iterator first1,
                                  Iterator last1,
                                  Iterator first2,
                                  Iterator last2) const {
      return std::lexicographical_compare(first1, last1, first2, last2);
    }
  };

  template <typename Iterator,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
  [[nodiscard]] bool shortlex_compare(Iterator first1,
                                      Iterator last1,
                                      Iterator first2,
                                      Iterator last2) {
    return (last1 - first1) < (last2 - first2)
           || ((last1 - first1) == (last2 - first2)
               && std::lexicographical_compare(first1, last1, first2, last2));
  }

  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool shortlex_compare(Thing const& x, Thing const& y) {
    return shortlex_compare(x.cbegin(), x.cend(), y.cbegin(), y.cend());
  }

  template <typename Thing>
  [[nodiscard]] bool shortlex_compare(Thing* const x, Thing* const y) {
    return shortlex_compare(x->cbegin(), x->cend(), y->cbegin(), y->cend());
  }

  struct ShortLexCompare {
    template <typename Thing>
    [[nodiscard]] bool operator()(Thing const& x, Thing const& y) const {
      return shortlex_compare(x, y);
    }
  };

  template <typename Iterator,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
  [[nodiscard]] bool recursive_path_compare(Iterator first1,
                                            Iterator last1,
                                            Iterator first2,
                                            Iterator last2) noexcept;

  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool recursive_path_compare(Thing const& x,
                                            Thing const& y) noexcept {
    return recursive_path_compare(x.cbegin(), x.cend(), y.cbegin(), y.cend());
  }

  template <typename Thing>
  [[nodiscard]] bool recursive_path_compare(Thing* const x,
                                            Thing* const y) noexcept {
    return recursive_path_compare(
        x->cbegin(), x->cend(), y->cbegin(), y->cend());
  }

  struct RecursivePathCompare {
    template <typename Thing>
    [[nodiscard]] bool operator()(Thing const& x,
                                  Thing const& y) const noexcept {
      return recursive_path_compare(x, y);
    }
  };

  template <typename Iterator,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
  [[nodiscard]] bool
  wt_shortlex_compare_no_checks(Iterator                   first1,
                                Iterator                   last1,
                                Iterator                   first2,
                                Iterator                   last2,
                                std::vector<size_t> const& weights);

  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool
  wt_shortlex_compare_no_checks(Thing const&               x,
                                Thing const&               y,
                                std::vector<size_t> const& weights) {
    return wt_shortlex_compare_no_checks(
        x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);
  }

  template <typename Thing>
  [[nodiscard]] bool
  wt_shortlex_compare_no_checks(Thing* const               x,
                                Thing* const               y,
                                std::vector<size_t> const& weights) {
    return wt_shortlex_compare_no_checks(
        x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);
  }

  template <typename Iterator,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
  [[nodiscard]] bool wt_shortlex_compare(Iterator                   first1,
                                         Iterator                   last1,
                                         Iterator                   first2,
                                         Iterator                   last2,
                                         std::vector<size_t> const& weights);

  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool wt_shortlex_compare(Thing const&               x,
                                         Thing const&               y,
                                         std::vector<size_t> const& weights) {
    return wt_shortlex_compare(
        x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);
  }

  template <typename Thing>
  [[nodiscard]] bool wt_shortlex_compare(Thing* const               x,
                                         Thing* const               y,
                                         std::vector<size_t> const& weights) {
    return wt_shortlex_compare(
        x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);
  }

  struct WtShortLexCompare {
    static constexpr bool checks = true;

    static constexpr bool no_checks = false;

    WtShortLexCompare(std::vector<size_t> const& weights, bool should_check)
        : _weights(weights), _should_check(should_check) {}

    WtShortLexCompare& init(std::vector<size_t> const& weights,
                            bool                       should_check) {
      _weights      = weights;
      _should_check = should_check;
      return *this;
    }

    WtShortLexCompare(std::vector<size_t>&& weights, bool should_check)
        : _weights(std::move(weights)), _should_check(should_check) {}

    WtShortLexCompare& init(std::vector<size_t>&& weights, bool should_check) {
      _weights      = std::move(weights);
      _should_check = should_check;
      return *this;
    }

    template <typename Thing>
    [[nodiscard]] bool operator()(Thing const& x, Thing const& y) const {
      if (_should_check) {
        return wt_shortlex_compare(x, y, _weights);
      } else {
        return wt_shortlex_compare_no_checks(x, y, _weights);
      }
    }

    template <typename Thing>
    [[nodiscard]] bool call_no_checks(Thing const& x, Thing const& y) const {
      return wt_shortlex_compare_no_checks(x, y, _weights);
    }

    [[nodiscard]] bool should_check() const noexcept {
      return _should_check;
    }

    WtShortLexCompare& should_check(bool val) noexcept {
      _should_check = val;
      return *this;
    }

    [[nodiscard]] std::vector<size_t> const& weights() const noexcept {
      return _weights;
    }

    WtShortLexCompare& weights(std::vector<size_t> const& val) {
      _weights = val;
      return *this;
    }
 
   private:
    std::vector<size_t> _weights;
    bool                _should_check;
  };

  template <typename Iterator,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
  [[nodiscard]] bool
  wt_lex_compare_no_checks(Iterator                   first1,
                           Iterator                   last1,
                           Iterator                   first2,
                           Iterator                   last2,
                           std::vector<size_t> const& weights);

  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool
  wt_lex_compare_no_checks(Thing const&               x,
                           Thing const&               y,
                           std::vector<size_t> const& weights) {
    return wt_lex_compare_no_checks(
        x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);
  }

  template <typename Thing>
  [[nodiscard]] bool
  wt_lex_compare_no_checks(Thing* const               x,
                           Thing* const               y,
                           std::vector<size_t> const& weights) {
    return wt_lex_compare_no_checks(
        x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);
  }

  template <typename Iterator,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
  [[nodiscard]] bool wt_lex_compare(Iterator                   first1,
                                    Iterator                   last1,
                                    Iterator                   first2,
                                    Iterator                   last2,
                                    std::vector<size_t> const& weights);

  template <typename Thing,
            typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
  [[nodiscard]] bool wt_lex_compare(Thing const&               x,
                                    Thing const&               y,
                                    std::vector<size_t> const& weights) {
    return wt_lex_compare(x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);
  }

  template <typename Thing>
  [[nodiscard]] bool wt_lex_compare(Thing* const               x,
                                    Thing* const               y,
                                    std::vector<size_t> const& weights) {
    return wt_lex_compare(
        x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);
  }

  struct WtLexCompare {
    static constexpr bool checks = true;

    static constexpr bool no_checks = false;

    WtLexCompare(std::vector<size_t> const& weights, bool should_check)
        : _weights(weights), _should_check(should_check) {}

    WtLexCompare& init(std::vector<size_t> const& weights, bool should_check) {
      _weights      = std::move(weights);
      _should_check = should_check;
      return *this;
    }

    WtLexCompare(std::vector<size_t>&& weights, bool should_check)
        : _weights(std::move(weights)), _should_check(should_check) {}

    WtLexCompare& init(std::vector<size_t>&& weights, bool should_check) {
      _weights      = std::move(weights);
      _should_check = should_check;
      return *this;
    }

    template <typename Thing>
    [[nodiscard]] bool operator()(Thing const& x, Thing const& y) const {
      if (_should_check) {
        return wt_lex_compare(x, y, _weights);
      } else {
        return wt_lex_compare_no_checks(x, y, _weights);
      }
    }

    template <typename Thing>
    [[nodiscard]] bool call_no_checks(Thing const& x, Thing const& y) const {
      return wt_lex_compare_no_checks(x, y, _weights);
    }

    [[nodiscard]] bool should_check() const noexcept {
      return _should_check;
    }

    WtLexCompare& should_check(bool val) noexcept {
      _should_check = val;
      return *this;
    }

    [[nodiscard]] std::vector<size_t> const& weights() const noexcept {
      return _weights;
    }

    WtLexCompare& weights(std::vector<size_t> const& val) {
      _weights = val;
      return *this;
    }
 
   private:
    std::vector<size_t> _weights;
    bool                _should_check;
  };
 
  // end orders_group
 
}  // namespace libsemigroups
 
#include "order.tpp"
 
#endif  // LIBSEMIGROUPS_ORDER_HPP_