The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Arbitrarily ordered list

I was just looking at Ta-da List ( ) and how they allow you to order a list any way you want, not based on a particulary field like Name or Date.

I'm trying to  determine about what the most elegant way of implementing a sorted list like this would be. What do you think? A 'sort-order' column? A linked-list? What do you think?
mj Send private email
Thursday, July 20, 2006
Ta-da List probably uses, see:
John Topley Send private email
Thursday, July 20, 2006
A sort-order column would be a decent solution, it would just be a matter of making sure the order values are *always unique* -- watch out when several reordering actions occur simultaneously.  Or, each item could reference the item previous or after it, like a linked list.  Again, watch out for multiple simultaneously reorderings here.

As for which one, the linked list idea seems to be more flexible.  For instance, moving an item from the back of the list to the front requires changing a few references, as opposed to touching each item and changing it's sort order integer.
Derek I
Thursday, July 20, 2006

He was asking about the way to store the order in the backend  and not how the drag-drop is done in frontend.
JD Send private email
Thursday, July 20, 2006
I don't think sort order column will be too efficient in storing this information.

User can move around one item at a time for N number of times, so if your list has M items. For N movements, you will need to do N x M updates to the database if you store it using sort-order column. If you store it using linked list, you will need to do, at the most, 3 updates(?) for each move.
JD Send private email
Thursday, July 20, 2006
Oh, OK.

If you use "acts_as_list" in your Rails' model class then you need an integer column named "position" on the mapped database table. (Ta-da List is written using Rails).
John Topley Send private email
Thursday, July 20, 2006
Having a position field would be sufficient.  If you wanted to resolve same-id conflicts, a secondary column (name?) would probably be sufficient.
KC Send private email
Thursday, July 20, 2006
Re: NxM movements vs 3

That may be true, but they're probably updates in both cases, so you're only moving things on disk if it's part of a clustered index.

I think the SELECT cost of the linked list would be much higher than the order column, and SELECTs are much more frequent. (Potentially, N Selects per read, vs 1, unless you're reading the whole list each time).

This is one of those interesting problems that has different solutions compiled vs. in an RDMS, and at different scales...

Of course, if you were doing this for real, and cared about scaling, you might very well do the linked list approach (if you expect alot of reordering... I actually think there wouldn't be) but you'd cache the ordered results in a system like memcache or something.
PHDude Send private email
Monday, July 24, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz