Solved

Algorithm for multi batch move, preserving sequence

Posted on 2007-12-05
11
308 Views
Last Modified: 2010-05-18
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  

move(ImageAtIndex, toAfterIndex)

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.

Not nice
0
Comment
Question by:Mutley2003
  • 5
  • 3
  • 3
11 Comments
 
LVL 25

Expert Comment

by:imitchie
ID: 20409764
This is an algorithm I'd use: (pseudo)
move2 ( arr: array of integer; insertat: integer )
 
iEnd := // last possible index
cnt := 0;
for i = Low(arr) to High(arr)
begin
  if arr[i] >= insertat then
  begin
    Inc(cnt);
    dec(insertat);
  end;
  move ( arr[i], iEnd );  // push everything to end
end;
for i = Low(arr) to High(arr)
begin
  move ( iEnd, insertat -1);
end;

Open in new window

0
 

Author Comment

by:Mutley2003
ID: 20409865
hmm .. what is the role of cnt?

If I understand the algorithm correctly, you are moving all the items to be inserted to after the  end of the list, decrementing the insertion position for every item that is to be inserted after it (should not that be before it?), then 'popping' them off the tail of the list (in sequence) to the modified nsertion point.

I think I see hwre you are going with this .. let me study it a bit more.

Thanks

0
 
LVL 25

Expert Comment

by:imitchie
ID: 20409985
haha.. you're right. i was toying with stuff to front or stuff to end. then i rechecked that your proc is move ( , AFTERpos), so I went with the latter. it should be
arr[i] <= insertat indeed. there probably needs to be some boundary test with the  
  move ( iEnd, insertat -1);
 call as well, but like I said, pseudo!
0
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 
LVL 45

Assisted Solution

by:aikimark
aikimark earned 50 total points
ID: 20411226
@Mutley2003

Given the original index sequence:
dIDX:  [1,2,3,4,5,6]

how do you account for the resequencing of the selected items:
[1,6,4]?  (item 6 position has swapped places with item 4 position)

Is this something the user does?

=========================
My take on this algorithm goes something like this:
1. Initialize a numeric variable to zero.  This variable will be used to adjust the relative positions as you do your moves.  Call this intAdjust

2. Iterate through the move-from list, starting with the highest indexes in the move-from list, with position values greater than the move-to position.  Remove each item from your move-from list with each move.  Add the intAdjust value to each move-from value.

3. After each move, increment intAdjust by one.  

4. Reset intAdjust back to zero

5. Resume your iteration through the move-from list, starting with the highest indexes in the move-from list.  Remove each item from your move-from list with each move.  Add the intAdjust value to the move-to value.

6. After each move, decrement intAdjust by one.  
0
 
LVL 25

Expert Comment

by:imitchie
ID: 20414369
I think the algorithm I propose still stands. I am going through the "to move array" in sequence, i.e. 1 moves to back, then 6, then 4. When I shift them to the right place, whoala, 1,6,4!
0
 

Author Comment

by:Mutley2003
ID: 20417626
akimark, the 1, 6 4 business arises from the sequencein which the user clicks the items, and that is what I want to preserve.. I don't think your algorithm does that .. I think what you are doing is moving all the items prior to the insertion point in one operation, then all the items that were after the insertion point to the tail of that lot. That does not preserve the sequence I am after.

i mitchie, I coded up your algorithm as far as I could , but it does not work for me. Maybe a slip from pseudo to real code?

procedure TMainForm.btnBatchMoveClick(Sender: TObject);

var
  Stuff        : Tlist;



  procedure Multimove(const Items2Move: Array of Integer; const insertAfter: Integer);
    {
     both these arguments are in terms of the POSITIONS in the original Stuff array
    }
  var
    i, iEnd, _InsertAfter: integer;
  begin
  _InsertAfter := InsertAfter;
    iEnd := Stuff.count-1;
    for i := Low(Items2Move) to High(Items2Move) do begin
      if Items2Move[i] <= insertAfter then dec(_insertAfter);
      stuff.Move(Items2Move[i]-i, iEnd);  // push everything to end
    end;

    for i := Low(Items2Move) to High(Items2Move) do begin
      stuff.move(iEnd, _insertAfter - 1);
    end;
  end;

begin
  dsmemo1.clear;
  stuff := Tlist.create;
  stuff.add(pointer(17));
  stuff.add(pointer(107));
  stuff.add(pointer(41));
  stuff.add(pointer(2));
  stuff.add(pointer(18));
  stuff.add(pointer(16));
  Multimove([0, 5, 3], 1);
end;

Next steps?

0
 
LVL 25

Expert Comment

by:imitchie
ID: 20417667
TList.Move is Move(indexfrom, indexToInsertAt) which is considerably different from your stated

move(ImageAtIndex, toAfterIndex)   [AFTER] !
0
 
LVL 25

Accepted Solution

by:
imitchie earned 450 total points
ID: 20417749
This works. I have added Move2 to TMyList which is shown below, which moves the way you stated.
I had to change the algorithm slightly, but you'll figure it out!!
type
 TMyList = class(TList)
  procedure Move2(iFrom: integer; iAfter: integer);
 end;
 
var
  Stuff        : TMylist;
  log: string = '';
 
procedure LogStuff;
var
  i: integer;
begin
  for i := 0 to stuff.Count -1 do
    log := log + IntToStr(Integer(stuff[i])) + ';';
  log := log + #13#10;
end;
 
  procedure Multimove(Items2Move: Array of Integer; const insertAfter: Integer);
    {
     both these arguments are in terms of the POSITIONS in the original Stuff array
    }
  var
    i, j, iEnd, _InsertAfter: integer;
  begin
  _InsertAfter := InsertAfter;
    iEnd := Stuff.count-1;
    for i := Low(Items2Move) to High(Items2Move) do begin
      if Items2Move[i] <= insertAfter then dec(_insertAfter);
      stuff.Move2(Items2Move[i], iEnd);  // push everything to end
      LogStuff;
      for j := i+1 to High(Items2Move) do
        if Items2Move[j] > Items2Move[i] then
          Items2Move[j] := Items2Move[j] - 1;
    end;
 
    for i := Low(Items2Move) to High(Items2Move) do begin
      stuff.move2(iEnd, _insertAfter);
      LogStuff;
    end;
  end;
 
procedure Tform2.Button1Click(Sender: TObject);
begin
  log := '';
  stuff := TMylist.create;
  stuff.add(pointer(17));
  stuff.add(pointer(107));
  stuff.add(pointer(41));
  stuff.add(pointer(2));
  stuff.add(pointer(18));
  stuff.add(pointer(16));
  LogStuff;
  Multimove([0, 5, 3], 0);
  LogStuff;
  ShowMessage(log);
end;
 
{ TMyList }
 
procedure TMyList.Move2(iFrom, iAfter: integer);
begin
  if iAfter >= Count-1 then
    Move(iFrom, Count-1)
  else
    Move(iFrom, iAfter+1);
end;

Open in new window

0
 
LVL 45

Expert Comment

by:aikimark
ID: 20418310
@Mutley2003

You are correct.  My algorithm was for an order-preserving move.  You need an algorithm that allows for this reordering with the move.

Before I suggest a different algorithm, please confirm/correct my assumption that a MOVE() operation may cause reordering of the position index.  This was an assumption on my part, but a critical behavior in the algorithm's design.
0
 
LVL 45

Expert Comment

by:aikimark
ID: 20418318
@Mutley2003

The reason my original algorithm did NOT preserve the order of item selection was that the title of your question includes "preserving sequence", which I interpreted as "original item relative sequence" and not "user-selected sequence"

That is why I asked you about the resequencing of items in my comment.
0
 

Author Comment

by:Mutley2003
ID: 20424497
akimark .. sorry  "original item relative sequence"  vs "user-selected sequence" was not clear. But thanks for your input, and I will give you some points.

i mitchie .. yes, the "insert at" vs "insert after" issue caused us some confusion at this end, but the algorithm works fine now, thanks. The critical issue was that inner loop, adjusting the items2Move indeses

 for j := i+1 to High(Items2Move) do
        if Items2Move[j] > Items2Move[i] then
          Items2Move[j] := Items2Move[j] - 1;
    end;


Thanks all
0

Featured Post

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Delphi Form ownership 4 85
Press three keys together and trigger a function 3 55
JAudiorecorder record freezing the app 29 67
Installshield for Embarcadero EX 10.1 Berlin 4 39
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
Have you ever had your Delphi form/application just hanging while waiting for data to load? This is the article to read if you want to learn some things about adding threads for data loading in the background. First, I'll setup a general applica…
Along with being a a promotional video for my three-day Annielytics Dashboard Seminor, this Micro Tutorial is an intro to Google Analytics API data.
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question