Скажем, я хочу пройти от узла № 154 к узлу № 254, чтобы выбрать самый быстрый из возможных вариантов:
Лучшее, что я могу получить, это: получить первый узел в диапазоне и пройти по порядку от этого узла:
/*
* Look for a node matching a key range in tree.
* Returns a pointer to the node if found, else NULL.
*/
struct rb_node *rb_range(struct rb_tree *tree, void *data, int (*func)(const void *, const void *))
{
struct rb_node *node = rb_first(tree);
int res;
while (node != rb_nil(tree)) {
if ((res = func(data, node->data)) == 0) {
return node;
}
node = res < 0 ? node->left : node->right;
}
return NULL;
}
Функция сравнения выглядит так:
static int range_comp(const void *range, const void *data)
{
const long ele = *(const long *)data;
const long *arr = range;
if ((ele >= arr[0]) && (ele <= arr[1])) {
return 0;
}
if (ele > arr[0]) {
return -1;
} else {
return +1;
}
}
И обратный вызов, идущий по результату (есть комментарий, чтобы увидеть, сколько узлов было отправлено в обратный вызов):
static int print_data(void *data, void *cookie)
{
long value = *(long *)data;
const long *arr = cookie;
if (cookie != NULL) {
if (value > arr[1]) {
return 1;
}
// if (value >= arr[0]) {
printf("%ld\n", value);
// }
}
return 0;
}
Обход в порядке:
/*
* Call func() for each node, passing it the node data and a cookie;
* If func() returns non-zero for a node, the traversal stops and the
* error value is returned. Returns 0 on successful traversal.
*/
int rb_apply_node(struct rb_tree *tree, struct rb_node *node,
int (*func)(void *, void *), void *cookie, enum rb_traversal order)
{
int error;
if (node != rb_nil(tree)) {
if (order == preorder)
if ((error = func(node->data, cookie)) != 0)
return error;
if ((error = rb_apply_node(tree, node->left, func, cookie, order)) != 0)
return error;
if (order == inorder)
if ((error = func(node->data, cookie)) != 0)
return error;
if ((error = rb_apply_node(tree, node->right, func, cookie, order)) != 0)
return error;
if (order == postorder)
if ((error = func(node->data, cookie)) != 0)
return error;
}
return 0;
}
long x = rand() % n;
printf("%d) Printing from %ld to %ld\n", i, x, x + 100);
long arr[] = {x, x + 100};
node = rb_range(tree, arr, range_comp);
if (node != NULL) {
/* Iterate from node A to node B INORDER */
rb_apply_node(tree, node, print_data, arr, inorder);
}
Но я получаю слишком много результатов:
0 2 3 4 5 6 8 10 12 13 14 16 17 18 19 20 21 22 23 25 26 27 28 29 31 32 35 36 38 39 40 41 42 43 44 45 47 48 50 51 53 57 59 60 61 62 63 64 65 67 68 72 75 76 77 78 80 81 82 83 85 88 90 91 93 95 96 98 100 101 102 108 109 111 112 113 115 116 117 118 121 122 123 124 125 126 127 128 129 131 132 135 136 137 138 141 143 145 146 148 149 150 153 157 158 161 163 166 168 169 170 172 173 174 175 176 177 178 179 180 182 183 186 188 189 190 192 193 194 195 196 197 198 199 200 201 202 203 205 206 210 212 216 217 218 219 220 221 222 223 225 226 227 228 229 230 231 233 234 235 236 238 239 240 241 244 245 249 252 253 254
Как я могу ограничить результат (насколько это возможно) выбранным диапазоном (от 154 до 254)?