Quelle coset.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/>.
//

// This file contains the implementation for a class to manage cosets for a
// ToddCoxeter instance.

#include "libsemigroups/coset.hpp"

#include <cstddef>  // for size_t
#include <numeric>  // for iota

#include "libsemigroups/debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "libsemigroups/exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION

#ifdef LIBSEMIGROUPS_DEBUG
#include "libsemigroups/report.hpp"  // for REPORT_DEBUG
#endif

////////////////////////////////////////////////////////////////////////////////
//
// We use these two vectors to implement a doubly-linked list of cosets. There
// are two types of coset, those that are "active" and those that are "free".
//
// If c is a coset, then
//   * _forwd[c] is the coset that comes after c in the list,
//     _forwd[the last coset in the list] = UNDEFINED
//
//   * _bckwd[c] is the coset that comes before c in the list,
//     _bckwd[_id_coset] = _id_coset
//
// If c is an active coset, then _ident[c] = c.
//
// If c is a free coset, then _ident[c] != c.
//
// We also store some special locations in the list:
//
//   * _id_coset:  the first coset, this never changes.
//
//   * _current:   is the coset which we are currently using for something in a
//     loop somewhere, the member functions of this class guarantee that
//     _current always points to an active coset, even if the value changes
//     during a function call.
//
//   * _current_la: is similar to _current, and can be used independently of
//     _current.
//
//   * _last_active_coset points to the final active coset in the list.
//
//   * _first_free_coset points to the first free coset in the list, if there
//     are any, or is set to UNDEFINED if there aren't any. Otherwise,
//     _first_free_coset == _forwd[_last_active_coset].
//
////////////////////////////////////////////////////////////////////////////////

namespace libsemigroups {
  namespace detail {

    ////////////////////////////////////////////////////////////////////////
    // Typedefs/aliases
    ////////////////////////////////////////////////////////////////////////

    using coset_type = CosetManager::coset_type;
    constexpr coset_type CosetManager::_id_coset;

    ////////////////////////////////////////////////////////////////////////
    // Helper free function
    ////////////////////////////////////////////////////////////////////////

    static inline coset_type ff(coset_type c, coset_type d, coset_type r) {
      return (r == c ? d : (r == d ? c : r));
      // return (r == c) * d + (r == d) * c + (r != c && r != d) * r;
    }

    ////////////////////////////////////////////////////////////////////////
    // CosetManager - constructors - public
    ////////////////////////////////////////////////////////////////////////

    CosetManager::CosetManager()
        :  // protected
          _current(0),
          _current_la(0),
          // private
          _active(1),
          _bckwd(1, 0),
          _cosets_killed(0),
          _defined(1),
          _first_free_coset(UNDEFINED),
          _forwd(1, static_cast<coset_type>(UNDEFINED)),
          _growth_factor(2.0),
          _ident(1, 0),
          _last_active_coset(0) {}

    CosetManager::~CosetManager() = default;

    CosetManager& CosetManager::growth_factor(float val) {
      if (val < 1.0) {
        LIBSEMIGROUPS_EXCEPTION("expected a value of at least 1.0, found %f",
                                val);
      }
      _growth_factor = val;
      return *this;
    }

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

    void CosetManager::add_active_cosets(size_t n) {
      if (n > (coset_capacity() - number_of_cosets_active())) {
        size_t const m = n - (coset_capacity() - number_of_cosets_active());
        add_free_cosets(m);
        // add_free_cosets adds new free cosets to the start of the free list
        _last_active_coset = _forwd.size() - 1;
        _first_free_coset  = _forwd[_last_active_coset];
        std::iota(_ident.begin() + (_ident.size() - m),
                  _ident.end(),
                  _ident.size() - m);
        _active += m;
        _defined += m;
        n -= m;
      }
      _active += n;
      _defined += n;
      for (; n > 0; --n) {
        _bckwd[_first_free_coset]  = _last_active_coset;
        _last_active_coset         = _first_free_coset;
        _first_free_coset          = _forwd[_last_active_coset];
        _ident[_last_active_coset] = _last_active_coset;
      }
    }

    void CosetManager::add_free_cosets(size_t n) {
      // We add n new free cosets at the end of the current list, and link them
      // in as follows:
      //
      // 0 <-> ... <-> _last_active_coset <-> old_capacity <-> new free coset 1
      //   <-> ... <-> new free coset n   <-> old_first_free_coset
      //   <-> remaining old free cosets
      size_t const     old_capacity         = _forwd.size();
      coset_type const old_first_free_coset = _first_free_coset;

      _forwd.resize(_forwd.size() + n, UNDEFINED);
      std::iota(
          _forwd.begin() + old_capacity, _forwd.end() - 1, old_capacity + 1);

      _bckwd.resize(_bckwd.size() + n, 0);
      std::iota(_bckwd.begin() + old_capacity + 1, _bckwd.end(), old_capacity);

      _ident.resize(_ident.size() + n, 0);

      _first_free_coset          = old_capacity;
      _forwd[_last_active_coset] = _first_free_coset;
      _bckwd[_first_free_coset]  = _last_active_coset;

      if (old_first_free_coset != UNDEFINED) {
        _forwd[_forwd.size() - 1]    = old_first_free_coset;
        _bckwd[old_first_free_coset] = _forwd.size() - 1;
      }
#ifdef LIBSEMIGROUPS_DEBUG
      debug_validate_forwd_bckwd();
#endif
    }

    void CosetManager::erase_free_cosets() {
#ifdef LIBSEMIGROUPS_DEBUG
      size_t sum = 0;
      for (coset_type c = _id_coset; c != _first_free_coset; c = _forwd[c]) {
        LIBSEMIGROUPS_ASSERT(c < number_of_cosets_active());
        sum += c;
      }
      LIBSEMIGROUPS_ASSERT(sum
                           == number_of_cosets_active()
                                  * (number_of_cosets_active() - 1) / 2);
      std::vector<coset_type> copy(_forwd.cbegin(),
                                   _forwd.cbegin() + number_of_cosets_active());
      std::sort(copy.begin(), copy.end());
      LIBSEMIGROUPS_ASSERT(std::unique(copy.begin(), copy.end()) == copy.end());
#endif
      _first_free_coset = UNDEFINED;
      _forwd.erase(_forwd.begin() + number_of_cosets_active(), _forwd.end());
      _forwd[_last_active_coset] = UNDEFINED;
      _forwd.shrink_to_fit();
      _bckwd.erase(_bckwd.begin() + number_of_cosets_active(), _bckwd.end());
      _bckwd.shrink_to_fit();
      _ident.erase(_ident.begin() + number_of_cosets_active(), _ident.end());
      _ident.shrink_to_fit();
#ifdef LIBSEMIGROUPS_DEBUG
      debug_validate_forwd_bckwd();
#endif
    }

    coset_type CosetManager::new_active_coset() {
      if (_first_free_coset == UNDEFINED) {
        // There are no free cosets to recycle: make new ones.
        // It seems to be marginally faster to make lots like this, than to
        // just make 1, in some examples, notably ToddCoxeter 040 (Walker 3).
        add_free_cosets(growth_factor() * coset_capacity());
      }
      add_active_cosets(1);
      return _last_active_coset;
    }

    void CosetManager::switch_cosets(coset_type c, coset_type d) {
      LIBSEMIGROUPS_ASSERT(is_active_coset(c) || is_active_coset(d));
      coset_type fc = _forwd[c], fd = _forwd[d], bc = _bckwd[c], bd = _bckwd[d];

      if (fc != d) {
        _forwd[d]  = fc;
        _bckwd[c]  = bd;
        _forwd[bd] = c;
        if (fc != UNDEFINED) {
          _bckwd[fc] = d;
        }
      } else {
        _forwd[d] = c;
        _bckwd[c] = d;
      }

      if (fd != c) {
        _forwd[c]  = fd;
        _bckwd[d]  = bc;
        _forwd[bc] = d;
        if (fd != UNDEFINED) {
          _bckwd[fd] = c;
        }
      } else {
        _forwd[c] = d;
        _bckwd[d] = c;
      }

      if (!is_active_coset(c)) {
        _ident[d] = 0;
        _ident[c] = c;
      } else if (!is_active_coset(d)) {
        _ident[c] = 0;
        _ident[d] = d;
      }

      _current           = ff(c, d, _current);
      _last_active_coset = ff(c, d, _last_active_coset);
      _first_free_coset  = ff(c, d, _first_free_coset);
      // This is never called from lookahead so we don't have to update
      // _current_la, also it might be that we are calling this after
      // everything is finished and so _current may not be active.

      LIBSEMIGROUPS_ASSERT(is_active_coset(_last_active_coset));
      LIBSEMIGROUPS_ASSERT(!is_active_coset(_first_free_coset));
    }

    // The permutation p ^ -1 must map the active cosets to the [0, ..
    // , number_of_cosets_active())
    void CosetManager::apply_permutation(CosetManager::Perm& p) {
      size_t const n = p.size();
      for (coset_type i = 0; i < n; ++i) {
        coset_type current = i;
        while (i != p[current]) {
          size_t next = p[current];
          switch_cosets(current, next);
          p[current] = current;
          current    = next;
        }
        p[current] = current;
      }
    }

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

    void CosetManager::free_coset(coset_type c) {
      _active--;
      _cosets_killed++;
      LIBSEMIGROUPS_ASSERT(is_active_coset(c));
      // If any "controls" point to <c>, move them back one in the list
      LIBSEMIGROUPS_ASSERT(_current < _bckwd.size()
                           || _current == _first_free_coset);
      _current = (c == _current ? _bckwd[_current] : _current);
      LIBSEMIGROUPS_ASSERT(_current_la < _bckwd.size()
                           || _current_la == _first_free_coset);
      _current_la = (c == _current_la ? _bckwd[_current_la] : _current_la);

      if (c == _last_active_coset) {
        // Simply move the start of the free list back by 1
        LIBSEMIGROUPS_ASSERT(_last_active_coset < _bckwd.size());
        _last_active_coset = _bckwd[_last_active_coset];
      } else {
        LIBSEMIGROUPS_ASSERT(_forwd[c] != UNDEFINED);
        // Remove <c> from the active list
        _bckwd[_forwd[c]] = _bckwd[c];
        _forwd[_bckwd[c]] = _forwd[c];
        // Add <c> to the start of the free list
        _forwd[c] = _first_free_coset;
        LIBSEMIGROUPS_ASSERT(_last_active_coset < _forwd.size());
        if (_first_free_coset != UNDEFINED) {
          _bckwd[_first_free_coset] = c;
        }
        _forwd[_last_active_coset] = c;
      }
      _bckwd[c]         = _last_active_coset;
      _first_free_coset = c;
      _ident[c]         = _id_coset;
    }

#ifdef LIBSEMIGROUPS_DEBUG
    ////////////////////////////////////////////////////////////////////////
    // CosetManager - member functions (debug only) - protected
    ////////////////////////////////////////////////////////////////////////

    void CosetManager::debug_validate_forwd_bckwd() const {
      REPORT_DEBUG_DEFAULT("validating the doubly linked list of cosets...\n");
      LIBSEMIGROUPS_ASSERT(_forwd.size() == _bckwd.size());
      LIBSEMIGROUPS_ASSERT(_bckwd.size() == _ident.size());
      coset_type number_of_cosets = 0;
      coset_type e                = _id_coset;
      while (e != _first_free_coset) {
        LIBSEMIGROUPS_ASSERT(e == _id_coset || _forwd[_bckwd[e]] == e);
        LIBSEMIGROUPS_ASSERT(_forwd[e] == _first_free_coset
                             || _bckwd[_forwd[e]] == e);
        number_of_cosets++;
        LIBSEMIGROUPS_ASSERT(is_active_coset(_forwd[e])
                             || _forwd[e] == _first_free_coset);
        e = _forwd[e];
      }
      while (e != UNDEFINED) {
        LIBSEMIGROUPS_ASSERT(!is_active_coset(e));
        LIBSEMIGROUPS_ASSERT(_forwd[_bckwd[e]] == e);
        LIBSEMIGROUPS_ASSERT(_forwd[e] == UNDEFINED || _bckwd[_forwd[e]] == e);
        number_of_cosets++;
        e = _forwd[e];
      }
      LIBSEMIGROUPS_ASSERT(number_of_cosets == _forwd.size());
      LIBSEMIGROUPS_ASSERT(number_of_cosets == _bckwd.size());
      LIBSEMIGROUPS_ASSERT(number_of_cosets == _ident.size());
      REPORT_DEBUG_DEFAULT("...doubly linked list of cosets ok\n");
    }
#endif
  }  // namespace detail
}  // namespace libsemigroups

quality76%

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