[RFC] Sorted items in collection tree context menu actions

[Aneurin Price]

I've been trying to get items in the correct order when 
editing/organising/adding to playlist from the collection tree context 
menu, and I've found it harder than I expected. The problem is that I 
can't see any way of getting the selected items in any particular order 
from the model, nor can I see any way of iterating over each item and 
testing if it is selected, so I can't seem to do this in O(n) time, 
which should be possible with the appropriate underlying data structure.

However, I don't have much experience with Qt's model/view system so 
maybe I've just missed something? (I've found it particularly annoying 
that selectedIndices() returns a QList in no particular order, thus 
combining the drawbacks of lists and sets, with the benefits of neither. 
I see no reason that this wasn't a QSet in the first place.)

In the meantime, I've tried manually sorting the selected items, which 
is of course O(n log n) - not too good, but on the other hand the 
existing code for ignoring duplicates[0] looks to be just as slow, so my 
biggest problem with this code is that it's ugly. The removal of 
duplicates from the sorted list is asymptotically faster than the 
current set lookups, but it's less neat and may not be faster unless n 
is very large (though for smaller values of n either method would be 
easily fast enough, and eclipsed by the time taken to perform the 
query). Of course, the advantage is that ordering is preserved.

I've performed the sorting and duplicate filtering in 
contextMenuEvent(), in order to remove code duplication by guaranteeing 
that playChildTracks(), editTracks(), and organizeTracks() will always 
be called with a sorted list containing no duplicate entries (in theory 
anyway!). The choice to do it there was to minimize code churn; ideally 
there would be a method call dedicated to this, and it might go so far 
as to build a meta query for the selection, to remove further code 
duplication.

Anyway, I'd appreciate your thoughts on this.

-- Nye


[0] In this case, duplicates covers not only 'Track A' followed by 
'Track A', but also 'Album A' followed by 'Track X from Album A'
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sorted-collection-tree.diff
Type: text/x-diff
Size: 8523 bytes
Desc: not available
Url : http://mail.kde.org/pipermail/amarok-devel/attachments/20080309/0d4fb5c6/attachment.bin