NewsForumsCodeLogsGallerySpecsSearch

Sort a linked list alphabetically

BlitzMax Forums/BlitzMax Programming/Sort a linked list alphabetically

Pineapple(Posted 2010) [#1]
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.


Thareh(Posted 2010) [#2]
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)


Pineapple(Posted 2010) [#3]
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.


Muttley(Posted 2010) [#4]
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.


Pineapple(Posted 2010) [#5]
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)'


Thareh(Posted 2010) [#6]
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



Czar Flavius(Posted 2010) [#7]
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



Czar Flavius(Posted 2010) [#8]
Tharah, your function will fail if eihter object is null.


Thareh(Posted 2010) [#9]
Yeah, Nullify checks isn't my responsibility! :D


Muttley(Posted 2010) [#10]
@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.


Czar Flavius(Posted 2010) [#11]
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



Muttley(Posted 2010) [#12]
@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).


Jesse(Posted 2010) [#13]
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?


Muttley(Posted 2010) [#14]
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



Jesse(Posted 2010) [#15]
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.


Czar Flavius(Posted 2010) [#16]
Oh well, I personally just use compare functions and I don't use TList.Remove()!