| 1110 | |
| 1111 | template <typename METRIC, typename PAYLOAD> |
| 1112 | auto |
| 1113 | DiscreteSpace<METRIC, PAYLOAD>::lower_node(METRIC const &target) -> Node * { |
| 1114 | Node *n = _root; // current node to test. |
| 1115 | Node *zret = nullptr; // best node so far. |
| 1116 | |
| 1117 | // Fast check for sequential insertion |
| 1118 | if (auto ln = _list.tail(); ln != nullptr && ln->max() < target) { |
| 1119 | return ln; |
| 1120 | } |
| 1121 | |
| 1122 | while (n) { |
| 1123 | if (target < n->min()) { |
| 1124 | n = left(n); |
| 1125 | } else { |
| 1126 | zret = n; // this is a better candidate. |
| 1127 | if (n->max() < target) { |
| 1128 | n = right(n); |
| 1129 | } else { |
| 1130 | break; |
| 1131 | } |
| 1132 | } |
| 1133 | } |
| 1134 | return zret; |
| 1135 | } |
| 1136 | |
| 1137 | template <typename METRIC, typename PAYLOAD> |
| 1138 | auto |
no test coverage detected