Quelle coset.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 the declaration for a class to manage cosets for a
// ToddCoxeter instance.

#ifndef LIBSEMIGROUPS_COSET_HPP_
#define LIBSEMIGROUPS_COSET_HPP_

#include <cstddef>  // for size_t
#include <cstdint>  // for uint32_t
#include <vector>   // for vector

#include "constants.hpp"  // for UNDEFINED
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT/DEBUG

namespace libsemigroups {
  namespace detail {
    class CosetManager {
     public:
      ////////////////////////////////////////////////////////////////////////
      // CosetManager - typedefs - public
      ////////////////////////////////////////////////////////////////////////

      //! Type of cosets stored in the table.
      using coset_type = uint32_t;
      using Perm       = std::vector<coset_type>;

      ////////////////////////////////////////////////////////////////////////
      // CosetManager - constructors + destructor - public
      ////////////////////////////////////////////////////////////////////////

      CosetManager();

      CosetManager(CosetManager const&) = default;
      CosetManager(CosetManager&&)      = default;

      CosetManager& operator=(CosetManager const&) = delete;
      CosetManager& operator=(CosetManager&&)      = delete;

      ~CosetManager();

      ////////////////////////////////////////////////////////////////////////
      // CosetManager - member functions - public
      ////////////////////////////////////////////////////////////////////////

      //! Returns the capacity of the coset table.
      //!
      //! \returns A value of type \c size_t.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      //!
      //! \par Parameters
      //! (None)
      // std::vector::size is noexcept
      inline size_t coset_capacity() const noexcept {
        return _forwd.size();
      }

      //! Returns the first free coset.
      //!
      //! \returns A value of type CosetManager::coset_type
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      //!
      //! \par Parameters
      //! (None)
      inline coset_type first_free_coset() const noexcept {
        return _first_free_coset;
      }

      //! Check if there are any free cosets.
      //!
      //! \returns A value of type \c bool.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      //!
      //! \par Parameters
      //! (None)
      inline bool has_free_cosets() const noexcept {
        return _first_free_coset != UNDEFINED;
      }

      //! Check if the given coset is active or not.
      //!
      //! \param c the coset to check.
      //!
      //! \returns A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except
      //!
      //! \complexity
      //! Constant
      // not noexcept since std::vector::operator[] isn't.
      inline bool is_active_coset(coset_type c) const {
        LIBSEMIGROUPS_ASSERT(c < _ident.size() || c == UNDEFINED);
        return c != UNDEFINED && _ident[c] == c;
      }

      //! Check if the given coset is valid.
      //!
      //! \param c the coset to check.
      //!
      //! \returns A value of type \c bool.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      inline bool is_valid_coset(coset_type c) const noexcept {
        return c < _forwd.size();
      }

      //! Returns the next active coset after the given coset.
      //!
      //! \param c the coset.
      //!
      //! \returns A value of type CosetManager::coset_type
      //!
      //! \exceptions
      //! \no_libsemigroups_except
      //!
      //! \complexity
      //! Constant
      // not noexcept since std::vector::operator[] isn't.
      inline coset_type next_active_coset(coset_type c) const {
        LIBSEMIGROUPS_ASSERT(is_active_coset(c));
        return _forwd[c];
      }

      //! Returns the number of active cosets.
      //!
      //! \returns A value of type \c size_t.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      //!
      //! \par Parameters
      //! (None)
      inline size_t number_of_cosets_active() const noexcept {
        return _active;
      }

      //! Returns the total number of cosets defined so far.
      //!
      //! \returns A value of type \c size_t.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      //!
      //! \par Parameters
      //! (None)
      inline size_t number_of_cosets_defined() const noexcept {
        return _defined;
      }

      //! Returns the total number of cosets that have been killed so far.
      //!
      //! \returns A value of type \c size_t.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      //!
      //! \par Parameters
      //! (None)
      inline size_t number_of_cosets_killed() const noexcept {
        return _cosets_killed;
      }

      //! Set the value of the growth factor setting.
      //!
      //! This setting is used to determine the factor by which the number of
      //! cosets in the table is increased, when more cosets are required.
      //!
      //! The default value of this setting is \c 2.0.
      //!
      //! \param val the new value of the setting.
      //!
      //! \returns A reference to \c *this.
      //!
      //! \throws LibsemigroupsException if \p val is less than \c 1.0.
      //!
      //! \complexity
      //! Constant
      CosetManager& growth_factor(float val);

      //! The current value of the growth factor setting.
      //!
      //! \parameters
      //! (None)
      //!
      //! \returns A value of type \c float.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant
      float growth_factor() const noexcept {
        return _growth_factor;
      }

     protected:
      ////////////////////////////////////////////////////////////////////////
      // CosetManager - member functions - protected
      ////////////////////////////////////////////////////////////////////////

      // not noexcept because free_coset isn't, and std::vector::operator[]
      // isn't.
      //! No doc
      inline void union_cosets(coset_type min, coset_type max) {
        LIBSEMIGROUPS_ASSERT(is_active_coset(min));
        LIBSEMIGROUPS_ASSERT(is_active_coset(max));
        LIBSEMIGROUPS_ASSERT(max > min);
        free_coset(max);
        // Leave a "forwarding address" so we know what <max> was identified
        // with
        _ident[max] = min;
      }

      // not noexcept since std::vector::operator[] isn't.
      //! No doc
      inline coset_type find_coset(coset_type c) const {
        LIBSEMIGROUPS_ASSERT(is_valid_coset(c));
        while (true) {
          coset_type d = _ident[c];
          if (d == c) {
            return d;
          }
          coset_type e = _ident[d];
          if (d == e) {
            return d;
          }
          _ident[c] = e;
          c         = e;
        }
        LIBSEMIGROUPS_ASSERT(is_active_coset(c));
        return c;
      }

      //! No doc
      void add_active_cosets(size_t);
      //! No doc
      void add_free_cosets(size_t);
      //! No doc
      void erase_free_cosets();
      //! No doc
      coset_type new_active_coset();
      //! No doc
      void switch_cosets(coset_type const, coset_type const);
      //! No doc
      void apply_permutation(Perm& p);

      // not noexcept since std::vector::operator[] isn't.
      void free_coset(coset_type const);

      ////////////////////////////////////////////////////////////////////////
      // CosetManager - data - protected
      ////////////////////////////////////////////////////////////////////////

      static constexpr coset_type _id_coset = 0;
      coset_type                  _current;
      coset_type                  _current_la;

     private:
      ////////////////////////////////////////////////////////////////////////
      // CosetManager - member functions - private
      ////////////////////////////////////////////////////////////////////////

      ////////////////////////////////////////////////////////////////////////
      // CosetManager - data - private
      ////////////////////////////////////////////////////////////////////////

      size_t                          _active;
      std::vector<coset_type>         _bckwd;
      size_t                          _cosets_killed;
      size_t                          _defined;
      coset_type                      _first_free_coset;
      std::vector<coset_type>         _forwd;
      float                           _growth_factor;
      mutable std::vector<coset_type> _ident;
      coset_type                      _last_active_coset;

#ifdef LIBSEMIGROUPS_DEBUG

     protected:
      ////////////////////////////////////////////////////////////////////////
      // CosetManager - member functions (debug only) - protected
      ////////////////////////////////////////////////////////////////////////
      void debug_validate_forwd_bckwd() const;
#endif
    };

  }  // namespace detail
}  // namespace libsemigroups

#endif  // LIBSEMIGROUPS_COSET_HPP_

quality96%

¤ Dauer der Verarbeitung: 0.8 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.