NewsForumsCodeLogsGallerySpecsSearch

TList.Remove() method uses overridable compare

BlitzMax Forums/BlitzMax Programming/TList.Remove() method uses overridable compare

Muttley(Posted 2009) [#1]
Just got bitten by this.

TList uses the Compare method to find the link of the Object you wish to remove. Unfortunately I'd overridden the Compare method to sort my renderable objects by Z-Depth. This meant that when attempting to remove a specific renderable Object from the list it was removing the first renderable that had the same Z-Depth as the object I requested to be removed (which was a surprise to say the least).

This means that both TList.Remove(), TList.FindLink() and ListFindLink() don't really work as you would expect.

Is this working as designed, or an unexpected feature?

Cheers

Muttley


Mark Tiffany(Posted 2009) [#2]
That might just explain a weird bug I had ages ago when trying to re-factor some MaxIDE code (to over-ride Compare instead of having a dedicated SortThisList function)...


Muttley(Posted 2009) [#3]
Hmm, not sure why this got moved here. At the very least this is a bug report as the Remove method is not doing what it says it will do.


Tommo(Posted 2009) [#4]
It's not a bug.
TList.Remove uses "Compare" method to find the "matched" object and remove it.
You can extend TList and make your own version which doesn't use Compare for searching.
Type TListRaw extends TList
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
End Type


The best way to remove a object in list is using TLink, which save you a lot of time from searching.


Muttley(Posted 2009) [#5]
I'm aware of the possible workarounds, but storing the TLink in an object is not workable if your objects might be in one or more lists at the same time (for example). Your objects would then need to know in advance that they will be added to lists, and that's not a good design practice.

It's more that the docs imply it will remove the exact object you provide, but actually deletes the first object that matches using the compare method, which may or may not be the object you've asked it to remove.


Oddball(Posted 2009) [#6]
Why are you overriding the compare method? You can sort lists using the custom compare function parameter. 
SortList list,True,ZSort

Function ZSort:Int( o1:Object, o2:Object )
	Return TMyType(o1).z-TMyType(o2).z
End Function
This way you can sort your lists in multiple ways by using different custom compare functions, and best of all your compare method stays intact.


Mahan(Posted 2009) [#7]
Just wanted to add some knowledge from another language that uses a similar mechanism in collections, Java:

In java, developers have a "contract" i.e. written rules about how the equals() and hashCode() methods must work to be 100% functional when used in conjunction with javas collections:

See link here:
http://www.geocities.com/technofundo/tech/java/equalhash.html

On the other hand I agree with Oddball here. To override compare() with the z-order comparision should imho not be expected to work in conjunction with the existing collection library.

You can almost hear it in the meaning of the word: "compare". It's meaning it insanely broad. What do we compare? An instance to another? One Z-order to another Z-order? Apples to oranges? Religions to Political ideologies?

This is where the java equals() contract comes in as a solution as it defines exactly what is expected of a possible implementation.

And maybe BlitzMax should have such a written contract for compare() too?


Czar Flavius(Posted 2009) [#8]
Instead of a TLink, give each object a list of TLinks :D


Tommo(Posted 2009) [#9]
that's not a good design practice.

I agree with that. It also happens on TMap.
I encountered this at a similar situation. I was trying to sort a array by Z-depth, since sorting method of array only supports native Compare method, I had to override the Compare method.

It was a surprise when I found that TList/TMap uses Compares in searching.


Muttley(Posted 2009) [#10]
@Oddball:
Why are you overriding the compare method? You can sort lists using the custom compare function parameter.


Well, for one the docs for the TList Sort method says: "User types should implement a Compare method in order to be sorted."

Secondly, I ran some tests which showed that using an overriden Compare method was up to 20% faster than using the SortList command with a sort function parameter.

@Mahan: In Java the compare()/compareTo() methods are only used for sorting and you will generally use whatever makes sense for the class itself, ie. sorting renderable objects on their z-depth makes perfect sense when you want to draw them in the correct order. ;)

For checking equality the equals() method is used (as you mention) which can also be overriden, but if not defaults to comparing object references, not object values, which makes perfect sense.

I think the main issue here is the misleading docs.

Method: Remove( value:Object )
Description: Remove an object from a linked list
Information: Remove scans a list for the specified value and removes its link.

To me that implies it will remove the specific object you pass it and should therefore really be comparing the objects reference to those in the list, not using the method that's supposed to be used (according to the same docs) for sorting objects.