| 1088 | typename mem_manager |
| 1089 | > |
| 1090 | bool sequence_kernel_1<T,mem_manager>:: |
| 1091 | remove_from_tree ( |
| 1092 | node*& t, |
| 1093 | unsigned long pos, |
| 1094 | T& item |
| 1095 | ) |
| 1096 | { |
| 1097 | |
| 1098 | // make a reference to the current node so we don't have to dereference |
| 1099 | // a pointer a bunch of times |
| 1100 | node& tree = *t; |
| 1101 | |
| 1102 | // if item is on the left |
| 1103 | if (pos < tree.left_size) |
| 1104 | { |
| 1105 | // adjust the left size |
| 1106 | --tree.left_size; |
| 1107 | |
| 1108 | // if the left side of the tree has the greatest height |
| 1109 | if (tree.balance == -1) |
| 1110 | { |
| 1111 | tree.balance += remove_from_tree(tree.left,pos,item); |
| 1112 | return !tree.balance; |
| 1113 | } |
| 1114 | else |
| 1115 | { |
| 1116 | tree.balance += remove_from_tree(tree.left,pos,item); |
| 1117 | return keep_node_balanced(t); |
| 1118 | } |
| 1119 | |
| 1120 | } |
| 1121 | // if item is found |
| 1122 | else if (pos == tree.left_size) |
| 1123 | { |
| 1124 | // if there is no left node |
| 1125 | if (tree.left == 0) |
| 1126 | { |
| 1127 | // swap nodes element into item |
| 1128 | exchange(tree.item,item); |
| 1129 | |
| 1130 | // plug hole left by removing this node and free memory |
| 1131 | t = tree.right; // plug hole with right subtree |
| 1132 | |
| 1133 | // delete old node |
| 1134 | tree.right = 0; |
| 1135 | delete_nodes(&tree); |
| 1136 | |
| 1137 | // indicate that the height has changed |
| 1138 | return true; |
| 1139 | } |
| 1140 | // if there is no right node |
| 1141 | else if (tree.right == 0) |
| 1142 | { |
| 1143 | // swap nodes element into item |
| 1144 | exchange(tree.item,item); |
| 1145 | |
| 1146 | // plug hole left by removing this node and free memory |
| 1147 | t = tree.left; // plug hole with left subtree |
nothing calls this directly
no test coverage detected