Quelle cong-intf.cpp 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/>.
//

#include "libsemigroups/cong-intf.hpp"

#include <algorithm>  // for remove_if

#include "libsemigroups/constants.hpp"          // for UNDEFINED
#include "libsemigroups/debug.hpp"              // for LIBSEMIGROUPS_ASSERT
#include "libsemigroups/exception.hpp"          // for LIBSEMIGROUPS_EXCEPTION
#include "libsemigroups/fpsemi-intf.hpp"        // for FpSemigroupInterface
#include "libsemigroups/froidure-pin-base.hpp"  // for FroidurePinBase
#include "libsemigroups/report.hpp"             // for REPORT_VERBOSE_DEFAULT
#include "libsemigroups/string.hpp"             // for detail::to_string

namespace libsemigroups {

  class CongruenceInterface::LazyFroidurePin {
   public:
    LazyFroidurePin() = default;

    void set(std::shared_ptr<FroidurePinBase> ptr) {
      LIBSEMIGROUPS_ASSERT(_froidure_pin == nullptr);
      LIBSEMIGROUPS_ASSERT(_fp_semigroup == nullptr);
      _froidure_pin = ptr;
    }

    void set(std::shared_ptr<FpSemigroupInterface> ptr) {
      LIBSEMIGROUPS_ASSERT(_froidure_pin == nullptr);
      LIBSEMIGROUPS_ASSERT(_fp_semigroup == nullptr);
      _fp_semigroup = ptr;
    }

    bool has_froidure_pin() const noexcept {
      return _froidure_pin != nullptr;
    }

    bool has_fpsemigroup() const noexcept {
      return _fp_semigroup != nullptr;
    }

    bool can_compute_froidure_pin() const noexcept {
      return _froidure_pin != nullptr || _fp_semigroup != nullptr;
    }

    std::shared_ptr<FroidurePinBase> froidure_pin() const {
      if (!has_froidure_pin()) {
        if (_fp_semigroup != nullptr
            && !_fp_semigroup->is_obviously_infinite()) {
          _froidure_pin = _fp_semigroup->froidure_pin();
        } else {
          // This can be the case if a CongruenceInterface is default
          // constructed, i.e. constructed neither from a FroidurePinBase
          // nor an FpSemigroupInterface, or the _fp_semigroup is obviously
          // infinite
          LIBSEMIGROUPS_EXCEPTION("no parent FroidurePin can be determined!");
        }
      }
      return _froidure_pin;
    }

    std::shared_ptr<FpSemigroupInterface> fpsemigroup() const {
      return _fp_semigroup;
    }

   private:
    mutable std::shared_ptr<FroidurePinBase>      _froidure_pin;
    mutable std::shared_ptr<FpSemigroupInterface> _fp_semigroup;
  };

  ////////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - constructors + destructor - public
  ////////////////////////////////////////////////////////////////////////////

  CongruenceInterface::CongruenceInterface(congruence_kind type)
      : Runner(),
        // Non-mutable
        _gen_pairs(),
        _nr_gens(UNDEFINED),
        _parent(std::make_shared<LazyFroidurePin>()),
        _type(type),
        // Mutable
        _init_ntc_done(),
        _is_obviously_finite(false),
        _is_obviously_infinite(false),
        _quotient(nullptr),
        _non_trivial_classes() {
    reset();
  }

  CongruenceInterface::~CongruenceInterface() = default;

  ////////////////////////////////////////////////////////////////////////////
  // Runner - non-pure virtual overridden function - public
  ////////////////////////////////////////////////////////////////////////////

  void CongruenceInterface::before_run() {
    if (number_of_generators() == UNDEFINED) {
      LIBSEMIGROUPS_EXCEPTION("no generators have been set!");
    }
  }

  ////////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-pure virtual methods - public
  ////////////////////////////////////////////////////////////////////////////

  tril CongruenceInterface::const_contains(word_type const& u,
                                           word_type const& v) const {
    validate_word(u);
    validate_word(v);
    if (u == v) {
      return tril::TRUE;
    }
    class_index_type uu, vv;
    try {
      uu = const_word_to_class_index(u);
      vv = const_word_to_class_index(v);
    } catch (LibsemigroupsException const& e) {
      REPORT_VERBOSE_DEFAULT("ignoring exception:\n%s", e.what());
      return tril::unknown;
    }
    if (uu == UNDEFINED || vv == UNDEFINED) {
      return tril::unknown;
    } else if (uu == vv) {
      return tril::TRUE;
    } else if (finished()) {
      return tril::FALSE;
    } else {
      return tril::unknown;
    }
  }

  void CongruenceInterface::set_number_of_generators(size_t n) {
    if (number_of_generators() != UNDEFINED) {
      if (number_of_generators() != n) {
        LIBSEMIGROUPS_EXCEPTION("cannot change the number of generators");
      } else {
        return;  // do nothing
      }
    } else if (n == 0) {
      LIBSEMIGROUPS_EXCEPTION("the number of generators must be non-zero!");
    } else if (started()) {
      LIBSEMIGROUPS_EXCEPTION(
          "cannot set the number of generator at this stage");
    }
    _nr_gens = n;
    set_number_of_generators_impl(n);
    reset();
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-virtual methods - public
  /////////////////////////////////////////////////////////////////////////

  void CongruenceInterface::add_pair(word_type const& u, word_type const& v) {
    if (started()) {
      LIBSEMIGROUPS_EXCEPTION(
          "cannot add further generating pairs at this stage");
    }
    validate_word(u);
    validate_word(v);
    if (u == v) {
      return;
    } else if (has_parent_froidure_pin()
               && parent_froidure_pin()->equal_to(u, v)) {
      return;
    }
    // Note that _gen_pairs might contain pairs of distinct words that
    // represent the same element of the parent semigroup (if any).
    _gen_pairs.emplace_back(u, v);
    add_pair_impl(u, v);
    reset();
  }

  word_type CongruenceInterface::class_index_to_word(class_index_type i) {
    if (number_of_generators() == UNDEFINED) {
      LIBSEMIGROUPS_EXCEPTION("no generators have been defined");
    } else if (i >= number_of_classes()) {
      LIBSEMIGROUPS_EXCEPTION("invalid class index, expected a value in the "
                              "range [0, %d), found %d",
                              number_of_classes(),
                              i);
    }
    return class_index_to_word_impl(i);
  }

  // Basic exception guarantee (since is_quotient_obviously_infinite() may
  // change the object).
  std::shared_ptr<FroidurePinBase>
  CongruenceInterface::quotient_froidure_pin() {
    if (_quotient != nullptr) {
      LIBSEMIGROUPS_ASSERT(kind() == congruence_kind::twosided);
      return _quotient;
    } else if (kind() != congruence_kind::twosided) {
      LIBSEMIGROUPS_EXCEPTION("the congruence must be two-sided");
    }
    _quotient = quotient_impl();
    _quotient->immutable(true);
    return _quotient;
  }

  bool CongruenceInterface::is_quotient_obviously_infinite() {
    // If has_parent_froidure_pin(), then that is either finite (and so this
    // is not obviously infinite), or infinite, which is undecidable in
    // general, so we leave the answer to this question to
    // is_quotient_obviously_infinite_impl in the derived class.
    if (number_of_generators() == UNDEFINED) {
      // If number_of_generators() is undefined, then there is no quotient yet,
      // and so it is not obviously infinite, or anything!
      REPORT_VERBOSE("not obviously infinite (no generators yet defined)");
      return false;
    } else if (has_quotient_froidure_pin()
               && quotient_froidure_pin()->finished()) {
      // If the quotient FroidurePin is fully enumerated, it must be
      // finite, and hence this is not (obviously) infinite.
      REPORT_VERBOSE("not obviously infinite (finite)");
      return false;
    } else if (has_parent_froidure_pin() && parent_froidure_pin()->finished()) {
      REPORT_VERBOSE("not obviously infinite (parent finite)");
      return false;
    } else if (is_quotient_obviously_infinite_impl()) {
      // The derived class of CongruenceInterface knows the quotient is
      // infinite
      return true;
    }
    REPORT_VERBOSE("the quotient is not obviously infinite . . .");
    return false;
  }

  bool CongruenceInterface::is_quotient_obviously_finite() {
    if ((has_quotient_froidure_pin() && quotient_froidure_pin()->finished())
        || (has_parent_froidure_pin() && parent_froidure_pin()->finished())
        || is_quotient_obviously_finite_impl()) {
      return true;
    }
    return false;
  }

  size_t CongruenceInterface::number_of_classes() {
    if (number_of_generators() == UNDEFINED) {
      return UNDEFINED;
    } else if (!finished() && is_quotient_obviously_infinite()) {
      return POSITIVE_INFINITY;
    }
    return number_of_classes_impl();
  }

  CongruenceInterface::class_index_type
  CongruenceInterface::word_to_class_index(word_type const& word) {
    // validate_word throws if number_of_generators is undefined.
    validate_word(word);
    return word_to_class_index_impl(word);
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-virtual methods - protected
  /////////////////////////////////////////////////////////////////////////

  void CongruenceInterface::set_parent_froidure_pin(
      std::shared_ptr<FroidurePinBase> prnt) {
    LIBSEMIGROUPS_ASSERT(!_parent->has_froidure_pin());
    LIBSEMIGROUPS_ASSERT(number_of_generators() == UNDEFINED
                         || prnt->number_of_generators()
                                == number_of_generators());
    LIBSEMIGROUPS_ASSERT(!finished());
    if (number_of_generators() == UNDEFINED) {
      set_number_of_generators(prnt->number_of_generators());
    }
    _parent->set(prnt);
    reset();
  }

  void CongruenceInterface::set_parent_froidure_pin(
      std::shared_ptr<FpSemigroupInterface> prnt) {
    LIBSEMIGROUPS_ASSERT(!_parent->has_froidure_pin());
    LIBSEMIGROUPS_ASSERT(number_of_generators() == UNDEFINED
                         || prnt->alphabet().size() == number_of_generators());
    LIBSEMIGROUPS_ASSERT(!finished());
    if (number_of_generators() == UNDEFINED && !prnt->alphabet().empty()) {
      set_number_of_generators(prnt->alphabet().size());
    }
    _parent->set(prnt);
    reset();
  }

  void CongruenceInterface::add_generators(size_t n) {
    if (n == 0) {
      return;
    } else if (started()) {
      LIBSEMIGROUPS_EXCEPTION("cannot add generators at this stage");
    }
    _nr_gens += n;
    add_generators_impl(_nr_gens);
    reset();
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-pure virtual methods - private
  /////////////////////////////////////////////////////////////////////////

  void CongruenceInterface::add_pair_impl(word_type const&, word_type const&) {}

  CongruenceInterface::class_index_type
  CongruenceInterface::const_word_to_class_index(word_type const&) const {
    return UNDEFINED;
  }

  void CongruenceInterface::set_number_of_generators_impl(size_t) {
    // do nothing
  }

  void CongruenceInterface::add_generators_impl(size_t) {
    // do nothing
  }

  std::shared_ptr<CongruenceInterface::non_trivial_classes_type const>
  CongruenceInterface::non_trivial_classes_impl() {
    if (!_parent->can_compute_froidure_pin()) {
      LIBSEMIGROUPS_EXCEPTION("Cannot determine the parent FroidurePin and so "
                              "cannot compute non-trivial classes!");
    }
    // The next line may trigger an infinite computation
    auto fp  = _parent->froidure_pin();
    auto ntc = non_trivial_classes_type(number_of_classes(),
                                        std::vector<word_type>());

    word_type w;
    for (size_t pos = 0; pos < fp->size(); ++pos) {
      fp->factorisation(w, pos);
      LIBSEMIGROUPS_ASSERT(word_to_class_index(w) < ntc.size());
      ntc[word_to_class_index(w)].push_back(w);
    }
    ntc.erase(std::remove_if(ntc.begin(),
                             ntc.end(),
                             [](std::vector<word_type> const& klass) -> bool {
                               return klass.size() <= 1;
                             }),
              ntc.end());
    return std::make_shared<non_trivial_classes_type>(ntc);
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-virtual methods - private
  /////////////////////////////////////////////////////////////////////////

  void CongruenceInterface::init_non_trivial_classes() {
    if (!_init_ntc_done) {
      _non_trivial_classes = non_trivial_classes_impl();
      _init_ntc_done       = true;
    }
  }

  void CongruenceInterface::reset() noexcept {
    // set_finished(false);
    _non_trivial_classes.reset();
    _init_ntc_done = false;
    _quotient.reset();
    _is_obviously_finite   = false;
    _is_obviously_infinite = false;
  }

  std::shared_ptr<FroidurePinBase>
  CongruenceInterface::parent_froidure_pin() const {
    return _parent->froidure_pin();
  }

  bool CongruenceInterface::has_parent_froidure_pin() const noexcept {
    return _parent->has_froidure_pin();
  }

  std::shared_ptr<FpSemigroupInterface>
  CongruenceInterface::parent_fpsemigroup() const {
    return _parent->fpsemigroup();
  }

  bool CongruenceInterface::has_parent_fpsemigroup() const noexcept {
    return _parent->has_fpsemigroup();
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-virtual methods - protected
  /////////////////////////////////////////////////////////////////////////

  bool CongruenceInterface::validate_letter(letter_type c) const {
    if (number_of_generators() == UNDEFINED) {
      LIBSEMIGROUPS_EXCEPTION("no generators have been defined");
    }
    return c < _nr_gens;
  }

  void CongruenceInterface::validate_word(word_type const& w) const {
    for (auto l : w) {
      // validate_letter throws if no generators are defined
      if (!validate_letter(l)) {
        LIBSEMIGROUPS_EXCEPTION(
            "letter index out of bounds in word %s, expected "
            "value in [0, %d), got %d",
            detail::to_string(w).c_str(),
            _nr_gens,
            l);
      }
    }
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - non-virtual static methods - protected
  /////////////////////////////////////////////////////////////////////////

  std::string const&
  CongruenceInterface::congruence_kind_to_string(congruence_kind typ) {
    switch (typ) {
      case congruence_kind::twosided:
        return STRING_TWOSIDED;
      case congruence_kind::left:
        return STRING_LEFT;
      case congruence_kind::right:
        return STRING_RIGHT;
      default:
        LIBSEMIGROUPS_EXCEPTION("incorrect type");
    }
  }

  /////////////////////////////////////////////////////////////////////////
  // CongruenceInterface - static data members - private
  /////////////////////////////////////////////////////////////////////////

  const std::string CongruenceInterface::STRING_TWOSIDED = "two-sided";
  const std::string CongruenceInterface::STRING_LEFT     = "left";
  const std::string CongruenceInterface::STRING_RIGHT    = "right";
}  // namespace libsemigroups

quality99%

¤ Dauer der Verarbeitung: 0.6 Sekunden ¤

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.