2

I need to do the following with a Java/Grails GORM application.

I have a domain class Item:

class Item {

   int position
   String name

}

When I create a list of items I can update the position attribute such that it represents the index of each item in the list: 0,1,2,3,... Each position is unique, i.e., at each position can only be one item.

It should be able to change the order of the items. Let's assume I have the following list of items and there positions: 

A1, A2, A3, A4, A5
1   2   3   4   5

When I want A4 to be at position 2 I have to update the positions of A2, A3 and respectively. This means that I have to update three data base entries A4, A2 and A3. If the list is very long then there are a lot of updates to do.

  1. Is there a data structure which handler the repositioning of list elements for me?
  2. How can I update the items efficiently?
Michael
  • 32,527
  • 49
  • 210
  • 370
  • Do you mean like a List where you insert an element and indexes all changes? Why does the position need to be an element of the Item, shouldn't the container for these Items manange the position? – Peter Lawrey Jun 24 '14 at 00:50
  • 1
    Why does an item store its position? if instead you ask the data structure for the position of the object then you wont have this issue of multiple updates – pwilmot Jun 24 '14 at 00:52
  • @PeterLawrey yes I mean a list where the indexes change automatically. – Michael Jun 24 '14 at 09:09
  • @pwilmot An item has to store its position because when you make a reload or inform other clients the position must be the same as for the other clients. – Michael Jun 24 '14 at 09:11
  • So now you want to have a distributed list? Can you use a server side option? or pass updates to all clients at the same time? – pwilmot Jun 24 '14 at 16:05
  • @yes I use a server which controls the lis and updates all the clients. – Michael Jun 24 '14 at 18:24

2 Answers2

0

Since your int position will always be in order, you can forget about that and use the data structure's index to get your position. (Just add 1, since the index begins at 0). Use either a LinkedList<String> or an ArrayList<String>. They will be almost identical - either way, you are going to have some type of O(n) operation. You won't be able to get around having to traverse the list.

Rather than go into more detail about the efficiency of each data structure, this post gives a very thorough summary.

Community
  • 1
  • 1
RogueBaneling
  • 4,331
  • 4
  • 22
  • 33
  • How do I map the position update in GORM. I know that I can use the index of a list this is trivial, but this is still in memory. – Michael Jun 24 '14 at 18:54
0

It sounds like you need a way to identify the list items across a network. Have you considered itentifying the elements with a UUID instead of the list index? That way, you don't have to modify the ID of the element when the order of the list changes. You can get a new UUID by calling

UUID.randomUUID()

As for ordering elements automatically, that is one of the primary responsibilities of a list. If you don't have a list, the elements will need to know of each other in order to update the index values, which will probably result in an implementation of an embedded linked list.

Peter
  • 199
  • 4