Quelle order.hpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019 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 some functionality for generating elements in the free
// monoid over an alphabet with a given number of letters up to a given length
// in a particular order.

// 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

namespace libsemigroups {
  //! Defined in ``order.hpp``.
  //!
  //! A stateless struct with binary call operator using
  //! [std::lexicographical_compare].
  //!
  //! This only exists to be used as a template parameter, and has no
  //! advantages over using [std::lexicographical_compare] otherwise.
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \sa
  //! [std::lexicographical_compare].
  //!
  //! [std::lexicographical_compare]:
  //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
  template <typename T>
  struct LexicographicalCompare {
    //! Call operator that compares \p x and \p y using
    //! [std::lexicographical_compare].
    //!
    //! \param x const reference to the first object for comparison
    //! \param y const reference to the second object for comparison
    //!
    //! \returns A `bool`.
    //!
    //! \exceptions
    //! See [std::lexicographical_compare].
    //!
    //! \complexity
    //! See [std::lexicographical_compare].
    //!
    //! [std::lexicographical_compare]:
    //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
    bool operator()(T const& x, T const& y) const {
      return std::lexicographical_compare(
          x.cbegin(), x.cend(), y.cbegin(), y.cend());
    }

    //! Call operator that compares iterators using
    //! [std::lexicographical_compare].
    //!
    //! \param first1 the start of the first object to compare
    //! \param last1 one beyond the end of the first object to compare
    //! \param first2 the start of the second object to compare
    //! \param last2 one beyond the end of the second object to compare
    //!
    //! \returns A `bool`.
    //!
    //! \exceptions
    //! See [std::lexicographical_compare].
    //!
    //! \complexity
    //! See [std::lexicographical_compare].
    //!
    //! [std::lexicographical_compare]:
    //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
    template <typename S>
    bool operator()(S first1, S last1, S first2, S last2) const {
      return std::lexicographical_compare(first1, last1, first2, last2);
    }
  };

  //! Compare two objects of the same type using
  //! [std::lexicographical_compare].
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! std::lexicographical_compare(
  //!   x.cbegin(), x.cend(), y.cbegin(), y.cend());
  //! \endcode
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \param x const reference to the first object for comparison
  //! \param y const reference to the second object for comparison
  //!
  //! \returns A `bool`.
  //!
  //! \exceptions
  //! See [std::lexicographical_compare].
  //!
  //! \complexity
  //! See [std::lexicographical_compare].
  //!
  //! [std::lexicographical_compare]:
  //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
  template <typename T>
  bool lexicographical_compare(T const& x, T const& y) {
    return std::lexicographical_compare(
        x.cbegin(), x.cend(), y.cbegin(), y.cend());
  }

  //! Compare two objects via their pointers using [lexicographical_compare].
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! lexicographical_compare(
  //!   x->cbegin(), x->cend(), y->cbegin(), y->cend());
  //! \endcode
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \param x pointer to the first object for comparison
  //! \param y pointer to the second object for comparison
  //!
  //! \returns A `bool`.
  //!
  //! \sa
  //! [std::lexicographical_compare].
  //!
  //! [std::lexicographical_compare]:
  //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
  template <typename T>
  bool lexicographical_compare(T* const x, T* const y) {
    return std::lexicographical_compare(
        x->cbegin(), x->cend(), y->cbegin(), y->cend());
  }

  //! Compare two objects of the same type using the short-lex reduction
  //! ordering.
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! template <typename T, typename S>
  //! bool shortlex_compare(T const& first1,
  //!                       T const& last1,
  //!                       S const& first2,
  //!                       S const& last2) {
  //!   return (last1 - first1) < (last2 - first2)
  //!          || ((last1 - first1) == (last2 - first2)
  //!              && std::lexicographical_compare
  //!                   (first1, last1, first2, last2));
  //! }
  //! \endcode
  //!
  //! \tparam T the type of iterators to the first object to be compared.
  //! \tparam S the type of iterators to the second object to be compared.
  //!
  //! \param first1 beginning iterator of first object for comparison.
  //! \param last1 ending iterator of first object for comparison.
  //! \param first2 beginning iterator of second object for comparison.
  //! \param last2 ending iterator of second object for comparison.
  //!
  //! \returns A `bool`.
  //!
  //! \exceptions
  //! Throws if [std::lexicographical_compare] does.
  //!
  //! \complexity
  //! At most \f$O(n)\f$ where \f$n\f$ is the minimum of the distance between
  //! \p last1 and \p first1, and the distance between \p last2 and \p first2.
  //!
  //! [std::lexicographical_compare]:
  //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
  template <typename T, typename S>
  bool shortlex_compare(T const& first1,
                        T const& last1,
                        S const& first2,
                        S const& last2) {
    return (last1 - first1) < (last2 - first2)
           || ((last1 - first1) == (last2 - first2)
               && std::lexicographical_compare(first1, last1, first2, last2));
  }

  //! Compare two objects of the same type using shortlex_compare.
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! shortlex_compare(
  //!   x.cbegin(), x.cend(), y.cbegin(), y.cend());
  //! \endcode
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \param x const reference to the first object for comparison
  //! \param y const reference to the second object for comparison
  //!
  //! \returns A `bool`.
  //!
  //! \sa shortlex_compare(T const, T const, S const, S const)
  template <typename T>
  bool shortlex_compare(T const& x, T const& y) {
    return shortlex_compare(x.cbegin(), x.cend(), y.cbegin(), y.cend());
  }

  //! Compare two objects via their pointers using shortlex_compare.
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! shortlex_compare(
  //!   x->cbegin(), x->cend(), y->cbegin(), y->cend());
  //! \endcode
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \param x pointer to the first object for comparison
  //! \param y pointer to the second object for comparison
  //!
  //! \returns A `bool`.
  //!
  //! \sa shortlex_compare(T const, T const, S const, S const)
  template <typename T>
  bool shortlex_compare(T* const x, T* const y) {
    return shortlex_compare(x->cbegin(), x->cend(), y->cbegin(), y->cend());
  }

  //! Defined in ``order.hpp``.
  //!
  //! A stateless struct with binary call operator using
  //! \ref shortlex_compare.
  //!
  //! This only exists to be used as a template parameter, and has no
  //! advantages over using \ref shortlex_compare otherwise.
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \sa
  //! shortlex_compare(T const, T const, S const, S const)
  template <typename T>
  struct ShortLexCompare {
    //! Call operator that compares \p x and \p y using
    //! \ref shortlex_compare.
    //!
    //! \param x const reference to the first object for comparison
    //! \param y const reference to the second object for comparison
    //!
    //! \returns A `bool`.
    //!
    //! \exceptions
    //! See shortlex_compare(T const, T const, S const, S const).
    //!
    //! \complexity
    //! See shortlex_compare(T const, T const, S const, S const).
    bool operator()(T const& x, T const& y) {
      return shortlex_compare(x.cbegin(), x.cend(), y.cbegin(), y.cend());
    }
  };

  //! Compare two objects of the same type using the recursive path comparison
  //! described in [Jan12](../biblio.html#Jantzen2012aa) (Definition 1.2.14,
  //! page 24).
  //!
  //! Defined in ``order.hpp``.
  //!
  //! If \f$u, v\in X ^ {*}\f$, \f$u \neq v\f$, and \f$u = a'u\f$,
  //! \f$v = bv'\f$ for some \f$a,b \in X\f$, \f$u',v'\in X ^ {*}\f$, then
  //! \f$u > v\f$ if one of the following conditions holds:
  //! 1. \f$a = b\f$ and \f$u' \geq v'\f$;
  //! 2. \f$a > b\f$ and \f$u  > v'\f$;
  //! 3. \f$b > a\f$ and \f$u' > v\f$.
  //!
  //! This documentation and the implementation of \ref recursive_path_compare
  //! is based on the source code of [Hol19](../biblio.html#Holt2019aa).
  //!
  //! \tparam T the type of iterators to the first object to be compared.
  //! \tparam S the type of iterators to the second object to be compared.
  //!
  //! \param first1 beginning iterator of first object for comparison.
  //! \param last1 ending iterator of first object for comparison.
  //! \param first2 beginning iterator of second object for comparison.
  //! \param last2 ending iterator of second object for comparison.
  //!
  //! \returns A `bool`.
  //!
  //! \exceptions
  //! \noexcept
  //!
  //! \warning
  //! This function has significantly worse performance than all
  //! the variants of \ref shortlex_compare
  //! and [std::lexicographical_compare].
  //!
  //! [std::lexicographical_compare]:
  //! https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
  template <typename T, typename S>
  bool recursive_path_compare(T const& first1,
                              T        last1,
                              S const& first2,
                              S        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;
      }
    }
  }

  //! Compare two objects of the same type using recursive_path_compare.
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! recursive_path_compare(
  //!   x.cbegin(), x.cend(), y.cbegin(), y.cend());
  //! \endcode
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \param x const reference to the first object for comparison
  //! \param y const reference to the second object for comparison
  //!
  //! \returns A `bool`.
  //!
  //! \exceptions
  //! \noexcept
  //!
  //! \sa recursive_path_compare(T const, T, S const, S)
  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());
  }

  //! Compare two objects via their pointers using recursive_path_compare.
  //!
  //! Defined in ``order.hpp``.
  //!
  //! \par Possible Implementation
  //! \code
  //! recursive_path_compare(
  //!   x->cbegin(), x->cend(), y->cbegin(), y->cend());
  //! \endcode
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \param x pointer to the first object for comparison
  //! \param y pointer to the second object for comparison
  //!
  //! \returns A `bool`.
  //!
  //! \exceptions
  //! \noexcept
  //!
  //! \sa recursive_path_compare(T const, T, S const, S)
  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());
  }

  //! Defined in ``order.hpp``.
  //!
  //! A stateless struct with binary call operator using
  //! \ref recursive_path_compare.
  //!
  //! This only exists to be used as a template parameter, and has no
  //! advantages over using \ref recursive_path_compare otherwise.
  //!
  //! \tparam T the type of the objects to be compared.
  //!
  //! \sa
  //! recursive_path_compare(T const, T const, S const, S const)
  template <typename T>
  struct RecursivePathCompare {
    //! Call operator that compares \p x and \p y using
    //! \ref recursive_path_compare.
    //!
    //! \param x const reference to the first object for comparison
    //! \param y const reference to the second object for comparison
    //!
    //! \returns A `bool`.
    //!
    //! \exceptions
    //! \noexcept
    bool operator()(T const& x, T const& y) noexcept {
      return recursive_path_compare(x.cbegin(), x.cend(), y.cbegin(), y.cend());
    }
  };
}  // namespace libsemigroups

#endif  // LIBSEMIGROUPS_ORDER_HPP_

quality92%

¤ Dauer der Verarbeitung: 0.15 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.