Tlist Compare, Sort, and Contains, or Why God Why
BlitzMax Forums/BlitzMax Programming/Tlist Compare, Sort, and Contains, or Why God Why
| ||
| Ok, so I'm overriding the Compare method in one of my types so I can sort a list of them easily using Tlist.Sort(). So far so good, easy stuff, works. Now when it comes to using Tlist.Contains() on the same set of objects, everything breaks. Looking at linkedlist.bmx, Contains() checks if Compare() returns 0 for each item in the list, assuming that means they're the same. Obviously, as I've overridden Compare(), it will return 0 for things that aren't exactly the same object. Everything breaks; I'm not happy. I can't think of a way round this, other than writing my own version of either Sort or Contains. Is there a sensible reason why Contains uses _value.Compare(value) and not just _value=value? Edit: I'm an eejit, it was returning null because the thing was actually null :P And I now see Compare() in Contains would always work because it's using Object.Compare(), not whatever I've got. |
| ||
| Bump "And I now see Compare() in Contains would always work because it's using Object.Compare(), not whatever I've got." No it doesn't, because it will use the overridden version of Compare() in MyObject (derived from Object (right?)). So, "Is there a sensible reason why Contains uses _value.Compare(value) and not just _value=value?" |
| ||
| because = is mathmatically equals, where as compare is user defined (by default it subtracts variable pointers) being able to override it (and needing to do _value.compare(value)) makes it very much more flexible and very powerful |
| ||
| Is there a sensible reason why Contains uses _value.Compare(value) and not just _value=value? Contains does not do what you think it does, or what the help file says it does. BlitzMax uses the term "value" to refer to the object a link points to, but it also uses it to refer to the "value" of that object, and the "value" of the OBJECT is whatever the object's compare() method says it is. Here, "value" is referring to the OBJECT's value, not the value of the link. So the help file is wrong. In other words, if your compare function is set up to use the sprite's draw order as its "value" then Contains tells you the first sprite it comes across that has a particular order. I don't know why they did it this way, and the help file is damn confusing with regards to it, but that's what's happening. If you're using a for eachin loop, you'll probably be better off setting up your own loop with while wend to loop through the list one member at a time so you can compare them properly. |
| ||
| "Is there a sensible reason why Contains uses _value.Compare(value) and not just _value=value?" Because two different objects might be identical, without being the same physical object?Type Vector Field x:Int , y:Int EndType Local vect1:Vector = New Vector Local vect2:Vector = New Vector vect1.x = 200 vect2.x = 200 vect1.y = 30 vect2.y = 30 Print vect1 = vect2 |
| ||
| I think we need two functions, ContainsReference and ContainsValue. I can see the merit in a contains value function but I really don't see why its the default-and-only! |
| ||
| If you want it to be value identical, you could do the compare that way. Mine for example only returns 0 if the value references are identical. Otherwise it only returns 1 and -1. Reason: Remove bases on compare as well, if you return 0 for anything beside reference identities, you will have BAD problems, when you ever ask yourself why stuff is in lists, that you removed before ... |
| ||
| WTF? I'm confused now, and concerned that there might be a serious problem with my code. Here's some internal code from BlitzMax: Rem bbdoc: Remove an object from a linked list about: #RemoveLink is more efficient than #ListRemove. end rem Function RemoveLink( link:TLink ) link.Remove End Function "Remove an object from a linked list" There aren't a whole lot of ways that can be interpreted. So we should assume this is intended to remove the link passed to the function right? So what does that method it is calling do? Rem bbdoc: Remove an object from a linked list about: Remove scans a list for the specified value and removes its link. End Rem Method Remove( value:Object ) Local link:TLink=FindLink( value ) If Not link Return False link.Remove Return True End Method Once again, "remove an object form a linked list". So what does that findlink method do? Rem bbdoc: Returns the first link in the list with the given value, or null if none found. End Rem Method FindLink:TLink( value:Object ) Local link:TLink=_head._succ While link<>_head If link._value.Compare( value )=0 Return link link=link._succ Wend End Method Oh wonderful. It uses the compare method of the link's value! Rem bbdoc: Sort a list in either ascending (default) or decending order. about: User types should implement a Compare method in order to be sorted. End Rem Method Sort( ascending=True ) Local term:TLink=_head Repeat Local link:TLink=_head._succ Local sorted=True Repeat Local succ:TLink=link._succ If succ=term Exit Local cc=link._value.Compare( succ._value ) If (cc>0 And ascending) Or (cc<0 And Not ascending) Local link_pred:TLink=link._pred Local succ_succ:TLink=succ._succ link_pred._succ=succ succ._succ=link succ._pred=link_pred link._succ=succ_succ link._pred=succ succ_succ._pred=link sorted=False Else link=succ EndIf Forever If sorted Return term=link Forever End Method "User types should implement a Compare method in order to be sorted." It seems to me that this behavior of the linked list system using the compare method to determine if links should be removed makes the sort function entirely WORTHLESS, because the ONLY way to use the linked list system is to leave the compare method ALONE. Otherwise it is impossible to remove links after they have been created, EVEN if you SAVE THE LINKS! Also, what the hell is the point of saving the link pointer if the thing SEARCHES THE WHOLE LIST TO FIND THE LINK TO BE REMOVED ANYWAY? "More efficient" indeed. Comparing the value of one link to all the other linkes is HARDLY more efficient than comparing the value of the value of a link to the value of the value of another link. I guess someone's gonna have to write up a test app to make sure this is really the case, but it sure seems like it unless I'm misinterpreting the code above. |
| ||
| Whats your problem? don't see any problem with the way it is implemented. Compare is used to find an element in a list, no mather if you search for the link pointing to that element or for the value itself. The fact is that the way BM does that, is the best possible I could think of!! Because in OO, the definition of "the same" is very dependant of the subject or the system they are used in. For integers, the same is very clear, as they are the same value. But what if you have a class "Car". What makes them the same? Their color? The manufacturer? The model? The owner? Or an arbitrary combination of those? Without the compare, "the same" would be a quite useless terminology. If you want it to return reference equalness, then you can implement that in the compare, as you can any other wished behavior. Its just a mather of planning and your softwares design. And that it needs the compare to order and find is logical if you only have the least idea of OO design. Sort: Think that does not need an explanation Find: How would you find out when you can stop searching if you don't know if you already passed the point, where the object should be? (as long =1 you haven't reached it, if =-1 then you passed the point and thus return null) And if youy use TLink.remove() it does NOT search the whole list to remove it. It removes the link and links _succ and _prev to maintain the double linked list structure. If you need to do internal stuff on the List, then using the TLink is the way (or if you want to search a specific object, do some operations on it and the remove it without researching it in the list to readd it at the end, like you do in GUI systems with draging windows etc.) If you need any other help, feel free to mail me and I will try to help you. But it has no use if you come up with "why the heck" just because you seem to have no full understanding in OO design and still think on procedural somehow (at least it seems so. sorry if I'm wrong) Believe us, if the implementation was crap, we would have done our job in bringing up a better implementation that had replaced the BRL one long times ago! |
| ||
| Here is a test program. I haven't been able to get it to screw up, and I don't know why: But what if you have a class "Car". What makes them the same? Their color? The manufacturer? The model? The owner? Or an arbitrary combination of those? Without the compare, "the same" would be a quite useless terminology. I don't understand what you are saying. Look at my example above. In it I create four sprites. Each of the four sprites has the SAME order in my example, but really their order could be anyhting. I want to sort them by ORDER. So I change the compare method so that the SORT() method will work. But if I understand what Mark's code is doing, when I overrode that compare method, the REMOVE method now uses that instead, and if I pass it a link pointer to tell it to delete a specific sprite, it will compare that to the ORDER of the other sprites, and should in theory always return false. Of course now I am totally unsure of whether I have that right because I can't get my test program to screw up. And if youy use TLink.remove() it does NOT search the whole list to remove it. Ohhh yes it does. Method Remove( value:Object ) Local link:TLink=FindLink( value ) If Not link Return False link.Remove Return True End Method Method FindLink:TLink( value:Object ) Local link:TLink=_head._succ While link<>_head If link._value.Compare( value )=0 Return link link=link._succ Wend End Method See? The remove method uses findlink, even though we are passing it the pointer to the exact link that needs to be removed. And Findlink does a while loop to loop through the whole list looking for a link whose value (which is dtermined by the compare method I overrode to use order?) is the same as the specified link. So yes, it definitely is looping through the entire list when you use remove. |
| ||
| Also, I'm not sure Mark's findlink code there is even correct. Correct me if I'm wrong but: Local link:TLink=_head._succ This sets Link to be the sucessor of the head of the list, correct? Wouldn't that mean we're starting our search at the SECOND link in the list? Why start there instead of at the first link in the list? While link<>_head link=link._succ wend Okay, so if we started at the first link, the while loop would exit immediately. It seems then like Mark intended to loop through the list in reverse order, from the end, back to the head, and to stop when it reaches the head. But link=link._succ indicates that he is looping through the list in a FORWARD direction, and starting from the second link as indicated above no less. I really haven't got a clue what the hell is going on here. If I were to code this function the way I think it's supposed to work, I think it would look like this: Method FindLink:TLink( value:Object ) Local link:TLink=_head While link<>Null If link._value.Compare( value )=0 Return link link=link._succ Wend End Method Now it starts at the beginning of the list, and loops through all the elements till it reaches the end which is denoted by Null. |
| ||
| Well I can't seem to get that example to screw up no matter what I do. I guess I must have some misunderstanding here about how the compare override works. Shouldn't link._value.Compare( value ) be using the Compare value of my sprite? Is not "_value" here, the pointer to my sprite type? So would not _value.compare() execute the sprite's compare method? What's going on here? |
| ||
The RemoveLink() function does this - which decrements the ref to the object (_value) and updates the prev/next links. It isn't calling the function you thought it was Shawn.Rem bbdoc: Removes the link from the List. End Rem Method Remove() _value=Null _succ._pred=_pred _pred._succ=_succ End Method |
| ||
| Wait a minute... There are two remove methods in the tlist source file! Type TLink Method Remove() _value=Null _succ._pred=_pred _pred._succ=_succ End Method End Type Type TList Extends TData Rem bbdoc: Remove an object from a linked list about: Remove scans a list for the specified value and removes its link. End Rem Method Remove( value:Object ) Local link:TLink=FindLink( value ) If Not link Return False link.Remove Return True End Method End Type I see now. ThisSprite.Remove() calls the first one. The RemoveLink() function also calls the first one. And Sprite.SpriteList.Remove() would call the second one. Well I blame this half on my stupidity. But I also place half the blame on Mark. Using the term VALUE to refer to both the object a link points to, and the value of that object has just been confusing the hell out of me from day 1. I guess I shouldn't have flown off the handle so quick, but after that other fiasco with being unable to find previous and next links from within an EachIn loop, I was ready to believe the problems ran deeper than that. I think I'll have to start over from scratch looking at this fellows problem now that I have a little better understanding what is going on. |
| ||
| I agree. It would be more appropriate to call _value, "object" or something similar - since it is in fact, an object. May I also take this opportunity to have another dig about the absolute TRASH that is the "documentation" supplied with BlitzMax. Sort it out fellas. |
| ||
Okay so looking at contains again:Rem bbdoc: Check if list contains a value returns: True if list contains @value, else false end rem Method Contains( value:Object ) Local link:TLink=_head._succ While link<>_head If link._value.Compare( value )=0 Return True link=link._succ Wend Return False End Method Contains uses the compare method of the object you placed in the linked list. So contains would tell me if my list contains a sprite with order 5. But it would not tell me if my list contains my ship sprite. (Unless I didn't have a compare function, or wrote one that compared the object pointers.) The reason Warpy and I have been getting confused is the stupid "Value" variable name Mark has used all over the place: In this case, Value is the object you want to place in the linked list: Method AddFirst:TLink( value:Object ) In this case, Value is the value of the object you placed in the linked list according to that object's compare method: Method Contains( value:Object ) That is way too confusing, and should be changed. |
| ||
| I see your point. Surely the TList.Contains() method should be checking that link._value = value. Mark? As an extra thought Shawn. When you call Sprite.Remove() I presume it is calling link.Remove() (assuming the sprite is referencing its own link in the Sprite list). If you do not set the Sprite.link to Null within Sprite.Release() - will the link ever be released? (or will it be released once the sprite is garbage collected?) |
| ||
| It's actually Sprite.Free() and it does set Sprite._Link to Null. You are correct, if I did not do that, then the link created in the list would never truly be freed, and the sprite itself would continue to exist as well because the link would point back to it. |
| ||
| Thanks. Just trying confirm with myself how the gc system works. Well, in your case had you not set the _Link to Null, the link would persist, but the Sprite would be removed ok (since calling TLink.Remove() will set the _value to Null) |
| ||
| Well if that's the case, yeah. Hm... In that case, maybe setting _Link to Null is not neccessary. If I don't set _Link to null, but I do tell the list to remove the link, then if the list nulls ouf the link back to the sprite, and you set your own link to the sprite to null after calling the free function, then there is no longer a link to the sprite, and the garbage collector should remove the sprite... which would in turn remove the link which hasn't been freed yet. |
| ||
| I'm sure something just popped in my head whilst reading that ;) I'd stick with setting _Link to Null - just to be on the safe side :) |
| ||
| I understand the TList.Contains() method now. But it's completely mis-documented. Par for the course really. The gist of the method is to see whether a list contains an object which is 'comparably equal' to the object being passed into the call. But NOT, as the doc/method name suggests, to check whether a list CONTAINS the ACTUAL object in question. In order to test for that condition (a list containing a specific object) you should call TList.FindLink( object ) - which returns Null if the object is not in the list I wonder if BRL are actually listening to the complaints about documentation. |
| ||
Here is how your compare should look like:Method Compare%(OtherObject:Object) Local OtherSprite:Sprite = Sprite(OtherObject) If self = OtherSprite return 0 if _Order >= OtherSprite._Order return 1 endif return -1 End Method There were 3 main errors in: 1. Creating lists of differing types can't use compare (only reference pointer equalnes is counted on them) and are thus useless beside "reference ensuring", no mather what you do. They must at least extend the same basetype which has the compare implemented to be of real use with lists. 2. 0 must only be returned if the references are identical 3. due to 2, return something - something is not adviceable, because it can as well return 0 -> break. All 3 things are taken into account in the above method. I assumed that you only want to count objects the same if they point to the same object actually, not if the have the same _Order. The return 1 on >= does not destroy the relative order within a layer (nor would > and <= btw. As long as = can't return 0 TList methods will work) Most problems and errors connected to TList result out of compare method with return something - something which can return 0 and thus breaks the whole list or more than 1 equality, which points to a design error in the software system itself. Hope the compare method helps you :-) |
| ||
| errmmm shouldnt if _Order = OtherSprite._Order return 0??? |
| ||
| Dreamora: There you go telling me my compare method is wrong again. But I already told you before, I based my compare method on one of the examples. Look at this page in the Wiki, which is the same as the information in the BlitzMax docs under Objects: http://www.blitzwiki.org/index.php/Objects Returns a value less than 0 if an object is less than another object, a value greater than 0 if an object is greater than another object or the value 0 if an object equals another object. As for your point 1, I don't care about that, I don't plan on making lists that contain more than one kind of type. As for point 2, 0 must be returned only if the references are identical... I think you mean the value of the object... in this case the order. My code does that. As for point 3, being in conflict with 2, that's absurd. If Object 1 has an order of 5, and Object 2 has an order of 5, then Compare should return 0 because they are the same. 5-5 = 0 If Object 1 has an order of 10 and Object 2 has an order of 5, then Compare should return a value greater than 0. 10-5 = 5 which is greater than 0. If Object 1 has an order of 5 and Object 2 has an order of 10, then Compare should return a value less than 0. 5-10 = -5 which is less than 0. YOUR example is the one which is broken, because it will never return 0 if the two objects are equal. It will return 1. And if it returns 1, then the sorter will always thinks one value is greater than the other. And that will probably break the sort. At the very least, it will probably make the sort go from a sort where values do not change position in the list if they don't need to, to one where the values get shuffled when they don't need to be moved at all, and that reduces the efficiency of the sort and can lead to the sprites flipping back and forth which is drawn in front if they have the same orders, rather than it just being whichever was added last which is drawn in front. Anyway, maybe I am wrong here, but what you are telling me goes against the docs, and provides no way to determine if two objects have equal value, only if one is less than, or greater than AND equal to. Also, I do not see how changing the compare method should break how the list works. Most of the list functions are accessing the compare method of the link type, not the compare method of the object which the link type points to. Btw, I have already tested sorting my sprite list by the order... Look at the example I posted. It works just fine with compare set up that way. Show me an example which breaks with compare set up to use the _order - _order thing. |
| ||
| If compare returns 0 for _order = other._order, remove will remove the first with the same order as the searched object, no mather if it is the one you wanted to remove. Same goes for contains. Sswift: Compare which returns 0 means they are "the same". This means if you look for them through contains / remove, they will be removed, no mather if they are the same as they are "object compare equal" (the only real equalness test on objects). Thats why I restricted 0 to reference qualness. You did not comment in that _Order is a unique value which can't be shared by 2 objects, in which case the return on _order - _order would break with .Remove/.Contains. My compare was especially targeted for general usage, where no "reference to TLink" is used. So in general: My compare works, yours will fail. But in the special circumstances you use yours with the TLink backsave, yours will work as long as you do not use TList.Remove / TList.Contains (perhaps others) as those will fail. You cut of some functionality for speed gains. (I would better add a comment on that, to prevent untrackable bugs later) I only added my method as the talk was on the "general TList usage level" not a specific usage. Sorry if I did not write it like that. |
| ||
| TList.Remove() is fundamentally flawed anyway. The documentation is wrong (or rather inconsistent with the comments in TLink.Remove() which suggests it is the more effiecient version of TList.Remove() ) You can't even use TList.FindLink( object ) in order to find the link and remove it using link.Remove() - since TList.FindLink() uses Compare(). Note, this is only a problem if you override the Compare() function - which you need to do to perform a sort. Dreamora: your Compare function is incorrect - Swift has implemented a correct Compare function as per the definition. However - due to the flaws listed above there is a conflict between sorting and finding an object in a list - Mark's fault. |
| ||
| How should FindLink find the link for a value without compare? What in my version is incorrect? Show me the example that will break it. I use it in several spots and did not get into any trouble. If marks implementation is the wrong one, then I fear that some of the true OO languages available (which are used for critical tasks like airplanes and medic equip), are badly flawed as well, right? Its more that most seem to think of C++ OO as the correct OO which it isn't from the modern point of view. No mather how many things miss in BM, the OO parts it has are at least following the modern OO design rules. |
| ||
| It breaks on Sorts when two items have the same value but are NOT the same object. Let's not debate OO, that is not the issue, nor the problem - I've been programming C++ for over 12 years. The point is :- Compare() is used in 2 disparate situations :- 1) To act as a value comparator in a Sort. Sswift has implemented it correctly for this. 2) To act as a comparator when finding a link in a list. It cannot act for both situations without breaking one or the other. It's flawed. |
| ||
| I already assumed that this is the reason all believe my version breaks, although it does not. Same value and not same object does not break. Depending on >= or <= it will either place it as first or last object in the listpart where all have this same value. It won't interfer with higher / lower values. Its all a question of how you design your code and how much time you put into it. OO is not procedural and naturally needs far more time in planning before writting. But it has its benefits that let you forget this time, you first thought would be wasted. Sswifts code is correct for his specific situation (beside the =null check that is not needed) which is trimed for maximum speed on remove of single objects which is a really good usage of the BM possibilities. Mine is targeted to general usage where the list serves other purposes. Here the proof that it does not break
Strict
Type Test
Field value:Int
Field name:String
Method Compare:Int(other:Object)
Local obj:Test = Test(other)
If obj = Self Return 0
If value >= obj.value
Return 1
EndIf
Return -1
End Method
End Type
Function CreateTest:Test(name:String, value:Int)
Local result:Test = New Test
result.name = name
result.value = value
Return result
End Function
Global List:TList = CreateList()
For Local i:Int = 1 To 100
List.Addlast(CreateTest("In" + i,Rand(0,6)))
Next
List.sort()
For Local t:Test = EachIn List
Print Chr(34) + t.name + Chr(34) + " with value: " + t.value + "~n"
Next
End |
| ||
| I remember having this problem and ended up having to have a global sort_mode variable depending on what I was doing, which is a bit of a kludge... there should be comparevalue and compareobject methods really I guess? |
| ||
| No. Compare is a "object based equality test". If you as the designer of your software are not able to say if 2 objects of the same class are equal or if not, which one is larger, whats the use of any object oriented programming then? If your system only takes reference equalness as true equal, then only return 0 then (which indicates equal). If you don't need a that "hard" equalness (there are cases where this might happen although I can't think of any ...), you can return 0 for field equalness or level equalness (on tree structures) or anything your class needs to test for equalness (like same shape, same color, same size -> same geometric object). |
| ||
| I'm sorry but your reply doesnt make sence can you re-word it? I want to be able to compare values and also have findlink remove etc work... |
| ||
| Dreamora - what happens if you sort in descending order? |
| ||
| EDIT: Brendane, Dreamora's version works both way. Try his example. :) Thanks for that btw Dreamora. I'm guessing the problem is that the TList methods, Compare, Contains, FindLink, etc, doesn't do what the name of the methods, comments in the code and documentation suggest they do (when you override the Compare method in your own type(s)). I think most of us expect Contains to check for reference equalness, and only Sort to use Compare(?). |
| ||
| It works, but you are relying on the Sort function performing it's test in a very specific way. The interface to Compare() is clearly defined - and the usage of that is not appropriate for FindLink() etc. What if the sort function implementation was changed and the test was inverted? Your code breaks because you are not conforming to the true definition of Compare() |
| ||
| I am conforming: 1: -> actual object is larger than "other" 0: -> object is, depending on the definition, equal to "other" -1: -> actual object is smaller than "other" Don't see where this is not following the interface declaration for the method "compare". On the FindLink: How should it work out of your sight? How shall it find the tlink whichs value is "OO equal" to the object you use to search the link if it does NOT use compare? As mentioned: the equalness fully depends on the object and is nothing BM should define as it would fully break the OO usability of BM. Eiffel and other modern OO language work the same way. There is no other usefull way than the actual one. |
| ||
| "depending on the definition" is the key phrase there. You are writing your Compare function in order to make FindLink work for your Type. However in your case I cannot call Compare() on 2 (different) instances of your Type in order to test that they are equal. In that case I get 1 returned - not 0 FindLink was surely intended to find the TLink in a list which contains the ACTUAL object - no? It's only really used in TList.Remove() (as far as I can tell) - what sense does it make to use Compare in FindLink? Either that or TList.Remove() should not be using FindLink at all but should be scanning the list for the object to be removed. |
| ||
| However in your case I cannot call Compare() on 2 (different) instances of your Type in order to test that they are equal. exactly the point and an important one! |
| ||
| Sorry Chris C - are you saying Dreamora's definition of Compare is correct? It's not, I assure you. |
| ||
| Compare is not meant to be called to 2 arbitary types. Problem is you can't fix the list to a given "basetype" as BM lacks generics. Thats why I mentioned: Use a basetype from which you extend. If you plan to compare any type with each other, your design has a BIG design flaw! In a modern language, the BM way would not even be possible! You would have to use generics to define a fixed type from which everything is extended. Which is the way I suggested as well. How would you compare apples with bananas? (as a realworld example) There is no equal between those, not even a usefull possibility to define equalness. You really miss the points behind type safe (modern) OO. This is NOT C++ where you can hack around any stupid and unsecure OO stuff just because C++ does allow it. Thats BM, a language that follows actual OO design rules, not ones that were ok 20 years ago. At least from your postings, I get the real impression that you have not much experience or knowledge in type safe OO design or modern OO in general. If you aren't a Linux user, you hopefully will change this soon and fill the OO knowledge holes ... everywhere beside Linux, C++ will die sooner or later. (OSX: Objective C, Win: C#, All 3: Java) Blaming Mark for following modern programming is about the worst antisupport you can give BM!! I'm not going to post any further on this topic. Discussing with C++ programmers on modern OO system designs only makes lot of headaches with no real use. I've nothing against C++ as long as they don't want their unsecure, OO breaking pointer-unsafe hick-hacking in "real world" |
| ||
| Dreamora you have misunderstood. I never said 2 arbitrary Types, I said 2 instances of the same Type. Someone please inform me how Dreamora's Compare() correctly informs me when 2 instances of a Type are quantitatively equal. ie. item1:Fruit = CreateFruit("apple") item2:Fruit = CreateFruit("apple") if item1.Compare( item2 ) = 0 ' fruits are the same! endif It's flawed. If you write it to function correctly such that you are comparing the strings, then TList.Remove() on a Fruit does not do what you intend - rather it removes the first item which is comparably equal to the item you intend to remove, BUT not necessarily THE item you intend to remove. |
| ||
| And for your information BM has more OO holes than a swiss cheese. Constructors anyone? Safe encapsulation? Give me a break. |
| ||
| 2 instaces of the same type won't have problems with the compare methode. But the definition of "the same" depends on what you see as requirement to call them the same. In most cases this will be reference equality (at least for me so far, have not met something that would make a field based equality usefull), which is why I have the reference check as first part in the compare method and which is the only way my compare can ever return 0 (ie the only case that TList will both accept as beeing equal) For your example, this would mean, that 0 would never happen, as the Fruit Compare would do a self = fruit(other) comparision to decide if they are equal which can never be the case for item1 = item2 as those 2 references point to 2 different objects. if that fails, then they can't be equal anymore which means that only 1 and -1 can be returned after that point (the output of those 2 most likely then will depend on fields. in this case depend on the fruits name for example). That only 1 and -1 is returned, using >= and < on the names of the fruits isn't a problem for sorting as well as it won't mix the order between different names. and at which point in a "same name block" a specific instance of an apple ends for example is of no interest for the lists absolute ordering. An apple is an apple :-) |
| ||
| "Compare is not meant to be called to 2 arbitary types." He didn't say it was. He said 2 instances of your type. Ie, two apples. However in your case I cannot call Compare() on 2 (different) instances of your Type in order to test that they are equal. See? How can he call your compare and test if the two apples are mathematically equal? He can't. With your function you have only mathematically less than, POINTER equal, and mathematically greater than OR equal. 1: -> actual object is larger than "other" 0: -> object is, depending on the definition, equal to "other" -1: -> actual object is smaller than "other" Ah, but your test doesn't follow that definition. EVEN IF you assume that you can use MATHEMATICALLY greater than or less than for two of the cases, and POINTER EQUAL, your function does not follow the definition because: 1: -> actual object is larger than "other" If value >= obj.value Return 1 EndIf You return 1 if actual object is larger than or equal to "other". And that does not mesh with the definition! Also, your example is broken! Run that. That is the same as your test, but I have set all the values to 0. When the list starts out, it is sorted from 1 to 100. When it ends, it is sorted from 100 to 1. Every single element in the list has moved, even though they all had the same value! http://en.wikipedia.org/wiki/Sort_algorithm Mark's Sort function is a Bubble Sort. Bubble Sort is supposed to be INVARIANT. Ie, if two elements in the list are sorted relative to one another, then they do not swap positions relative to one another. But as you can see here, your compare function caused all the objects in the list to swap positions. Your compare method therefore broke Mark's code! If on the other hand you use my compare method: Mark's sort function does not break! If I ran your code using my sprite system, then every single update all sprites with the same order would swap positions in the list! In other words, if the user created all their sprites with the same order, and assumed that the order of creation would cause them to be drawn in the order they desired, they'd be in for a shock when every frame the sprites swapped from drawing back to front to front to back, and vice versa! |
| ||
| My example is a valid and real world requirement. I very often need to know whether I already have an item (judged by value not reference) in a list. How can I then Sort that list unless I write a separate function to compare items and forfeit the built in list scanning functions such as TList.FindLink()? Hint, I can't. The PROPER OO way to do this is to provide the call to Sort() with a function to call back to do the comparison - NOT to use the Type's overridden comparison operator. |
| ||
| Sswift: 1 and -1 are only used for sorting, while 0 is used for equality test (which is of minor importance on sorting. In trees this would normally end in a return unless you allow node value overrides). >= 1 does sort correctly as my example above has shown. For the same values, there is no rule on "how they are sorted" as I was not interested in their internal ordering. If you want it to output the elements in the ordering they were put into the list use if value > obj.value return 1 else return -1 instead of >= But as mentioned. Unless you define a ordering rule for all elements with the same value, there is no "true" or "wrong" in the sort as they are taken as relatively equal within the value = 0 group. If you need a further distinction in whats larger and what smaller, you will have to add it or it is not there. For example Method Compare:Int(other:Object) Local obj:Test = Test(other) If obj = Self Return 0 If value >= obj.value If name > obj.name Return 1 EndIf EndIf Return -1 End Method And the second block breaks baaaadly. Do a remove for any object of the "added at last" ones and you will see it as it will remove the ones at the front because it return 0 on compare for anything and TList.remove will remove the first object with compare = 0, not the one with the reference you give it due to the implementation. Marks code will only work correctly if the comparision value is unique (no 2 instances can have the same value. You could get such a unique key by using a type global int field which is incremented in method new but never decremented.before incrementing, assing its value to the ID field. that way you have unique IDs that can be used in marks way), I think that is even mentioned somewhere. Brendane: And why not? Sort only needs to know if an object is larger (for ascending sorting) or smaller (for descending sorting), so the OO compare method is exactly the thing thats needed. 0 is not even needed for sorting as sorting algos sort basing on "while smaller push to front" or "while larger push to back" ideas behind them. Quicksort would not even allow a compare 0 result as it only accepts unique sorting keys. Same goes for trees normally if they are meant to work efficiently (AVL, dictionary, segment trees, interval trees and the like). This does not mean that the actual way is perfect. But it is as perfect as the cut down OO implementation does allow it to be without making its handling the hell on earth. We have no delegates nor have we generics / multi inheritance. Delegates would be needed for the call back idea *-> method pointers* (although I would use the call back for the actual sorting method, not the compare. I use such techniques to have EventHandlers a la C# on my own ingame GUI elements or for animate AI) btw: Nothing prevents you from creating a type TSortable that has 2 distinct comparision methods and create an extended TList Type that does not base on Object but on TSortable (you then will have to extend all types from that instead of object, but that shouldn't be a problem). So its not like BM would prevent more "user intuitive" implementations of their datastructures. And that should not even be a problem btw in that case :-) |
| ||
| Dreamora: I still don't understand where you are coming from. You say my compare method is bad. Well create an example for me where MY compare method breaks, so I can see what it is you are saying is wrong about my method. I've shown you how your example breaks. "For the same values, there is no rule on "how they are sorted" as I was not interested in their internal ordering." doesn't cut it. A Bubble sort by definition is invariant. Mark's bubble sort is invariant when using my compare method. It is not invariant when using your compare method. Your compare method therefore is not compatible with Mark's bubble sort. It clearly does not return the values Mark's bubble sort expects it to return. And if it doesn't return the values MARK expects it to return, how can you possibly say it is the correct way to implement it? Wouldn't MARK know best how it is supposed to work? Wouldn't Marks OWN compare methods implemented in his own types return the correct values? Here is how Mark has implemented compare functions in HIS OWN TYPES: win32gui.bmx: Type TIntWrapper Field value Method Compare(o:Object) Return value-TIntWrapper(o).value End Method data.bmx: Type TDataId Field id Method Compare( with:Object ) Return id-TDataId(with).id End Method cocoamaxgui: Type TIntWrapper Field value Method Compare(o:Object) Return value-TIntWrapper(o).value End Method And the last one, which is the only one which is different: fltkgui.bmx: Type TFLFont Field name$,ids[4],sizes[] Method Compare( o:Object ) Local f:TFLFont=TFLFont(o) Assert f Return name.ToLower().Compare( f.name.ToLower() ) End Method This one is different because it's comparing strings, and converts the strings to lowercase before comparison. It's still returning -1 0 or 1 if the strings are less than equal or greater than one another. None of that pointer funny business. Those four examples comprise every single compare method Mark implemented in the max code. Not one is like your own. So again, I ask how you can say your method is correct when the author of the language, who should know better than you how it works, uses a different method from yours? |
| ||
| Your compare in your "real code" is not bad, it will work as it is optimized for your task :-) But marks code will break, if you use Remove / Contains on it, it will return the wrong values if the value you compare is not unique (no 2 instances can have the same value), as those 2 TList methods search for the "correct" instance through compare. They won't break unless you use one of those 2 TList methods or if you are lucky and never try to remove objects in the "wrong" order ... I can't check the BM sources at the moment, but I assume that the used IDs are unique. Either through their own functionality or through the Object that creates them and assigns the ID. |
| ||
| "But marks code will break, if you use Remove / Contains on it" You mean List.Remove() not Link.Remove()... I would argue that the problem here is that the List.Remove() and List.Contains() functions are designed to find a link with a specific value, NOT a specific link. So you're right, those do break if you change Compare() in the way I and Mark have... But that is ONLY because the "value" of a link by default is its memory location. If you decide to have the "value" of a link be the links "order" or whatever, then it makes perfect sense that List.Remove() and List.Contains() break, because those are designed to search for a link with a specific value and NOT a link with a specific location in memory. So YOU'RE one breaking List.Remove() and List.Contains()... Because they are intended to search for a link with the specified value, NOT to search for a specific link! It is totally NOT breaking them if you specify one link to them, and they delete another, because that is what they're supposed to do. So in this example, I pass it sprite3, which has a value of 2, and it removes sprite 2 because sprite 2 is the first sprite it comes across which has a value of 2. Remove scans a list for the specified value and removes its link. It says value, and if we assume that here, Mark does indeed mean VALUE, and not OBJECT, then the List.Remove() function works exactly the way it should when you have the Compare() function set up the way Mark and I have it set up. Consider this: If the List.Remove() function were NOT meant to behave in this way, then why is it comparing the value of the link's value? Method Remove( value:Object ) Local link:TLink=FindLink( value ) If Not link Return False link.Remove Return True End Method Method FindLink:TLink( value:Object ) Local link:TLink=_head._succ While link<>_head If link._value.Compare( value )=0 Return link link=link._succ Wend End Method If the List.Remove() method were meant to remove the specified object from the list, and not just any old object with the same value, then why is the findlink function coded like that? Shouldn't it be like this instead? If link.Compare(_value )=0 Return link Shouldn't it be trying to find the link in the list which has the _Value (MEMORY address) which matches the specified memory address? As it is written now, it's finding the link in the list with the object that has a Value that matches the specified object's value. And that's totally wrong and absurd if the point is to remove the specified object, and not any old object with the same value! |
| ||
| You have hit upon the real point. TList.Remove() is implemented incorrectly - or only half the functionality is there. Either it was intended to remove a mathematically equal item - or it was intended to remove the exact object. Either way, half the functionality is missing. The "documentation" gives no real clue either since there are conflicting comparisons between TList.Remove() and TLink.Remove(). No surprises there. All you're doing is abusing the Compare() method in order to make TList.Remove() work when you have non-unique items. By the very definition of Compare() (and it is clearly defined) it is meant to return 0 when 2 items are quantitavely equal. Are you doing that? No. |
| ||
| Sswift: It depends on what you search. Normally you don't create 10 objects which are value equal as this is pure waste of memory (at least I did not so far). But if you have such cases, you would most likely not do a reference check but check all fields your object has for equality. There you are right :-) But thats the strength of the compare ... you define what is allowed and required for your object and what not, not BM. And the docs state clear the same value, right. But same depends on how your object is built. In most cases you do not want to have an object removed, just because it shares 1 fields value with a different object. As mentioned, BM does not suffer of that as the IDs used within are unique. There can never be 2 objects with the same ID ... In those cases, marks will work without problems as well. But the examples you bring up use a value to compare which is not unique to only 1 instance in which case it will break and remove the wrong object as you proofed yourself. This means it does not work as intended as it does not remove the object you specified but one on the same order level. (for a sprite system, the order although should be unique as there must be one above the other in any case, so there it won't break as well). Brendane: It does remove the OO equal item (for numerics that would be mathematically equal item), and there is nothing missing to do so ... Compare = 0 -> equal. Everything <> 0 means unequal. That it is a 3 way result is just a nice addition, that makes sorting far easier as you don't need to implement several methods for it. But as I mentioned: you could use a TSortable as base Object which has a isEqual and a Compare method and use an own list. Or you could implement it and suggest it as an addition to the official thing (if it gets enough fans it could even happen that the original is adjusted and the methods split as you suggest, which surely has its good points as well) Where the conflict on TLink.remove should be is a mystery to me. It does not compare anything, it just removes itself from the list and maintains the list structure. And that different object have same names for familiar functions is what OO is for ... Otherwise we could use procedural where a function name only can exist once. But I think we are somehow turning around the whole topic instead of really getting to the point. |
| ||
| Without going over what has already been said you can always simply extend the base TList type and reimplement the way links are compared to suit your requirements. Isn't that one of the main advantages of OOp? For example you can have a TStrictList type that will check that the object is a specific instance instead of a comparision with the following code... Type TStrictList 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 Method Contains:Int( value:Object ) Local link:TLink=_head._succ While link<>_head If link._value = value Return True link=link._succ Wend Return False End Method End Type This will then give you a dropin replacement whenever you need it and because your extending the TList type you dont need to change any variable declarations they can simply stay as a TList type but you now use "New TStrictList" when creating a new instance. For example... Local l:TList l = New TStrictList |
| ||
| Compare() was designed to act as a value comparator to perform in a Sort algorithm. This bears no direct relation to 'equality' (imagine I am sorting on a single non-unique field). The problem is Compare() is being used in TList.Remove() which has nothing to do with sort criteria. Lomat you are very right - I could simply derive from the TList class and override those members. I could also ditch the TList and write my own. My point is that the base class is flawed from the beginning and ought to be addressed. |
   |