Backwards list enumeration

BlitzMax Forums/BlitzMax Programming/Backwards list enumeration

plash(Posted 2009) [#1]
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?!


Arowx(Posted 2009) [#2]
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



plash(Posted 2009) [#3]
I was thinking of doing it internal, having a separate enumerators (like the TMap has the Value and Key enumerators).


Arowx(Posted 2009) [#4]
You could try something like this...



Brucey(Posted 2009) [#5]
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



plash(Posted 2009) [#6]
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.


Brucey(Posted 2009) [#7]
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


plash(Posted 2009) [#8]
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.


jsp(Posted 2009) [#9]
Is

MyList.reverse()
or
ReverseList(MyList)

not good enough?
Or do you need the forward and reverse access at the same time?


Brucey(Posted 2009) [#10]
MyList.reverse()

Problem with that is it does a full list copy. Which, if you had 10,000 items, wouldn't be very efficient.


jsp(Posted 2009) [#11]
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.


plash(Posted 2009) [#12]
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.


jsp(Posted 2009) [#13]
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(Posted 2009) [#14]
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.


Arowx(Posted 2009) [#15]
Nice one Brucey!

Although I don't think you need the HasNext() method in TReverseListEnum! ;o)


plash(Posted 2009) [#16]
@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.


Arowx(Posted 2009) [#17]
@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.


plash(Posted 2009) [#18]
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.


Arowx(Posted 2009) [#19]
@Plash: Sorry the HasNext method, not the NextObject method!


plash(Posted 2009) [#20]
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.


Arowx(Posted 2009) [#21]
No hindrance merely unnecessary that's all, otherwise it's ideal!


dmaz(Posted 2009) [#22]
http://www.blitzbasic.com/codearcs/codearcs.php?code=1807


Arowx(Posted 2009) [#23]
Wow that looks like it should be added to BRL!


Brucey(Posted 2009) [#24]
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.


Arowx(Posted 2009) [#25]
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?


Brucey(Posted 2009) [#26]
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 :-)


Arowx(Posted 2009) [#27]
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?


plash(Posted 2009) [#28]
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!!!)


Brucey(Posted 2009) [#29]
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


plash(Posted 2009) [#30]
Excellent. Thanks again.