Quelle test-ukkonen.cpp Sprache: C

// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021-2023 James D. Mitchell + Maria Tsalakou
//
// 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 <algorithm>  // for count_if, all_of
#include <cstddef>    // for size_t
#include <tuple>      // for tie
#include <utility>    // for pair
#include <vector>     // for vector

#include "catch.hpp"      // for REQUIRE, REQUIRE_THROWS_AS
#include "test-main.hpp"  // for LIBSEMIGROUPS_TEST_CASE

#include "libsemigroups/constants.hpp"  // for operator==, POSITIVE_INFINITY
#include "libsemigroups/exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "libsemigroups/int-range.hpp"  // for IntegralRange
#include "libsemigroups/types.hpp"      // for word_type
#include "libsemigroups/ukkonen.hpp"    // for Ukkonen, Ukkonen::State
#include "libsemigroups/wislo.hpp"      // for const_wislo_iterator, cbegi...
#include "libsemigroups/word.hpp"       // for literals

namespace libsemigroups {

  using literals::operator""_w;

  namespace {
    // TODO Should really be just a use of presentation::longest_common_subword
    auto best_subword(Ukkonen& u) {
      ukkonen::detail::GreedyReduceHelper helper(u);
      return ukkonen::dfs(u, helper);
    }
  }  // namespace

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "000", "basic tests", "[quick][ukkonen]") {
    Ukkonen t;
    // aaeaaa$
    // abcd$'
    // a -> 0
    // b -> 1
    // c -> 2
    // d -> 3
    // e -> 4
    t.add_word(004000_w);
    REQUIRE(t.nodes().size() == 10);

    REQUIRE(ukkonen::is_subword(t, 004000_w));
    REQUIRE(ukkonen::is_subword(t, 04_w));
    REQUIRE(!ukkonen::is_subword(t, 44_w));
    REQUIRE(ukkonen::is_subword(t, ""_w));
    REQUIRE(ukkonen::is_subword(t, 0_w));
    REQUIRE(ukkonen::is_subword(t, 00_w));
    REQUIRE(ukkonen::is_subword(t, 000_w));
    REQUIRE(ukkonen::is_subword(t, 000_w));
    REQUIRE(!ukkonen::is_subword(t, 0000_w));
    REQUIRE(!ukkonen::is_subword(t, 1_w));
    REQUIRE(ukkonen::number_of_distinct_subwords(t) == 16);
    REQUIRE(cbegin_wislo(5, {}, 0000000_w)->empty());
    REQUIRE(std::count_if(
                cbegin_wislo(6, {}, 00000000_w),
                cend_wislo(6, {}, 00000000_w),
                [&t](word_type const& w) { return ukkonen::is_subword(t, w); })
            == 16);

    REQUIRE(ukkonen::is_subword(t, ""_w));  // 1
    REQUIRE(ukkonen::is_subword(t, 004000_w));
    REQUIRE(ukkonen::is_subword(t, 00400_w));
    REQUIRE(ukkonen::is_subword(t, 0040_w));
    REQUIRE(ukkonen::is_subword(t, 004_w));  // 5
    REQUIRE(ukkonen::is_subword(t, 00_w));
    REQUIRE(ukkonen::is_subword(t, 0_w));
    REQUIRE(ukkonen::is_subword(t, 04000_w));
    REQUIRE(ukkonen::is_subword(t, 0400_w));
    REQUIRE(ukkonen::is_subword(t, 040_w));  // 10
    REQUIRE(ukkonen::is_subword(t, 04_w));
    REQUIRE(ukkonen::is_subword(t, 4000_w));
    REQUIRE(ukkonen::is_subword(t, 400_w));
    REQUIRE(ukkonen::is_subword(t, 40_w));
    REQUIRE(ukkonen::is_subword(t, 4_w));    // 15
    REQUIRE(ukkonen::is_subword(t, 000_w));  // 16

    t.add_word(0123_w);
    REQUIRE(t.nodes().size() == 15);

    REQUIRE(ukkonen::is_subword(t, ""_w));  // 1
    REQUIRE(ukkonen::is_subword(t, 004000_w));
    REQUIRE(ukkonen::is_subword(t, 00400_w));
    REQUIRE(ukkonen::is_subword(t, 0040_w));
    REQUIRE(ukkonen::is_subword(t, 004_w));  // 5
    REQUIRE(ukkonen::is_subword(t, 00_w));
    REQUIRE(ukkonen::is_subword(t, 0_w));
    REQUIRE(ukkonen::is_subword(t, 04000_w));
    REQUIRE(ukkonen::is_subword(t, 0400_w));
    REQUIRE(ukkonen::is_subword(t, 040_w));  // 10
    REQUIRE(ukkonen::is_subword(t, 04_w));
    REQUIRE(ukkonen::is_subword(t, 4000_w));
    REQUIRE(ukkonen::is_subword(t, 400_w));
    REQUIRE(ukkonen::is_subword(t, 40_w));
    REQUIRE(ukkonen::is_subword(t, 4_w));    // 15
    REQUIRE(ukkonen::is_subword(t, 000_w));  // 16

    REQUIRE(ukkonen::is_subword(t, 01_w));
    REQUIRE(ukkonen::is_subword(t, 012_w));
    REQUIRE(ukkonen::is_subword(t, 0123_w));
    REQUIRE(ukkonen::is_subword(t, 1_w));
    REQUIRE(ukkonen::is_subword(t, 12_w));
    REQUIRE(ukkonen::is_subword(t, 123_w));
    REQUIRE(ukkonen::is_subword(t, 2_w));
    REQUIRE(ukkonen::is_subword(t, 23_w));
    REQUIRE(ukkonen::is_subword(t, 3_w));

    REQUIRE(!ukkonen::is_subword(t, 33_w));
    REQUIRE(!ukkonen::is_subword(t, "ab"));
    REQUIRE(!ukkonen::is_subword(t, std::string("ab")));
    REQUIRE(!ukkonen::is_subword_no_checks(t, 33_w));
    REQUIRE(!ukkonen::is_subword_no_checks(t, "ab"));
    REQUIRE(!ukkonen::is_subword_no_checks(t, std::string("ab")));
    REQUIRE_THROWS_AS(ukkonen::is_subword(t, word_type({UNDEFINED})),
                      LibsemigroupsException);

    REQUIRE(ukkonen::number_of_distinct_subwords(t) == 25);

    REQUIRE(!ukkonen::is_suffix(t, 1235_w));
    REQUIRE(ukkonen::is_suffix(t, 123_w));

    REQUIRE(ukkonen::is_suffix(t, ""_w));
    REQUIRE(ukkonen::is_suffix(t, 004000_w));
    REQUIRE(ukkonen::is_suffix(t, 04000_w));
    REQUIRE(ukkonen::is_suffix(t, 4000_w));
    REQUIRE(ukkonen::is_suffix(t, 000_w));
    REQUIRE(ukkonen::is_suffix(t, 00_w));
    REQUIRE(ukkonen::is_suffix(t, 0_w));
    REQUIRE(ukkonen::is_suffix(t, 0123_w));
    REQUIRE(ukkonen::is_suffix(t, 123_w));
    REQUIRE(ukkonen::is_suffix(t, 23_w));
    REQUIRE(ukkonen::is_suffix(t, 3_w));
    REQUIRE(!ukkonen::is_suffix(t, 33_w));
    REQUIRE(!ukkonen::is_suffix(t, "ab"));
    REQUIRE_THROWS_AS(ukkonen::is_suffix(t, word_type({UNDEFINED})),
                      LibsemigroupsException);
    REQUIRE(!ukkonen::is_suffix(t, std::string("ab")));
    REQUIRE(!ukkonen::is_suffix_no_checks(t, 33_w));
    REQUIRE(!ukkonen::is_suffix_no_checks(t, "ab"));
    REQUIRE(!ukkonen::is_suffix_no_checks(t, std::string("ab")));

    REQUIRE(std::count_if(
                cbegin_wislo(5, {}, 0000000_w),
                cend_wislo(5, {}, 0000000_w),
                [&t](word_type const& w) { return ukkonen::is_suffix(t, w); })
            == 11);

    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 004000_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 0123_w) == 1);
    REQUIRE_THROWS_AS(
        ukkonen::length_maximal_piece_prefix(t, word_type({UNDEFINED})),
        LibsemigroupsException);

    REQUIRE(ukkonen::length_maximal_piece_prefix(t, "ab") == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, std::string("ab")) == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 00043456_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 0123456_w) == 1);
    REQUIRE(ukkonen::length_maximal_piece_prefix_no_checks(t, "ab") == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix_no_checks(t, std::string("ab"))
            == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix_no_checks(t, 00043456_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_prefix_no_checks(t, 0123456_w) == 1);

    REQUIRE(*ukkonen::maximal_piece_prefix(t, "ab") == 'a');
    REQUIRE(*ukkonen::maximal_piece_prefix(t, std::string("ab")) == 'a');
    REQUIRE(*ukkonen::maximal_piece_prefix(t, 00043456_w) == 0);
    REQUIRE(*ukkonen::maximal_piece_prefix(t, 0123456_w) == 1);
    REQUIRE(*ukkonen::maximal_piece_prefix_no_checks(t, "ab") == 'a');
    REQUIRE(*ukkonen::maximal_piece_prefix_no_checks(t, std::string("ab"))
            == 'a');
    REQUIRE(*ukkonen::maximal_piece_prefix_no_checks(t, 00043456_w) == 0);
    REQUIRE(*ukkonen::maximal_piece_prefix_no_checks(t, 0123456_w) == 1);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen",
                          "001",
                          "maximal_piece_prefix 1",
                          "[quick][ukkonen]") {
    Ukkonen t;
    t.add_word({0, 5, 7});
    t.add_word({1, 6, 7});
    t.add_word({7, 2});
    t.add_word({3, 4});
    t.add_word({4, 8});
    t.add_word({9});
    t.add_word({5, 7, 10});
    t.add_word({6, 7, 11});

    REQUIRE(t.nodes().size() == 32);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {0, 5, 7}) == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {1, 6, 7}) == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {7, 2}) == 1);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {3, 4}) == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {4, 8}) == 1);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {9}) == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {5, 7, 10}) == 2);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, {6, 7, 11}) == 2);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen",
                          "002",
                          "maximal_piece_prefix 2",
                          "[quick][ukkonen]") {
    Ukkonen t;
    t.add_word(004000_w);
    t.add_word(45_w);

    REQUIRE(ukkonen::number_of_distinct_subwords(t) == 18);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 004000_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 45_w) == 1);

    t.add_word(0123_w);
    REQUIRE(ukkonen::number_of_distinct_subwords(t) == 27);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 004000_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 45_w) == 1);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 0123_w) == 1);

    t.add_word(004_w);
    REQUIRE(ukkonen::number_of_distinct_subwords(t) == 27);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 004000_w) == 3);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, "00456789"_w) == 3);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 45_w) == 1);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 0123_w) == 1);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 004_w) == 3);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen",
                          "003",
                          "maximal_piece_prefix 3",
                          "[quick][ukkonen]") {
    Ukkonen t;
    REQUIRE(t.number_of_distinct_words() == 0);
    t.add_word(012_w);
    REQUIRE(t.number_of_distinct_words() == 1);
    t.add_word(124_w);
    REQUIRE(t.number_of_distinct_words() == 2);

    REQUIRE(t.nodes().size() == 11);
    REQUIRE(ukkonen::number_of_distinct_subwords(t) == 10);

    REQUIRE(ukkonen::is_subword(t, ""_w));
    REQUIRE(ukkonen::is_subword(t, 0_w));
    REQUIRE(ukkonen::is_subword(t, 1_w));
    REQUIRE(ukkonen::is_subword(t, 2_w));
    REQUIRE(ukkonen::is_subword(t, 4_w));
    REQUIRE(ukkonen::is_subword(t, 01_w));
    REQUIRE(ukkonen::is_subword(t, 12_w));
    REQUIRE(ukkonen::is_subword(t, 24_w));
    REQUIRE(ukkonen::is_subword(t, 012_w));
    REQUIRE(ukkonen::is_subword(t, 124_w));
    REQUIRE_THROWS_AS(
        ukkonen::is_subword(
            t, std::vector<size_t>({static_cast<size_t>(-1), 124})),
        LibsemigroupsException);

    REQUIRE(!ukkonen::is_subword(t, 123_w));
    REQUIRE(!ukkonen::is_subword(t, 1234_w));
    REQUIRE(!ukkonen::is_subword(t, 3_w));
    REQUIRE(!ukkonen::is_subword(t, 13_w));

    REQUIRE(std::count_if(
                cbegin_wislo(5, {}, 00000_w),
                cend_wislo(5, {}, 00000_w),
                [&t](word_type const& w) { return ukkonen::is_subword(t, w); })
            == 10);

    REQUIRE(ukkonen::is_suffix(t, ""_w));
    REQUIRE(!ukkonen::is_suffix(t, 0_w));
    REQUIRE(!ukkonen::is_suffix(t, 1_w));
    REQUIRE(ukkonen::is_suffix(t, 2_w));
    REQUIRE(ukkonen::is_suffix(t, 4_w));
    REQUIRE(!ukkonen::is_suffix(t, 01_w));
    REQUIRE(ukkonen::is_suffix(t, 12_w));
    REQUIRE(ukkonen::is_suffix(t, 24_w));
    REQUIRE(ukkonen::is_suffix(t, 012_w));
    REQUIRE(ukkonen::is_suffix(t, 124_w));
    REQUIRE_THROWS_AS(ukkonen::is_suffix(t, {static_cast<size_t>(-1), 124}),
                      LibsemigroupsException);

    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 012_w) == 0);
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, 012_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_suffix_no_checks(t, 012_w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, 124_w) == 0);
    REQUIRE(ukkonen::length_maximal_piece_suffix_no_checks(t, 124_w) == 0);

    REQUIRE(*ukkonen::maximal_piece_suffix(t, 012_w) == 1);
    auto w = 124_w;
    REQUIRE(ukkonen::maximal_piece_suffix(t, w) == w.cend());

    REQUIRE(*ukkonen::maximal_piece_suffix_no_checks(t, 012_w) == 1);
    REQUIRE(ukkonen::maximal_piece_suffix_no_checks(t, w) == w.cend());

    REQUIRE(ukkonen::number_of_pieces(t, 012_w) == POSITIVE_INFINITY);
    REQUIRE(ukkonen::number_of_pieces_no_checks(t, 012_w) == POSITIVE_INFINITY);
    REQUIRE(ukkonen::number_of_pieces_no_checks(t, "abc") == POSITIVE_INFINITY);
    REQUIRE(ukkonen::number_of_pieces_no_checks(t, std::string("abc"))
            == POSITIVE_INFINITY);
    REQUIRE(ukkonen::number_of_pieces(t, 012_w) == POSITIVE_INFINITY);
    REQUIRE(ukkonen::number_of_pieces(t, "abc") == POSITIVE_INFINITY);
    REQUIRE(ukkonen::number_of_pieces(t, std::string("abc"))
            == POSITIVE_INFINITY);
    REQUIRE(ukkonen::pieces(t, 012_w) == std::vector<word_type>());
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, 124_w) == 2);
    REQUIRE(ukkonen::number_of_pieces(t, 124_w) == POSITIVE_INFINITY);
    REQUIRE(ukkonen::pieces(t, 124_w) == std::vector<word_type>());
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen",
                          "004",
                          "number_of_pieces",
                          "[quick][ukkonen]") {
    Ukkonen t;
    t.add_word(012_w);
    t.add_word(0_w);
    t.add_word(1_w);
    t.add_word(2_w);

    REQUIRE(ukkonen::number_of_pieces(t, 012_w) == 3);
    REQUIRE(ukkonen::pieces(t, 012_w)
            == std::vector<word_type>({0_w, 1_w, 2_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 0_w) == 1);
    REQUIRE(ukkonen::pieces(t, 0_w) == std::vector<word_type>({0_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 1_w) == 1);
    REQUIRE(ukkonen::pieces(t, 1_w) == std::vector<word_type>({1_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 2_w) == 1);
    REQUIRE(ukkonen::pieces(t, 2_w) == std::vector<word_type>({2_w}));

    t.add_word("01284567"_w);
    t.add_word(012_w);  // does nothing
    t.add_word(845_w);
    t.add_word(56_w);
    t.add_word(567_w);

    REQUIRE(t.number_of_distinct_words() == 8);
    REQUIRE(t.number_of_words() == 9);

    REQUIRE(ukkonen::number_of_pieces(t, 012_w) == 1);
    REQUIRE(ukkonen::pieces(t, 012_w) == std::vector<word_type>({012_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 0_w) == 1);
    REQUIRE(ukkonen::number_of_pieces(t, 1_w) == 1);
    REQUIRE(ukkonen::number_of_pieces(t, 2_w) == 1);

    REQUIRE(ukkonen::number_of_pieces(t, "01284567"_w) == 3);
    REQUIRE(ukkonen::pieces(t, "01284567"_w)
            == std::vector<word_type>({012_w, 845_w, 67_w}));
    REQUIRE(ukkonen::is_piece(t, 012_w));
    REQUIRE(ukkonen::is_piece(t, 845_w));
    REQUIRE(ukkonen::is_piece(t, 67_w));
    REQUIRE(ukkonen::is_piece_no_checks(t, 012_w));
    REQUIRE(ukkonen::is_piece_no_checks(t, 845_w));
    REQUIRE(ukkonen::is_piece_no_checks(t, 67_w));
    REQUIRE(ukkonen::number_of_pieces(t, 845_w) == 1);
    REQUIRE(ukkonen::pieces(t, 845_w) == std::vector<word_type>({845_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 56_w) == 1);
    REQUIRE(ukkonen::pieces(t, 56_w) == std::vector<word_type>({56_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 567_w) == 1);

    REQUIRE(ukkonen::pieces(t, 567_w) == std::vector<word_type>({567_w}));
    REQUIRE(ukkonen::number_of_pieces(t, 12845_w) == 2);
    REQUIRE(ukkonen::pieces(t, 12845_w)
            == std::vector<word_type>({12_w, 845_w}));

    auto w = "0128456701284567"_w;
    REQUIRE(ukkonen::pieces(t, w.cbegin(), w.cend()).size() == 7);
    REQUIRE(ukkonen::pieces(t, w)
            == std::vector<word_type>(
                {{0, 1, 2}, {8, 4, 5}, {6, 7}, {0, 1, 2}, {8, 4, 5}, {6, 7}}));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "005", "traverse", "[quick][ukkonen]") {
    using State = Ukkonen::State;
    Ukkonen t;
    t.add_word(004000_w);

    auto s = ukkonen::traverse(t, {});
    REQUIRE(s.first.v == 0);
    REQUIRE(s.first.pos == 0);

    s = ukkonen::traverse(t, 4_w);
    REQUIRE(s.first.v == 4);
    REQUIRE(s.first.pos == 1);

    s = ukkonen::traverse(t, 40_w);
    REQUIRE(s.first.v == 4);
    REQUIRE(s.first.pos == 2);

    s = ukkonen::traverse(t, 4000_w);
    REQUIRE(s.first.v == 4);
    REQUIRE(s.first.pos == 4);

    s = ukkonen::traverse(t, 0_w);
    REQUIRE(s.first.v == 2);
    REQUIRE(s.first.pos == 1);

    s = ukkonen::traverse(t, 04_w);
    REQUIRE(s.first.v == 3);
    REQUIRE(s.first.pos == 1);

    s = ukkonen::traverse(t, 04000_w);
    REQUIRE(s.first.v == 3);
    REQUIRE(s.first.pos == 4);
    REQUIRE(s.first == State(3, 4));

    s = ukkonen::traverse(t, 002_w);
    REQUIRE(t.distance_from_root(t.nodes()[s.first.v]));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "006", "dot", "[quick][ukkonen]") {
    {
      Ukkonen t;
      t.add_word(00_w);
      t.add_word(00_w);
      t.add_word(010_w);
      t.add_word(00_w);
      t.add_word(0101_w);
      t.add_word(010_w);
      REQUIRE_NOTHROW(ukkonen::dot(t));
    }
    {
      Ukkonen u;
      // No words
      REQUIRE_THROWS_AS(ukkonen::dot(u), LibsemigroupsException);
      ukkonen::add_words(
          u, cbegin_wislo(2, ""_w, "00000"_w), cend_wislo(2, ""_w, "00000"_w));
      REQUIRE(u.number_of_distinct_words() == 30);
      // Too many words
      REQUIRE_THROWS_AS(ukkonen::dot(u), LibsemigroupsException);
    }
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "007", "strings", "[quick][ukkonen]") {
    Ukkonen t;
    t.add_word("aaaeaa");
    t.add_word("abcd");
    REQUIRE(t.number_of_distinct_words() == 2);
    t.add_word("");
    REQUIRE(t.number_of_distinct_words() == 2);

    REQUIRE(t.nodes().size() == 15);
    REQUIRE(ukkonen::number_of_pieces(t, "aaaeaa") == POSITIVE_INFINITY);
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, "aaaeaa") == 2);

    auto w = "aaaeaa";
    REQUIRE(std::string(ukkonen::maximal_piece_suffix(t, w), w + 6) == "aa");
    REQUIRE(std::string(ukkonen::maximal_piece_suffix_no_checks(t, w), w + 6)
            == "aa");
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, w) == 2);
    REQUIRE(ukkonen::length_maximal_piece_suffix_no_checks(t, w) == 2);
    REQUIRE(std::string(w, ukkonen::maximal_piece_prefix_no_checks(t, w))
            == "aa");

    std::string ww = "aaaeaa";
    REQUIRE(std::string(ukkonen::maximal_piece_suffix(t, ww), ww.cend())
            == "aa");
    REQUIRE(
        std::string(ukkonen::maximal_piece_suffix_no_checks(t, ww), ww.cend())
        == "aa");

    REQUIRE(ukkonen::pieces(t, ww) == std::vector<std::string>());
    REQUIRE(ukkonen::pieces(t, "aaaaaa")
            == std::vector<std::string>({"aa", "aa", "aa"}));
    REQUIRE_THROWS_AS(ukkonen::pieces(t, word_type({UNDEFINED})),
                      LibsemigroupsException);
    REQUIRE(
        std::string(ww.cbegin(), ukkonen::maximal_piece_prefix_no_checks(t, ww))
        == "aa");
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, ww) == 2);
    REQUIRE(ukkonen::length_maximal_piece_suffix_no_checks(t, ww) == 2);

    REQUIRE(ukkonen::length_maximal_piece_suffix(t, "abcd") == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, "aaaeaa") == 2);
    REQUIRE(!ukkonen::is_suffix(t, "aaaeaaaaaaaaaaaaaaaa"));
    REQUIRE(ukkonen::is_suffix(t, ""));
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, "") == 0);
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, "") == 0);
    REQUIRE(ukkonen::number_of_pieces(t, "") == 0);
    REQUIRE(ukkonen::length_maximal_piece_prefix(t, "xxx") == 0);
    REQUIRE(ukkonen::length_maximal_piece_suffix(t, "xxx") == 0);
    REQUIRE(ukkonen::number_of_pieces(t, "xxx") == POSITIVE_INFINITY);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "008", "dfs #01", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word(1212_w);
    t.add_word(0_w);
    t.add_word(1213121312131213_w);
    t.add_word(0_w);
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == word_type(1213_w));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "009", "dfs #02", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;

    Ukkonen t;
    t.add_word("aaaaa");
    t.add_word("bbb");
    t.add_word("ababa");
    t.add_word("aaabaabaaabaa");
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == word_type({97, 98, 97}));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "010", "dfs #03", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word("aaaaa");
    t.add_word("bbb");
    t.add_word("cba");
    t.add_word("aaccaca");
    t.add_word("aba");
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == word_type());
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "011", "dfs #04", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word(00_w);
    t.add_word(10_w);
    t.add_word(01_w);
    t.add_word(20_w);
    t.add_word(02_w);
    t.add_word(30_w);
    t.add_word(03_w);
    t.add_word(11_w);
    t.add_word(23_w);
    t.add_word(222_w);
    t.add_word(12121212121212_w);
    t.add_word(12131213121312131213121312131213_w);
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == 12131213_w);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "012", "dfs #05", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word(00_w);
    t.add_word(10_w);
    t.add_word(01_w);
    t.add_word(20_w);
    t.add_word(02_w);
    t.add_word(30_w);
    t.add_word(03_w);
    t.add_word(11_w);
    t.add_word(23_w);
    t.add_word(222_w);
    t.add_word(12121212121212_w);
    t.add_word(44444444_w);
    t.add_word(1213_w);
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == 12_w);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "013", "dfs #06", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word(00_w);
    t.add_word(10_w);
    t.add_word(01_w);
    t.add_word(20_w);
    t.add_word(02_w);
    t.add_word(30_w);
    t.add_word(03_w);
    t.add_word(11_w);
    t.add_word(23_w);
    t.add_word(222_w);
    t.add_word(5555555_w);
    t.add_word(44444444_w);
    t.add_word(513_w);
    t.add_word(12_w);
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == 4444_w);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "014", "dfs #07", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word("aaaaaaaaaaaaaa");
    t.add_word("bbbbbbbbbbbbbb");
    t.add_word("cccccccccccccc");
    t.add_word("aaaaba");
    t.add_word("bbb");
    t.add_word("bbbbab");
    t.add_word("aaa");
    t.add_word("aaaaca");
    t.add_word("ccc");
    t.add_word("ccccac");
    t.add_word("aaa");
    t.add_word("bbbbcb");
    t.add_word("ccc");
    t.add_word("ccccbc");
    t.add_word("bbb");
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == word_type({99, 99, 99}));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "015", "dfs #08", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word("aaaaaaaaaaaaaa");
    t.add_word("bbbbbbbbbbbbbb");
    t.add_word("ddddcc");
    t.add_word("aaaaba");
    t.add_word("bbb");
    t.add_word("bbbbab");
    t.add_word("aaa");
    t.add_word("aaaaca");
    t.add_word("dcac");
    t.add_word("aaa");
    t.add_word("bbbbcb");
    t.add_word("dcbc");
    t.add_word("bbb");
    t.add_word("ccc");
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == word_type({98, 98, 98}));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "016", "dfs #09", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
    t.add_word("bbb");
    t.add_word("ababa");
    t.add_word("aaaaaaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaabaaaa");
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last)
            == word_type({
                97,
                97,
                97,
                97,
            }));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "017", "dfs #10", "[quick][ukkonen]") {
    using const_iterator = typename Ukkonen::const_iterator;
    Ukkonen t;
    t.add_word("aBCbac");
    t.add_word("bACbaacA");
    t.add_word("accAABab");
    const_iterator first, last;
    std::tie(first, last) = best_subword(t);
    REQUIRE(word_type(first, last) == word_type());
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen", "018", "pieces", "[quick][ukkonen]") {
    Ukkonen              t;
    detail::StringToWord string_to_word("ab");
    t.add_word(string_to_word("baabbaaaa"));
    t.add_word(string_to_word("abababbbaa"));

    REQUIRE(ukkonen::number_of_pieces(t, string_to_word("baabbaaaa")) == 3);
    REQUIRE(ukkonen::pieces(t, string_to_word("baabbaaaa"))
            == std::vector<word_type>({100_w, 1100_w, 00_w}));
    REQUIRE(ukkonen::is_piece(t, string_to_word("baa")));
    REQUIRE(ukkonen::is_piece(t, string_to_word("bbaa")));
    REQUIRE(ukkonen::is_piece(t, string_to_word("aa")));
    REQUIRE(!ukkonen::is_piece(t, "aa"));
    REQUIRE(!ukkonen::is_piece(t, std::string("aa")));
    REQUIRE(!ukkonen::is_piece_no_checks(t, "aa"));
    REQUIRE(!ukkonen::is_piece_no_checks(t, std::string("aa")));
    REQUIRE(ukkonen::is_piece_no_checks(t, string_to_word("baa")));
    REQUIRE(ukkonen::is_piece_no_checks(t, string_to_word("bbaa")));
    REQUIRE(ukkonen::is_piece_no_checks(t, string_to_word("aa")));

    REQUIRE(ukkonen::number_of_pieces(t, string_to_word("abababbbaa")) == 3);
    REQUIRE(ukkonen::pieces(t, string_to_word("abababbbaa"))
            == std::vector<word_type>({0101_w, 011_w, 100_w}));
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen",
                          "019",
                          "code coverage",
                          "[quick][ukkonen]") {
    Ukkonen u;
    u.add_word_no_checks(0001000_w);
    auto w = "abcdefabababab";
    u.add_word_no_checks(w, w + std::strlen(w));
    u.add_word_no_checks(w);
    u.add_word_no_checks({1, 2, 3, 4, 0, 0, 1, 1, 0, 0, 1});
    std::string ww("abdbadbabdbabdabdj");
    u.add_word_no_checks(ww);
    u.add_word(ww);

    auto www = 0001000_w;
    u.add_word_no_checks(www.cbegin(), www.cend());

    REQUIRE(u.nodes().size() == 78);
    REQUIRE(u.length_of_distinct_words() == 50);
    REQUIRE(u.length_of_words() == 89);
    REQUIRE(std::equal(u.cbegin(), u.cend(), u.begin(), u.end()));
    REQUIRE(word_type(u.begin(), u.end())
            == word_type({0,
                          0,
                          0,
                          1,
                          0,
                          0,
                          0,
                          u.unique_letter(0),
                          97,
                          98,
                          99,
                          100,
                          101,
                          102,
                          97,
                          98,
                          97,
                          98,
                          97,
                          98,
                          97,
                          98,
                          u.unique_letter(1),
                          1,
                          2,
                          3,
                          4,
                          0,
                          0,
                          1,
                          1,
                          0,
                          0,
                          1,
                          u.unique_letter(2),
                          97,
                          98,
                          100,
                          98,
                          97,
                          100,
                          98,
                          97,
                          98,
                          100,
                          98,
                          97,
                          98,
                          100,
                          97,
                          98,
                          100,
                          106,
                          u.unique_letter(3)}));
    std::vector<size_t> distances(u.nodes().size(), 0);
    std::transform(u.nodes().cbegin(),
                   u.nodes().cend(),
                   distances.begin(),
                   [&u](auto const& n) { return u.distance_from_root(n); });
    REQUIRE(distances
            == std::vector<size_t>(
                {0,  8,  2,  7,  1,  6, 5,  3, 4,  3, 2,  1,  15, 14, 13, 12,
                 11, 10, 2,  9,  1,  8, 6,  7, 5,  6, 4,  5,  3,  4,  3,  2,
                 1,  1,  12, 11, 10, 9, 3,  8, 2,  7, 6,  3,  5,  4,  3,  2,
                 1,  19, 18, 1,  17, 2, 16, 1, 15, 3, 14, 13, 5,  12, 4,  11,
                 5,  10, 4,  9,  3,  8, 2,  7, 6,  5, 4,  3,  2,  1}));

    distances.resize(u.number_of_distinct_words(), 0);
    auto range = IntegralRange<size_t>(0, u.number_of_distinct_words());
    std::transform(range.cbegin(),
                   range.cend(),
                   distances.begin(),
                   [&u](auto i) { return u.multiplicity(i); });
    REQUIRE(distances == std::vector<size_t>({2, 2, 1, 2}));

    std::vector<word_type> v = {www, www};
    ukkonen::add_words_no_checks(u, v);
    ukkonen::add_words(u, v);
    ukkonen::add_words_no_checks(u, v.cbegin(), v.cend());
    ukkonen::add_words(u, v.cbegin(), v.cend());
    REQUIRE(u.nodes().size() == 78);
  }

  LIBSEMIGROUPS_TEST_CASE("Ukkonen",
                          "020",
                          "code coverage",
                          "[quick][ukkonen]") {
    Ukkonen u;
    REQUIRE(u.is_suffix(Ukkonen::State()) == UNDEFINED);
    REQUIRE(ukkonen::is_suffix(u, ""_w) == true);
  }
}  // namespace libsemigroups

quality90%

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