konieczny.cpp

//
// libsemigroups_pybind11
// Copyright (C) 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/>.
//

// libsemigroups headers
#include <libsemigroups/bmat-adapters.hpp>
#include <libsemigroups/bmat8.hpp>
#include <libsemigroups/konieczny.hpp>
#include <libsemigroups/matrix.hpp>
#include <libsemigroups/transf.hpp>

// pybind11. ..  .
#include <pybind11/pybind11.h>
#include <pybind11/stl.h>

// libsemigroups_pybind11. ..  .
#include "main.hpp"  // for init_konieczny

namespace libsemigroups {
  namespace py = pybind11;

  namespace {
    template <typename Element>
    void bind_konieczny(py::module& m, std::string const& name) {
      using Konieczny_ = Konieczny<Element>;

      std::string actual_name = "Konieczny" + name;

      py::class_<Konieczny_, Runner> thing(m,
                                           actual_name.c_str(),
                                           R"pbdoc(
The class :any:`Konieczny` implements Konieczny's algorithm as described
in Konieczny's article :cite:`Konieczny1994aa`. This algorithm is similar to
that of Lallement and McFadden from :cite:`Lallement1990aa`. It differs in
being applicable to subsemigroups of a non-regular semigroup, though is
essentially the same algorithm for elements which happen to be regular. A
:any:`Konieczny` instance is defined by a generating set, and the main
function is :any:`Runner.run`, which implements Konieczny's Algorithm. If
:any:`Runner.run` is invoked and :any:`Runner.finished` returns ``True``, then
the size, partial order of :math:`\mathscr{D}`-classes, and frames for each
:math:`\mathscr{D}`-class are known.

.. seealso:: :any:`Konieczny.DClass` and :any:`Runner`.

.. |name| replace:: :any:`Konieczny`

.. include:: ../../_static/runner_non_inherit.rst
)pbdoc");
      thing.def("__repr__", [](Konieczny_ const& self) {
        return to_human_readable_repr(self);
      });
      thing.def("__copy__",
                [](Konieczny_ const& self) { return Konieczny_(self); });
      thing.def(
          "copy",
          [](Konieczny_ const& self) { return Konieczny_(self); },
          R"pbdoc(
:sig=(self: Konieczny) -> Konieczny:
Copy a Konieczny.

:returns: A copy of the argument.
:rtype: Konieczny
)pbdoc");

      thing.def(py::init([](std::vector<Element> const& gens) {
                  return make<Konieczny>(gens);
                }),
                py::arg("gens"),
                R"pbdoc(
:sig=(self: Konieczny, gens: list[Element]) -> None:
:only-document-once:

Construct from generators.

This function constructs a :any:`Konieczny` instance generated by the specified
container of generators. There can be duplicate generators and although they do
not count as distinct elements, they do count as distinct generators. In other
words, the generators are precisely (a copy of) *gens* in the same order they
occur in *gens*.

:param gens: the generators represented by this.
:type gens: list[Element]

:raises LibsemigroupsError: if *gens* is empty.
:raises LibsemigroupsError:
  if the items in *gens* do not all have the same degree.
)pbdoc");

      thing.def("init",
                &Konieczny_::init,
                R"pbdoc(
:sig=(self: Konieczny) -> Konieczny:

Reinitialize an existing :any:`Konieczny` object.

This function re-initializes a :any:`Konieczny` instance so that it is in the
same (logical) state as if it had just been default-constructed.

:returns: ``self``.
:rtype: Konieczny
)pbdoc");

      // This constructor can't be used directly so isn't documented.
      thing.def(py::init<>(), R"pbdoc(
:sig=(self: Konieczny, gens: list[Element]) -> None:
:only-document-once:
)pbdoc");

      thing.def("add_generator",
                &Konieczny_::add_generator,
                py::arg("gen"),
                R"pbdoc(
:sig=(self: Konieczny, gen: Element) -> Konieczny:

Add a copy of an element to the generators.

It is possible, if perhaps not desirable, to add the same generator multiple
times.

:param gen: the generator to add.
:type gen: Element

:returns: *self*.
:rtype: Konieczny

:raises LibsemigroupsError:
  if the degree of *x* is incompatible with the existing degree.
:raises LibsemigroupsError: if :any:`started` returns ``True``.
)pbdoc");

      thing.def(
          "add_generators",
          [](Konieczny_&                 self,
             std::vector<Element> const& coll) -> Konieczny_& {
            konieczny::add_generators(self, coll);
            return self;
          },
          py::arg("coll"),
          R"pbdoc(
:sig=(self: Konieczny, coll: list[Element]) -> Konieczny:

Add collection of generators from a list.

See :any:`Konieczny.add_generator` for a detailed description.

:param coll: the collection of generators to add.
:type coll: list[Element]

:returns: *self*.
:rtype: Konieczny

:raises LibsemigroupsError:
    the degree of any item in *coll* is incompatible
    with the existing degree (if any).
:raises LibsemigroupsError:
   :any:`started` returns ``True``.
)pbdoc");
      thing.def(
          "current_D_classes",
          [](Konieczny_ const& self) {
            return py::make_iterator(self.cbegin_current_D_classes(),
                                     self.cend_current_D_classes());
          },
          R"pbdoc(
:sig=(self: Konieczny) -> collections.abc.Iterator[Konieczny.DClass]:

Returns an iterator yielding the :math:`\mathscr{D}`-classes.

This function does not trigger any enumeration; the iterator returned may be
invalidated by any call to a non-const member function of the
:any:`Konieczny` class.

:returns:
   An iterator.

:rtype:
   collections.abc.Iterator[Konieczny.DClass]
)pbdoc");
      thing.def(
          "D_classes",
          [](Konieczny_& self) {
            self.run();
            return py::make_iterator(self.cbegin_D_classes(),
                                     self.cend_D_classes());
          },
          R"pbdoc(
:sig=(self: Konieczny) -> collections.abc.Iterator[Konieczny.DClass]:

Returns an iterator yielding the :math:`\mathscr{D}`-classes of a
:any:`Konieczny` object. This function triggers a full enumeration.

:returns:
   An iterator yielding :math:`\mathscr{D}`-classes.

:rtype:
   collections.abc.Iterator[Konieczny.DClass]
)pbdoc");
      thing.def(
          "generators",
          [](Konieczny_ const& self) {
            return py::make_iterator(self.cbegin_generators(),
                                     self.cend_generators());
          },
          R"pbdoc(
:sig=(self: Konieczny) -> collections.abc.Iterator[Konieczny.DClass]:

Returns an iterator yielding the generators of a :any:`Konieczny` object.
This function does not trigger any enumeration; the iterator returned may be
invalidated by any call to a non-const member function of the
:any:`Konieczny` class.

:returns:
   An iterator yielding the generators.
:rtype: collections.abc.Iterator[Konieczny.DClass]
)pbdoc");
      thing.def(
          "current_regular_D_classes",
          [](Konieczny_ const& self) {
            return py::make_iterator(self.cbegin_current_regular_D_classes(),
                                     self.cend_current_regular_D_classes());
          },
          R"pbdoc(
:sig=(self: Konieczny) -> collections.abc.Iterator[Konieczny.DClass]:

Returns an iterator yielding the so-far enumerated regular
:math:`\mathscr{D}`-classes of a :any:`Konieczny` object. This function
does not trigger any enumeration; the iterator returned may be invalidated by
any call to a non-const member function of the :any:`Konieczny` class.

:returns:
   An iterator yielding regular :math:`\mathscr{D}`-classes.
:rtype: collections.abc.Iterator[Konieczny.DClass]
)pbdoc");
      thing.def("contains",
                &Konieczny_::contains,
                py::arg("x"),
                R"pbdoc(
:sig=(self: Konieczny, x: Element) -> bool:

Test membership of an element.

Returns ``True`` if *x* belongs to *self* and ``False`` if it does not.

:param x: a possible element.
:type x: Element

:returns:
  Whether or not *x* belongs to the semigroup represented by a
  :any:`Konieczny` object.
:rtype: bool
)pbdoc");
      thing.def("current_number_of_D_classes",
                &Konieczny_::current_number_of_D_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of :math:`\mathscr{D}`-classes.

:returns:
  The number of :math:`\mathscr{D}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_H_classes",
                &Konieczny_::current_number_of_H_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of :math:`\mathscr{H}`-classes.

:returns:
  The number of :math:`\mathscr{H}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_idempotents",
                &Konieczny_::current_number_of_idempotents,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of idempotents.

:returns:
  The number of idempotents so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_L_classes",
                &Konieczny_::current_number_of_L_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of :math:`\mathscr{L}`-classes.

:returns:
  The number of :math:`\mathscr{L}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_R_classes",
                &Konieczny_::current_number_of_R_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of regular :math:`\mathscr{R}`-classes.

:returns:
  The number of :math:`\mathscr{L}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_regular_D_classes",
                &Konieczny_::current_number_of_regular_D_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of regular :math:`\mathscr{D}`-classes

:returns:
  The number of regular :math:`\mathscr{D}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_regular_elements",
                &Konieczny_::current_number_of_regular_elements,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of regular elements.

:returns:
  The number of regular elements so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_regular_L_classes",
                &Konieczny_::current_number_of_regular_L_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of regular :math:`\mathscr{L}`-classes.

:returns:
  The number of regular :math:`\mathscr{L}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_number_of_regular_R_classes",
                &Konieczny_::current_number_of_regular_R_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current number of regular :math:`\mathscr{R}`-classes.

:returns:
  The number of regular :math:`\mathscr{R}`-classes so far enumerated.
:rtype:
   int
)pbdoc");
      thing.def("current_size",
                &Konieczny_::current_size,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the current size.

:returns: The number of elements so far enumerated.
:rtype: int

.. seealso::  :any:`Konieczny.size`.
)pbdoc");
      thing.def(
          "D_class_of_element",
          [](Konieczny_& self, Element const& x) ->
          typename Konieczny_::DClass& { return self.D_class_of_element(x); },
          py::arg("x"),
          R"pbdoc(
:sig=(self: Konieczny, x: Element) -> Konieczny.DClass:

Returns the :math:`\mathscr{D}`-class containing an element.

:param x: a possible element.
:type x: Element

:returns: The :any:`Konieczny.DClass` containing *x*.
:rtype: Konieczny.DClass

:raises LibsemigroupsError: if *x* does not belong to *self*.
)pbdoc",
          py::return_value_policy::reference_internal);

      thing.def("degree",
                &Konieczny_::degree,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the degree of elements. All elements of a :any:`Konieczny` must have
the same degree; this function returns that degree.

:returns: The degree of any (and all) elements.
:rtype: int
)pbdoc");
      thing.def("generator",
                &Konieczny_::generator,
                py::return_value_policy::reference_internal,
                py::arg("pos"),
                R"pbdoc(
:sig=(self: Konieczny, pos: int) -> Element:

Returns the generator given by an index.

This function returns the generator of *self* with index *pos*.

:param pos: the index of the generator.
:type pos: int

:returns: The generator with given index.
:rtype: Element

:raises LibsemigroupsError:
  if the value of *pos* is greater than :any:`number_of_generators()`.

:complexity: Constant.

.. seealso::
  :any:`Konieczny.add_generator` and :any:`Konieczny.add_generators`.
)pbdoc");
      thing.def("is_regular_element",
                &Konieczny_::is_regular_element,
                py::arg("x"),
                R"pbdoc(
:sig=(self: Konieczny, x: Element) -> bool:

Test regularity of an element.

This function returns ``True`` if *x* is a regular element
and ``False`` if it is not.

:param x: a possible element.
:type x: Element

:returns: Whether or not *x* belongs to *self*.
:rtype: bool
)pbdoc");
      thing.def("number_of_D_classes",
                &Konieczny_::number_of_D_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of :math:`\mathscr{D}`-classes.

:returns:
   The number of :math:`\mathscr{D}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("number_of_generators",
                &Konieczny_::number_of_generators,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of generators.

This function returns the number of generators given to *self*. Note that there
may be duplicate generators, and so *self* may have more generators than unique
generators.

:returns: The number of generators.
:rtype: int

.. seealso::
  :any:`Konieczny.add_generator` and :any:`Konieczny.add_generators`.
)pbdoc");
      thing.def("number_of_H_classes",
                &Konieczny_::number_of_H_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of :math:`\mathscr{H}`-classes.

:returns:
  The number of :math:`\mathscr{H}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("number_of_idempotents",
                &Konieczny_::number_of_idempotents,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of idempotents.

:returns:
  The number of idempotents.
:rtype:
   int
)pbdoc");
      thing.def("number_of_L_classes",
                &Konieczny_::number_of_L_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of :math:`\mathscr{L}`-classes.

:returns:
  The number of :math:`\mathscr{L}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("number_of_R_classes",
                &Konieczny_::number_of_R_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of :math:`\mathscr{R}`-classes.

:returns:
  The number of :math:`\mathscr{R}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("number_of_regular_D_classes",
                &Konieczny_::number_of_regular_D_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of regular :math:`\mathscr{D}`-classes.

:returns:
  The number of regular :math:`\mathscr{D}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("number_of_regular_elements",
                &Konieczny_::number_of_regular_elements,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of regular elements.

:returns:
  The number of regular elements.
:rtype:
   int
)pbdoc");
      thing.def("number_of_regular_L_classes",
                &Konieczny_::number_of_regular_L_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of regular :math:`\mathscr{L}`-classes.

:returns:
  The number of regular :math:`\mathscr{L}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("number_of_regular_R_classes",
                &Konieczny_::number_of_regular_R_classes,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the number of regular :math:`\mathscr{R}`-classes.

:returns:
  The number of regular :math:`\mathscr{R}`-classes.
:rtype:
   int
)pbdoc");
      thing.def("size",
                &Konieczny_::size,
                R"pbdoc(
:sig=(self: Konieczny) -> int:

Returns the size.

This function triggers a full enumeration.

:returns: The size.
:rtype: int

.. seealso::  :any:`current_size`.
)pbdoc");

      py::class_<typename Konieczny_::DClass> thing2(
          m,
          (actual_name + "DClass").c_str(),
          R"pbdoc(
Class representing a :math:`\mathscr{D}`-class.

The class :any:`Konieczny.DClass` represents a :math:`\mathscr{D}`-class via a frame as
computed in Konieczny's algorithm; see :cite:`Konieczny1994aa` for more
details. :any:`Konieczny.DClass` objects cannot be directly constructed; instead you
should obtain a :math:`\mathscr{D}`-class by calling
:any:`Konieczny.D_class_of_element`.

.. seealso::  :any:`Konieczny`.)pbdoc");

      thing2.def("__repr__", [](typename Konieczny_::DClass const& self) {
        return to_human_readable_repr<Element, KoniecznyTraits<Element>>(self);
      });

      // TODO(1) copy?

      thing2.def("__contains__",
                 [](typename Konieczny_::DClass& self, Element const& x) {
                   return self.contains(x);
                 });
      thing2.def(
          "contains",
          [](typename Konieczny_::DClass& self, Element const& x) {
            return self.contains(x);
          },
          py::arg("x"),
          R"pbdoc(
:sig=(self: Konieczny.DClass, x: Element) -> bool:

Test membership of an element.

Given an element *x*, this function returns whether *x* is an element of the
:math:`\mathscr{D}`-class represented by *self* . This function triggers the
computation of most of the frame for *self*, if it is not already known.

:param x: the element.
:type x: Element

:returns: Whether or not *x* belongs to the :math:`\mathscr{D}`-class.
:rtype: bool
      )pbdoc");
      thing2.def("is_regular_D_class",
                 &Konieczny_::DClass::is_regular_D_class,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> bool:

Test regularity of a :math:`\mathscr{D}`-class.

:returns:
   Whether or not the :math:`\mathscr{D}`-class is regular.
:rtype:
   bool
)pbdoc");
      thing2.def("number_of_idempotents",
                 &Konieczny_::DClass::number_of_idempotents,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> int:

Returns the number of idempotents. This function triggers the computation
of most of the frame for *self*, if it is not already known.

:returns: The number of idempotents in a :math:`\mathscr{D}`-class.
:rtype: int
)pbdoc");
      thing2.def("number_of_L_classes",
                 &Konieczny_::DClass::number_of_L_classes,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> int:

Returns the number of :math:`\mathscr{L}`-classes. This function
triggers the computation of most of the frame for *self*, if it is
not already known.

:returns:
   The number of :math:`\mathscr{L}`-classes.
:rtype:
   int
)pbdoc");
      thing2.def("number_of_R_classes",
                 &Konieczny_::DClass::number_of_R_classes,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> int:

Returns the number of :math:`\mathscr{R}`-classes. This function
triggers the computation of most of the frame for *self*, if it is
not already known.

:returns:
   The number of :math:`\mathscr{R}`-classes.
:rtype:
   int
)pbdoc");
      thing2.def("rep",
                 &Konieczny_::DClass::rep,
                 py::return_value_policy::reference_internal,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> Element:

Returns a representative of the :math:`\mathscr{D}`-class. The frame
used to represent :math:`\mathscr{D}`-classes depends on the choice of
representative. This function returns the representative used by a
:any:`Konieczny.DClass` instance. This may not be the same representative as
used to construct the instance, but is guaranteed to not change.

:returns:
   A representative of the :math:`\mathscr{D}`-class.
:rtype:
   Element
)pbdoc");
      thing2.def("size",
                 &Konieczny_::DClass::size,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> int:

Returns the size of a :math:`\mathscr{D}`-class. This function triggers
the computation of most of the frame for *self*, if it is not already
known.

:returns:
   The size of the :math:`\mathscr{D}`-class.
:rtype:
   int
)pbdoc");
      thing2.def("size_H_class",
                 &Konieczny_::DClass::size_H_class,
                 R"pbdoc(
:sig=(self: Konieczny.DClass) -> int:

Returns the size of the :math:`\mathscr{H}`-classes. This function
triggers the computation of most of the frame for *self*, if it is
not already known.

:returns:
   The size of any (and all) :math:`\mathscr{H}`-classes in the
   :math:`\mathscr{D}`-class.
:rtype:
   int
)pbdoc");
    }  // bind_konieczny
  }  // namespace

  void init_konieczny(py::module& m) {
    bind_konieczny<BMat8>(m, "BMat8");
    bind_konieczny<Transf<0, uint8_t>>(m, "Transf1");
    bind_konieczny<Transf<0, uint16_t>>(m, "Transf2");
    bind_konieczny<Transf<0, uint32_t>>(m, "Transf4");
    bind_konieczny<BMat<>>(m, "BMat");
    bind_konieczny<PPerm<0, uint8_t>>(m, "PPerm1");
    bind_konieczny<PPerm<0, uint16_t>>(m, "PPerm2");
    bind_konieczny<PPerm<0, uint32_t>>(m, "PPerm4");
  }

}  // namespace libsemigroups