Quelle freeband.cpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021 James D. Mitchell
//                    Tom D. Conti-Leslie
//                    Murray T. Whyte
//                    Reinis Cirpons
//
// 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/freeband.hpp"

#include <algorithm>    // for max_element
#include <cstddef>      // for size_t
#include <iterator>     // for distance, reverse_iterator
#include <type_traits>  // for decay_t, is_same
#include <vector>       // for vector

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

namespace libsemigroups {

  namespace {
    using level_edges_type = std::vector<std::vector<size_t>>;
    using left_type        = std::vector<size_t>;
    using right_type       = std::vector<size_t>;
    template <typename T>
    bool is_standardized(T first, T last) {
      size_t m = 0;
      for (auto it = first; it != last; ++it) {
        if (*it > m + 1) {
          return false;
        } else if (*it > m) {
          ++m;
        }
      }
      return true;
    }

    size_t content_size(word_type const& w) {
      // LIBSEMIGROUPS_ASSERT(is_standardized(w.cbegin(), w.cend()));
      return *std::max_element(w.cbegin(), w.cend()) + 1;
    }

    void standardize(word_type& x) {
      if (x.empty()) {
        return;
      }

      size_t              distinct_chars = 0;
      size_t const        N = *std::max_element(x.cbegin(), x.cend()) + 1;
      std::vector<size_t> lookup(N, N);
      lookup[x[0]] = 0;
      x[0]         = 0;
      for (size_t i = 1; i < x.size(); ++i) {
        if (lookup[x[i]] == N) {
          lookup[x[i]] = ++distinct_chars;
        }
        x[i] = lookup[x[i]];
      }
    }

    // Returns a vector `out` of indices in [0, last - first) or UNDEFINED,
    // where [i, i + out[i]) has content exactly k, and `out[i]` is the minimum
    // such value.
    //
    // Complexity O(last - first)

    template <typename T>
    void right(T first, T last, size_t const k, std::vector<size_t>& out) {
      // TODO(later) assertions
      static_assert(
          std::is_same<std::decay_t<T>,
                       typename word_type::const_iterator>::value
              || std::is_same<
                  std::decay_t<T>,
                  typename word_type::const_reverse_iterator>::value,
          "The template parameter must be a word_type::const_iterator or a "
          "word_type::const_reverse_iterator");

      out.clear();
      if (std::distance(first, last) == 0) {
        return;
      }
      T                   j            = first;
      size_t              content_size = 0;
      size_t const        N            = *std::max_element(first, last) + 1;
      std::vector<size_t> multiplicity(N + 2, 0);
      for (auto i = first; i != last; ++i) {
        if (i != first) {
          LIBSEMIGROUPS_ASSERT(multiplicity[*(i - 1)] != 0);
          --multiplicity[*(i - 1)];
          if (multiplicity[*(i - 1)] == 0) {
            --content_size;
          }
        }
        while (j < last && (multiplicity[*j] != 0 || content_size < k)) {
          if (multiplicity[*j] == 0) {
            ++content_size;
          }
          ++multiplicity[*j];
          ++j;
        }
        out.push_back(content_size == k ? size_t(std::distance(first, j)) - 1
                                        : UNDEFINED);
      }
    }

    template <typename T>
    void left(T first, T last, size_t const k, std::vector<size_t>& out) {
      right(std::reverse_iterator<T>(last),
            std::reverse_iterator<T>(first),
            k,
            out);
      std::reverse(out.begin(), out.end());
      for (auto& x : out) {
        if (x != UNDEFINED) {
          x = out.size() - x - 1;
        }
      }
    }

    // What types should we be using? I get that word_type is an alias to
    // std::vector<size_t>, but wouldn't using the vector be more useful,
    // since the output/input is not really a representation of a word.
    // Also the input i here will range from 0 to 3, so is it better
    // to assign it to a unsigned short or something?
    void count_sort(std::vector<word_type> const& level_edges,
                    word_type&                    index_list,
                    size_t                        i,
                    size_t                        radix) {
      // Could actually reuse an already existing count array
      word_type counts(radix + 1, 0);
      for (auto j : index_list) {
        if (level_edges[j][i] != UNDEFINED)
          counts[level_edges[j][i]]++;
        else
          counts[radix]++;
      }
      for (size_t j = 1; j < counts.size(); j++)
        counts[j] += counts[j - 1];
      // This can also be reused and doesn't even have to be initialized if we
      // reuse it.
      word_type result_index_list(index_list.size(), 0);
      for (auto j = index_list.rbegin(); j != index_list.rend(); j++) {
        if (level_edges[*j][i] != UNDEFINED) {
          counts[level_edges[*j][i]]--;
          result_index_list[counts[level_edges[*j][i]]] = *j;
        } else {
          counts[radix]--;
          result_index_list[counts[radix]] = *j;
        }
      }
      std::swap(result_index_list, index_list);
    }

    void radix_sort(std::vector<word_type> const& level_edges,
                    size_t                        alphabet_size,
                    std::vector<size_t>&          result_index_list,
                    std::vector<size_t>&          index_list) {
      LIBSEMIGROUPS_ASSERT(result_index_list.size() == level_edges.size());
      LIBSEMIGROUPS_ASSERT(index_list.size() == level_edges.size());

      std::fill(result_index_list.begin(), result_index_list.end(), 0);
      std::fill(index_list.begin(), index_list.end(), 0);

      for (size_t j = 0; j < index_list.size(); j++) {
        index_list[j] = j;
      }

      count_sort(level_edges, index_list, 0, index_list.size());
      count_sort(level_edges, index_list, 1, alphabet_size);
      count_sort(level_edges, index_list, 2, alphabet_size);
      count_sort(level_edges, index_list, 3, index_list.size());

      size_t c = 0;
      for (size_t j = 1; j < index_list.size(); j++) {
        if (level_edges[index_list[j]] != level_edges[index_list[j - 1]])
          c++;
        result_index_list[index_list[j]] = c;
      }
      result_index_list[index_list[0]] = 0;
    }

    void level_edges(word_type const&           w,
                     size_t const               k,
                     std::vector<size_t> const& rdx,
                     right_type const&          rightk,
                     left_type const&           leftk,
                     right_type const&          rightm,
                     left_type const&           leftm,
                     level_edges_type&          out) {
      size_t const n = w.size();
      LIBSEMIGROUPS_ASSERT(out.size() == 2 * n);
      std::fill(
          out.begin(),
          out.end(),
          std::vector<size_t>({UNDEFINED, UNDEFINED, UNDEFINED, UNDEFINED}));

      if (k == 1) {
        for (size_t i = 0; i < n; ++i) {
          out[i]     = {0, w.at(i), w.at(i), 0};
          out[i + n] = {0, w.at(i), w.at(i), 0};
        }
        return;
      }

      for (size_t i = 0; i < n; ++i) {
        if (rightk.at(i) != UNDEFINED) {
          out[i] = {rdx.at(i),
                    w.at(rightm.at(i) + 1),
                    w.at(leftm.at(rightk.at(i)) - 1),
                    rdx.at(rightk.at(i) + n)};
        }
        if (leftk.at(i) != UNDEFINED) {
          out[i + n] = {rdx.at(leftk.at(i)),
                        w.at(rightm.at(leftk.at(i)) + 1),
                        w.at(leftm.at(i) - 1),
                        rdx.at(i + n)};
        }
      }
    }
  }  // namespace

  bool freeband_equal_to(word_type const& x, word_type const& y) {
    if (x == y) {
      return true;
    }
    if (x.empty() || y.empty()) {
      // FIXME: Code segfaults without this check, its possible there is some
      // unsafe memory access further in the code.
      return false;
    }
    size_t N = content_size(x);
    if (N != content_size(y)) {
      return false;
    }
    word_type xy(x);
    xy.push_back(N);
    xy.insert(xy.end(), y.cbegin(), y.cend());
    standardize(xy);
    LIBSEMIGROUPS_ASSERT(xy.at(x.size())
                         == *std::max_element(xy.cbegin(), xy.cend()));
    N = content_size(xy);

    level_edges_type    lvldgs(2 * xy.size(), {0, 0, 0, 0});
    std::vector<size_t> rdx(2 * xy.size(), 0);
    std::vector<size_t> ndx(2 * xy.size(), 0);

    left_type  leftk;
    right_type rightk;
    left_type  leftm;
    right_type rightm;

    for (size_t k = 1; k < N; ++k) {
      std::swap(rightm, rightk);
      std::swap(leftm, leftk);

      right(xy.cbegin(), xy.cend(), k, rightk);
      left(xy.cbegin(), xy.cend(), k, leftk);
      level_edges(xy, k, rdx, rightk, leftk, rightm, leftm, lvldgs);
      radix_sort(lvldgs, N + 1, rdx, ndx);
    }

    return rdx[0] == rdx[x.size() + 1];
  }
}  // namespace libsemigroups

quality96%

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