Backwards list enumeration
BlitzMax Forums/BlitzMax Programming/Backwards list enumeration
| ||
I'm not entirely sure how to do this, as I can't even discern how TListEnum gets the first object in the list.. But it would be handy for GUI systems, like in FryGUI, when it draws it reverses the child list, enumerates and renders them, then reverses it again. Obviously that could slow things down if you have a lot of things going on. Any ideas?! |
| ||
You could sort the list, or use two lists if memoy is no problem. Then again a list is just a set of List items with pervious and next links, you could just loop through all the previous items until the arrive at the first... testList:TList = New TList testList.AddLast("A") testList.AddLast("B") testList.AddLast("C") For t$ = EachIn testList Print t Next Local link:TLink = testList.LastLink() Repeat t$ = String(link.value()) Print t link = link.PrevLink() Until link = Null |
| ||
I was thinking of doing it internal, having a separate enumerators (like the TMap has the Value and Key enumerators). |
| ||
You could try something like this... |
| ||
Just for fun... Ideally you'd want to override most of the methods, since they all specifically work forwards... but if you just want to iterate... does the job. No sorting required :-p Edit : somewhat like Merx's example, only mine works without exposing a new iterator to the code... For Local s:String = EachIn rlist |
| ||
The idea was to have it integrated with TList and have EachIn just enumerate like it always would, but have a method from the TList to enumerate backwards.. but that would take Sibly involvement, and we would have to wait for the next release. Thanks. |
| ||
The idea was to have it integrated with TList and have EachIn just enumerate like it always would It does. It's called Polymorphism :-p |
| ||
After editing and whatnot that post came out slightly wrong, your code is excellent, and you can simply wrap TReverseList around a TList, which is the next best thing to having it implemented directly in TList. |
| ||
Is MyList.reverse() or ReverseList(MyList) not good enough? Or do you need the forward and reverse access at the same time? |
| ||
MyList.reverse() Problem with that is it does a full list copy. Which, if you had 10,000 items, wouldn't be very efficient. |
| ||
Don't see a new list here. From the source: Rem bbdoc: Reverse the order of the list. End Rem Method Reverse() Local pred:TLink=_head,succ:TLink=pred._succ Repeat Local link:TLink=succ._succ pred._pred=succ succ._succ=pred pred=succ succ=link Until pred=_head End Method But i see it can be too much on a huge list, so another enumerator would be fine. Didn't thought it alters the hole list, but probably done to be sure all other commands work as expected. |
| ||
Don't see a new list here. He didn't say there would be a new list, clearly just enumerating the values in the list backwards is faster than reversing, enumerating, and then reversing again. |
| ||
Plash i meant Brucey, because he said a full list copy is done during reverse. But beside that, you (and Brucey) are completely right it will be much faster on huge lists and should be available official. |
| ||
Plash i meant Brucey Notice "He didn't say ..." because he said a full list copy is done during reverse. Ah, right :)Anyways, yes it should be official. |
| ||
Nice one Brucey! Although I don't think you need the HasNext() method in TReverseListEnum! ;o) |
| ||
@Merx: My guess is NextObject would throw an Assert (which was also in the TList code, probably as a fail-safe.. that would never be reached) if you did remove HasNext. |
| ||
@Plash: Just tried the example and it worked fine with and without the HasNext method. I believe that this is becase this method already exisits in TListEnum and as the overloaded version in TReverseListEnum is exactly the same it is in effect redundant. |
| ||
EDIT: That's impossible, my output is this (with NextObject removed):Forward A-Z Reverse Z Makes sense too, it will just get the first value from TReverseList.ObjectEnumerator() and since there is no NextObject method it can't go anywhere. |
| ||
@Plash: Sorry the HasNext method, not the NextObject method! |
| ||
I'm seeing that here too (with the HasNext method), it is probably, like you said, reverting to the HasNext method in TListEnum. Even if that was a hindrance, I don't think it would be a very big one. |
| ||
No hindrance merely unnecessary that's all, otherwise it's ideal! |
| ||
http://www.blitzbasic.com/codearcs/codearcs.php?code=1807 |
| ||
Wow that looks like it should be added to BRL! |
| ||
Except that you can't use it to pass a TList to a function, and expect it to "just work", since you need to explicitly use the relevant enumerator. |
| ||
Yes but if you were to use the TListF or update TList with it's features you would only have to add the relevant method call to get alternate behavior as opposed to creating a New object with reverse behavior. So... '... list created and setup 'reversed list created Local rlist:TReverseList = TReverseList.Create(list) 'reverse list used For Local s:String = EachIn rlistBecomes... '... flist created and setup 'list used in reverse For Local s:String = EachIn flist.Reverse() Assuming that a Reverse method is added that just starts at the last element and wraps ReverseFrom(). It seems simpler and more intuitive to me? |
| ||
It seems simpler and more intuitive to me? I think it is cumbersome and ugly ;-) Function ProcessList(list:TList) For Local s:String = EachIn list ' .... Next End Function ' normal... ProcessList(myList) ' reverse... ProcessList(TReverseList.Create(myList)) None of this messing about with enumerators. Of course it all depends how you work with OOP I suppose. In my case, I believe that if you want to reverse the functionality of a class, you extend and apply, without exposing NEW unnecessary methods. Your code doesn't care what direction it works in... only that it can be called in the same way as usual. The whole idea of Polymorphism is to enable you not to have to expose 4 functions in your API to process lists in different ways, but rather have 1 function which can be passed many different subclasses and be indifferent to the actual underlying implementations. But, each to their own :-) |
| ||
I think you might have something the thing is we don't really want extra methods on the list, what were after is seperate ways to enumerate/iterate a provided list/container, and eachin expects an enumerator it just gets the default one from the list! In effect all we have been doing is overloading the obtain enumerator method and providing an enumerator that goes to the previous link! Or iterates a different way, doesn't Java and C++ have iterators for this kind of thing, could they be added to BlitzMax? |
| ||
Rawr! This broke my whole app. As soon as GC kicks in that list is toast. I tried sticking a Delete method in TListReversed but it doesn't seem to override the TList delete method (which clears the list!!!) |
| ||
This should fix it.Type TListReversed Extends TList Field _origHead:TLink Method Delete() _head = _origHead End Method Method Create:TListReversed(list:TList) _origHead = _head Self._head = list._head._pred Return Self End Method Method ObjectEnumerator:TListEnum() Local enum:TListReversedEnum = New TListReversedEnum enum._link = _head Return enum End Method End Type Before "Delete", we replace _head with our original TLink... :-p |
| ||
Excellent. Thanks again. |