//
// 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 nodes for a
// ToddCoxeterDigraph instance.
#include "libsemigroups/node-manager.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 nodes. There
// are two types of node, those that are "active" and those that are "free".
//
// If c is a node, then
// * _forwd[c] is the node that comes after c in the list,
// _forwd[the last node in the list] = UNDEFINED
//
// * _bckwd[c] is the node that comes before c in the list,
// _bckwd[_id_node] = _id_node
//
// If c is an active node, then _ident[c] = c.
//
// If c is a free node, then _ident[c] != c.
//
// We also store some special locations in the list:
//
// * _id_node: the first node, this never changes.
//
// * _current: is the node 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 node, even if the value changes
// during a function call.
//
// * _current_la: is similar to _current, and can be used independently of
// _current.
//
// * _last_active_node points to the final active node in the list.
//
// * _first_free_node points to the first free node in the list, if there
// are any, or is set to UNDEFINED if there aren't any. Otherwise,
// _first_free_node == _forwd[_last_active_node].
//
////////////////////////////////////////////////////////////////////////////////
namespace libsemigroups {
namespace detail {
////////////////////////////////////////////////////////////////////////
// Typedefs/aliases
////////////////////////////////////////////////////////////////////////
using node_type = NodeManager::node_type;
constexpr node_type NodeManager::_id_node;
////////////////////////////////////////////////////////////////////////
// Helper free function
////////////////////////////////////////////////////////////////////////
static inline node_type ff(node_type c, node_type d, node_type r) {
return (r == c ? d : (r == d ? c : r));
// return (r == c) * d + (r == d) * c + (r != c && r != d) * r;
}
////////////////////////////////////////////////////////////////////////
// NodeManager - constructors - public
////////////////////////////////////////////////////////////////////////
NodeManager::NodeManager()
:
// protected
_current(0),
_current_la(0),
// private - stats
_active(1),
_
defined(1),
_nodes_killed(0),
// private - settings
_growth_factor(2.0),
// private - data
_bckwd(1, 0),
_first_free_node(UNDEFINED),
_forwd(1,
static_cast<node_type>(UNDEFINED)),
_ident(1, 0),
_last_active_node(0) {}
NodeManager::~NodeManager() =
default;
NodeManager& NodeManager::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;
}
////////////////////////////////////////////////////////////////////////
// NodeManager - member functions - protected
////////////////////////////////////////////////////////////////////////
void NodeManager::add_active_nodes(size_t n) {
if (n > (node_capacity() - number_of_nodes_active())) {
size_t
const m = n - (node_capacity() - number_of_nodes_active());
add_free_nodes(m);
// add_free_nodes adds new free nodes to the start of the free list
_last_active_node = _forwd.size() - 1;
_first_free_node = _forwd[_last_active_node];
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_node] = _last_active_node;
_last_active_node = _first_free_node;
_first_free_node = _forwd[_last_active_node];
_ident[_last_active_node] = _last_active_node;
}
}
void NodeManager::add_free_nodes(size_t n) {
// We add n new free nodes at the end of the current list, and link them
// in as follows:
//
// 0 <-> ... <-> _last_active_node <-> old_capacity <-> new free node 1
// <-> ... <-> new free node n <-> old_first_free_node
// <-> remaining old free nodes
size_t
const old_capacity = _forwd.size();
node_type
const old_first_free_node = _first_free_node;
_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_node = old_capacity;
_forwd[_last_active_node] = _first_free_node;
_bckwd[_first_free_node] = _last_active_node;
if (old_first_free_node != UNDEFINED) {
_forwd[_forwd.size() - 1] = old_first_free_node;
_bckwd[old_first_free_node] = _forwd.size() - 1;
}
#ifdef LIBSEMIGROUPS_DEBUG
debug_validate_forwd_bckwd();
#endif
}
void NodeManager::erase_free_nodes() {
#ifdef LIBSEMIGROUPS_DEBUG
size_t sum = 0;
for (node_type c = _id_node; c != _first_free_node; c = _forwd[c]) {
LIBSEMIGROUPS_ASSERT(c < number_of_nodes_active());
sum += c;
}
LIBSEMIGROUPS_ASSERT(
sum == number_of_nodes_active() * (number_of_nodes_active() - 1) / 2);
std::vector<node_type> copy(_forwd.cbegin(),
_forwd.cbegin() + number_of_nodes_active());
std::sort(copy.begin(), copy.end());
LIBSEMIGROUPS_ASSERT(std::unique(copy.begin(), copy.end()) == copy.end());
#endif
_first_free_node = UNDEFINED;
_forwd.erase(_forwd.begin() + number_of_nodes_active(), _forwd.end());
_forwd[_last_active_node] = UNDEFINED;
_forwd.shrink_to_fit();
_bckwd.erase(_bckwd.begin() + number_of_nodes_active(), _bckwd.end());
_bckwd.shrink_to_fit();
_ident.erase(_ident.begin() + number_of_nodes_active(), _ident.end());
_ident.shrink_to_fit();
#ifdef LIBSEMIGROUPS_DEBUG
debug_validate_forwd_bckwd();
#endif
}
node_type NodeManager::new_active_node() {
if (_first_free_node == UNDEFINED) {
// There are no free nodes 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_nodes(growth_factor() * node_capacity());
}
add_active_nodes(1);
return _last_active_node;
}
void NodeManager::switch_nodes(node_type c, node_type d) {
LIBSEMIGROUPS_ASSERT(is_active_node(c) || is_active_node(d));
node_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_node(c)) {
_ident[d] = 0;
_ident[c] = c;
}
else if (!is_active_node(d)) {
_ident[c] = 0;
_ident[d] = d;
}
_current = ff(c, d, _current);
_last_active_node = ff(c, d, _last_active_node);
_first_free_node = ff(c, d, _first_free_node);
// 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_node(_last_active_node));
LIBSEMIGROUPS_ASSERT(!is_active_node(_first_free_node));
}
// The permutation p ^ -1 must map the active nodes to the [0, ..
// , number_of_nodes_active())
void NodeManager::apply_permutation(NodeManager::Perm& p) {
size_t
const n = p.size();
for (node_type i = 0; i < n; ++i) {
node_type current = i;
while (i != p[current]) {
size_t next = p[current];
switch_nodes(current, next);
p[current] = current;
current = next;
}
p[current] = current;
}
}
////////////////////////////////////////////////////////////////////////
// NodeManager - member functions - private
////////////////////////////////////////////////////////////////////////
void NodeManager::free_node(node_type c) {
_active--;
_nodes_killed++;
LIBSEMIGROUPS_ASSERT(is_active_node(c));
// If any "controls" point to <c>, move them back one in the list
LIBSEMIGROUPS_ASSERT(_current < _bckwd.size()
|| _current == _first_free_node);
_current = (c == _current ? _bckwd[_current] : _current);
LIBSEMIGROUPS_ASSERT(_current_la < _bckwd.size()
|| _current_la == _first_free_node);
_current_la = (c == _current_la ? _bckwd[_current_la] : _current_la);
if (c == _last_active_node) {
// Simply move the start of the free list back by 1
LIBSEMIGROUPS_ASSERT(_last_active_node < _bckwd.size());
_last_active_node = _bckwd[_last_active_node];
}
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_node;
LIBSEMIGROUPS_ASSERT(_last_active_node < _forwd.size());
if (_first_free_node != UNDEFINED) {
_bckwd[_first_free_node] = c;
}
_forwd[_last_active_node] = c;
}
_bckwd[c] = _last_active_node;
_first_free_node = c;
_ident[c] = _id_node;
}
// Basically free all nodes
void NodeManager::clear() {
_nodes_killed += (_active - 1);
_active = 1;
std::iota(_forwd.begin(), _forwd.end() - 1, 1);
_forwd.back() = UNDEFINED;
std::iota(_bckwd.begin() + 1, _bckwd.end(), 0);
std::fill(_ident.begin(), _ident.end(), 0);
if (_forwd.size() > 1) {
_first_free_node = 1;
}
else {
_first_free_node = UNDEFINED;
}
_last_active_node = 0;
_current = _id_node;
_current_la = _id_node;
}
#ifdef LIBSEMIGROUPS_DEBUG
////////////////////////////////////////////////////////////////////////
// NodeManager - member functions (debug only) - protected
////////////////////////////////////////////////////////////////////////
void NodeManager::debug_validate_forwd_bckwd()
const {
REPORT_DEBUG_DEFAULT(
"validating the doubly linked list of nodes...\n");
LIBSEMIGROUPS_ASSERT(_forwd.size() == _bckwd.size());
LIBSEMIGROUPS_ASSERT(_bckwd.size() == _ident.size());
node_type number_of_nodes = 0;
node_type e = _id_node;
while (e != _first_free_node) {
LIBSEMIGROUPS_ASSERT(e == _id_node || _forwd[_bckwd[e]] == e);
LIBSEMIGROUPS_ASSERT(_forwd[e] == _first_free_node
|| _bckwd[_forwd[e]] == e);
number_of_nodes++;
LIBSEMIGROUPS_ASSERT(is_active_node(_forwd[e])
|| _forwd[e] == _first_free_node);
e = _forwd[e];
}
while (e != UNDEFINED) {
LIBSEMIGROUPS_ASSERT(!is_active_node(e));
LIBSEMIGROUPS_ASSERT(_forwd[_bckwd[e]] == e);
LIBSEMIGROUPS_ASSERT(_forwd[e] == UNDEFINED || _bckwd[_forwd[e]] == e);
number_of_nodes++;
e = _forwd[e];
}
LIBSEMIGROUPS_ASSERT(number_of_nodes == _forwd.size());
LIBSEMIGROUPS_ASSERT(number_of_nodes == _bckwd.size());
LIBSEMIGROUPS_ASSERT(number_of_nodes == _ident.size());
REPORT_DEBUG_DEFAULT(
"...doubly linked list of nodes ok\n");
}
#endif
}
// namespace detail
}
// namespace libsemigroups
