News for hackers. Stuff that matters.
Re:Google Tasks API Released by gregschlom on Thursday May 12, 2011 @06:07AM (#2540022)
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.
Re:Google Tasks API Released by gregschlom on Thursday May 12, 2011 @06:23AM (#2540052)
Nevermind, I found the answer. It looks like a self-balancing binary search tree.

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tr...

Re:Google Tasks API Released by 6ren on Thursday May 12, 2011 @06:23AM (#2540055)
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.

Re:Google Tasks API Released by gregschlom on Thursday May 12, 2011 @06:31AM (#2540067)
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.

Re:Google Tasks API Released by 6ren on Thursday May 12, 2011 @06:56AM (#2540113)
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