MCPcopy Create free account
hub / github.com/davisking/dlib / remove_from_tree

Method remove_from_tree

dlib/sequence/sequence_kernel_1.h:1090–1208  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

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

Callers

nothing calls this directly

Calls 1

exchangeFunction · 0.85

Tested by

no test coverage detected