order.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-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/>.
//
 
// TODO(later)
// 1. add the others (recursive path words) from test-todd-coxeter.cpp
// 2. add some documentation
 
#ifndef LIBSEMIGROUPS_ORDER_HPP_
#define LIBSEMIGROUPS_ORDER_HPP_
 
#include <cstddef>  // for size_t
#include <vector>   // for vector
 
#include "ranges.hpp"  // for shortlex_compare
 
#include "ranges.hpp"
 
namespace libsemigroups {
  enum class Order : uint8_t {
    none = 0,

    shortlex,

    lex,

    recursive
 
    // wreath TODO(later)
  };


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

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

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

    template <typename T>
    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(v3) remove this?
    template <typename T>
    bool operator()(T first1, T last1, T first2, T last2) const {
      return std::lexicographical_compare(first1, last1, first2, last2);
    }
  };

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

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

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

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

  template <typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>
  bool recursive_path_compare(T const& first1,
                              T        last1,
                              T const& first2,
                              T        last2) noexcept {
    bool lastmoved = false;
    --last1;
    --last2;
    while (true) {
      if (last1 < first1) {
        if (last2 < first2) {
          return lastmoved;
        }
        return true;
      }
      if (last2 < first2) {
        return false;
      }
      if (*last1 == *last2) {
        last1--;
        last2--;
      } else if (*last1 < *last2) {
        last1--;
        lastmoved = false;
      } else if (*last2 < *last1) {
        last2--;
        lastmoved = true;
      }
    }
  }

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

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

  struct RecursivePathCompare {
    template <typename T>
    bool operator()(T const& x, T const& y) const noexcept {
      return recursive_path_compare(x, y);
    }
  };
 
  // end orders_group
 
}  // namespace libsemigroups
 
#endif  // LIBSEMIGROUPS_ORDER_HPP_