| 1086 | typename U |
| 1087 | > |
| 1088 | bool validate_join_tree ( |
| 1089 | const T& n, |
| 1090 | U& deads, |
| 1091 | unsigned long parent = 0xffffffff |
| 1092 | ) |
| 1093 | /*! |
| 1094 | this function makes sure that a join tree satisfies the following criterion for paths starting at the given node: |
| 1095 | - for all valid i and j such that i and j are both < #join_tree.number_of_nodes() |
| 1096 | - let X be the set of numbers that is contained in both #join_tree.node(i).data |
| 1097 | and #join_tree.node(j).data |
| 1098 | - It is the case that all nodes on the unique path between #join_tree.node(i) |
| 1099 | and #join_tree.node(j) contain the numbers from X in their sets. |
| 1100 | |
| 1101 | returns true if validation passed and false if there is a problem with the tree |
| 1102 | !*/ |
| 1103 | { |
| 1104 | n.data.reset(); |
| 1105 | while (n.data.move_next()) |
| 1106 | { |
| 1107 | if (deads.is_member(n.data.element())) |
| 1108 | return false; |
| 1109 | } |
| 1110 | |
| 1111 | |
| 1112 | for (unsigned long i = 0; i < n.number_of_neighbors(); ++i) |
| 1113 | { |
| 1114 | if (n.neighbor(i).index() == parent) |
| 1115 | continue; |
| 1116 | |
| 1117 | // add anything to dead stuff |
| 1118 | n.data.reset(); |
| 1119 | while (n.data.move_next()) |
| 1120 | { |
| 1121 | if (n.neighbor(i).data.is_member(n.data.element()) == false) |
| 1122 | { |
| 1123 | unsigned long temp = n.data.element(); |
| 1124 | deads.add(temp); |
| 1125 | } |
| 1126 | } |
| 1127 | |
| 1128 | if (validate_join_tree(n.neighbor(i), deads, n.index()) == false) |
| 1129 | return false; |
| 1130 | |
| 1131 | // remove this nodes stuff from dead stuff |
| 1132 | n.data.reset(); |
| 1133 | while (n.data.move_next()) |
| 1134 | { |
| 1135 | if (n.neighbor(i).data.is_member(n.data.element()) == false) |
| 1136 | { |
| 1137 | unsigned long temp = n.data.element(); |
| 1138 | deads.destroy(temp); |
| 1139 | } |
| 1140 | } |
| 1141 | } |
| 1142 | |
| 1143 | return true; |
| 1144 | } |
| 1145 | } |
no test coverage detected