user2980252 user2980252 - 1 year ago 59
Java Question

Move up, move down, specify position

I know this should seem elementary, but for some reason I just can't wrap my head around the algorithm that would solve this problem, so I'm going to reach out to the community on this one.

I have a class that looks like this:

class MapElementModel {
int id;
String name;
int position;
//other fields ommitted for space reasons

//getters and setters
}


Now I'm storing the MapElementModel in a standard ArrayList. The user wants to move an element up in the list, down in the list, or specify a new position for the MapElementModel. The list is sorted based on MapElementModel.position.

So basically, if the user moves item 14 to position 3, that item needs to be inserted at position 3, the position field needs to change to 3 and all following positions need to change accordingly.

Likewise, a user could hit the "move up" button and move the item at position 9 to position 8. Again all remaining MapElementModel.position items needs to have their position field change accordingly.

Finally, a user could hit the "move down" button and move an item down in the list. Again all MapElementModel.position fields must be updated.

Does anyone have a good solution for this problem? Thanks for the help!

Answer Source

You said, "The list is sorted based on MapElementModel.position", so my answer will be based off this. If it were sorted based on MapElementModel.id, this would be a different algorithm.

Think of the ArrayList as your ordered collection of items. Instead of "storing" the position in the MapElementModel, just let the index of the element in the ArrayList be its position. For example, if your ArrayList has the elements ["Red", "Blue", "Green", "Yellow", "Pink", "Purple"], then the position of "Red" is 0, the position of "Blue" is 1, and the position of "Green" is 2, and so on...

I'm assuming you don't care much about efficiency - i.e. you're not dealing with a list of 1 billion items.

Now, to move an item, our algorithm is to simply remove it from the list and insert it again at the correct location. Suppose we have the list again:

["Red", "Blue", "Green", "Yellow", "Pink", "Purple"]

Let's consider a few test cases:

  • Move item at position 3 to position 0
  • Move item at position 3 to position 5
  • Move item at position 3 to position 3 (redundant case)

In the first case, we move "Yellow" to in front of "Red". So remove "Yellow" like this

String removed = list.remove( 3 );

Now we want to insert it back into position 0. It looks like we can just do

list.add( 0 , removed );

Simple, right? Remove element at given index, insert it at desired index. Let's see if it works for the second test case.

In case 2, we want to move "Yellow" to position 5. Notice that there are six elements in our list, and position 5 corresponds to the sixth position (if our array indexing starts at 0), so "Yellow" would go to the end of the list, after "Purple." So, we remove "Yellow" again:

String removed = list.remove( 3 );

But look now, everything after yellow has shifted down by 1:

["Red, "Blue", "Green", "Pink", "Purple"]

Conveniently, the index of "Purple" is 4, and if we insert at position 5 with

list.add( 5 , removed );

we get

["Red, "Blue", "Green", "Pink", "Purple"]

See if this algorithm works with putting yellow at position 3, the redundant case.

It looks like our algorithm works as follows: Remove at the given position, insert at the target position. It looks like we can just write an algorithm like this:

public void moveItem( int idxToMove , int targetIdx ) {
    String removed = list.remove( idxToMove );
    list.add( targetIdx , removed );
}

If the user wants to move the item at position 3 up 1 spot the list, you call

moveItem( 3 , 3+1 );

If the user wants to move the item at position 3 down 1 spot in the list, you call

moveItem( 3 , 3-1 );

What would you do if the user wants to move the item at position 0 down 1 spot in the list?

If the user wants to move item at position 5 to item at position 2, you call

moveItem( 5 , 2 );

Now you can implement this algorithm for an ArrayList of MapElementModel. If you really need the position field of your MapElementModel object to be correct, you simply go through the ArrayList and update it. The position of an element in the ArrayList is the element's position.

public void moveItem( int idxToMove , int targetIdx ) {
    //move the item as I did with Strings

    for ( int i=0 ; i<list.size() ; i++ ) {
        list.get( i ).position = i;
    }
}

If you need to move an item with a specified id, you would locate it in the ArrayList and then move it:

public void moveItemById( int itemId , int newPosition ) {
    int positionOfItem = -1;
    for ( int i=0 ; i<list.size() ; i++ ) {
        if ( list.get( i ).id == itemId ) {
            positionOfItem = i;
            break;
        }
    }
    if ( positionOfItem != -1 ) {
        moveItem( positionOfItem , newPosition );
    }
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download