1 // 2 // libsemigroups - C++ library for semigroups and monoids 3 // Copyright (C) 2019 James D. Mitchell 4 // 5 // This program is free software: you can redistribute it and/or modify 6 // it under the terms of the GNU General Public License as published by 7 // the Free Software Foundation, either version 3 of the License, or 8 // (at your option) any later version. 9 // 10 // This program is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU General Public License for more details. 14 // 15 // You should have received a copy of the GNU General Public License 16 // along with this program. If not, see <http://www.gnu.org/licenses/>. 17 // 18 19 #include <cstddef> // for size_t 20 #include <cstdint> // for uint32_t, int32_t, int64_t 21 #include <vector> // for vector 22 23 #include "blocks.hpp" // for Blocks 24 #include "bmat8.hpp" // for BMat8 25 #include "catch.hpp" // for TEST_CASE 26 #include "element-helper.hpp" // for TransfHelper 27 #include "element.hpp" // for Bipartition, Element 28 #include "libsemigroups-config.hpp" // for LIBSEMIGROUPS_SIZEOF_VO... 29 #include "semiring.hpp" // for Semiring ... 30 #include "test-main.hpp" // LIBSEMIGROUPS_TEST_CASE 31 #include "types.hpp" // for SmallestInteger, Smalle... 32 33 namespace libsemigroups { 34 struct LibsemigroupsException; 35 36 LIBSEMIGROUPS_TEST_CASE("Element", 37 "001", 38 "comparison operators", 39 "[quick][element]") { 40 auto x = Transformation<uint16_t>({0, 1, 0}); 41 auto y = Transformation<uint16_t>({0, 1}); 42 REQUIRE(x > y); 43 } 44 45 LIBSEMIGROUPS_TEST_CASE("Transformation", 46 "001", 47 "uint16_t methods", 48 "[quick][element]") { 49 auto x = Transformation<uint16_t>({0, 1, 0}); 50 auto y = Transformation<uint16_t>({0, 1, 0}); 51 REQUIRE(x == y); 52 REQUIRE(y * y == x); 53 REQUIRE((x < y) == false); 54 55 auto z = Transformation<uint16_t>({0, 1, 0, 3}); 56 REQUIRE(x < z); 57 58 auto expected = Transformation<uint16_t>({0, 0, 0}); 59 REQUIRE(expected < x); 60 61 REQUIRE(x.degree() == 3); 62 REQUIRE(y.degree() == 3); 63 REQUIRE(x.complexity() == 3); 64 REQUIRE(y.complexity() == 3); 65 REQUIRE(x.crank() == 2); 66 REQUIRE(y.crank() == 2); 67 auto id = x.identity(); 68 69 expected = Transformation<uint16_t>({0, 1, 2}); 70 REQUIRE(id == expected); 71 72 x.increase_degree_by(10); 73 REQUIRE(x.degree() == 13); 74 REQUIRE(x.end() - x.begin() == 13); 75 } 76 77 LIBSEMIGROUPS_TEST_CASE("Transformation", 78 "002", 79 "uint16_t hash", 80 "[quick][element]") { 81 Element* x = new Transformation<uint16_t>({9, 7, 3, 5, 3, 4, 2, 7, 7, 1}); 82 for (size_t i = 0; i < 1000000; i++) { 83 x->hash_value(); 84 } 85 delete x; 86 } 87 88 // Transformation 003 was deleted 89 90 LIBSEMIGROUPS_TEST_CASE("Transformation", 91 "004", 92 "uint32_t methods", 93 "[quick][element]") { 94 Element* x = new Transformation<uint32_t>({0, 1, 0}); 95 Element* y = new Transformation<uint32_t>({0, 1, 0}); 96 REQUIRE(*x == *y); 97 x->redefine(y, y); 98 REQUIRE(*x == *y); 99 REQUIRE((*x < *y) == false); 100 Element* expected = new Transformation<uint32_t>({0, 0, 0}); 101 REQUIRE(*expected < *x); 102 103 delete expected; 104 105 REQUIRE(x->degree() == 3); 106 REQUIRE(y->degree() == 3); 107 REQUIRE(x->complexity() == 3); 108 REQUIRE(y->complexity() == 3); 109 REQUIRE(static_cast<Transformation<uint32_t>*>(x)->crank() == 2); 110 REQUIRE(static_cast<Transformation<uint32_t>*>(y)->crank() == 2); 111 Transformation<uint32_t> id 112 = static_cast<Transformation<uint32_t>*>(x)->identity(); 113 114 expected = new Transformation<uint32_t>({0, 1, 2}); 115 REQUIRE(id == *expected); 116 delete expected; 117 118 delete x; 119 delete y; 120 } 121 122 LIBSEMIGROUPS_TEST_CASE("Transformation", 123 "005", 124 "uint32_t hash", 125 "[quick][element]") { 126 Element* x = new Transformation<uint32_t>({9, 7, 3, 5, 3, 4, 2, 7, 7, 1}); 127 for (size_t i = 0; i < 1000000; i++) { 128 x->hash_value(); 129 } 130 delete x; 131 } 132 133 // Transformation 006 deleted 134 135 LIBSEMIGROUPS_TEST_CASE("Transformation", 136 "007", 137 "exceptions", 138 "[quick][element]") { 139 REQUIRE_NOTHROW(Transformation<uint16_t>(std::vector<uint16_t>())); 140 REQUIRE_NOTHROW(Transformation<uint16_t>(std::vector<uint16_t>({0}))); 141 REQUIRE_THROWS_AS(Transformation<uint16_t>(std::vector<uint16_t>({1})), 142 LibsemigroupsException); 143 144 REQUIRE_NOTHROW(Transformation<uint16_t>(std::vector<uint16_t>({0, 1, 2}))); 145 REQUIRE_NOTHROW( 146 Transformation<uint16_t>(std::initializer_list<uint16_t>({0, 1, 2}))); 147 // Implicit type initializer lists are not accepted. 148 // REQUIRE_NOTHROW(Transformation<uint16_t>({0, 1, 2}))); 149 150 std::vector<uint16_t> pimgs = {1, 2, 3}; 151 // REQUIRE_NOTHROW(Transformation<uint16_t>(pimgs)); 152 REQUIRE_THROWS_AS(Transformation<uint16_t>({1, 2, 3}), 153 LibsemigroupsException); 154 REQUIRE_THROWS_AS( 155 Transformation<uint16_t>(std::initializer_list<uint16_t>({1, 2, 3})), 156 LibsemigroupsException); 157 158 REQUIRE_THROWS_AS(Transformation<uint16_t>(std::initializer_list<uint16_t>( 159 {UNDEFINED, UNDEFINED, UNDEFINED})), 160 LibsemigroupsException); 161 } 162 163 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 164 "001", 165 "uint16_t methods", 166 "[quick][element]") { 167 auto x = PartialPerm<uint16_t>({4, 5, 0}, {9, 0, 1}, 10); 168 auto y = PartialPerm<uint16_t>({4, 5, 0}, {9, 0, 1}, 10); 169 REQUIRE(x == y); 170 auto yy = x * x; 171 REQUIRE(yy.at(0) == UNDEFINED); 172 REQUIRE(yy.at(1) == UNDEFINED); 173 REQUIRE(yy.at(2) == UNDEFINED); 174 REQUIRE(yy.at(3) == UNDEFINED); 175 REQUIRE(yy.at(4) == UNDEFINED); 176 REQUIRE(yy.at(5) == 1); 177 178 REQUIRE(yy < y); 179 REQUIRE(!(x < x)); 180 auto expected = PartialPerm<uint16_t>({UNDEFINED, UNDEFINED, UNDEFINED}); 181 REQUIRE(expected < x); 182 183 REQUIRE(x.degree() == 10); 184 REQUIRE(y.degree() == 10); 185 REQUIRE(x.complexity() == 10); 186 REQUIRE(y.complexity() == 10); 187 REQUIRE(yy.crank() == 1); 188 REQUIRE(y.crank() == 3); 189 REQUIRE(x.crank() == 3); 190 auto id = x.identity(); 191 192 expected = PartialPerm<uint16_t>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}); 193 REQUIRE(id == expected); 194 195 x.increase_degree_by(10); 196 REQUIRE(x.degree() == 20); 197 REQUIRE(x.end() - x.begin() == x.degree()); 198 } 199 200 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 201 "002", 202 "uint16_t hash", 203 "[quick][element]") { 204 Element* x = new PartialPerm<uint16_t>( 205 {0, 1, 2, 3, 5, 6, 9}, {9, 7, 3, 5, 4, 2, 1}, 10); 206 for (size_t i = 0; i < 1000000; i++) { 207 x->hash_value(); 208 } 209 delete x; 210 } 211 212 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 213 "003", 214 "uint16_t delete/copy", 215 "[quick][element]") { 216 Element* x = new PartialPerm<uint16_t>( 217 {0, 1, 2, 3, 5, 6, 9}, {9, 7, 3, 5, 4, 2, 1}, 10); 218 Element* y = x->heap_copy(); 219 delete x; 220 221 Element* expected = new PartialPerm<uint16_t>( 222 {0, 1, 2, 3, 5, 6, 9}, {9, 7, 3, 5, 4, 2, 1}, 10); 223 REQUIRE(*y == *expected); 224 225 PartialPerm<uint16_t> yy = *static_cast<PartialPerm<uint16_t>*>(y); 226 REQUIRE(yy == *y); 227 PartialPerm<uint16_t> zz(yy); 228 delete y; // does not delete the _vector in y, yy, or zz 229 REQUIRE(zz == *expected); 230 delete expected; 231 } 232 233 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 234 "004", 235 "uint32_t methods", 236 "[quick][element]") { 237 auto x = PartialPerm<uint32_t>({4, 5, 0}, {10, 0, 1}, 11); 238 auto y = PartialPerm<uint32_t>({4, 5, 0}, {10, 0, 1}, 11); 239 REQUIRE(x == y); 240 auto xx = x * x; 241 REQUIRE(xx.at(0) == UNDEFINED); 242 REQUIRE(xx.at(1) == UNDEFINED); 243 REQUIRE(xx.at(2) == UNDEFINED); 244 REQUIRE(xx.at(3) == UNDEFINED); 245 REQUIRE(xx.at(4) == UNDEFINED); 246 REQUIRE(xx.at(5) == 1); 247 REQUIRE((xx < y) == true); 248 249 auto z = PartialPerm<uint32_t>({UNDEFINED, UNDEFINED, UNDEFINED}); 250 REQUIRE(z < x); 251 252 REQUIRE(x.degree() == 11); 253 REQUIRE(y.degree() == 11); 254 REQUIRE(x.complexity() == 11); 255 REQUIRE(y.complexity() == 11); 256 REQUIRE(xx.crank() == 1); 257 REQUIRE(x.crank() == 3); 258 REQUIRE(y.crank() == 3); 259 auto id = x.identity(); 260 261 auto expected = PartialPerm<uint32_t>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}); 262 REQUIRE(id == expected); 263 } 264 265 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 266 "005", 267 "uint32_t hash", 268 "[quick][element]") { 269 Element* x = new PartialPerm<uint32_t>( 270 {0, 1, 2, 3, 5, 6, 9}, {9, 7, 3, 5, 4, 2, 1}, 10); 271 for (size_t i = 0; i < 1000000; i++) { 272 x->hash_value(); 273 } 274 delete x; 275 } 276 277 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 278 "006", 279 "uint32_t delete/copy", 280 "[quick][element]") { 281 Element* x = new PartialPerm<uint32_t>( 282 {0, 1, 2, 3, 5, 6, 9}, {9, 7, 3, 5, 4, 2, 1}, 10); 283 Element* y = x->heap_copy(); 284 delete x; 285 286 Element* expected = new PartialPerm<uint32_t>( 287 {0, 1, 2, 3, 5, 6, 9}, {9, 7, 3, 5, 4, 2, 1}, 10); 288 REQUIRE(*y == *expected); 289 290 PartialPerm<uint32_t> yy = *static_cast<PartialPerm<uint32_t>*>(y); 291 REQUIRE(yy == *y); 292 PartialPerm<uint32_t> zz(yy); 293 delete y; // does not delete the _vector in y, yy, or zz 294 REQUIRE(zz == *expected); 295 296 delete expected; 297 } 298 299 LIBSEMIGROUPS_TEST_CASE("PartialPerm", 300 "007", 301 "exceptions", 302 "[quick][element]") { 303 REQUIRE_NOTHROW(PartialPerm<uint16_t>(std::vector<uint16_t>())); 304 REQUIRE_NOTHROW(PartialPerm<uint16_t>(std::vector<uint16_t>({0}))); 305 REQUIRE_NOTHROW(PartialPerm<uint16_t>(std::vector<uint16_t>({UNDEFINED}))); 306 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1})), 307 LibsemigroupsException); 308 309 REQUIRE_NOTHROW(PartialPerm<uint16_t>(std::vector<uint16_t>({0, 1, 2}))); 310 REQUIRE_NOTHROW( 311 PartialPerm<uint16_t>(std::initializer_list<uint16_t>({0, 1, 2}))); 312 REQUIRE_NOTHROW( 313 PartialPerm<uint16_t>(std::vector<uint16_t>({0, UNDEFINED, 2}))); 314 REQUIRE_NOTHROW(PartialPerm<uint16_t>( 315 std::vector<uint16_t>({0, UNDEFINED, 5, UNDEFINED, UNDEFINED, 1}))); 316 317 std::vector<uint16_t> pimgs = {1, 2, 3}; 318 // REQUIRE_NOTHROW(PartialPerm<uint16_t>(pimgs)); 319 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 2, 3})), 320 LibsemigroupsException); 321 REQUIRE_THROWS_AS( 322 PartialPerm<uint16_t>(std::vector<uint16_t>({UNDEFINED, UNDEFINED, 3})), 323 LibsemigroupsException); 324 REQUIRE_THROWS_AS( 325 PartialPerm<uint16_t>(std::vector<uint16_t>({1, UNDEFINED, 1})), 326 LibsemigroupsException); 327 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>( 328 {3, UNDEFINED, 2, 1, UNDEFINED, 3})), 329 LibsemigroupsException); 330 REQUIRE_THROWS_AS( 331 PartialPerm<uint16_t>(std::initializer_list<uint16_t>({1, 2, 3})), 332 LibsemigroupsException); 333 REQUIRE_NOTHROW(PartialPerm<uint16_t>( 334 std::vector<uint16_t>({1, 2}), std::vector<uint16_t>({0, 3}), 5)); 335 REQUIRE_NOTHROW(PartialPerm<uint16_t>( 336 std::vector<uint16_t>({1, 2}), std::vector<uint16_t>({0, 5}), 6)); 337 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 2}), 338 std::vector<uint16_t>({0}), 339 5), 340 LibsemigroupsException); 341 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 2}), 342 std::vector<uint16_t>({0, 5}), 343 4), 344 LibsemigroupsException); 345 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 5}), 346 std::vector<uint16_t>({0, 2}), 347 4), 348 LibsemigroupsException); 349 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 1}), 350 std::vector<uint16_t>({0, 2}), 351 3), 352 LibsemigroupsException); 353 } 354 355 LIBSEMIGROUPS_TEST_CASE("BooleanMat", "001", "methods", "[quick][element]") { 356 auto x = BooleanMat({{1, 0, 1}, {0, 1, 0}, {0, 1, 0}}); 357 auto y = BooleanMat({{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}); 358 auto z = BooleanMat({{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}); 359 REQUIRE(y == z); 360 z.redefine(x, y); 361 REQUIRE(y == z); 362 z.redefine(y, x); 363 REQUIRE(y == z); 364 REQUIRE(!(y < z)); 365 REQUIRE(x.degree() == 3); 366 REQUIRE(y.degree() == 3); 367 REQUIRE(z.degree() == 3); 368 REQUIRE(x.complexity() == 27); 369 REQUIRE(y.complexity() == 27); 370 REQUIRE(z.complexity() == 27); 371 auto id = x.identity(); 372 z.redefine(id, x); 373 REQUIRE(z == x); 374 z.redefine(x, id); 375 REQUIRE(z == x); 376 } 377 378 LIBSEMIGROUPS_TEST_CASE("BooleanMat", "002", "hash", "[quick][element]") { 379 Element* x = new BooleanMat({{1, 0, 1}, {0, 1, 0}, {0, 1, 0}}); 380 for (size_t i = 0; i < 1000000; i++) { 381 x->hash_value(); 382 } 383 delete x; 384 } 385 386 LIBSEMIGROUPS_TEST_CASE("BooleanMat", 387 "003", 388 "delete/copy", 389 "[quick][element]") { 390 Element* x = new BooleanMat({{1, 0, 1}, {0, 1, 0}, {0, 1, 0}}); 391 Element* y = x->heap_copy(); 392 delete x; 393 394 Element* expected = new BooleanMat({{1, 0, 1}, {0, 1, 0}, {0, 1, 0}}); 395 REQUIRE(*y == *expected); 396 397 BooleanMat& yy = *static_cast<BooleanMat*>(y); 398 REQUIRE(yy == *y); 399 BooleanMat zz(yy); 400 delete y; // does not delete the _vector in y, yy, or zz 401 REQUIRE(zz == *expected); 402 delete expected; 403 } 404 405 LIBSEMIGROUPS_TEST_CASE("Bipartition", 406 "001", 407 "overridden methods", 408 "[quick][element]") { 409 auto x = Bipartition( 410 {0, 1, 2, 1, 0, 2, 1, 0, 2, 2, 0, 0, 2, 0, 3, 4, 4, 1, 3, 0}); 411 auto y = Bipartition( 412 {0, 1, 1, 1, 1, 2, 3, 2, 4, 5, 5, 2, 4, 2, 1, 1, 1, 2, 3, 2}); 413 auto z = Bipartition( 414 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); 415 REQUIRE(!(y == z)); 416 417 z.redefine(x, y, 0); 418 auto expected = Bipartition( 419 {0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1}); 420 REQUIRE(z == expected); 421 422 expected = Bipartition( 423 {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 1, 2, 1}); 424 z.redefine(y, x, 0); 425 REQUIRE(z == expected); 426 427 REQUIRE(!(y < z)); 428 REQUIRE(x.degree() == 10); 429 REQUIRE(y.degree() == 10); 430 REQUIRE(z.degree() == 10); 431 REQUIRE(x.complexity() == 100); 432 REQUIRE(y.complexity() == 100); 433 REQUIRE(z.complexity() == 100); 434 435 auto id = x.identity(); 436 z.redefine(id, x, 0); 437 REQUIRE(z == x); 438 z.redefine(x, id, 0); 439 REQUIRE(z == x); 440 z.redefine(id, y, 0); 441 REQUIRE(z == y); 442 z.redefine(y, id, 0); 443 REQUIRE(z == y); 444 } 445 446 LIBSEMIGROUPS_TEST_CASE("Bipartition", "002", "hash", "[quick][element]") { 447 Element* x = new Bipartition( 448 {0, 1, 2, 1, 0, 2, 1, 0, 2, 2, 0, 0, 2, 0, 3, 4, 4, 1, 3, 0}); 449 for (size_t i = 0; i < 1000000; i++) { 450 x->hash_value(); 451 } 452 delete x; 453 } 454 455 LIBSEMIGROUPS_TEST_CASE("Bipartition", 456 "003", 457 "non-overridden methods", 458 "[quick][element]") { 459 Bipartition* x = new Bipartition( 460 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 461 462 REQUIRE(x->rank() == 3); 463 REQUIRE(x->at(0) == 0); 464 REQUIRE(x->at(6) == 1); 465 REQUIRE(x->at(10) == 0); 466 REQUIRE(x->const_nr_blocks() == 5); 467 REQUIRE(x->nr_blocks() == 5); 468 REQUIRE(x->const_nr_blocks() == 5); 469 REQUIRE(x->nr_blocks() == 5); 470 REQUIRE(x->nr_left_blocks() == 3); 471 REQUIRE(x->nr_right_blocks() == 5); 472 REQUIRE(x->is_transverse_block(0)); 473 REQUIRE(x->is_transverse_block(1)); 474 REQUIRE(x->is_transverse_block(2)); 475 REQUIRE(!x->is_transverse_block(3)); 476 REQUIRE(!x->is_transverse_block(4)); 477 478 Bipartition* y = new Bipartition( 479 {0, 0, 1, 2, 3, 3, 0, 4, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1}); 480 481 Blocks* a = x->left_blocks(); 482 Blocks* b = y->right_blocks(); 483 REQUIRE(*a == *b); 484 delete a; 485 delete b; 486 a = x->right_blocks(); 487 b = y->left_blocks(); 488 REQUIRE(*a == *b); 489 delete a; 490 delete b; 491 delete x; 492 delete y; 493 494 x = new Bipartition( 495 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 496 x->set_nr_blocks(5); 497 REQUIRE(x->nr_blocks() == 5); 498 delete x; 499 500 x = new Bipartition( 501 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 502 x->set_nr_left_blocks(3); 503 REQUIRE(x->nr_left_blocks() == 3); 504 REQUIRE(x->nr_right_blocks() == 5); 505 REQUIRE(x->nr_blocks() == 5); 506 delete x; 507 508 x = new Bipartition( 509 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 510 x->set_rank(3); 511 REQUIRE(x->rank() == 3); 512 delete x; 513 } 514 515 LIBSEMIGROUPS_TEST_CASE("Bipartition", 516 "004", 517 "delete/copy", 518 "[quick][element]") { 519 Element* x = new Bipartition({0, 0, 0, 0}); 520 Element* y = x->heap_copy(); 521 delete x; 522 523 Element* expected = new Bipartition({0, 0, 0, 0}); 524 REQUIRE(*y == *expected); 525 526 Bipartition yy = *static_cast<Bipartition*>(y); 527 REQUIRE(yy == *y); 528 Bipartition zz(yy); 529 delete y; // does not delete the _vector in y, yy, or zz 530 REQUIRE(zz == *expected); 531 delete expected; 532 } 533 534 LIBSEMIGROUPS_TEST_CASE("Bipartition", 535 "005", 536 "degree 0", 537 "[quick][element]") { 538 Bipartition* x = new Bipartition(std::vector<uint32_t>({})); 539 REQUIRE(x->const_nr_blocks() == 0); 540 REQUIRE(x->nr_left_blocks() == 0); 541 542 Blocks* b = x->left_blocks(); 543 REQUIRE(b->degree() == 0); 544 REQUIRE(b->nr_blocks() == 0); 545 delete b; 546 547 b = x->right_blocks(); 548 REQUIRE(b->degree() == 0); 549 REQUIRE(b->nr_blocks() == 0); 550 delete b; 551 552 delete x; 553 } 554 555 LIBSEMIGROUPS_TEST_CASE("Bipartition", 556 "006", 557 "exceptions", 558 "[quick][element]") { 559 REQUIRE_NOTHROW(Bipartition(std::vector<uint32_t>())); 560 REQUIRE_THROWS_AS(Bipartition({0}), LibsemigroupsException); 561 REQUIRE_THROWS_AS(Bipartition({1, 0}), LibsemigroupsException); 562 } 563 564 LIBSEMIGROUPS_TEST_CASE("Bipartition", 565 "007", 566 "convenience constructor", 567 "[quick][element]") { 568 Bipartition* xx = new Bipartition( 569 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 570 571 Bipartition* x = new Bipartition({{1, 2, 3, 4, 5, 6, 9, -1, -2, -7}, 572 {7, 10, -3, -9, -10}, 573 {8, -4}, 574 {-5, -6}, 575 {-8}}); 576 REQUIRE(*x == *xx); 577 578 REQUIRE(x->rank() == 3); 579 REQUIRE(x->at(0) == 0); 580 REQUIRE(x->at(6) == 1); 581 REQUIRE(x->at(10) == 0); 582 REQUIRE(x->const_nr_blocks() == 5); 583 REQUIRE(x->nr_blocks() == 5); 584 REQUIRE(x->const_nr_blocks() == 5); 585 REQUIRE(x->nr_blocks() == 5); 586 REQUIRE(x->nr_left_blocks() == 3); 587 REQUIRE(x->nr_right_blocks() == 5); 588 REQUIRE(x->is_transverse_block(0)); 589 REQUIRE(x->is_transverse_block(1)); 590 REQUIRE(x->is_transverse_block(2)); 591 REQUIRE(!x->is_transverse_block(3)); 592 REQUIRE(!x->is_transverse_block(4)); 593 594 Bipartition* yy = new Bipartition( 595 {0, 0, 1, 2, 3, 3, 0, 4, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1}); 596 597 Bipartition* y = new Bipartition({{1, 2, 7, -1, -2, -3, -4, -5, -6, -9}, 598 {3, 9, 10, -7, -10}, 599 {4, -8}, 600 {5, 6}, 601 {8}}); 602 603 REQUIRE(*y == *yy); 604 605 Blocks* a = x->left_blocks(); 606 Blocks* b = y->right_blocks(); 607 REQUIRE(*a == *b); 608 delete a; 609 delete b; 610 a = x->right_blocks(); 611 b = y->left_blocks(); 612 REQUIRE(*a == *b); 613 delete a; 614 delete b; 615 delete x; 616 delete y; 617 delete xx; 618 delete yy; 619 620 xx = new Bipartition( 621 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 622 x = new Bipartition({{1, 2, 3, 4, 5, 6, 9, -1, -2, -7}, 623 {7, 10, -3, -9, -10}, 624 {8, -4}, 625 {-5, -6}, 626 {-8}}); 627 REQUIRE(*x == *xx); 628 x->set_nr_blocks(5); 629 REQUIRE(x->nr_blocks() == 5); 630 delete x; 631 delete xx; 632 633 xx = new Bipartition( 634 {0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3, 3, 0, 4, 1, 1}); 635 x = new Bipartition({{1, 2, 3, 4, 5, 6, 9, -1, -2, -7}, 636 {7, 10, -3, -9, -10}, 637 {8, -4}, 638 {-5, -6}, 639 {-8}}); 640 REQUIRE(*x == *xx); 641 x->set_nr_left_blocks(3); 642 REQUIRE(x->nr_left_blocks() == 3); 643 REQUIRE(x->nr_right_blocks() == 5); 644 REQUIRE(x->nr_blocks() == 5); 645 delete x; 646 delete xx; 647 648 x = new Bipartition({{1, 2, 3, 4, 5, 6, 9, -1, -2, -7}, 649 {7, 10, -3, -9, -10}, 650 {8, -4}, 651 {-5, -6}, 652 {-8}}); 653 x->set_rank(3); 654 REQUIRE(x->rank() == 3); 655 delete x; 656 657 REQUIRE_THROWS_AS(Bipartition({{0, 2, 3, 4, 5, 6, 9, -1, -2, -7}, 658 {7, 10, -3, -9, -10}, 659 {8, -4}, 660 {-5, -6}, 661 {-8}}), 662 LibsemigroupsException); 663 664 REQUIRE_THROWS_AS(Bipartition({{1, 2, 3, 4, 5, 6, 9, 11, -1, -2, -7}, 665 {7, 10, -3, -9, -10}, 666 {8, -4}, 667 {-5, -6}, 668 {-8}}), 669 LibsemigroupsException); 670 671 REQUIRE_THROWS_AS(Bipartition({{1, 2, 3, 4, 5, 6, 11, -1, -2, -7}, 672 {7, 10, -3, -9, -10}, 673 {8, -4}, 674 {-5, -6}, 675 {-8}}), 676 LibsemigroupsException); 677 678 REQUIRE_THROWS_AS(Bipartition({{1, 2, 3, 4, 5, 6, -11, -1, -2, -7}, 679 {7, 10, -3, -9, -10}, 680 {8, -4}, 681 {-5, -6}, 682 {-8}}), 683 LibsemigroupsException); 684 685 REQUIRE_THROWS_AS(Bipartition({{0, 2, 3, 4, 5, 6, 9, -1}, 686 {7, 10, -3, -9, -10}, 687 {8, -4}, 688 {-5, -6}, 689 {-8}}), 690 LibsemigroupsException); 691 692 REQUIRE_THROWS_AS(Bipartition({{0, 2, 3, 4, 5, 6, 9, -1, -2}, 693 {7, 10, -3, -9, -10}, 694 {8, -4}, 695 {-5, -6}, 696 {-8}}), 697 LibsemigroupsException); 698 } 699 700 LIBSEMIGROUPS_TEST_CASE("Bipartition", 701 "008", 702 "force copy constructor over move constructor", 703 "[quick][element]") { 704 std::vector<uint32_t> xx( 705 {0, 1, 2, 1, 0, 2, 1, 0, 2, 2, 0, 0, 2, 0, 3, 4, 4, 1, 3, 0}); 706 auto x = Bipartition(xx); 707 std::vector<uint32_t> yy( 708 {0, 1, 1, 1, 1, 2, 3, 2, 4, 5, 5, 2, 4, 2, 1, 1, 1, 2, 3, 2}); 709 auto y = Bipartition(yy); 710 std::vector<uint32_t> zz( 711 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); 712 auto z = Bipartition(zz); 713 REQUIRE(!(y == z)); 714 715 z.redefine(x, y, 0); 716 auto expected = Bipartition( 717 {0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1}); 718 REQUIRE(z == expected); 719 720 expected = Bipartition( 721 {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 1, 2, 1}); 722 z.redefine(y, x, 0); 723 REQUIRE(z == expected); 724 725 REQUIRE(!(y < z)); 726 REQUIRE(x.degree() == 10); 727 REQUIRE(y.degree() == 10); 728 REQUIRE(z.degree() == 10); 729 REQUIRE(x.complexity() == 100); 730 REQUIRE(y.complexity() == 100); 731 REQUIRE(z.complexity() == 100); 732 733 auto id = x.identity(); 734 z.redefine(id, x, 0); 735 REQUIRE(z == x); 736 z.redefine(x, id, 0); 737 REQUIRE(z == x); 738 z.redefine(id, y, 0); 739 REQUIRE(z == y); 740 z.redefine(y, id, 0); 741 REQUIRE(z == y); 742 } 743 LIBSEMIGROUPS_TEST_CASE("ProjectiveMaxPlusMatrix", 744 "001", 745 "methods", 746 "[quick][element]") { 747 Semiring<int64_t>* sr = new MaxPlusSemiring(); 748 749 auto x = ProjectiveMaxPlusMatrix({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 750 auto expected = ProjectiveMaxPlusMatrix( 751 {{-4, 0, -2}, {-3, -2, -2}, {-1, -5, -1}}, sr); 752 REQUIRE(x == expected); 753 754 REQUIRE(x.semiring() == sr); 755 756 auto y = ProjectiveMaxPlusMatrix( 757 {{NEGATIVE_INFINITY, 0, 0}, {0, 1, 0}, {1, -1, 0}}, sr); 758 expected = ProjectiveMaxPlusMatrix( 759 {{NEGATIVE_INFINITY, -1, -1}, {-1, 0, -1}, {0, -2, -1}}, sr); 760 REQUIRE(y == expected); 761 REQUIRE(!(x == y)); 762 763 y.redefine(x, x); 764 expected = ProjectiveMaxPlusMatrix( 765 {{-2, -1, -1}, {-2, -2, -2}, {-1, 0, -1}}, sr); 766 REQUIRE(y == expected); 767 768 REQUIRE(x < y); 769 REQUIRE(x.degree() == 3); 770 REQUIRE(y.degree() == 3); 771 REQUIRE(x.complexity() == 27); 772 REQUIRE(y.complexity() == 27); 773 auto id = x.identity(); 774 y.redefine(id, x); 775 REQUIRE(y == x); 776 y.redefine(x, id); 777 REQUIRE(y == x); 778 delete sr; 779 } 780 781 LIBSEMIGROUPS_TEST_CASE("ProjectiveMaxPlusMatrix", 782 "002", 783 "hash", 784 "[quick][element]") { 785 Semiring<int64_t>* sr = new MaxPlusSemiring(); 786 Element* x 787 = new ProjectiveMaxPlusMatrix({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 788 for (size_t i = 0; i < 1000000; i++) { 789 x->hash_value(); 790 } 791 delete x; 792 delete sr; 793 } 794 795 LIBSEMIGROUPS_TEST_CASE("ProjectiveMaxPlusMatrix", 796 "003", 797 "delete/copy", 798 "[quick][element]") { 799 Semiring<int64_t>* sr = new MaxPlusSemiring(); 800 Element* x 801 = new ProjectiveMaxPlusMatrix({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 802 Element* y = x->heap_copy(); 803 delete x; 804 805 Element* expected 806 = new ProjectiveMaxPlusMatrix({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 807 REQUIRE(*y == *expected); 808 delete expected; 809 810 ProjectiveMaxPlusMatrix yy = *static_cast<ProjectiveMaxPlusMatrix*>(y); 811 REQUIRE(yy == *y); 812 813 ProjectiveMaxPlusMatrix zz(yy); 814 delete y; // does not delete the _vector in y, yy, or zz 815 expected 816 = new ProjectiveMaxPlusMatrix({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 817 REQUIRE(zz == *expected); 818 delete expected; 819 delete sr; 820 } 821 822 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 823 "001", 824 "Integers methods", 825 "[quick][element]") { 826 Semiring<int64_t>* sr = new Integers(); 827 828 auto x 829 = MatrixOverSemiring<int64_t>({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 830 auto expected 831 = MatrixOverSemiring<int64_t>({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 832 REQUIRE(x == expected); 833 834 auto y = MatrixOverSemiring<int64_t>({{-100, 0, 0}, {0, 1, 0}, {1, -1, 0}}, 835 sr); 836 REQUIRE(!(x == y)); 837 838 y.redefine(x, x); 839 expected 840 = MatrixOverSemiring<int64_t>({{2, -4, 0}, {2, -2, 0}, {2, -1, 1}}, sr); 841 REQUIRE(y == expected); 842 843 REQUIRE(x < y); 844 REQUIRE(x.degree() == 3); 845 REQUIRE(y.degree() == 3); 846 REQUIRE(x.complexity() == 27); 847 REQUIRE(y.complexity() == 27); 848 auto id = x.identity(); 849 y.redefine(id, x); 850 REQUIRE(y == x); 851 y.redefine(x, id); 852 REQUIRE(y == x); 853 delete sr; 854 } 855 856 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 857 "002", 858 "Integers, hash", 859 "[quick][element]") { 860 Semiring<int64_t>* sr = new Integers(); 861 Element* x = new MatrixOverSemiring<int64_t>( 862 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 863 for (size_t i = 0; i < 1000000; i++) { 864 x->hash_value(); 865 } 866 delete x; 867 delete sr; 868 } 869 870 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 871 "003", 872 "MaxPlusSemiring methods", 873 "[quick][element]") { 874 Semiring<int64_t>* sr = new MaxPlusSemiring(); 875 876 auto x 877 = MatrixOverSemiring<int64_t>({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 878 auto expected 879 = MatrixOverSemiring<int64_t>({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 880 REQUIRE(x == expected); 881 882 auto y = MatrixOverSemiring<int64_t>({{-100, 0, 0}, {0, 1, 0}, {1, -1, 0}}, 883 sr); 884 REQUIRE(!(x == y)); 885 886 y.redefine(x, x); 887 expected 888 = MatrixOverSemiring<int64_t>({{1, 2, 2}, {1, 1, 1}, {2, 3, 2}}, sr); 889 REQUIRE(y == expected); 890 891 REQUIRE(x < y); 892 REQUIRE(x.degree() == 3); 893 REQUIRE(y.degree() == 3); 894 REQUIRE(x.complexity() == 27); 895 REQUIRE(y.complexity() == 27); 896 auto id = x.identity(); 897 y.redefine(id, x); 898 REQUIRE(y == x); 899 y.redefine(x, id); 900 REQUIRE(y == x); 901 delete sr; 902 } 903 904 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 905 "004", 906 "MaxPlusSemiring hash", 907 "[quick][element]") { 908 Semiring<int64_t>* sr = new MaxPlusSemiring(); 909 Element* x = new MatrixOverSemiring<int64_t>( 910 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 911 for (size_t i = 0; i < 1000000; i++) { 912 x->hash_value(); 913 } 914 delete x; 915 delete sr; 916 } 917 918 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 919 "005", 920 "MinPlusSemiring methods", 921 "[quick][element]") { 922 Semiring<int64_t>* sr = new MinPlusSemiring(); 923 924 auto x 925 = MatrixOverSemiring<int64_t>({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 926 auto expected 927 = MatrixOverSemiring<int64_t>({{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 928 REQUIRE(x == expected); 929 930 auto y = MatrixOverSemiring<int64_t>({{-100, 0, 0}, {0, 1, 0}, {1, -1, 0}}, 931 sr); 932 REQUIRE(!(x == y)); 933 934 y.redefine(x, x); 935 expected = MatrixOverSemiring<int64_t>( 936 {{-4, -3, -2}, {-3, -3, -1}, {-4, -3, -3}}, sr); 937 REQUIRE(y == expected); 938 939 REQUIRE(!(x < y)); 940 REQUIRE(x.degree() == 3); 941 REQUIRE(y.degree() == 3); 942 REQUIRE(x.complexity() == 27); 943 REQUIRE(y.complexity() == 27); 944 auto id = x.identity(); 945 y.redefine(id, x); 946 REQUIRE(y == x); 947 y.redefine(x, id); 948 REQUIRE(y == x); 949 delete sr; 950 } 951 952 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 953 "006", 954 "MinPlusSemiring hash", 955 "[quick][element]") { 956 Semiring<int64_t>* sr = new MinPlusSemiring(); 957 Element* x = new MatrixOverSemiring<int64_t>( 958 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 959 for (size_t i = 0; i < 1000000; i++) { 960 x->hash_value(); 961 } 962 delete x; 963 delete sr; 964 } 965 966 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 967 "007", 968 "TropicalMaxPlusSemiring methods", 969 "[quick][element]") { 970 Semiring<int64_t>* sr = new TropicalMaxPlusSemiring(33); 971 972 auto x = MatrixOverSemiring<int64_t>({{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, 973 sr); 974 auto expected = MatrixOverSemiring<int64_t>( 975 {{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, sr); 976 REQUIRE(x == expected); 977 978 REQUIRE_THROWS_AS( 979 MatrixOverSemiring<int64_t>({{-100, 0, 0}, {0, 1, 0}, {1, -1, 0}}, sr), 980 LibsemigroupsException); 981 auto y 982 = MatrixOverSemiring<int64_t>({{10, 0, 0}, {0, 1, 0}, {1, 1, 0}}, sr); 983 REQUIRE(!(x == y)); 984 985 y.redefine(x, x); 986 expected = MatrixOverSemiring<int64_t>( 987 {{33, 33, 22}, {32, 32, 10}, {33, 33, 32}}, sr); 988 REQUIRE(y == expected); 989 990 REQUIRE(x < y); 991 REQUIRE(x.degree() == 3); 992 REQUIRE(y.degree() == 3); 993 REQUIRE(x.complexity() == 27); 994 REQUIRE(y.complexity() == 27); 995 auto id = x.identity(); 996 y.redefine(id, x); 997 REQUIRE(y == x); 998 y.redefine(x, id); 999 REQUIRE(y == x); 1000 delete sr; 1001 } 1002 1003 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1004 "008", 1005 "TropicalMaxPlusSemiring hash", 1006 "[quick][element]") { 1007 Semiring<int64_t>* sr = new TropicalMaxPlusSemiring(33); 1008 Element* x = new MatrixOverSemiring<int64_t>( 1009 {{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, sr); 1010 for (size_t i = 0; i < 1000000; i++) { 1011 x->hash_value(); 1012 } 1013 delete x; 1014 delete sr; 1015 } 1016 1017 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1018 "009", 1019 "TropicalMinPlusSemiring methods", 1020 "[quick][element]") { 1021 Semiring<int64_t>* sr = new TropicalMinPlusSemiring(33); 1022 1023 auto x = MatrixOverSemiring<int64_t>({{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, 1024 sr); 1025 1026 auto expected = MatrixOverSemiring<int64_t>( 1027 {{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, sr); 1028 REQUIRE(x == expected); 1029 1030 auto y 1031 = MatrixOverSemiring<int64_t>({{10, 0, 0}, {0, 1, 0}, {1, 1, 0}}, sr); 1032 REQUIRE(!(x == y)); 1033 1034 y.redefine(x, x); 1035 expected 1036 = MatrixOverSemiring<int64_t>({{1, 21, 1}, {1, 0, 0}, {2, 22, 1}}, sr); 1037 REQUIRE(y == expected); 1038 1039 REQUIRE(!(x < y)); 1040 REQUIRE(x.degree() == 3); 1041 REQUIRE(y.degree() == 3); 1042 REQUIRE(x.complexity() == 27); 1043 REQUIRE(y.complexity() == 27); 1044 auto id = x.identity(); 1045 y.redefine(id, x); 1046 REQUIRE(y == x); 1047 y.redefine(x, id); 1048 REQUIRE(y == x); 1049 delete sr; 1050 } 1051 1052 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1053 "010", 1054 "TropicalMinPlusSemiring hash", 1055 "[quick][element]") { 1056 Semiring<int64_t>* sr = new TropicalMinPlusSemiring(33); 1057 Element* x = new MatrixOverSemiring<int64_t>( 1058 {{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, sr); 1059 for (size_t i = 0; i < 1000000; i++) { 1060 x->hash_value(); 1061 } 1062 delete x; 1063 delete sr; 1064 } 1065 1066 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1067 "011", 1068 "NaturalSemiring methods", 1069 "[quick][element]") { 1070 Semiring<int64_t>* sr = new NaturalSemiring(33, 2); 1071 1072 auto x = MatrixOverSemiring<int64_t>({{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, 1073 sr); 1074 auto expected = MatrixOverSemiring<int64_t>( 1075 {{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, sr); 1076 REQUIRE(x == expected); 1077 1078 auto y 1079 = MatrixOverSemiring<int64_t>({{10, 0, 0}, {0, 1, 0}, {1, 1, 0}}, sr); 1080 REQUIRE(!(x == y)); 1081 1082 y.redefine(x, x); 1083 expected = MatrixOverSemiring<int64_t>( 1084 {{34, 34, 0}, {34, 34, 0}, {33, 33, 1}}, sr); 1085 REQUIRE(y == expected); 1086 1087 REQUIRE(x < y); 1088 REQUIRE(x.degree() == 3); 1089 REQUIRE(y.degree() == 3); 1090 REQUIRE(x.complexity() == 27); 1091 REQUIRE(y.complexity() == 27); 1092 auto id = x.identity(); 1093 y.redefine(id, x); 1094 REQUIRE(y == x); 1095 y.redefine(x, id); 1096 REQUIRE(y == x); 1097 delete sr; 1098 } 1099 1100 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1101 "012", 1102 "NaturalSemiring hash", 1103 "[quick][element]") { 1104 Semiring<int64_t>* sr = new NaturalSemiring(33, 2); 1105 Element* x = new MatrixOverSemiring<int64_t>( 1106 {{22, 21, 0}, {10, 0, 0}, {1, 32, 1}}, sr); 1107 1108 for (size_t i = 0; i < 1000000; i++) { 1109 x->hash_value(); 1110 } 1111 delete x; 1112 delete sr; 1113 } 1114 1115 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1116 "013", 1117 "Integers delete/copy", 1118 "[quick][element]") { 1119 Semiring<int64_t>* sr = new Integers(); 1120 Element* x = new MatrixOverSemiring<int64_t>( 1121 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 1122 Element* y = x->heap_copy(); 1123 1124 delete x; 1125 Element* expected = new MatrixOverSemiring<int64_t>( 1126 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 1127 REQUIRE(*y == *expected); 1128 delete expected; 1129 1130 MatrixOverSemiring<int64_t> yy 1131 = *static_cast<MatrixOverSemiring<int64_t>*>(y); 1132 REQUIRE(yy == *y); 1133 MatrixOverSemiring<int64_t> zz(yy); 1134 delete y; // does not delete the _vector in y, yy, or zz 1135 REQUIRE(zz == yy); 1136 delete sr; 1137 } 1138 1139 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1140 "014", 1141 "MaxPlusSemiring delete/copy", 1142 "[quick][element]") { 1143 Semiring<int64_t>* sr = new MaxPlusSemiring(); 1144 Element* x = new MatrixOverSemiring<int64_t>( 1145 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 1146 Element* y = x->heap_copy(); 1147 1148 delete x; 1149 Element* expected = new MatrixOverSemiring<int64_t>( 1150 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 1151 REQUIRE(*y == *expected); 1152 delete expected; 1153 1154 MatrixOverSemiring<int64_t> yy 1155 = *static_cast<MatrixOverSemiring<int64_t>*>(y); 1156 REQUIRE(yy == *y); 1157 MatrixOverSemiring<int64_t> zz(yy); 1158 delete y; // does not delete the _vector in y, yy, or zz 1159 REQUIRE(zz == yy); 1160 delete sr; 1161 } 1162 1163 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1164 "015", 1165 "MinPlusSemiring delete/copy", 1166 "[quick][element]") { 1167 Semiring<int64_t>* sr = new MinPlusSemiring(); 1168 Element* x = new MatrixOverSemiring<int64_t>( 1169 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 1170 Element* y = x->heap_copy(); 1171 1172 delete x; 1173 Element* expected = new MatrixOverSemiring<int64_t>( 1174 {{-2, 2, 0}, {-1, 0, 0}, {1, -3, 1}}, sr); 1175 REQUIRE(*y == *expected); 1176 delete expected; 1177 1178 MatrixOverSemiring<int64_t> yy 1179 = *static_cast<MatrixOverSemiring<int64_t>*>(y); 1180 REQUIRE(yy == *y); 1181 MatrixOverSemiring<int64_t> zz(yy); 1182 delete y; // does not delete the _vector in y, yy, or zz 1183 REQUIRE(zz == yy); 1184 delete sr; 1185 } 1186 1187 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1188 "016", 1189 "TropicalMaxPlusSemiring delete/copy", 1190 "[quick][element]") { 1191 Semiring<int64_t>* sr = new TropicalMaxPlusSemiring(23); 1192 Element* x = new MatrixOverSemiring<int64_t>( 1193 {{2, 2, 0}, {1, 0, 0}, {1, 3, 1}}, sr); 1194 Element* y = x->heap_copy(); 1195 1196 delete x; 1197 Element* expected = new MatrixOverSemiring<int64_t>( 1198 {{2, 2, 0}, {1, 0, 0}, {1, 3, 1}}, sr); 1199 REQUIRE(*y == *expected); 1200 delete expected; 1201 1202 MatrixOverSemiring<int64_t> yy 1203 = *static_cast<MatrixOverSemiring<int64_t>*>(y); 1204 REQUIRE(yy == *y); 1205 MatrixOverSemiring<int64_t> zz(yy); 1206 delete y; // does not delete the _vector in y, yy, or zz 1207 REQUIRE(zz == yy); 1208 delete sr; 1209 } 1210 1211 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1212 "017", 1213 "TropicalMinPlusSemiring delete/copy", 1214 "[quick][element]") { 1215 Semiring<int64_t>* sr = new TropicalMinPlusSemiring(23); 1216 Element* x = new MatrixOverSemiring<int64_t>( 1217 {{2, 2, 0}, {1, 0, 0}, {1, 3, 1}}, sr); 1218 Element* y = x->heap_copy(); 1219 1220 delete x; 1221 Element* expected = new MatrixOverSemiring<int64_t>( 1222 {{2, 2, 0}, {1, 0, 0}, {1, 3, 1}}, sr); 1223 REQUIRE(*y == *expected); 1224 delete expected; 1225 1226 MatrixOverSemiring<int64_t> yy 1227 = *static_cast<MatrixOverSemiring<int64_t>*>(y); 1228 REQUIRE(yy == *y); 1229 MatrixOverSemiring<int64_t> zz(yy); 1230 delete y; // does not delete the _vector in y, yy, or zz 1231 REQUIRE(zz == yy); 1232 delete sr; 1233 } 1234 1235 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1236 "018", 1237 "NaturalSemiring delete/copy", 1238 "[quick][element]") { 1239 Semiring<int64_t>* sr = new NaturalSemiring(23, 1); 1240 Element* x = new MatrixOverSemiring<int64_t>( 1241 {{2, 2, 0}, {1, 0, 0}, {1, 3, 1}}, sr); 1242 Element* y = x->heap_copy(); 1243 1244 delete x; 1245 Element* expected = new MatrixOverSemiring<int64_t>( 1246 {{2, 2, 0}, {1, 0, 0}, {1, 3, 1}}, sr); 1247 REQUIRE(*y == *expected); 1248 delete expected; 1249 1250 MatrixOverSemiring<int64_t> yy 1251 = *static_cast<MatrixOverSemiring<int64_t>*>(y); 1252 REQUIRE(yy == *y); 1253 MatrixOverSemiring<int64_t> zz(yy); 1254 delete y; // does not delete the _vector in y, yy, or zz 1255 REQUIRE(zz == yy); 1256 delete sr; 1257 } 1258 1259 LIBSEMIGROUPS_TEST_CASE("MatrixOverSemiring", 1260 "019", 1261 "exceptions", 1262 "[quick][element]") { 1263 Semiring<int64_t>* sr = new NaturalSemiring(23, 1); 1264 REQUIRE_THROWS_AS(MatrixOverSemiring<int64_t>({{0, 0}, {0, 0}}, nullptr), 1265 LibsemigroupsException); 1266 REQUIRE_THROWS_AS( 1267 MatrixOverSemiring<int64_t>(std::vector<std::vector<int64_t>>(), sr), 1268 LibsemigroupsException); 1269 REQUIRE_THROWS_AS( 1270 MatrixOverSemiring<int64_t>({{2, 2, 0}, {0, 0}, {1, 3, 1}}, sr), 1271 LibsemigroupsException); 1272 delete sr; 1273 } 1274 1275 LIBSEMIGROUPS_TEST_CASE("PBR", 1276 "001", 1277 "universal product with convenience constructor", 1278 "[quick][element]") { 1279 Element* x = new PBR({{-3, -1}, {-3, -2, -1, 1, 2, 3}, {-3, -2, -1, 1, 3}}, 1280 {{-3, -1, 1, 2, 3}, {-3, 1, 3}, {-3, -2, -1, 2, 3}}); 1281 1282 Element* y = new PBR({{-3, -2, -1, 1}, {-3, -2, 3}, {-3, 2, 3}}, 1283 {{-3, -2, -1, 3}, {-3, -2, -1, 3}, {-2, 2, 3}}); 1284 1285 Element* z = new PBR({{-3, -2, -1, 1}, {-3, -2, 3}, {-3, 2, 3}}, 1286 {{-3, -2, -1, 3}, {-3, -2, -1, 3}, {-2, 2, 3}}); 1287 1288 Element* xx = new PBR({{5, 3}, 1289 {5, 4, 3, 0, 1, 2}, 1290 {5, 4, 3, 0, 2}, 1291 {5, 3, 0, 1, 2}, 1292 {5, 0, 2}, 1293 {5, 4, 3, 1, 2}}); 1294 Element* yy = new PBR({{5, 4, 3, 0}, 1295 {5, 4, 2}, 1296 {5, 1, 2}, 1297 {5, 4, 3, 2}, 1298 {5, 4, 3, 2}, 1299 {4, 1, 2}}); 1300 1301 REQUIRE(*x == *xx); 1302 REQUIRE(*y == *yy); 1303 1304 z->redefine(x, y); 1305 1306 Element* expected = new PBR({{0, 1, 2, 3, 4, 5}, 1307 {0, 1, 2, 3, 4, 5}, 1308 {0, 1, 2, 3, 4, 5}, 1309 {0, 1, 2, 3, 4, 5}, 1310 {0, 1, 2, 3, 4, 5}, 1311 {0, 1, 2, 3, 4, 5}}); 1312 REQUIRE(*z == *expected); 1313 1314 delete x; 1315 delete xx; 1316 delete y; 1317 delete yy; 1318 delete z; 1319 delete expected; 1320 } 1321 1322 LIBSEMIGROUPS_TEST_CASE("PBR", 1323 "002", 1324 "universal product", 1325 "[quick][element]") { 1326 Element* x = new PBR({{5, 3}, 1327 {5, 4, 3, 0, 1, 2}, 1328 {5, 4, 3, 0, 2}, 1329 {5, 3, 0, 1, 2}, 1330 {5, 0, 2}, 1331 {5, 4, 3, 1, 2}}); 1332 Element* y = new PBR({{5, 4, 3, 0}, 1333 {5, 4, 2}, 1334 {5, 1, 2}, 1335 {5, 4, 3, 2}, 1336 {5, 4, 3, 2}, 1337 {4, 1, 2}}); 1338 1339 Element* z = new PBR({{5, 4, 3, 0}, 1340 {5, 4, 2}, 1341 {5, 1, 2}, 1342 {5, 4, 3, 2}, 1343 {5, 4, 3, 2}, 1344 {4, 1, 2}}); 1345 z->redefine(x, y); 1346 1347 Element* expected = new PBR({{0, 1, 2, 3, 4, 5}, 1348 {0, 1, 2, 3, 4, 5}, 1349 {0, 1, 2, 3, 4, 5}, 1350 {0, 1, 2, 3, 4, 5}, 1351 {0, 1, 2, 3, 4, 5}, 1352 {0, 1, 2, 3, 4, 5}}); 1353 REQUIRE(*z == *expected); 1354 1355 delete x; 1356 delete y; 1357 delete z; 1358 delete expected; 1359 } 1360 1361 LIBSEMIGROUPS_TEST_CASE("PBR", 1362 "003", 1363 "product [bigger than previous]", 1364 "[quick][element]") { 1365 Element* x = new PBR({{5, 3}, 1366 {5, 4, 3, 0, 1, 2}, 1367 {5, 4, 3, 0, 2}, 1368 {5, 3, 0, 1, 2}, 1369 {5, 0, 2}, 1370 {5, 4, 3, 1, 2}, 1371 {}, 1372 {}}); 1373 Element* y = new PBR({{5, 3}, 1374 {5, 4, 3, 0, 1, 2}, 1375 {5, 4, 3, 0, 2}, 1376 {5, 3, 0, 1, 2}, 1377 {5, 0, 2}, 1378 {5, 4, 3, 1, 2}, 1379 {}, 1380 {6}}); 1381 x->redefine(y, y); 1382 Element* expected = new PBR({{0, 1, 2, 3, 4, 5}, 1383 {0, 1, 2, 3, 4, 5}, 1384 {0, 1, 2, 3, 4, 5}, 1385 {0, 1, 2, 3, 4, 5}, 1386 {0, 1, 2, 3, 4, 5}, 1387 {0, 1, 2, 3, 4, 5}, 1388 {}, 1389 {6}}); 1390 1391 REQUIRE(*x == *expected); 1392 1393 delete x; 1394 delete y; 1395 delete expected; 1396 1397 x = new PBR( 1398 {{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {7}}); 1399 y = new PBR( 1400 {{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {7}}); 1401 1402 x->redefine(y, y); 1403 expected = new PBR( 1404 {{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {7}}); 1405 REQUIRE(*x == *expected); 1406 1407 delete x; 1408 delete y; 1409 delete expected; 1410 } 1411 1412 LIBSEMIGROUPS_TEST_CASE("PBR", "004", "hash", "[quick][element]") { 1413 Element* x = new PBR({{1}, {4}, {3}, {1}, {0, 2}, {0, 3, 4, 5}}); 1414 for (size_t i = 0; i < 1000000; i++) { 1415 x->hash_value(); 1416 } 1417 delete x; 1418 } 1419 1420 LIBSEMIGROUPS_TEST_CASE("PBR", "005", "delete/copy", "[quick][element]") { 1421 Element* x = new PBR({{1}, {4}, {3}, {1}, {0, 2}, {0, 3, 4, 5}}); 1422 Element* y = x->heap_copy(); 1423 delete x; 1424 Element* z = new PBR({{1}, {4}, {3}, {1}, {0, 2}, {0, 3, 4, 5}}); 1425 REQUIRE(*y == *z); 1426 delete z; 1427 PBR yy = *static_cast<PBR*>(y); 1428 REQUIRE(yy == *y); 1429 PBR zz(yy); 1430 delete y; // does not delete the _vector in y, yy, or zz 1431 Element* a = new PBR({{1}, {4}, {3}, {1}, {0, 2}, {0, 3, 4, 5}}); 1432 REQUIRE(zz == *a); 1433 delete a; 1434 } 1435 1436 LIBSEMIGROUPS_TEST_CASE("PBR", "006", "exceptions", "[quick][element]") { 1437 REQUIRE_THROWS_AS(PBR({{1}, {4}, {3}, {10}, {0, 2}, {0, 3, 4, 5}}), 1438 LibsemigroupsException); 1439 REQUIRE_THROWS_AS(PBR({{4}, {3}, {0}, {0, 2}, {0, 3, 4, 5}}), 1440 LibsemigroupsException); 1441 1442 REQUIRE_NOTHROW(PBR({{-3, -1}, {-3, -2, -1, 1, 2, 3}, {-3, -2, -1, 1, 3}}, 1443 {{-3, -1, 1, 2, 3}, {-3, 1, 3}, {-3, -2, -1, 2, 3}})); 1444 1445 REQUIRE_NOTHROW(PBR({{}, {}})); 1446 1447 REQUIRE_THROWS_AS(PBR({{-4, -1}, {-3, -2, -1, 1, 2, 3}, {-3, -2, -1, 1, 3}}, 1448 {{-3, -1, 1, 2, 3}, {-3, 1, 3}, {-3, -2, -1, 2, 3}}), 1449 LibsemigroupsException); 1450 1451 REQUIRE_THROWS_AS(PBR({{-4, -1}, {-3, -2, -1, 1, 2, 3}, {-3, -2, -1, 1, 3}}, 1452 {{-3, -1, 1, 2, 3}, {-3, 1, 3}, {-3, -2, -1, 2, 3}}), 1453 LibsemigroupsException); 1454 1455 REQUIRE_THROWS_AS( 1456 PBR({{-4, -1}, {-3, -2, -1, 1, 2, 3}, {-3, -2, -1, 1, 3}}, 1457 {{-3, -1, 1, 2, 3}, {-3, 1, 3}, {-3, -2, -1, 2, 3}, {-1, -2}}), 1458 LibsemigroupsException); 1459 } 1460 1461 template <typename T> test_inverse(Permutation<T> const & p)1462 bool test_inverse(Permutation<T> const& p) { 1463 return p * p.inverse() == p.identity() && p.inverse() * p == p.identity(); 1464 } 1465 1466 LIBSEMIGROUPS_TEST_CASE("Permutation", "001", "inverse", "[quick][element]") { 1467 // Those two constructor if not passed a vector return an element 1468 // with _vector set to null (see issue #87). 1469 // REQUIRE(test_inverse(Permutation<uint16_t>({}))); 1470 // REQUIRE(test_inverse(Permutation<uint16_t>({0}))); 1471 REQUIRE(test_inverse(Permutation<uint16_t>({1, 0}))); 1472 REQUIRE(test_inverse(Permutation<uint16_t>({0, 1}))); 1473 REQUIRE(test_inverse(Permutation<uint16_t>({2, 0, 1, 4, 3}))); 1474 REQUIRE(test_inverse(Permutation<uint16_t>({4, 2, 0, 1, 3}))); 1475 REQUIRE(test_inverse(Permutation<uint16_t>({0, 1, 2, 3, 4}))); 1476 } 1477 1478 LIBSEMIGROUPS_TEST_CASE("Permutation", 1479 "002", 1480 "exceptions", 1481 "[quick][element]") { 1482 REQUIRE_NOTHROW(Permutation<uint16_t>(std::vector<uint16_t>({}))); 1483 REQUIRE_NOTHROW(Permutation<uint16_t>(std::vector<uint16_t>({0}))); 1484 REQUIRE_NOTHROW(Permutation<uint16_t>(std::vector<uint16_t>({0, 1}))); 1485 REQUIRE_NOTHROW(Permutation<uint16_t>(std::vector<uint16_t>({1, 0}))); 1486 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 2})), 1487 LibsemigroupsException); 1488 REQUIRE_THROWS_AS(PartialPerm<uint16_t>(std::vector<uint16_t>({1, 0, 3})), 1489 LibsemigroupsException); 1490 REQUIRE_NOTHROW( 1491 Permutation<uint16_t>(std::vector<uint16_t>({1, 4, 0, 3, 2}))); 1492 REQUIRE_THROWS_AS( 1493 PartialPerm<uint16_t>(std::vector<uint16_t>({1, 0, 3, 6, 4})), 1494 LibsemigroupsException); 1495 REQUIRE_THROWS_AS( 1496 PartialPerm<uint16_t>(std::vector<uint16_t>({1, 5, 0, 3, 2})), 1497 LibsemigroupsException); 1498 } 1499 1500 LIBSEMIGROUPS_TEST_CASE("SmallestInteger", "001", "", "[quick][element]") { 1501 REQUIRE(sizeof(SmallestInteger<0>::type) == 1); 1502 REQUIRE(sizeof(SmallestInteger<255>::type) == 1); 1503 REQUIRE(sizeof(SmallestInteger<256>::type) == 2); 1504 REQUIRE(sizeof(SmallestInteger<65535>::type) == 2); 1505 REQUIRE(sizeof(SmallestInteger<65536>::type) == 4); 1506 #if LIBSEMIGROUPS_SIZEOF_VOID_P == 8 1507 REQUIRE(sizeof(SmallestInteger<4294967295>::type) == 4); 1508 REQUIRE(sizeof(SmallestInteger<4294967296>::type) == 8); 1509 #endif 1510 } 1511 1512 LIBSEMIGROUPS_TEST_CASE("Transf", "002", "", "[quick][element]") { 1513 auto x = TransfHelper<3>::type({0, 1, 2}); 1514 (void) x; 1515 auto y = PPermHelper<3>::type({0, 1, 2}); 1516 (void) y; 1517 auto z = PermHelper<3>::type({0, 1, 2}); 1518 (void) z; 1519 auto a = BMatHelper<3>::type({{0, 1}, {0, 1}}); 1520 (void) a; 1521 } 1522 } // namespace libsemigroups 1523