Insert one element in the tree somewhere below node_idx */
| 120 | |
| 121 | /** Insert one element in the tree somewhere below node_idx */ |
| 122 | void InsertRecursive(const T &element, size_t node_idx, int level) |
| 123 | { |
| 124 | /* Dimension index of current level */ |
| 125 | int dim = level % 2; |
| 126 | /* Node reference */ |
| 127 | node &n = this->nodes[node_idx]; |
| 128 | |
| 129 | /* Coordinate of element splitting at this node */ |
| 130 | CoordT nc = TxyFunc()(n.element, dim); |
| 131 | /* Coordinate of the new element */ |
| 132 | CoordT ec = TxyFunc()(element, dim); |
| 133 | /* Which side to insert on */ |
| 134 | size_t &next = (ec < nc) ? n.left : n.right; |
| 135 | |
| 136 | if (next == INVALID_NODE) { |
| 137 | /* New leaf */ |
| 138 | size_t newidx = this->AddNode(element); |
| 139 | /* Vector may have been reallocated at this point, n and next are invalid */ |
| 140 | node &nn = this->nodes[node_idx]; |
| 141 | if (ec < nc) nn.left = newidx; else nn.right = newidx; |
| 142 | } else { |
| 143 | this->InsertRecursive(element, next, level + 1); |
| 144 | } |
| 145 | } |
| 146 | |
| 147 | /** |
| 148 | * Free all children of the given node |