Keep children sorted

Hello,

I have extended the base object to enable managing widget children in a sorted manner. Kind of the emails in your inbox are kept sorted by some criteria even if new emails arrive and/or other emails are deleted.

For this, I’ve added new functions lv_XXX_create_sorted, which work similar to the existing functions, but insert at positions defined by user-defined sort-criteria instead of the end of the child list. If no sort-criteria is defined, those functions fall back to act like the old lv_XXX_create functions.

Here’s an example:


static int sort_compar (const void *btn, const void *new_obj_data)
{
    char *user_data = lv_obj_get_user_data (btn);

    return strcmp (user_data, new_obj_data);
}

static void add_new_item (lv_obj_t *parent, char *criteria)
{
    lv_obj_t *b = lv_btn_create_sorted (parent,
                                        NULL,
                                        sort_compar,
                                        criteria);

    lv_obj_allocate_user_data(b, strlen(criteria)+1, criteria);
}

void create_sorted_page (void)
{
    lv_obj_t *page = lv_page_create (it1010_container_main, NULL);
    lv_obj_t *scrollable = lv_page_get_scrollable (evlist_page);

    add_item (scrollable, "Orange");
    add_item (scrollable, "Banana");
    add_item (scrollable, "Pie");
    add_item (scrollable, "Beer");
    add_item (scrollable, "Apple");
}

The original lv_XXX_create functions still exist, but simply call the new functions with the last two arguments set to NULL.

As can be seen in this example, I’ve also added two functions to handle user_data, which are much simpler to use and also way more flexible than the currently existing user_data functions. The user_data could be anything. I prefer strings, as they are very flexible.

A drawback here is that one have to manually go to the container part of the parent widget. I’ve not yet figured how to modify the page, list (and maybe other) widgets to “forward” the create onto their proper container part.

For deleting obejects, I’ve also added a new function:

static int match_cb (const void *btn, const void *match_data)
{
    char *user_data = lv_obj_get_user_data (btn);

    return ! strcmp(user_data, match_data);
}
void delete_object(lv_obj_t* scrollable)
{
    lv_obj_del_matching (scrollable, match_cb, "Banana", LV_DEL_MATCH_ALL);
}

Any suggestions or thoughts on this?

Hi,

I think this feature would be useful in many cases.

I have a different idea about the implementation to avoid adding new create functions.

I’m thinking in v8, where multiple event callbacks can be added to an object and end each event_cb can store a user_data. See an example here.

So we could define a new event_code, e.g. LV_EVENT_GET_SORT_CRITERIA and add the criteria like this after the object is created:

lv_obj_add_event_cb(obj, criteria_event_cb, LV_EVENT_GET_SORT_CRITERIA, "Apple");

Of course this function can be hidden like:

lv_obj_set_sort_criteria(lv_obj_t * obj, const chart * s)
{
  lv_obj_add_event_cb(obj, criteria_event_cb, LV_EVENT_GET_SORT_CRITERIA, s);
}

To get the criteria:

const char * str = NULL;
lv_event_send(obj, LV_EVENT_GET_SORT_CRITERIA, &str);
...
void criteria_event_cb(lv_event_t * e) {
  const char ** s = lv_event_get_param(e);
  *s = lv_event_get_param(e);  //Save the crteria
}

For 2) there can be a generic function that sorts the children when it’s called.

This way this feature is independent of LVGL’s core and it’s an optional plugin.

What do you think?

I don’t understand what events have to do with sorting at all.

Can you give an example how your suggestion would be used?

If I understand your suggestion correctly, you would:

  1. create the child (adding it to the parent on the wrong position)
  2. set the sort criteria for the child (which would trigger an event)
  3. in the event_cb sort the list

The list of children will get unsorted temporarily in step 1. What if something else (maybe another event?) would be triggered at this time? Later in step 3, the full list needs to be sorted. And since the list is almost sorted, something like quicksort could degrade to O(n^2). Quicksort is no option anyway, since children are kept in a double-linked list. So something like mergesort is needed here.

This seems to be somewhat awkward to me. And it seems to add a lot of complexity for such a simple feature.

But probably I misunderstood your suggestion. Can you give an example?

With my suggestion, the child is inserted to the correct position in the first place, because the sort criteria is available at the time the child is created. This is guaranteed to run in O(n). A full-fledged sort is only needed when the comparison function is changed. But this is rarely done.

I don’t see the point in going through hoops by sending events.

I have no idea about LVGL’s policy.

I understand that a feature should be optional if it consumes considerable resources.
This feature does not consume any resources as long as it is not used. Even IF it is used, the added overhead is just the sort procedure itself, which is the whole point of the feature.

So I don’t see the point in making it optional.

Here is an example:

API:

  /*Register a new event code*/
  LV_EVENT_GET_SORT_CRITERIA = lv_event_register_id();
 
  /*Craete new objects and add a criteria */
  lv_obj_t * obj1 = lv_obj_create(lv_scr_act());
  lv_obj_set_sort_criteria(obj1, "banana");

  lv_obj_t * obj2 = lv_obj_create(lv_scr_act());
  lv_obj_set_sort_criteria(obj2, "apple");

  /*Start sorting*/
  lv_obj_sort(lv_scr_act());

Internals:

/*New event code*/
uint32_t LV_EVENT_GET_SORT_CRITERIA;

/*An event callback to get the criteria*/
void criteria_event_cb(lv_event_t * e)
{
    const char ** s = lv_event_get_param(e); /*The result stored in the event parameter*/
    *s = lv_event_get_user_data(e);   /*The criteria was saved as event user_data*/
}

void lv_obj_set_sort_criteria(lv_obj_t * obj, const char * criteria)
{
    /* 'criteria' is the event's user data*/
    lv_obj_add_event_cb(obj, criteria_event_cb, LV_EVENT_GET_SORT_CRITERIA, (char*)criteria);
}

void lv_obj_sort(lv_obj_t * parent)
{
   /*Iterate through the children*/
    uint32_t i;
    for(i = 0; i < lv_obj_get_child_cnt(parent); i++) {
        lv_obj_t * child = lv_obj_get_child(parent, I);

        /*Get the criteria saved in the event's user data and store it in 's'*/
        /*lv_event_send will call criteria_event_cb as it is attached to the object as an event_cb*/
        const char * s;
        lv_event_send(child, LV_EVENT_GET_SORT_CRITERIA, &s);
        printf("criteria: %s\n", s);
        /* Sort here as you wish*/
        /* The children are stored in an array so it's easy to swap them:
         * E.g. parent->spec_attr->children[0] = parent->spec_attr->children[2] */
    }
}

I see two issues with adding it as a core feature:

  1. It’s another rule to follow if a new widget is added. That’s it it has maintenance “cost”. It needs to be documented and tested for every widget.
  2. It makes the API larger for a feature that probably will be used rarely. (I believe it’s a useful feature but certainly not needed by the vast majority of the users).

@kisvegabor, I still don’t understand why events need to be involved in this topic at all.

Why can’t lv_obj_sort() do the sort directly?

And what’s the point of lv_event_send(…&s)? Why can’t lv_obj_sort() call lv_obj_get_sort_criteria() or lv_obj_get_user_data() directly?

For me, from the perspective of a user, events are a mechanism for asynchronous operations. The sorting-problem is a totally synchronic operation. Involving events in this topic appears to be extremely counter-intuitive.

Using events here might appear as a clever use case for somebody who has just implemented a powerful event mechanism. But for me, who looks at it from the perspective as a user, this looks somewhat awkward…

And still, as I wrote in my previous message, You’d do an inefficient full-fledged sort every time a child is added while a simple and efficient insert-sort would do fine.

While talking about documentation cost: a lot of the documentation is redundant. Every API function has a comment block where it is implemented and this block is duplicated in the header file along with the prototype of the function.

At the end of the day, the API should make the use of the library easy. Forcing the user to go through hoops of the event handler don’t seem to be the better alternative to me.

Events are completly hidden from the user. All he sees is lv_obj_set_sort_criteria and lv_obj_sort.

The only reason why I suggest using event’s here because in v8 they became very flexibly due to 2 reasons:

  1. There is a user_data parameter in lv_obj_add_event_cb that allows attaching any arbitrary data to an object without modifying lv_xxx_ext_t.
  2. Multiple events can be assigned to an object so any number of data can be attached this way independently from each other. All this in runtime, adding extra memory usage only on objects where it’s used.

So the event is used only to store a string that can be get later.

I see it the opposite way. You can create 100 children and call lv_obj_sort() once, instead of inserting new objects to the correct place 100 times.

It’s already removed in v8 and the docs is added only in the header files (some files still need to be cleaned up though)

As I mentioned at the beginning of the post the user wouldn’t see the events at all.


I think it’s important to make LVGL modular instead of monolithic for various reasons. Modularity

  • keeps LVGL small in memory usage because unused modules can be easily disabled
  • keeps the API small (e.g. in the MicroPython binding every implemented public function costumes memory even if it’s never called.)
  • increases readability and makes maintenance easier because modules are shorter
  • allows changing parts without affecting the other parts of the library or the global public API

Maybe it would make sense to decouple this memory handling from the event handling into something more general? Using events just to allocate memory only adds to the confusion.

But this is not a realistic scenario.

Creating 100 children in one go is done only on startup, if at all. If you want to create a list of 100 sorted children, there’s no point in extending the API. Just go ahead and run qsort() on your items before creating the list from them.

I am about a list which is kept sorted while items are added/removed at runtime, maybe because datagrams are received on some communication line. Here, you have an already sorted list and every time a new datagram is received, an item is added or removed on the list. Children are added/removed one-by-one. You would virtually never add 100 items in one go in such a scenario. This is the perfect use-case for an insertion sort.

It was the most flexible thing that I could come up with, but if you have any ideas I’d be very happy to hear them.

The use case I imagined is sorting products (name, price, popularity, etc). The criteria can be a pointer to a product descriptor and the user can change the ordering to “by name”, “by price”, “by popularity” etc in ascending or descending order.

The event+data idea is only to store the criteria. We can still have a function like lv_obj_sort_child(parent, child) which moves a child to the correct place.

What I’d like to avoid is adding a new API function to current and upcoming widgets for a not mandatory feature.

Any updates on this? Is it already implemented?