1 // Copyright 2015, Tobias Hermann and the FunctionalPlus contributors.
2 // https://github.com/Dobiasd/FunctionalPlus
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt or copy at
5 //  http://www.boost.org/LICENSE_1_0.txt)
6 
7 #include <doctest/doctest.h>
8 #include <fplus/fplus.hpp>
9 
10 
11 namespace {
12     typedef std::pair<int, int> IntPair;
13     typedef std::vector<int> IntVector;
14     typedef std::vector<IntPair> IntPairVector;
15     typedef fplus::tree<IntPair> IntPairTree;
16     typedef fplus::tree<int> IntTree;
17     typedef std::vector<IntPairTree> IntPairTreeVector;
18 }
19 
20 TEST_CASE("tree_test - are_trees_equal")
21 {
22     using namespace fplus;
23 
24     const IntPairTree a =
25         {{0, 8}, {
26             {{0, 4}, {}},
27             {{5, 7}, {}}}};
28 
29     const IntPairTree b =
30         {{0, 8}, {
31             {{5, 7}, {}},
32             {{0, 4}, {}}}};
33 
34     REQUIRE(are_trees_equal(a, b));
35 }
36 
37 TEST_CASE("tree_test - sequence_to_tree small")
38 {
39     using namespace fplus;
40     IntPairVector elems = {
41         {0, 4},
42         {0, 8},
43         {5, 7}
44     };
45 
46     const auto is_child_of = [](const IntPair& a, const IntPair& b) -> bool
__anonb3137d250202(const IntPair& a, const IntPair& b) 47     {
48         return a.first >= b.first && a.second <= b.second;
49     };
50 
51     const auto result_1 = trees_from_sequence(is_child_of, elems);
52     const auto result_2 = trees_from_sequence(is_child_of, fplus::shuffle(0, elems));
53 
54     const IntPairTreeVector result = {
55         {{0, 8}, {
56             {{0, 4}, {}},
57             {{5, 7}, {}}}}
58         };
59 
60     REQUIRE_EQ(result_1.size(), result_2.size());
61     REQUIRE(all(zip_with(are_trees_equal<IntPair>, result_1, result_2)));
62 
63     REQUIRE_EQ(result_1.size(), result.size());
64     REQUIRE(all(zip_with(are_trees_equal<IntPair>, result_1, result)));
65 }
66 
67 TEST_CASE("tree_test - sequence_to_tree medium")
68 {
69     using namespace fplus;
70     IntPairVector elems = {
71         {0, 4},
72         {0, 8},
73         {5, 7},
74         {9, 10},
75         {12, 13},
76         {9, 17},
77         {11, 15},
78         {13, 14},
79         {8, 20}
80     };
81 
82     const auto is_child_of = [](const IntPair& a, const IntPair& b) -> bool
__anonb3137d250302(const IntPair& a, const IntPair& b) 83     {
84         return a.first >= b.first && a.second <= b.second;
85     };
86 
87     const auto result_1 = trees_from_sequence(is_child_of, elems);
88     const auto result_2 = trees_from_sequence(is_child_of, fplus::shuffle(0, elems));
89 
90     const IntPairTreeVector result = {
91         {{0, 8}, {
92             {{0, 4}, {}},
93             {{5, 7}, {}}
94         }},
95         {{8, 20}, {
96             {{9, 17}, {
97                 {{9, 10}, {}},
98                 {{11, 15}, {
99                     {{12, 13}, {}},
100                     {{13, 14}, {}}
101                 }}
102             }},
103         }},
104     };
105 
106     REQUIRE_EQ(result_1.size(), result_2.size());
107     REQUIRE(all(zip_with(are_trees_equal<IntPair>, result_1, result_2)));
108 
109     REQUIRE_EQ(result_1.size(), result.size());
110     REQUIRE(all(zip_with(are_trees_equal<IntPair>, result_1, result)));
111 }
112 
113 TEST_CASE("tree_test - tree_depth")
114 {
115     const IntTree t =
116         {{0}, {
117             {{1}, {
118                 {{2}, {
119                 }},
120                 {{3}, {
121                     {{4}, {
122                     }},
123                     {{5}, {
124                     }}
125                 }},
126                 {{6}, {
127                 }}
128             }},
129             {{7}, {
130             }},
131             {{8}, {
132             }}
133         }};
134     REQUIRE_EQ(tree_depth(t), 4);
135 }
136 
137 TEST_CASE("tree_test - flatten_tree_depth_first")
138 {
139     const IntTree t =
140         {{0}, {
141             {{1}, {
142                 {{2}, {
143                 }},
144                 {{3}, {
145                     {{4}, {
146                     }},
147                     {{5}, {
148                     }}
149                 }},
150                 {{6}, {
151                 }}
152             }},
153             {{7}, {
154             }},
155             {{8}, {
156             }}
157         }};
158     REQUIRE_EQ(flatten_tree_depth_first(t), IntVector({0,1,2,3,4,5,6,7,8}));
159 }
160 
161 TEST_CASE("tree_test - flatten_tree_breadth_first")
162 {
163     const IntTree t =
164         {{0}, {
165             {{1}, {
166                 {{4}, {
167                 }},
168                 {{5}, {
169                     {{7}, {
170                     }},
171                     {{8}, {
172                     }}
173                 }},
174                 {{6}, {
175                 }}
176             }},
177             {{2}, {
178             }},
179             {{3}, {
180             }}
181         }};
182     REQUIRE_EQ(flatten_tree_breadth_first(t), IntVector({0,1,2,3,4,5,6,7,8}));
183 }
184