re-"ordering" elements based on number from user

[MIDIman]

Anyone have a good article on the ideas behind "ordering" a list of items where, one or many of them have changed?

i.e. like the Netflix screen where, you can type in a number for each rental designating the order in which you wish to receive movies.

Shouldn't matter what the language is IMHO, but in this case its Coldfusion.

The difficulty is what to do when multiple entries have changed and when any two or more of them are the exact same number.

 

[Crusty]

Well your input processing would check the values to make sure somebody doesn't specify two numbers in the same list. Either by automatically adjusting the list, or by forcing them to re-enter the values. The way I would check for duplicates would be to iterate through the elements and store the values in a hash table, so long as all the buckets only have 1 element then you have no duplicates.

As for your original question, I do not understand what you are trying to ask.

Are you looking for different sort algorithms, or are you looking more at the general process of keeping a list of indexes that are linked to items and being able to change the order of the indexes without altering the underlying items?

 

[MIDIman]

Yeah, looking for a totally generic idea in processing.

Visually - like Netflix, I have a form input box for each item in the list. Type a 1 in the input and the item appears at the top of the list. User fills in some numbers and clicks GO.

The list is from a DB. Currently, there's a "displayorder" field and the DB is ordering by "displayorder." I suppose as the table grows, that could pose to be a problem, couldn't it - because I have to loop through the entire table. If a new item is added to the list, and it appears at the top, then I have to loop through ever item and do orderingIndex +1.

The second question is what to do if I have two of the same number in the input fields. For instance, say I have two input boxes where the user type "2"'s and I don't want to force a validation on the form.... maybe I could just do the two "2's" alphabeticaly? i.e.:

ordering input: Title

1: Some Title
2: New Second Title
2: Also Second Title
4: Last Title

Would become 1,3,2,4 because Also comes before New alphabetically.

Originally posted by: Crusty
Well your input processing would check the values to make sure somebody doesn't specify two numbers in the same list. Either by automatically adjusting the list, or by forcing them to re-enter the values. The way I would check for duplicates would be to iterate through the elements and store the values in a hash table, so long as all the buckets only have 1 element then you have no duplicates.

As for your original question, I do not understand what you are trying to ask.

Are you looking for different sort algorithms, or are you looking more at the general process of keeping a list of indexes that are linked to items and being able to change the order of the indexes without altering the underlying items?

 

[Crusty]

Well, if you wanted to not force the user to re-enter the values you would have to come up with an algorithm to choose which one gets priority. As far as altering the list to get rid of the duplicates a simple loop will do the trick, so long as the list is sorted.

for (int i = 1 ;i < list.count ; i++)
{
if (list[i-1] >= list[ i ])
list[ i ] = list[i-1]+1;
}

So, before that loop you would make sure that the list of numbers is in the correct order of how you want them ordered(even if it puts the numbers out of order), so first sort it purely on numbers and then apply your custom algorithm that arranges items with the same number. Eventually you could integrate your algorithm into your sort function to make it a bit more efficient, especially if it's something as simple as alphabetically sorting those.


One of the things you have to keep in mind is that what you see on the form doesn't necessarily mean that's how anything is stored in the database. In fact, I would guess that Netflix just keeps an ordered list of items to ship to each customer, and the form you are seeing is only used to order those items to insert them into the table. So those shipping priority numbers are probably only stored in memory for the short time they are needed on the website.

 

[Furor]

I had this same problem a while ago...
I couldn't find an elegant solution, so what I did was update the database with the values the user input, then immediately after I would query the table sorting by the order and primary key, so that if there were two entries with the same number, the first primary key would get precedence..i'm sure it is not the best way, but it works..here is my code..

<cfquery name="qGetPositions" datasource="#Request.Datasource#">
SELECT Position, RuleID
FROM xxx
ORDER BY Position, RuleID
</cfquery>
<cfset x = 0>
<cfloop query="qGetPositions">
<cfset x = x + 1>
<cfquery datasource="#Request.Datasource#">
UPDATE xx
SET Position = #x#
WHERE RuleID = #qGetPositions.RuleID#
</cfquery>
</cfloop>

Edit: I also evalulated javascript, ajax, and some other solutions but the the amount of work compared to this solution wasn't worth it