Algorithm for multi batch move, preserving sequence
Posted on 2007-12-05
I have an algorithmic problem relating to a "batch move" that someone might be able to see an elegant way forward on.
It actually relates to a display of images in a grid, and moving several images at once (but a similar problem could be found elsewhere eg in a listview).
Suppose I have record numbers displayed in the following order (dIDX = display index)
Rec No r17 r107 r41 r2 r18 r16
dIDX 1 2 3 4 5 6
I drag the three items displayed at position 1, 6 and 4 (rec numbers 17,16,2) as a single batch, to insert them after the item in position 2 (r107)in that sequence. Note that the items that I wish to move originally appear both before and after the one I want them positioned at.
The operation I have available to me is a single move in terms of display indexes ie
Of course, this alters the display indexes (positions).
What I really want is move([1,6,4],2) to result in a display sequence of
r107, r17, r16, r2, r41, r18
but I don't have such a multimove.
Is there a logical way of doing this with a sequence of single moves .. something involving a stack perhaps?
I can see a brute force way of doing it, like so
a) my request in terms of position numbers is "place 1, 6 and 4 after 2"
b) translate this to record ids ie "place r17, r16, r2 after r107"
c) turn this into pairs .. move r17 after r107, r16 after r17, r2 after r17
d) each pair request (in terms of record numbers) will then have to be translated back into terms of positions .. find, by linear search the positions of record ra and record rb.