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...
Type TListRevEnum Extends TListEnum
Method NextObject:Object()
Local value:Object=_link._value
Assert value<>_link
_link=_link._pred
Return value
End Method
End Type
Type TReverseListEnum
Method ObjectEnumerator:TListEnum()
Return _enumerator
End Method
Field _enumerator:TListEnum
End Type
Type TListRev Extends TList
Method ReverseEnum:TReverseListEnum()
Local rev:TReverseListEnum = New TReverseListEnum
rev._enumerator = ReverseEnumerator()
Return rev
End Method
Method ReverseEnumerator:TListEnum()
Local enum:TListEnum=New TListRevEnum
enum._link=_head._pred
Return enum
End Method
EndType
testList:TListRev = New TListRev
testList.AddLast("A")
testList.AddLast("B")
testList.AddLast("C")
Local t$
For t$ = EachIn testList.ReverseEnum()
Print t
Next
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
Just for fun...
SuperStrict
Framework brl.linkedlist
Import brl.standardio
Type TReverseListEnum Extends TListEnum
Method HasNext:Int()
Return _link._value<>_link
End Method
Method NextObject:Object()
Local value:Object=_link._value
Assert value<>_link
_link=_link._pred
Return value
End Method
End Type
Type TReverseList Extends TList
Function Create:TReverseList(list:TList)
Local this:TReverseList = New TReverseList
this._head = list._head._pred
Return this
End Function
Method ObjectEnumerator:TListEnum()
Local enum:TReverseListEnum=New TReverseListEnum
enum._link=_head
Return enum
End Method
End Type
' TEST
Local list:TList = New TList
For Local i:Int = 0 Until 26
list.AddLast(Chr(i + 65))
Next
Print "Forward"
For Local s:String = EachIn list
Print s
Next
Local rlist:TReverseList = TReverseList.Create(list)
Print "~nReverse"
For Local s:String = EachIn rlist
Print s
Next
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!
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 rlist
Becomes...
'... 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.
SuperStrict
Framework brl.blitz
Import brl.standardio
Import brl.linkedlist
Local _list:TList = New TList
_list.AddLast("sag")
For Local obj:Object = EachIn New TListReversed.Create(_list)
Print "eachin"
If obj <> Null Then Print "Object"
Next
While True
For Local obj:Object = EachIn _list
Print "eachin"
If obj <> Null Then Print "Object"
Next
Wend
Type TListReversedEnum Extends TListEnum
Method HasNext:Int()
Return _link._value <> _link
End Method
Method NextObject:Object()
Local value:Object = _link._value
Assert value <> _link
_link = _link._pred
Return value
End Method
End Type
Type TListReversed Extends TList
Method Delete()
' TRY TO DO NOTHING!!
End Method
Method Create:TListReversed(list:TList)
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 TypeAs 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.