module TestChildren

include("../src/GraphIdx.jl")

using Test
import .GraphIdx.Tree: ChildrenIndex, node_degrees, root_node, find_root


@testset "generate(width=5): low level   " begin
    # root, parent = TreeInstance.generate(5)[3:4]
    root = 1
    parent = Int[1, 1, 2, 3, 4, 1, 8, 9, 4, 9]
    cidx = ChildrenIndex(parent, root)
    value_, idx_ = cidx.value, cidx.idx
    @test value_ == [1, 2, 6, 3, 4, 5, 9, 7, 8, 10]
    @test idx_ == [2, 4, 5, 6, 8, 8, 8, 8, 9, 11, 11]
    @test root_node(cidx) == root
    @test length(cidx) == length(parent)
end


@testset "generate(width=5): index access" begin
    # root, parent = TreeInstance.generate(5)[3:4]
    root = 1
    parent = Int[1, 1, 2, 3, 4, 1, 8, 9, 4, 9]
    cidx = ChildrenIndex(parent)
    @test cidx[1] == [2,6]
    @test cidx[2] == [3]
    @test cidx[9] == [8, 10]
    @test cidx[4] == [5, 9]
    @test cidx[10] == []
    @test cidx[7] == []
    @test root_node(cidx) == root
    @test length(cidx) == length(parent)
end


@testset "generate(width=5): index access" begin
    parent0 = Int[1, 1, 2, 3, 4, 1, 8, 9, 4, 9]
    root0 = 1
    @test find_root(parent0) == root0
    n = length(parent0)

    # import Random
    # perm = Random.randperm(Random.MersenneTwister(42), 10)
    perm = [9, 3, 1, 5, 10, 7, 2, 6, 4, 8]
    iperm = invperm(perm)
    @test perm[iperm] == 1:n
    @test iperm[perm] == 1:n
    # perm: old  -> new
    # iperm: new -> old
    # parent0: old i -> old parent
    # parent1: new i -> old i -> old parent -> new parent
    parent1 = perm[parent0[iperm]]
    root1 = find_root(parent1)
    @test root1 == perm[root0]

    cidx = ChildrenIndex(parent1)
    @test root_node(cidx) == root1
    @test length(cidx) == length(parent1)

    @test Set(cidx[perm[1]]) == Set(perm[[2,6]])
    @test Set(cidx[perm[2]]) == Set(perm[[3]])
    @test Set(cidx[perm[9]]) == Set(perm[[8, 10]])
    @test Set(cidx[perm[4]]) == Set(perm[[5, 9]])
    @test Set(cidx[perm[10]]) == Set(perm[[]])
    @test Set(cidx[perm[7]]) == Set(perm[[]])
end


@testset "generate(width=21): some tests " begin
    # pi = TreeInstance.generate(21)[4]
    pi = [1, 1, 2, 3, 4, 7, 8, 29, 8, 9, 32, 33, 34, 35, 36, 37, 16,
    19, 40, 21, 42, 1, 22, 25, 4, 25, 26, 27, 28, 29, 10, 31, 34, 55,
    56, 57, 36, 17, 18, 41, 20, 63, 64, 23, 44, 67, 48, 69, 28, 29,
    72, 51, 52, 33, 76, 55, 56, 57, 38, 59, 60, 63, 84, 65, 86, 65,
    66, 47, 70, 49, 70, 73, 74, 95, 74, 75, 98, 99, 78, 59, 80, 81,
    104, 105, 86, 87, 108, 67, 68, 111, 92, 71, 92, 93, 94, 95, 76,
    97, 98, 79, 122, 103, 82, 103, 104, 127, 108, 109, 110, 89, 110,
    91, 114, 93, 114, 115, 138, 117, 98, 119, 120, 121, 144, 103, 146,
    105, 128, 107, 130, 131, 110, 131, 134, 155, 134, 137, 116, 137,
    138, 141, 142, 121, 164, 145, 124, 145, 126, 127, 128, 149, 152,
    153, 132, 153, 154, 155, 156, 137, 138, 159, 140, 163, 142, 163,
    166, 145, 146, 147]

    cidx = ChildrenIndex(pi)
    @test cidx[162] == []
    @test Set(cidx[137]) == Set([138, 136, 158])
    @test Set(cidx[1]) == Set([2, 22])
    @test cidx[89] == [110]
    @test root_node(cidx) == 1
    @test length(cidx) == length(pi)
end

@testset "generate(width=50)             " begin
    # pi =  TreeInstance.generate(50)[4]

    pi = [1, 1, 2, 3, 4, 7, 57, 7, 59, 9, 61, 13, 63, 64, 16, 17, 67,
    68, 18, 21, 71, 21, 73, 23, 24, 25, 28, 78, 28, 31, 81, 82, 32,
    84, 85, 35, 36, 88, 40, 90, 91, 43, 93, 45, 95, 45, 97, 98, 99,
    100, 101, 51, 3, 55, 5, 55, 56, 108, 60, 110, 111, 61, 62, 63, 64,
    116, 117, 67, 68, 69, 70, 71, 72, 73, 76, 26, 127, 128, 78, 79,
    82, 132, 82, 83, 135, 36, 137, 89, 139, 89, 90, 91, 92, 144, 94,
    95, 98, 99, 149, 99, 102, 103, 53, 54, 55, 107, 157, 107, 59, 160,
    110, 62, 112, 115, 165, 117, 167, 168, 118, 70, 71, 72, 73, 74,
    75, 125, 126, 127, 128, 129, 130, 182, 134, 184, 185, 86, 136,
    137, 138, 90, 140, 141, 193, 145, 195, 96, 146, 198, 199, 149,
    152, 153, 103, 104, 105, 155, 207, 159, 209, 159, 162, 112, 162,
    214, 164, 165, 217, 167, 119, 120, 172, 122, 123, 175, 176, 126,
    176, 177, 178, 179, 180, 181, 182, 183, 184, 187, 137, 138, 239,
    140, 141, 191, 192, 144, 245, 246, 198, 248, 198, 199, 151, 203,
    153, 254, 155, 156, 206, 258, 259, 211, 261, 211, 212, 213, 165,
    215, 267, 268, 169, 219, 271, 272, 224, 274, 175, 176, 228, 278,
    179, 180, 232, 182, 283, 233, 236, 186, 187, 288, 238, 241, 242,
    243, 193, 243, 244, 247, 297, 247, 248, 300, 201, 302, 252, 255,
    205, 257, 207, 259, 309, 310, 260, 212, 262, 263, 315, 216, 266,
    269, 219, 271, 321, 273, 223, 324, 276, 326, 327, 328, 329, 230,
    231, 281, 282, 334, 284, 236, 286, 287, 288, 291, 241, 291, 243,
    344, 245, 246, 298, 348, 349, 299, 302, 352, 304, 254, 304, 256,
    257, 309, 359, 309, 261, 311, 312, 313, 316, 317, 367, 368, 269,
    319, 320, 323, 373, 323, 324, 376, 326, 378, 330, 331, 332, 333,
    283, 333, 336, 337, 338, 288, 289, 341, 291, 341, 293, 343, 344,
    345, 346, 347, 348, 400, 401, 353, 403, 304, 405, 306, 307, 357,
    358, 359, 311, 412, 313, 363, 364, 367, 368, 369, 319, 420, 321,
    371, 372, 324, 374, 377, 427, 377, 380, 330, 380, 381, 433, 385,
    386, 436, 437, 338, 390, 391, 441, 442, 392, 344, 345, 395, 347,
    348, 398, 399, 451, 452, 402, 454, 455, 356, 457, 358, 359, 460,
    410, 462, 414, 464, 365, 417, 367, 368, 418, 419, 371, 372, 424,
    374, 424, 427, 428, 478, 430, 380, 432, 382, 432, 384, 485, 486,
    487, 388, 438, 390, 491, 441, 442, 494, 444, 445, 448, 398, 499,
    500, 452, 502, 503, 453, 505, 455, 456, 459, 460, 510, 411, 463,
    464, 514, 415, 467, 417, 467, 419, 520, 472, 422, 423, 424, 425,
    526, 427, 479, 429, 530, 431, 532, 533, 483, 535, 536, 488, 438,
    539, 489, 541, 493, 443, 493, 445, 446, 498, 548, 498, 499, 502,
    503, 504, 505, 555, 507, 508, 509, 510, 511, 561, 462, 463, 564,
    514, 517, 467, 568, 518, 570, 522, 472, 573, 574, 575, 527, 477,
    529, 479, 580, 581, 582, 583, 484, 585, 586, 536, 488, 538, 490,
    540, 592, 544, 494, 546, 547, 548, 598, 548, 600, 601, 551, 603,
    604, 556, 506, 507, 557, 509, 561, 611, 561, 562, 563, 564, 516,
    568, 569, 570, 571, 521, 571, 572, 575, 625, 575, 527, 528, 529,
    579, 580, 632, 582, 534, 584, 587, 588, 589, 539, 589, 590, 591,
    592, 593, 645, 546, 598, 599, 600, 650, 602, 652, 604, 605, 606,
    556, 557, 558, 610, 611, 661, 611, 663, 664, 616, 566, 567, 617,
    618, 621, 622, 572, 622, 625, 626, 627, 677, 578, 628, 631, 581,
    631, 632, 633, 685, 686, 587, 588, 640, 590, 640, 692, 693, 645,
    646, 696, 646, 698, 648, 700, 652, 653, 654, 604, 656, 706, 607,
    608, 609, 659, 662, 712, 664, 665, 615, 716, 666, 718, 619, 669,
    721, 671, 723, 673, 625, 675, 678, 628, 678, 630, 631, 683, 633,
    683, 686, 687, 637, 638, 688, 640, 641, 693, 694, 644, 694, 746,
    647, 697, 698, 750, 702, 652, 753, 654, 706, 707, 657, 658, 708,
    660, 710, 713, 663, 713, 714, 766, 667, 719, 669, 670, 722, 772,
    722, 725, 726, 776, 677, 678, 779, 729, 730, 731, 734, 735, 736,
    737, 687, 788, 738, 690, 740, 743, 744, 694, 744, 796, 748, 749,
    699, 749, 752, 753, 754, 704, 754, 806, 758, 708, 758, 761, 811,
    712, 764, 714, 815, 816, 766, 818, 719, 769, 821, 773, 823, 824,
    825, 777, 727, 777, 780, 830, 731, 781, 833, 783, 735, 787, 737,
    787, 788, 789, 741, 791, 792, 795, 845, 846, 847, 799, 749, 850,
    851, 803, 753, 803, 804, 856, 808, 758, 759, 760, 861, 811, 812,
    764, 814, 815, 867, 868, 820, 821, 822, 872, 822, 825, 875, 825,
    826, 778, 879, 880, 881, 782, 832, 884, 885, 786, 836, 888, 838,
    890, 840, 841, 844, 845, 895, 896, 846, 798, 899, 849, 901, 802,
    803, 853, 854, 855, 856, 857, 809, 861, 862, 863, 864, 865, 866,
    816, 866, 867, 868, 869, 870, 871, 872, 924, 876, 877, 927, 828,
    878, 879, 882, 883, 933, 883, 886, 836, 886, 938, 939, 889, 890,
    842, 892, 893, 945, 895, 896, 848, 898, 850, 902, 903, 904, 854,
    855, 856, 906, 907, 959, 911, 861, 913, 863, 913, 965, 866, 916,
    968, 869, 870, 871, 972, 873, 923, 924, 976, 977, 927, 928, 929,
    930, 931, 932, 884, 936, 937, 887, 937, 989, 939, 940, 892, 893,
    943, 995, 947, 897, 947, 950, 900, 952, 953, 903, 955, 956, 906,
    907, 957, 960, 961, 911, 961, 964, 914, 966, 916, 966, 967, 968,
    971, 972, 973, 974, 975, 925, 975, 976, 977, 929, 930, 931, 932,
    933, 983, 935, 987, 988, 938, 988, 940, 941, 993, 994, 944, 994,
    997, 947, 948, 998, 999]

    n = length(pi)
    @test all(pi .>= 1)
    @test all(pi .<= n)
    deg = node_degrees(pi)
    @test maximum(deg) == 3
    cidx = ChildrenIndex(pi)
    @test root_node(cidx) == 1
    @test length(cidx) == length(pi)
end

end
