3 ms·

Anyone knows what's the name of the algorithm / strategy that they use to allocate tasks position numbers? I've created a new list and added 4 tasks a, b, c an

Anyone knows what's the name of the algorithm / strategy that they use to allocate tasks position numbers? I've created a new list and added 4 tasks a, b, c and d, and later added a2 after a. Here's what they are doing: Position: a 01111111111111111111111111111111 b 10111111111111111111111111111111 c 11011111111111111111111111111111 d 11100111111111111111111111111111 a2 10011111111111111111111111111111 So it seems a clever way of allocating the position numbers without having to change them all everytime a task is moved, but I'd love to read more about it.

gregschlom 15y ago
Nevermind, I found the answer. It looks like a self-balancing binary search tree. http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree http://en.wikipedia.org/wiki/Self-balancing_binary_search_tr...
6ren 15y ago
That is clever, it's like a binary version of the old BASIC convention of numbering lines 10, 20, 30 etc, to leave space in case you want to add lines in between. But why number them at all - why not just use the order in the list as the ordering? I haven't studied their API, so there may be a good reason.
- gregschlom 15y ago
  Because the 'order in the list' usually is the creation order of the items. If you want to change the tasks order, you need to save the position numbers in the database. This is not specific to Google tasks. If you tried to display a list of items that your users could reorder, you'd run into the same problem.
  - 6ren 15y ago
    Thanks. You could also recreate the list with the new ordering; or record the changes in list order and replay them on server (e.g. insert the 5th one after the 2nd one), perhaps even reducing it to the simplest change if the user played around with the order a lot. But I guess for RDB (and other DB?), the "physical" order isn't meant to be used as a "logical" order, and it might not even be reliable - so you need some other ordering mechanism, like position numbers. Also, not good if anything in the system depends on that physical ordering. \not a DB programmer

gregschlom 15y ago

Nevermind, I found the answer. It looks like a self-balancing binary search tree. http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree http://en.wikipedia.org/wiki/Self-balancing_binary_search_tr...

6ren 15y ago

That is clever, it's like a binary version of the old BASIC convention of numbering lines 10, 20, 30 etc, to leave space in case you want to add lines in between. But why number them at all - why not just use the order in the list as the ordering? I haven't studied their API, so there may be a good reason.

gregschlom 15y ago
Because the 'order in the list' usually is the creation order of the items. If you want to change the tasks order, you need to save the position numbers in the database. This is not specific to Google tasks. If you tried to display a list of items that your users could reorder, you'd run into the same problem.
- 6ren 15y ago
  Thanks. You could also recreate the list with the new ordering; or record the changes in list order and replay them on server (e.g. insert the 5th one after the 2nd one), perhaps even reducing it to the simplest change if the user played around with the order a lot. But I guess for RDB (and other DB?), the "physical" order isn't meant to be used as a "logical" order, and it might not even be reliable - so you need some other ordering mechanism, like position numbers. Also, not good if anything in the system depends on that physical ordering. \not a DB programmer