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