------------------------------------------------------------------------ P6 Requirements: x is the root of the pertinent subtree and has two partial children. P1, P2 and P4 didn't match ==> at least two partial children.
| 1158 | // ==> at least two partial children. |
| 1159 | // |
| 1160 | bool pq_tree::P6(p_node* x) |
| 1161 | { |
| 1162 | if (x->partial_count > 2) { |
| 1163 | return false; |
| 1164 | } |
| 1165 | |
| 1166 | |
| 1167 | q_node* part2 = x->partial_sons.front()->Q(); |
| 1168 | x->partial_sons.erase(x->partial_sons.begin()); |
| 1169 | q_node* part1 = x->partial_sons.front()->Q(); |
| 1170 | part1->n = x->n; |
| 1171 | part1->id = x->id; |
| 1172 | pq_node* ins; |
| 1173 | |
| 1174 | if (x->full_count > 1) { |
| 1175 | ins = new p_node(x->n, x->id, x->full_sons); |
| 1176 | } |
| 1177 | else if (x->full_count == 1) { |
| 1178 | ins = x->full_sons.front(); |
| 1179 | x->full_sons.erase(x->full_sons.begin()); |
| 1180 | assert(x->full_sons.empty()); |
| 1181 | } |
| 1182 | else { |
| 1183 | ins = 0; |
| 1184 | } |
| 1185 | |
| 1186 | part1->sons.back()->is_endmost = false; |
| 1187 | |
| 1188 | if (ins) { |
| 1189 | ins->up = x->n; |
| 1190 | ins->up_id = x->id; |
| 1191 | ins->is_endmost = false; |
| 1192 | ins->pos = part1->sons.insert(part1->sons.end(), ins); |
| 1193 | } |
| 1194 | |
| 1195 | part2->turn(); |
| 1196 | part2->sons.front()->is_endmost = false; |
| 1197 | part2->sons.back()->father = part1; |
| 1198 | part1->sons.splice(part1->sons.end(), part2->sons.begin(), |
| 1199 | part2->sons.end()); |
| 1200 | part1->pert_end = part2->pert_begin; |
| 1201 | part1->pert_end.reverse(); |
| 1202 | x->child_count -= (x->full_count + 1); |
| 1203 | delete part2; |
| 1204 | |
| 1205 | if (x->child_count == 1) { |
| 1206 | if (root == x) { |
| 1207 | root = part1; |
| 1208 | } |
| 1209 | else { |
| 1210 | *(x->pos) = part1; |
| 1211 | } |
| 1212 | part1->pos = x->pos; |
| 1213 | part1->is_endmost = x->is_endmost; |
| 1214 | part1->father = x->father; |
| 1215 | part1->up = x->up; |
| 1216 | part1->up_id = x->up_id; |
| 1217 | x->partial_sons.erase(x->partial_sons.begin()); |