I've been racking my brain over this and I just can't come up with an elegant solution. Imagine you have a list of ten books that you need to rank 1-10. You can rank them in any order and when you rank one, if that rank is already taken, the list needs to reshuffle. for example:

A 1 B - C - D 4 E - F 6

if F goes to one, it should look like:

F 1 A 2 B - C - D 4 E - F 6

Any ideas would be GREATLEY appreciated.

Use a linked list

Otis wrote:

Use a linked list

Is there one in .NET?

Just found it, thanks!

Any suggestions of implementation? I was using an ArrayList with my custom objects but I don't see how the LinkedList will make this task any easier? Am I missing something?

MarcoP wrote:

Any suggestions of implementation? I was using an ArrayList with my custom objects but I don't see how the LinkedList will make this task any easier? Am I missing something?

I think I misunderstand the requirements you have but how I understand it is that if you have to store a value V in the slot for ranking R, and it's already occupied, that value is moved upwards so V is placed the slot for R. This is doable with a linked list, because you can simply insert an item at the index R and everything moves over

Though what's the exact usage of this?

Otis wrote:

MarcoP wrote:

Any suggestions of implementation? I was using an ArrayList with my custom objects but I don't see how the LinkedList will make this task any easier? Am I missing something?

I think I misunderstand the requirements you have but how I understand it is that if you have to store a value V in the slot for ranking R, and it's already occupied, that value is moved upwards so V is placed the slot for R. This is doable with a linked list, because you can simply insert an item at the index R and everything moves over

Though what's the exact usage of this?

Well basically, we have a list of documents the user need to rank 1 thru N (N equals the number of documents). So my entity has two properties, document name and rank. The problem is the user can rank them in any order, so if he ranks three documents like this:

A - 1 B - 5 C = 7

And then moves C to 1, the rank property needs to change to reflect C - 1 A - 2 (This increments and any below that need changed do as well) B - 5 (Note this stays the same)

Does this make sense? Not sure why I'm having such a brain fart on this...

Yes, so you sort them on the initial rank, dump them in a linked list, and any node which gets a different rank is placed at the spot of that new rank. So the index (in the linked list) is the real rank id. As the linkedlist moves everything up for you automatically, it's really easy.

After hte ranking is done, you simply iterate over the linked list, and every element gets the rank of the index it's on.

cool, thanks man, i'll take a stab @ it! i figured it was going to b easy!

Otis wrote:

Yes, so you sort them on the initial rank, dump them in a linked list, and any node which gets a different rank is placed at the spot of that new rank. So the index (in the linked list) is the real rank id. As the linkedlist moves everything up for you automatically, it's really easy.

After hte ranking is done, you simply iterate over the linked list, and every element gets the rank of the index it's on.

If the linked list's index is the rank, how does it work for this:

A - 1 B - 5 C = 7

Wouldn't the index of the linked list for 'B' be 2, when the rank is actually 5?

Ok, I didn't take that into account... but... what does '5' mean if there are just 3 items ranked? I didn't find that making any sense because: what happened to the item ranked as no 2 ?

Imagine a datalist with 10 documents that are presented on the screen 'un-ranked', so the user can go through each one and rank one at a time in any order. That's our requirements

p.s. if u help me come up with a solution, i'll throw a 'I Love LLBLGenPro' bumper sticker on my ride!

MarcoP wrote:

Imagine a datalist with 10 documents that are presented on the screen 'un-ranked', so the user can go through each one and rank one at a time in any order. That's our requirements

p.s. if u help me come up with a solution, i'll throw a 'I Love LLBLGenPro' bumper sticker on my ride!

Heh

Ok, here we go simple bucket class: public class Bucket { public int Rank { get; set} public Document RankedDocument { get; set;} }

Ok, now you dump every document in a List<Bucket>.

You then sort it on Rank. When the user ranks a document on the screen, you go to its bucket and set the rank again. Now, traverse the list and check if there are other buckets with the same rank. If so, increase the rank with one. Now pick THAT rank and repeat the process. Process stops when you end up at the end of the list with a rank so there are no duplicates.

This is the initial algo. It isn't that efficient, so it might need some lookup thingies here and there, although traversing 10 documents is really really fast.

Ok cool, that definetly gets me going on the right track! Sounds like it needs to be recursive?

MarcoP wrote:

Ok cool, that definetly gets me going on the right track! Sounds like it needs to be recursive?

Could be recursive yes But the problem with doing this recursive is that you have to take into account that when recursion comes back from the call, you simply quit the routine and don't proceed.

MarcoP wrote:

Otis wrote:

Yes, so you sort them on the initial rank, dump them in a linked list, and any node which gets a different rank is placed at the spot of that new rank. So the index (in the linked list) is the real rank id. As the linkedlist moves everything up for you automatically, it's really easy.

After hte ranking is done, you simply iterate over the linked list, and every element gets the rank of the index it's on.

If the linked list's index is the rank, how does it work for this:

A - 1 B - 5 C = 7

Wouldn't the index of the linked list for 'B' be 2, when the rank is actually 5?

Are you ranking them or rating them? Seems like two different operations to me!

BOb

ranking them. no dups are allowed

Otis wrote:

MarcoP wrote:

Imagine a datalist with 10 documents that are presented on the screen 'un-ranked', so the user can go through each one and rank one at a time in any order. That's our requirements

p.s. if u help me come up with a solution, i'll throw a 'I Love LLBLGenPro' bumper sticker on my ride!

Heh

Ok, here we go simple bucket class: public class Bucket { public int Rank { get; set} public Document RankedDocument { get; set;} }

Ok, now you dump every document in a List<Bucket>.

You then sort it on Rank. When the user ranks a document on the screen, you go to its bucket and set the rank again. Now, traverse the list and check if there are other buckets with the same rank. If so, increase the rank with one. Now pick THAT rank and repeat the process. Process stops when you end up at the end of the list with a rank so there are no duplicates.

This is the initial algo. It isn't that efficient, so it might need some lookup thingies here and there, although traversing 10 documents is really really fast.

I got caught up on some other stuff friday, so I'm going to get back to this today. frans, i dont think this is totally correct if i'm reading it properly, b/c sometimes you are moving documents down the list, for example if you moved a ranked document from 1 to 8 (all the docs below have their rank subtracted by one).