xref: /aosp_15_r20/external/fonttools/Tests/misc/treeTools_test.py (revision e1fe3e4ad2793916b15cccdc4a7da52a7e1dd0e9) 
1from fontTools.misc.treeTools import build_n_ary_tree
2import pytest
3
4
5@pytest.mark.parametrize(
6    "lst, n, expected",
7    [
8        ([0], 2, [0]),
9        ([0, 1], 2, [0, 1]),
10        ([0, 1, 2], 2, [[0, 1], 2]),
11        ([0, 1, 2], 3, [0, 1, 2]),
12        ([0, 1, 2, 3], 2, [[0, 1], [2, 3]]),
13        ([0, 1, 2, 3], 3, [[0, 1, 2], 3]),
14        ([0, 1, 2, 3, 4], 3, [[0, 1, 2], 3, 4]),
15        ([0, 1, 2, 3, 4, 5], 3, [[0, 1, 2], [3, 4, 5]]),
16        (list(range(7)), 3, [[0, 1, 2], [3, 4, 5], 6]),
17        (list(range(8)), 3, [[0, 1, 2], [3, 4, 5], [6, 7]]),
18        (list(range(9)), 3, [[0, 1, 2], [3, 4, 5], [6, 7, 8]]),
19        (list(range(10)), 3, [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], 9]),
20        (list(range(11)), 3, [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], 9, 10]),
21        (list(range(12)), 3, [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [9, 10, 11]]),
22        (list(range(13)), 3, [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [9, 10, 11], 12]),
23        (
24            list(range(14)),
25            3,
26            [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [[9, 10, 11], 12, 13]],
27        ),
28        (
29            list(range(15)),
30            3,
31            [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [9, 10, 11], [12, 13, 14]],
32        ),
33        (
34            list(range(16)),
35            3,
36            [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [[9, 10, 11], [12, 13, 14], 15]],
37        ),
38        (
39            list(range(23)),
40            3,
41            [
42                [[0, 1, 2], [3, 4, 5], [6, 7, 8]],
43                [[9, 10, 11], [12, 13, 14], [15, 16, 17]],
44                [[18, 19, 20], 21, 22],
45            ],
46        ),
47        (
48            list(range(27)),
49            3,
50            [
51                [[0, 1, 2], [3, 4, 5], [6, 7, 8]],
52                [[9, 10, 11], [12, 13, 14], [15, 16, 17]],
53                [[18, 19, 20], [21, 22, 23], [24, 25, 26]],
54            ],
55        ),
56        (
57            list(range(28)),
58            3,
59            [
60                [
61                    [[0, 1, 2], [3, 4, 5], [6, 7, 8]],
62                    [[9, 10, 11], [12, 13, 14], [15, 16, 17]],
63                    [[18, 19, 20], [21, 22, 23], [24, 25, 26]],
64                ],
65                27,
66            ],
67        ),
68        (list(range(257)), 256, [list(range(256)), 256]),
69        (list(range(258)), 256, [list(range(256)), 256, 257]),
70        (list(range(512)), 256, [list(range(256)), list(range(256, 512))]),
71        (list(range(512 + 1)), 256, [list(range(256)), list(range(256, 512)), 512]),
72        (
73            list(range(256**2)),
74            256,
75            [list(range(k * 256, k * 256 + 256)) for k in range(256)],
76        ),
77    ],
78)
79def test_build_n_ary_tree(lst, n, expected):
80    assert build_n_ary_tree(lst, n) == expected
81