Rrrrrggghhhh!!! Manual list iteration?

Monkey Forums/Monkey Programming/Rrrrrggghhhh!!! Manual list iteration?

DruggedBunny

(Posted 2011) [#1]

This has been driving me nuts for about an hour now! I just want to do the equivalent of this manual iteration through a list (BlitzMax code, and this was horrible enough), but keep getting bogged down with references to Nodes and Enumerators (neither of which are giving me any joy, just errors, because I don't understand how to use them properly)...

' Manual iteration...

Local link:TLink

link = list.FirstLink ()

While link <> Null

	t = Test (link.Value ())
	Print t.x
	
	link = link.NextLink ()
	
Wend

I won't be moving to the next item in a straight loop like this (or I'd just use For/Eachin), so need to store a reference to a current list item, then just jump to the next when it suits, ie. effectively call link = link.NextLink () when it suits me.

Here's about as close as I got before falling over flat, just to show I've tried! I can see why this fails now (though it took many abortions just to get here), but I don't get why there are no references to the next/previous items in these structures...

Import monkey.list

Class Tester
	Field something:String
	Field node:list.Node <Tester>
End

Function Main ()

	Local mylist:List <Tester> = New List <Tester>
	
	For Local loop:Int = 1 To 10
		Local t:Tester = New Tester
		t.something = "Hello: " + loop
		t.node = mylist.AddLast (t)
	Next

	' Test...
	
	For Local tt:Tester = Eachin mylist
		Print tt.something
	Next
	
	Local ttt:Tester = mylist.First
	Print ttt.something

	' OK, stuck.
		
'	Local abort:Int = 0
	
'	While ttt
'		Print ttt.something
'		ttt = Tester (ttt.node.Value) ' Yeah, that was stupid!
'		abort = abort + 1
'		If abort > 100 Then Error ""
'	Wend
	
End

Is there a reason Next and Prev couldn't be part of Monkey's List, similar to its First and Last methods? I can't really fathom how list.monkey operates at all!

Jesse

(Posted 2011) [#2]

I had to add those to list.monkey since list and node were pretty useless to me as they are.
Inside the Node class:

	Method NextNode:Node()
		If _pred<>_succ And _succ._data Return _succ
		Return Null
	End
	
	Method PrevNode:Node()
		If _pred<>_succ And _pred._data Return _pred
		Return Null
	End

then it works like this:

Import list

Class Tester
	Field something:String
	Field node:list.Node <Tester>
End

Function Main ()

	Local mylist:List <Tester> = New List <Tester>
	
	For Local loop:Int = 1 To 10
		Local t:Tester = New Tester
		t.something = "Hello: " + loop
		t.node = mylist.AddLast (t)
	Next

	' Test...
	
	For Local tt:Tester = Eachin mylist
		Print tt.something
	Next
	Print "************ link start ***********"
	Local ttt:Tester = mylist.First
	Local node:list.Node<Tester> = ttt.node
	Local abort:Int = 0
	
	While node
		Print Tester(node.Value()).something
		node = node.NextNode() ' Yeah, that was stupid!
		abort = abort + 1
		If abort > 100 Then Error ""
	Wend
	
End

can't really add them to the List class because the way it works.
if Mark had not made the Node fields as private I wouldn't have to be modifying the list class every time I update to the newer monkey version by just creating an extended class from the original node class. but apparently he think we all need a baby sitter.

Foppy

(Posted 2011) [#3]

Here's a (partial) example of a TCreature class in my game that maintains a custom linked list using gFirst and gLast globals, and fPrevious and fNext fields, as well as a method to add a new object to the list and a function to iterate through them for drawing all creatures:

Class TCreature
	Global gFirst:TCreature = Null
	Global gLast:TCreature = Null
	
	Field fPrevious:TCreature
	Field fNext:TCreature

	Function renderAll()
		Local creature:TCreature = gFirst
		While (creature <> Null)
			creature.render()
			creature = creature.fNext
		Wend
	End Function
	
	Method New()
		fPrevious = Null
		fNext = Null
		
		addToList()
	End Method
	
	Method addToList:Void()
		If (gFirst = Null) Then
			gFirst = Self
			gLast = Self
		Else
			gLast.fNext = Self
			fPrevious = gLast
			gLast = Self
		End If
	End Method
End

So this does not actually use a Monkey List. I use this to enable simple depth sorting as I couldn't figure out how to do that with a Monkey List.

muddy_shoes

(Posted 2011) [#4]

If you want to do this with monkey's list (without altering the standard code) then you need to initialise and hold your own reference to a list enumerator.

Import monkey.list

Class Tester
    Field something:String
    Field node:list.Node <Tester>
End

Function Main ()

    Local mylist:List <Tester> = New List <Tester>
	
    For Local loop:Int = 1 To 10
        Local t:Tester = New Tester
        t.something = "Hello: " + loop
        t.node = mylist.AddLast (t)
    Next

    ' Test...
	
    For Local tt:Tester = Eachin mylist
        Print tt.something
    Next
	
    Local ttt:list.Enumerator<Tester> = New list.Enumerator<Tester>(mylist)
	
    While ttt.HasNext()
        Print ttt.NextObject().something
    Wend
	
End

DruggedBunny

(Posted 2011) [#5]

Wow, thanks all. I don't want to modify the Monkey source on every update, if I can avoid it (though I'd really like to see those Next/Prev added to Node, or, better, to List in the same way as you can use First/Last).

The self-maintained list thing is simple to grasp, and I'll probably have a use for that method at some point, but muddy's Enumerator is probably my preference for now. It's very compact, actually, but there's no way I would have come up with ttt:list.Enumerator<Tester> = New list.Enumerator<Tester>(mylist), and no way I'm going to remember it on-the-fly for future reference!

@Mark: Pretty-please can we have a Next/Prev of some kind for lists?

Thanks again all!

muddy_shoes

(Posted 2011) [#6]

Well you can just do this:

Local ttt := mylist.ObjectEnumerator()

I just thought you'd rather see the workings.

Jesse

(Posted 2011) [#7]

I like that muddy!
although I still need to add those pesky methods as I don't always start from the first or last and don't like the fact that the enumarator crates a new object every time it is started.
but very useful none the less.

muddy_shoes

(Posted 2011) [#8]

As I believe I've posted before, considering the current implementation of the monkey collections and the difficulty of extending them it's pretty much required to create your own module/use a third-party library if you want anything more than the most basic features.

DruggedBunny

(Posted 2011) [#9]

I'll certainly be looking at "the workings" but I definitely stand more of a chance of remembering the short version! Thanks again, very useful stuff.

AdamRedwoods

(Posted 2011) [#10]

Yes, i think i forked my own version of List to make the GetNextNode and GetPrevNode methods.

	Method GetNext:T()
		Return _succ._data
	End Method
	
	Method GetPrev:T()
		Return _pred._data
	End Method

What is frustrating is that this _succ and _pred data is private so you can't even extend the Class to get what you want from vanilla Monkey, but no matter, just fork it.

marksibly

(Posted 2011) [#11]

Hi,

Haven't read the whole thread, but here's my take on this...

The big issue with adding GetNext() and GetPrev() methods to link is detecting the 'head' link. I had a quick hack at adding these just a short while ago and ran into this straight away.

The head link is a special link that makes it more efficient to add and remove items from a list. However, it's not a real link and should generally not even be returned by GetNext() or GetPrev(), so these methods need to be able to check for head nodes and return null when appropriate.

In BMX, you could detect head nodes by checking for 'Null' values in the node, since lists can't. That wasn't always the case, and there was originally some pretty convoluted code to detect head node case for use with GetNext() and GetPrev().

Monkey lists CAN contain Null though - a feature I consider important - so some other mechanism is required. I have a few ideas here and may revisit the issue at a later date, but I DO NOT want to sacrifice current list efficiency or compactness (such as they are) for the sake of GetNext/GetPrev.

But more to the point, not every container is gonna suit your needs 100%, and creating your own variation of list/stack/whatever etc is sometimes gonna be the 'right' solution. This is esp. true for things like games where you want as much efficiency as possible - ie: Foppy's code rulez!

And please, I strongly suggest NOT 'forking' Monkey, if by forking you mean modifying the current monkey.list code. Instead, why not create your own List class, and stick it in a separate module/file?

GfK	(Posted 2011) [#12]

When I hit this problem, I just switched to using a Stack instead of a List. Then its just a case of adding or subtracting 1 from the index.

muddy_shoes

(Posted 2011) [#13]

Monkey lists CAN contain Null though - a feature I consider important - so some other mechanism is required. I have a few ideas here and may revisit the issue at a later date, but I DO NOT want to sacrifice current list efficiency or compactness (such as they are) for the sake of GetNext/GetPrev.

Is there some reason why a sentinel value for the head data reference isn't a solution here?

marksibly

(Posted 2011) [#14]

Hi,

Ok, I think I've come up with a solution that should also make lists more efficient!

I've posted a new list module to the product updates section, so give it a whirl. Not well tested...

New methods:

List.FirstNode:Node<T>()
List.LastNode.Node<T>()
Node.NextNode:Node()
Node.PrevNode:Node()

> Is there some reason why a sentinel value for the head data reference isn't a solution here?

The problem here is that the sentinel needs to be a 'T' object, which complicates things enormously.

What I've done instead is to make List extend Node and added a private GetNode:Node() method to node that returns Self for a node, but Null for the list. A bit grubby, but it works and means one less node allocation per List, plus one less indirection for any 'head' ops inside list.

DruggedBunny

(Posted 2011) [#15]

Thanks for taking a look, Mark. I can certainly get by now, but I'll probably have to search on how to do it again in future, rather than just hitting the docs/typing the much more memorable GetPrev/Next.

EDIT: Ah, cool!

muddy_shoes

(Posted 2011) [#16]

list.monkey<203> : Error : Identifier '_prev' not found.

DruggedBunny

(Posted 2011) [#17]

Typo in experimental version!

	Method PrevNode:Node()
		Return _prev.GetNode()
	End

... should be:

	Method PrevNode:Node()
		Return _pred.GetNode()
	End

But that works fine once fixed:


Import monkey.list

Class Tester
	Field something:String
End

Function Main ()

	Local mylist:List <Tester> = New List <Tester>
	
	For Local loop:Int = 1 To 10
		Local t:Tester = New Tester
		t.something = "Hello: " + loop
		mylist.AddLast t
	Next
	
	Print "Forwards..."
	
	Local node:list.Node <Tester>
	
	node = mylist.FirstNode
	
	While node
		Print Tester (node.Value).something
		node = node.NextNode
	Wend
	
	Print "Backwards..."

	node = mylist.LastNode
	
	While node
		Print Tester (node.Value).something
		node = node.PrevNode
	Wend
	
End

Thanks, Mark.

muddy_shoes

(Posted 2011) [#18]

It works, but it's pretty odd from an interface perspective - what does "mylist.Value()" mean?

The same question applies to "mylist.Remove()" except that it throws a compilation error because of the mismatched override.

marksibly

(Posted 2011) [#19]

Hi,

> what does "mylist.Value()" mean?

Well, ideally you shouldn't be able to see these! You're using Jungle I take it?

If Monkey had 'private derivation' this could be solved, but it doesn't.

Unfortunately, it's the only sane solution I can think of for now.

List.Remove should probably be removed entirely and replaced by RemoveEach for good.

marksibly

(Posted 2011) [#20]

Hi,

> Typo in experimental version!

Thanks!

Another alternative would be to add a new HeadNode class that does the Return Null hack for GetNode, but we'd lose any optimizations this offers.

Or, just drop the idea of a head node and live with a slightly slower list that does a bit of extra special case checking. Also, Node.Remove becomes trickier this way - either you'd need to pass the list to Node.Remove (without any practical way of knowing whether it's the *right* list), or store the list in EVERY node (yuck).

muddy_shoes

(Posted 2011) [#21]

Does it matter if I'm using Jungle or not? It seems a bad idea in the long run to base the design of the class hierarchy on an assumption that people won't read the code or use an IDE with intellisense. In the absence of private derivation isn't composition the appropriate answer? I'm not entirely sure what the efficiency win really is anyway considering that the lifetime of the head node is equivalent to the lifetime of the list if you don't clear it (and even that could be changed to simply reset the head).

Class Node<T>

Private
	
    Field _succ:Node
    Field _pred:Node
    Field _data:T
    Global SENTINEL:Object = New Object()
    
Public

    'create a _head node
    Method New()
        _succ=Self
        _pred=Self
        _data=SENTINEL
    End

    'create a link node
    Method New( succ:Node,pred:Node,data:T )
        _succ=succ
        _pred=pred
        _succ._pred=Self
        _pred._succ=Self
        _data=data
    End
	
    Method NextNode:Node()
        If _succ._data <> SENTINEL
            Return _succ
        End
        Return Null
    End
	
    Method PrevNode:Node()
        If _pred._data <> SENTINEL
            Return _pred
        End
        Return Null
    End
    
    Method Value:T()
        Return _data
    End

    Method Remove()
        _succ._pred=_pred
        _pred._succ=_succ
    End Method

End

marksibly

(Posted 2011) [#22]

Hi,

> I'm not entirely sure what the efficiency win really is anyway considering that the lifetime of the head node is equivalent to the lifetime of the list

The main efficiency win is skipping all the _head. indirections in pretty much every list method.

> Global SENTINEL:Object = New Object()

Yuck, well I guess that'd work for now...

I can personally live with the 'public' extension of node method as it works at runtime (and is 'safe' in that it can't put an object into an illegal state) - what's the general consensus here?

...but you're probably right. It's not any worse than the current list anyway.

marksibly

(Posted 2011) [#23]

Hi,

Ok, new sentinal based version is up.

The sentinal object hack is probably the right way to do this, just threw me a little at first!

I've also nulled out the succ and pred fields of Node inside Node.Remove - otherwise, it'd be possible to mess up a list using multiple Node.Removes. Now, you'll get a Null object error if you try and Remove a Node twice.

marksibly

(Posted 2011) [#24]

...and, fixed version up!

Test app:

Function Main()

	Local list:=New IntList
	For Local i:=1 To 100
		list.AddLast Rnd( 1000 )
	Next
	
	Print list.Count()

	Print "Eachin"	
	list.Sort
	For Local i:=Eachin list
		Print i
	Next
	
	Print "Node.NextNode"
	Local node:=list.FirstNode()
	While node
		Print node.Value
		node=node.NextNode()
	Wend
	
	Print "Node.PrevNode"
	Local node2:=list.LastNode()
	While node2
		Print node2.Value
		node2=node2.PrevNode()
	Wend

End

GfK	(Posted 2011) [#25]

Cool!

marksibly

(Posted 2011) [#26]

Hi,

Another approach would be to have both List and Node extend a common, completely private _Node class such as:

Private
Class _Node<T>
	Private
	Field _succ:_Node<T>,_pred:_Node<T>,_data:T
	Method _GetNode:Node<T>()  'overriden by Node<T> to return self.
	End
End

So yes, users could indeed 'read the code' and see how List works, but wouldn't be able to access _Node<T> in any way whatsoever, so it'd be 'sort of' privately derived!

muddy_shoes

(Posted 2011) [#27]

Could be a goer. I'd be interested to see some measurements to see what the performance differences are across the targets.

From my perspective it's more about defining a stable interface that doesn't have any major oddities or potential for sneaky usage that becomes a compatibility issue at some later date. If the core list/node methods are stable then building/testing/deploying new implementations isn't as much of a problem.

Samah

(Posted 2011) [#28]

I don't know if it helps, but if you use Diddy's ArrayList, you can get a custom enumerator that supports forward and backward traversal. It does mean creating an object, but you can keep a reference to that enumerator and reset it every loop instead.
http://code.google.com/p/diddy/wiki/ArrayList

' create list
Local al:ArrayList<StringObject> = New ArrayList<StringObject>

' add stuff
al.Add("a")
al.Add("b")
al.Add("c")

' get the enumerator after you create the list
Local enum:AbstractEnumerator<StringObject> = al.ObjectEnumerator()

' forward
While enum.HasNext()
	Local obj:StringObject = enum.NextObject()
	Print obj.value
End

' backward
While enum.HasPrevious()
	Local obj:StringObject = enum.PreviousObject()
	Print obj.value
End

' move to first
enum.First()

' remove the object that was returned from the most recent call to NextObject, PreviousObject, Last, or First
enum.Remove()

' move to last
enum.Last()

' backward
While enum.HasPrevious()
	Local obj:StringObject = enum.PreviousObject()
	Print obj.value
End

Prints:

a
b
c
c
b
a
c
b

Note that the enumerator enforces concurrency checking, so if you modify the list at any stage (other than the enumerator's Remove() method), it will throw an error until you call Reset().

marksibly

(Posted 2011) [#29]

Hi,

I do like that approach, as exposing Node in first place just feels wrong to me.

Also, having Remove() in the enumerator gives more flexibility when it comes to implementing the list - an 'owner' list field per node might be too heavy, but not so per enumerator.

But it really depends on what people need to do, and that's not altogether clear - "I need to access the nodes" is not really an answer. The node approach does allow you to manage individual items more easily, which may or may not be important.

Some more interesting related reading:

http://www.uop.edu.jo/download/PdfCourses/Cplus/iterators-must-go.pdf

dmaz	(Posted 2011) [#30]

I consider removing nodes as critical and it's why many people are asking for them. you don't want to iterate a list just to find the object to remove. you need to be able to specify the node directly and ALSO, not just in the list that you are currently iterating. (unless you pick the approach to mark objects for removal, which I don't find ideal)

muddy_shoes

(Posted 2011) [#31]

In terms of "what people need to do", I'm seeing three main drives in threads about list access via nodes:

1. Delete stuff quickly.
2. Iterate backwards or forwards at will.
3. Make stuff look like the other Blitz languages.

To be honest, it's the last one that seems to be the main driver.

Jesse

(Posted 2011) [#32]

Yes and No.
In my opinion for me, Monkey language is a derived from Blitzmax and I have learn to use BlitzMax so efficiently(opinion) that I expect that same or better functionality in Monkey. but when I compare the list from monkey to the list in BltzMax it seems like a step backwards in some situations. if I could achieve the same functionality and efficiency in Monkey as with BlitzMax in a different way, I wouldn't be complaining about it. specially when I think it's something that can easily be achieved.

I think one of the biggest problems here(at least for me and maybe for many others) is that I learnt at home not at school so I don't really know any other way unless it is illustrated to me. Show me a better way of doing the same things as efficiently and I adopt. I won't look back. at lest that's how I feel.

as an example, I never worked with or seen interface in use. I didn't think I would ever have a need to use them either but now that I am learning how to use them I am glad it's there. now I feel like going to BlitzMax and say "why hasn't this been implemented yet?"

muddy_shoes

(Posted 2011) [#33]

I wasn't suggesting that there weren't real functional needs (see points 1 and 2). I was talking about why people are requesting the node access and, as far as I can tell, they're doing it because it's the solution they are familiar with from other Blitz products. When you see direct references to stuff like "TLink" it's not hard to spot where the thought process is rooted.

Difference

(Posted 2011) [#34]

But it really depends on what people need to do, and that's not altogether clear

I was recently looking for this, when I had a list of polygon points and was calculating the angle for each point, - thus needing to get point, previous point and next point.

It would be perfect if PrevNode() and NextNode() had options to loop so that:

If I was trying to use NextNode() and my node was the last in a list, I would get the first node.
If I was trying to use PrevNode() on the first node, I would get the last node.

Something to the effect of:

'Overloaded version of NextNode() that takes loop as a dummy parameter to call this version

Method NextNode:Node(loop:Bool)

	If Self.NextNode() Return Self.NextNode()
	
	Return FirstNode()

End Method


'Overloaded version of PrevNode() that takes loop as a dummy parameter to call this version

Method PrevNode:Node(loop:Bool )
	
	If Self.PrevNode() Return Self.PrevNode()
	
	Return Self.LastNode()

End Method

[EDIT]

Or just

Method NextLoopedNode:Node()

	If Self.NextNode() Return Self.NextNode()
	
	Return FirstNode()

End Method


Method NextLoopedNode:Node( )
	
	If Self.PrevNode() Return Self.PrevNode()
	
	Return Self.LastNode()

End Method

Jesse

(Posted 2011) [#35]

can't you just extend the list class for that?:

Class MyList Extends List<T>
	Method NextLoopedNode:Node()
	
		If NextNode() Return NextNode()
		
		Return FirstNode()
	
	End Method
	
	
	Method NextLoopedNode:Node( )
		
		If PrevNode() Return PrevNode()
		
		Return LastNode()
	
	End Method
End Class

Difference

(Posted 2011) [#36]

How can List<T> know what current node is?

If anything needs extending, it would be node.

If I can extend node:list.Node <Tester>
and use node = mylist.FirstNode

to get the extended not type that has the NextLoopedNode() method, I'm good with that, but I would think that this functionality belongs in the basic node code.