Is the ascend iteration work with a filter or not?

[steavenku]

I cannot do ascend iteration work with a filter(with a struct), is there any operation should be added in the function of iteration?

[Foxbud]

Did you try using the pivot parameter of the btree_ascend function?

The readme gives this example of how to use it:

printf("\n-- iterate beginning with last name `Murphy` --\n");
btree_ascend(tr, &(struct user){.first="",.last="Murphy"}, user_iter, NULL);

[ghost]

I've used the pivot parameter. The issue is, as the example, if the first item in the btree is the last name of "Murphy", the rest of the item in the btree will also iterate out even the item is not matching the last name of "Murphy".

[helple]

@tidwall Hi, btree_ascend & btree_descend with pivot parameter not working

#include <stdio.h>
#include <string.h>
#include "btree.h"

struct user {
    char *first;
    char *last;
    int age;
};

int user_compare(const void *a, const void *b, void *udata) {
    const struct user *ua = a;
    const struct user *ub = b;
    int cmp = strcmp(ua->last, ub->last);
    if (cmp == 0) {
        cmp = strcmp(ua->first, ub->first);
    }
    return cmp;
}

bool user_iter(const void *a, void *udata) {
    const struct user *user = a;
    printf("%s %s (age=%d)\n", user->first, user->last, user->age);
    return true;
}

int main() {
    // create a new btree where each item is a `struct user`. 
    struct btree *tr = btree_new(sizeof(struct user), 0, user_compare, NULL);

    // load some users into the btree. Each set operation performas a copy of 
    // the data that is pointed to in the second argument.
    btree_set(tr, &(struct user){ .first="John", .last="Doe", .age=101 });
    btree_set(tr, &(struct user){ .first="Barack", .last="Obama", .age=44 });
    btree_set(tr, &(struct user){ .first="Emmanuel", .last="Macron", .age=68 });
    btree_set(tr, &(struct user){ .first="Jeanne", .last="d'Arc", .age=47 });

    btree_ascend(tr, &(struct user){.first="",.last="Macron"}, user_iter, NULL);

    // btree_descend(tr, &(struct user){.first="",.last="Macron"}, user_iter, NULL);

    btree_free(tr);
}

Output :

Barack Obama (age=44)
Emmanuel Macron (age=68)
Jeanne d'Arc (age=47)
John Doe (age=101)

[tidwall]

@helple where's the "user_compare" function?

[helple]

@tidwall I forgot to add it when I had copy paste the code in this issue. I just added it

[tidwall]

I just ran your code. This is what I got:

Emmanuel Macron (age=68)
Barack Obama (age=44)
Jeanne d'Arc (age=47)

[helple]

@tidwall Hum, Can we pivot on age?

Maybe I don't understand how this function works? I was expecting to have the same effect as a sort function that would have sorted the tree relative to the pivot then iterate

[tidwall]

No, in your case you cannot pivot on age because the btree is not ordered by age. Your btree is ordered by (last name, first name).

If you want to order by age then you need an additional btree that is ordered by age.

[tidwall]

For example:

#include <stdio.h>
#include <string.h>
#include "btree.h"

struct user {
    char *first;
    char *last;
    int age;
};

int name_compare(const void *a, const void *b, void *udata) {
    const struct user *ua = a;
    const struct user *ub = b;
    int cmp = strcmp(ua->last, ub->last);
    if (cmp == 0) {
        cmp = strcmp(ua->first, ub->first);
    }
    return cmp;
}

int age_compare(const void *a, const void *b, void *udata) {
    const struct user *ua = a;
    const struct user *ub = b;
    if (ua->age < ub->age) {
        return -1;
    }
    if (ua->age > ub->age) {
        return 1;
    }
    return name_compare(a, b, udata);
}


bool user_iter(const void *a, void *udata) {
    const struct user *user = a;
    printf("%s %s (age=%d)\n", user->first, user->last, user->age);
    return true;
}

int main() {

    // create a new btree where each item is a `struct user`. 
    struct btree *tr = btree_new(sizeof(struct user), 0, name_compare, NULL);

    // load some users into the btree. Each set operation performas a copy of 
    // the data that is pointed to in the second argument.
    btree_set(tr, &(struct user){ .first="John", .last="Doe", .age=101 });
    btree_set(tr, &(struct user){ .first="Barack", .last="Obama", .age=44 });
    btree_set(tr, &(struct user){ .first="Emmanuel", .last="Macron", .age=68 });
    btree_set(tr, &(struct user){ .first="Jeanne", .last="d'Arc", .age=47 });

    // create a new btree where each item is a `struct user`. 
    struct btree *tr2 = btree_new(sizeof(struct user), 0, age_compare, NULL);

    // load some users into the btree. Each set operation performas a copy of 
    // the data that is pointed to in the second argument.
    btree_set(tr2, &(struct user){ .first="John", .last="Doe", .age=101 });
    btree_set(tr2, &(struct user){ .first="Barack", .last="Obama", .age=44 });
    btree_set(tr2, &(struct user){ .first="Emmanuel", .last="Macron", .age=68 });
    btree_set(tr2, &(struct user){ .first="Jeanne", .last="d'Arc", .age=47 });

    printf("\n-- by last name --\n");
    btree_ascend(tr, &(struct user){.first="",.last="Macron"}, user_iter, NULL);
    printf("\n-- by age --\n");
    btree_ascend(tr2, &(struct user){.first="",.last="",.age=47}, user_iter, NULL);

    btree_free(tr);
    btree_free(tr2);
}

-- by last name --
Emmanuel Macron (age=68)
Barack Obama (age=44)
Jeanne d'Arc (age=47)

-- by age --
Jeanne d'Arc (age=47)
Emmanuel Macron (age=68)
John Doe (age=101)

[helple]

OK, I understand. It's all related to the "compare" function, I just misunderstood how it worked.

Thanks for your help, so quickly. I appreciate. If you have a patreon or paypal, send me the link, i'd like to tip you for a coffee.

Have a nice day (I am French so sorry if my English was not perfect)