List.InsertAfter() ?

Monkey Forums/Monkey Programming/List.InsertAfter() ?

Midimaster

(Posted 2013) [#1]

There is no command to add object at a certain position in a LIST. Can I do it with copying all to a temporary list?

Class TTest
	Global Liste:List<TTest>=New List<TTest>
	
	Function InsertAfter:Void(After:TTest, NewOne:TTest)
		Local locListe:List<TTest>=New List<TTest>
		
		For Local loc:TTest=Eachin Liste
			locListe.AddLast loc
			If loc= After
				locListe.AddLast NewOne
			Endif
		Next
		Liste.Clear()
		For Local loc:TTest=Eachin locListe
			Liste.AddLast loc
		Next		
	End
End

I read something about timing problems and garbage collection problems with this method. But in my code it works perfect and fast.

here is a executable sample:

Strict
Import mojo

Class Game Extends App

	Global Number%=1000



	Method OnCreate%()
		SetUpdateRate 15
		TTest.StartUp Number
		TTest.Out
		Return 0
	End	



	Method OnUpdate%()
		If KeyHit(KEY_ESCAPE) Then Error ""
		
		
		If TouchHit(0) 
			Local AnyWhere:TTest= TTest.GetAny(Rnd(Number))
			
			Local ThisNewOne:TTest=New TTest
			Number=Number+1
			ThisNewOne.x=Number

			Local Zeit%=Millisecs()
			Zeit=Millisecs()-Zeit
			
			TTest.InsertAfter AnyWhere,ThisNewOne
			TTest.Out
			Print "time needed=" + Zeit
			
		Endif
		Return 0
	End	



	Method OnRender%()
		DrawText "click", 100,100
		Return 0
	End	
	
End



Function Main%()
	New Game
	Return 0
End



Class TTest

	Global Liste:List<TTest>=New List<TTest>
	Field x%

	
	Function StartUp:Void(Max%)
		For Local i%=0 To Max
			Local loc:TTest=New TTest
			loc.x=i
			Liste.AddLast loc
		Next
	End


	
	Function GetAny:TTest(Random%)
		Local i%
		For Local loc:TTest=Eachin Liste
			If i=Random
				Return loc
			Endif
			i=i+1
		Next
		Return Null
	End


	
	Function Out:Void()
		Local t$
		For Local loc:TTest=Eachin Liste
			t=t + " " + loc.x
		Next
		Print "Liste=" + t
	End


	
	Function InsertAfter:Void(After:TTest, NewOne:TTest)
		Local locListe:List<TTest>=New List<TTest>
		
		For Local loc:TTest=Eachin Liste
			locListe.AddLast loc
			If loc= After
					locListe.AddLast NewOne
			Endif
		Next
		Liste.Clear()
		For Local loc:TTest=Eachin locListe
			Liste.AddLast loc
		Next		
	End
End

Jesse

(Posted 2013) [#2]

skn3 posted it in the bug reports section:
http://www.monkeycoder.co.nz/Community/posts.php?topic=4793

AdamRedwoods

(Posted 2013) [#3]

it's hidden and i always forget too.

basically, when you search your list and find your node, you create a new node.

Class Node<T>

	Method New( succ:Node,pred:Node,data:T )

so if you have a node (after searching your list<MyClass>) labeled "myNode"
and want to InsertAfter

myNewNode:Node<MyClass> = New Node<MyClass>( myNode.NextNode(), myNode, data)

Insert Before would be:

myNewNode:Node<MyClass> = New Node<MyClass>( myNode, myNode.PrevNode(), data)

EDIT: mixed up the pred, succ nodes. Fixed.
also take note that if the node is first or last, next or prev node will be null. then just use the AddLast and AddFirst.

Midimaster

(Posted 2013) [#4]

oh!
...never heard about "nodes". I do not understand completely. But I see I have to re-think my perception of lists.

I thought (old school style) they are like this:

1.Fred
2.John
3.Rudi
4.Pete

But with your explanation it is more like this:

F-John-R
R-Pete-
 -Fred-J
J-Rudi-P

If I now want to add a element between John and Rudi, it is like this?

F-John-M
R-Pete-
 -Fred-J
M-Rudi-P
J-Mary-R

ok.. I opened list.monkey and found the part. List.AddLast() calls Node.New() . There the object, but also the links to the following and the previous node are saved into _succ and _prev.

But, if I understand right, the function also changes already the corresponding links in linked nodes there. So I do not have to take care about the two other nodes any more.

To have a perfect solution I would have to add a List.InsertAfter(OldObject, NewObject) function in the list.monkey. It has to find the node of my OldObject. Then call Node.New() with this node and with it's node link to create a new one.

... genius mechanism...

AdamRedwoods

(Posted 2013) [#5]

i think all forms of interpretation are ok, but i would explain lists like this

        successor-data-predecessor

           (null)-John-(pointer to Pete)
(pointer to John)-Pete-(pointer to Fred)
(pointer to Pete)-Fred-(pointer to Rudi)
(pointer to Fred)-Rudi-(null)

also note when using Nodes, the compiler will complain about two definitions of Node, so I usually do this:

Alias Node = list.Node

To have a perfect solution I would have to add a List.InsertAfter(OldObject, NewObject) function

even better, just extend List

Class ChunkList Extends List<Chunk>
  Method InsertAfter(old:Chunk, newchunk:Chunk)
End

this way you can add in a Compare() method if you need to use Sort() later.

MikeHart

(Posted 2013) [#6]

also note when using Nodes, the compiler will complain about two definitions of Node, so I usually do this:

I wonder why as I never had to do this. And I am using nodes in fE a lot.