Sort a linked list alphabetically
BlitzMax Forums/BlitzMax Programming/Sort a linked list alphabetically
| ||
I need to sort a list of objects alphabetically based on their name$ field. However, I'm failing to see any good way to do this. |
| ||
You should use the Sort function (List.Sort), see the list documentation for more information. (I don't have BlitzMax installed atm so I can't provide any example :P) |
| ||
There is no documentation; I've been searching the forums to (so far) no real success. I thought I was onto something with this: But it's screwing up on the link.value().name things. |
| ||
It's much, much easier than that.SortList(myList, True, SortFunction) Function SortFunction:int(s1:String, s2:String) If s1 < s2 Return -1 ElseIf s1 > s2 Return 1 Else Return 0 EndIf End Function Or to sort by an objects name field: SortList(myList, True, SortFunction) Function SortFunction:int(o1:MyObject, o2:MyObject) If o1.name < o2.name Return -1 ElseIf o1.name > o2.name Return 1 Else Return 0 EndIf End Function This is documented in the BRL.LinkedList section of the docs. |
| ||
Using your example,Framework brl.linkedlist Global myList:TList=CreateList() Type MyObject Field name% End Type SortList(myList, True, SortFunction) Function SortFunction:Int(o1:MyObject, o2:MyObject) If o1.name < o2.name Return -1 ElseIf o1.name > o2.name Return 1 Else Return 0 EndIf End Function I get a compile error. I'm using Bmax 1.39. Unable to convert from 'Int(MyObject,MyObject)' to 'Int(Object,Object)' |
| ||
You need to change MyObject to whatever object you're using. Edit: Oh, Wait. The above example didn't work? Perhaps the function should look like this: Function SortFunction:Int(o1:object, o2:object) If MyObject( o1 ).name < MyObject( o2 ).name Return -1 ElseIf MyObject( o1 ).name > MyObject( o2 ).name Return 1 Else Return 0 EndIf End Function |
| ||
It's much, much easier than that. Shouldn't the my_list.Sort() sort the strings alphabetically automatically? Edit: yes it does. Just call the Sort method your list! :D In case it doesn't (plus it's good to know) The compare function has to use Objects, not any other type. So you must cast them to MyObject inside the function, and check that they are not null. This is because a TList can contain anything and it is not guaranteed your compare function won't get something unexpected. Function AlphaSort:Int(o1:Object, o2:Object) 'as you can store anything in a TList, we need to check they are MyObjects Local mo1:MyObject = MyObject(o1) Local mo2:MyObject = MyObject(o2) 'if either are not MyObject, we cannot compare If Not (mo1 <> Null And mo2 <> Null) Then Return 0 If ... < ... Then Return -1 If ... > ... Then Return 1 If ... = ... Then Return 0 End Function |
| ||
Tharah, your function will fail if eihter object is null. |
| ||
Yeah, Nullify checks isn't my responsibility! :D |
| ||
@Czar Flavius: Unfortunately not, list.sort() uses Object's Compare() method which by default compares the address of the object. This Compare() method is also used when removing objects from a TList, which means if you try to override the Compare method on your objects for sorting purposes you can no longer delete a specific object from the TList unless you can guarantee the field you use for sorting is unique for all objects. Otherwise it will just delete the first match it finds, which is... inconvenient, to say the least. So, we're stuck with providing a compare function which is quite a bit slower than an overridden Compare() method. |
| ||
Strings override the compare method with one that compares them alphabetically. This is built in behavior that cannot be changed :) I added onto the Wikibook how to override compare methods without that problem: http://en.wikibooks.org/wiki/BlitzMax/Language/Objects Strict Local list:TList = New TList list.addlast("bob") list.addlast("azzle") list.addlast("apple") list.addlast("elephant") list.sort() For Local s:String = EachIn list Print s Next apple azzle bob elephant |
| ||
@Czar Flavius: Unfortunately that workaround will only work if you're comparing objects that are not the same type (I fixed the fact you were flipping the comparison so the Ascending/Descending parameter of the Sort method was not being honoured correctly). Try this code: SuperStrict Type THighScore Field name:String Field score:Int Method Compare:Int(other:Object) 'as you can store anything in a TList, we need to check this is a high score object Local hs:THighScore = THighScore(other) 'if this isn't a high score object, use a fail-safe compare method If Not hs Then Return Super.Compare(other) If score < hs.score Then Return - 1 If score > hs.score Then Return 1 If score = hs.score Then Return 0 End Method Function Create:THighScore(name:String, score:Int) Local high_score:THighScore = New THighScore high_score.name = name high_score.score = score Return high_score End Function Method ToString:String() Return score + " - " + name + " [" + Super.ToString() + "]" End Method End Type Function PrintScores() For Local score:THighScore = EachIn highScoreTable Print score.ToString() Next End Function Global highScoreTable:TList = New TList Local score1:THighScore = THighScore.Create("Dave", 12345) Local score2:THighScore = THighScore.Create("Pete", 345) Local score3:THighScore = THighScore.Create("Trevor", 12345) Local score4:THighScore = THighScore.Create("Norman", 99) Local score5:THighScore = THighScore.Create("Susan", 12345) highScoreTable.AddLast(score1) highScoreTable.AddLast(score2) highScoreTable.AddLast(score3) highScoreTable.AddLast(score4) highScoreTable.AddLast(score5) highScoreTable.Sort(False) PrintScores() Print "~nRemoving Susan~n" highScoreTable.Remove(score5) PrintScores() Output is as follows: 12345 - Dave [002E24B0] 12345 - Trevor [002E24D0] 12345 - Susan [002E24F0] 345 - Pete [002E24C0] 99 - Norman [002E24E0] Removing Susan 12345 - Trevor [002E24D0] 12345 - Susan [002E24F0] 345 - Pete [002E24C0] 99 - Norman [002E24E0] As you can see, although we ask it to remove a specific object (score5, Susans score), it just removes the first score it finds that is the same as Susans (poor Dave). |
| ||
I think I solved the problem. I modified "linkedlist.bmx" and seems to be working properly. I added this function to: Function areTheSame( o1:Object,o2:Object ) Return o1 = o2 End Function and modified FindLink method in Tlist to this: Method FindLink:TLink( value:Object ) Local link:TLink=_head._succ While link<>_head If areTheSame(link._value, value ) Return link link=link._succ Wend End Method for all of the tests I have done, it seems to work correctly but I would like to know for sure. anybody have an idea why I did this? |
| ||
You can do that, but then you have to remember to re-patch it every time you update, and also you might run into problems sharing code with people who haven't patched it themselves. Also, why create a 1 line function call for this, there's less overhead to do it inline: Method FindLink:TLink( value:Object ) Local link:TLink=_head._succ While link<>_head If link._value = value Return link link=link._succ Wend End Method |
| ||
yea, I got careless. I just noticed that the "Contains" method would have to be done this way also. maybe we can get Mark to do it this way which is faster anyway. |
| ||
Oh well, I personally just use compare functions and I don't use TList.Remove()! |