loop through list

Started by raven, May 17, 2018, 21:59:49

Previous topic - Next topic

raven

if I have a list of objects like:

Type Item
Field component:Item
EndType


how can I loop through them including the components?

i know to loop through a list you do:

For i:Item = EachIn list
Next


but if I want to handle the items linked in each item before going onto the next item, how can I do that? the component items might also have a component so that's where i am having trouble

Henri

Hi,

perhaps something to this effect:

Code (blitzmax) Select


Global counter:Int = 1

Type Item
Field component:Item
Field id:Int

'Act as incrementing id everytime New is called
Method New()
id = counter
counter:+ 1
EndMethod
EndType

Local ii:Item, list:TList = New TList

'Add some items to list just for testing
For Local a:Int = 1 Until 100
ii = New Item
list.addlast(ii)

'Add component on pair number
If a Mod 2 Then
ii.component = New Item

'Add sub component every fourth time
If a Mod 4 Then ii.component.component = New Item
EndIf
Next

'Show all
For Local i:Item = EachIn list

Print "Item:  " + i.id

ii = i.component
While ii
Print "Component:" + ii.id

ii = ii.component
Wend
Next


-Henri
- Got 01100011 problems, but the bit ain't 00000001

markcwm

If a type contains another type and you don't know if that type exists you check with Null:

If i=Null Then i=New Item

If a type doesn't exist and you try to access it then Bmx will crash.

raven

Quote from: Henri on May 17, 2018, 23:59:22
Hi,

perhaps something to this effect:

Code (blitzmax) Select


Global counter:Int = 1

Type Item
Field component:Item
Field id:Int

'Act as incrementing id everytime New is called
Method New()
id = counter
counter:+ 1
EndMethod
EndType

Local ii:Item, list:TList = New TList

'Add some items to list just for testing
For Local a:Int = 1 Until 100
ii = New Item
list.addlast(ii)

'Add component on pair number
If a Mod 2 Then
ii.component = New Item

'Add sub component every fourth time
If a Mod 4 Then ii.component.component = New Item
EndIf
Next

'Show all
For Local i:Item = EachIn list

Print "Item:  " + i.id

ii = i.component
While ii
Print "Component:" + ii.id

ii = ii.component
Wend
Next


-Henri

thanks. Unless I am mistaken, it seems to process the components more than it should?

Henri

Yes.

Only thing relevant is the 'Show all' loop. It will go through every item in the list, and also process every component in the field recursively (as long as field has value, or reference as is the more correct term ). ID part was just to prove that it works, and the rest was to setup a test environment.

-Henri
- Got 01100011 problems, but the bit ain't 00000001

raven

i understand what it is doing now.

sorry i don't think i explained myself properly. what i want is for it to only handle each item once. so it would go through them like:

first item has no component so handle it and move on
second item has a component so handle it and then the component
the component has a component itself so handle that
the last component hasn't have one of its own so move on
third item has a component so handle it and then the component...

is a list the best data method to handle this or is there a better way?

col

#6
Quote
first item has no component so handle it and move on
second item has a component so handle it and then the component
the component has a component itself so handle that
the last component hasn't have one of its own so move on
third item has a component so handle it and then the component...

Sounds like a job for 'recursion'. You have method/function that will look at its 'Item' and do something with it... including calling the same method/function of that 'Item' to repeat the process.

Setting up the Item along the lines of this may do the trick?


Type Item
Field component:Item
Field id:Int

'Act as incrementing id everytime New is called
Method New()
        id = counter
      counter:+ 1
EndMethod

Method DoSomething()
[... some code thats does something with this item ...]
If component
component.DoSomething()
EndIf
EndMethod
EndType


EDIT:- There are many ways to set up the 'recursion' code, but it sounds like that's what you're looking for?
https://github.com/davecamp

"When you observe the world through social media, you lose your faith in it."

Henri

#7
@Raven

This is exactly what my example does.

I'll try again with more commentary:
Code (blitzmax) Select

'Show all. Loop through every item.
For Local i:Item = EachIn list
   
'Insert item handling code here
Print "Item:  " + i.id

'Store component reference to temporary handle
ii = i.component

While ii ' While there is valid component available. If not, then while-loop is never executed.

'Going through every component. Insert your component handling code here
Print "Component:" + ii.id

'Store next component.
'While part checks if the component is valid, or have we reach the end of all the components of the current parent item
ii = ii.component
Wend

'Go to next item
Next


This is just one way of doing this. As col mentioned, there is 'function calling itself' - type recursion as well, that I use myself sometimes. Just have to be careful not to end in an endless loop. There are some limitations as to how many function calls can be made before running out of stack memory (or something like that :-)), but never have come across this barrier.

You could also store components inside a TList inside item. This might make better code readability.

-Henri 
- Got 01100011 problems, but the bit ain't 00000001

raven

thanks for the replies.

i got it working how i want by doing what col suggested. is there a risk of overflow doing this?

Henri

On my test code I get somewhere over 500 000 cycles before erroring.

Test:
Code (blitzmax) Select

Global count:Int
Global pos:Long

Const LIMIT:Int = 100000

test()

Function test()
PollSystem()
count:+ 1

If count = limit Then
count = 0; pos:+ 1
Print pos
EndIf

test()
EndFunction


-Henri
- Got 01100011 problems, but the bit ain't 00000001

col

#10
The total depth of recursion using functions is defined by the stack space allocated during program startup along with the number of local variables and parameters in the recursive function - all very low level stuff that you don't need to worry about really.

As Henri shows...
Running out of stack space is something that you don't really need to think of and if you do run out then there's probably something wrong with your code, or if you do really need deep stacks ( more than the default 4Mb that BMax uses ) then there are alternative methods as Henri also shows. There are also ways to increase the stack allocation amount if you REALLY wanted to.
https://github.com/davecamp

"When you observe the world through social media, you lose your faith in it."

raven

hi again,

i think the recursive way is giving me overflow problems.

i would like to try the way Henri suggested, which works but i want it to handle each item/component only once per loop...at present it will handle items with components more than once (once if it is a component itself and then again if it has components).

basically i would like it to work like this:

Item
Component1
Component2
ComponentA
Component3
Item

item > component1 > component2 > Component A > Component 3 > Item


what changes do i need to make to the code to make it do this?

Derron

Insert all components into a component manager (class + list/map). The manager takes care of each component only existing once (in a map this is easily done via unique keys - like a GUID or ID).

When updating components you can just iterate over the list/map to handle everything.

If you need to respect a certain order - you can use the auto-sort a TMap does: use keys describing the parentship "parentID_childID". Do not forget that it sorts "alphabetically" (so use leading zeros if using numeric IDs).


Without that approach you would need to have a "alreadyUpdated"-list which you constantly clear before updating the first item and filling it with each updated item - and checking it on each update if it already existed.
Or - you have a global "currentTick" - which increases on each tick. Then each component has a "lastUpdatedAtTick"-field. When updating you increase "currentTick" and when updating the individual components you skip update if "lastUpdatedAtTick = currentTick" - else do the update stuff and set "lastUpdatedAtTick = currentTick".


bye
Ron

TomToad

#13
If you are having overflow problems with recursion, you most likely have created an infinite loop.  The only way that it could otherwise overflow is if you have the components nested extremely deep.  I mean, hundreds of thousands of times.

You need to watch out for object methods calling itself on the same object.  If a calls a, b, c then you would have an infinite loop, as a would call a which would again call a until the stack overflows.  If there is a chance that one of the components points to itself, then you need to check for that condition.
If component and component <> self
    component.DoSomething()
EndIf


If, for some reason, you are nesting components that deep, then you might be better off creating your own stack which can grow to your computer's memory size.  Below is some example code with two ways to iterate through the items.  First example iterates using recursion, and the second with a stack.  The example uses a list for components so that each item can have several items, such as your example shows item1 with 3 components, component2 with one component and item2 with 0 components.
Code (blitzmax) Select
SuperStrict
Type TItem
Field id:String
Field Children:TList = CreateList()

'Constructor
Function Create:TItem(id:String)
Local Item:TItem = New TItem
Item.id = id
Return Item
End Function

'Adds a component to the child list
Method AddComponent(Component:TItem)
Children.AddLast(Component)
End Method

'Process this item
Method Process()
Print id
End Method

'recursively process each child after processing this item
Method ProcessAll()
Process()
For Local Item:TItem = EachIn Children
If Item <> Self Then Item.ProcessAll()
Next
End Method

End Type

Local List:TList = CreateList()

'create all the items
Local Item1:TItem = TItem.Create("Item1")
Local Item2:TItem = TItem.Create("Item2")
Local Component1:TItem = TItem.Create("  Component1")
Local Component2:TItem = TITem.Create("  Component2")
Local Component3:TItem = TItem.Create("  Component3")
Local ComponentA:TItem = TItem.Create("    ComponentA")

'create the heirarchy
List.AddLast(Item1)
List.AddLast(Item2)
Item1.AddComponent(Component1)
Item1.AddComponent(Component2)
Item1.AddComponent(Component3)
Component2.AddComponent(ComponentA)

Print "~nProcess using recursion"
For Local Item:TItem = EachIn List
Item.ProcessAll()
Next

Print "~nProcess without recursion"
Local Stack:TList = CreateList() 'create a stack

'function to push all children onto stack.  Children are pushed in
'  reversed order so they will be removed in order
Function PushChildren(Stack:TList,Children:TList)
If Not Children.IsEmpty()
Local Link:TLink = Children.LastLink()
While Link._value <> Link
Stack.AddLast(Link._value)
Link = Link._pred
Wend
End If
End Function

For Local Item:TItem = EachIn List
Print Item.id

'push all children onto the stack in reverse order
PushChildren(Stack,Item.Children)

'Process the stack
While Not Stack.IsEmpty()
Local Child:TItem = Item(Stack.RemoveLast())
PushChildren(Stack,Child.Children)
Child.Process()
Wend
Next


Edit: made small change in code above to make it a bit clearer.
------------------------------------------------
8 rabbits equals 1 rabbyte.

Henri

TomToad,

you are a mind reader. I was just about to post the same :-)


@raven

from you first post I figured that relationship is 1 to 1 (every parent can have only 1 children, meaning every item can have only 1 component, and every component can have only 1 component), but what you are describing in your last post seems more like 1 to n relationship(every parent can have n number of children). If this is true then what Ron suggested and Tom posted can be an elegant solution.

-Henri
- Got 01100011 problems, but the bit ain't 00000001