August 14, 2018, 10:09:21 AM

Author Topic: loop through list  (Read 525 times)

Offline raven

  • Jr. Member
  • **
  • Posts: 5
loop through list
« on: May 17, 2018, 09:59:49 PM »
if I have a list of objects like:

Code: [Select]
Type Item
Field component:Item
EndType

how can I loop through them including the components?

i know to loop through a list you do:

Code: [Select]
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

Offline Henri

  • Full Member
  • ***
  • Posts: 133
Re: loop through list
« Reply #1 on: May 17, 2018, 11:59:22 PM »
Hi,

perhaps something to this effect:

Code: BlitzMax
  1.  
  2. Global counter:Int = 1
  3.  
  4. Type Item
  5.         Field component:Item
  6.         Field id:Int
  7.        
  8.         'Act as incrementing id everytime New is called
  9.         Method New()
  10.                 id = counter
  11.                 counter:+ 1
  12.         EndMethod
  13. EndType
  14.  
  15. Local ii:Item, list:TList = New TList
  16.  
  17. 'Add some items to list just for testing
  18. For Local a:Int = 1 Until 100
  19.         ii = New Item
  20.         list.addlast(ii)
  21.        
  22.         'Add component on pair number
  23.         If a Mod 2 Then
  24.                 ii.component = New Item
  25.        
  26.                 'Add sub component every fourth time
  27.                 If a Mod 4 Then ii.component.component = New Item
  28.         EndIf
  29. Next
  30.  
  31. 'Show all
  32. For Local i:Item = EachIn list
  33.        
  34.         Print "Item:  " + i.id
  35.        
  36.         ii = i.component
  37.         While ii
  38.                 Print "Component:" + ii.id
  39.                
  40.                 ii = ii.component
  41.         Wend
  42. Next
  43.  

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

Offline markcwm

  • Sr. Member
  • ****
  • Posts: 282
Re: loop through list
« Reply #2 on: May 18, 2018, 01:46:12 AM »
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.

Offline raven

  • Jr. Member
  • **
  • Posts: 5
Re: loop through list
« Reply #3 on: May 18, 2018, 12:25:24 PM »
Hi,

perhaps something to this effect:

Code: BlitzMax
  1.  
  2. Global counter:Int = 1
  3.  
  4. Type Item
  5.         Field component:Item
  6.         Field id:Int
  7.        
  8.         'Act as incrementing id everytime New is called
  9.         Method New()
  10.                 id = counter
  11.                 counter:+ 1
  12.         EndMethod
  13. EndType
  14.  
  15. Local ii:Item, list:TList = New TList
  16.  
  17. 'Add some items to list just for testing
  18. For Local a:Int = 1 Until 100
  19.         ii = New Item
  20.         list.addlast(ii)
  21.        
  22.         'Add component on pair number
  23.         If a Mod 2 Then
  24.                 ii.component = New Item
  25.        
  26.                 'Add sub component every fourth time
  27.                 If a Mod 4 Then ii.component.component = New Item
  28.         EndIf
  29. Next
  30.  
  31. 'Show all
  32. For Local i:Item = EachIn list
  33.        
  34.         Print "Item:  " + i.id
  35.        
  36.         ii = i.component
  37.         While ii
  38.                 Print "Component:" + ii.id
  39.                
  40.                 ii = ii.component
  41.         Wend
  42. Next
  43.  

-Henri

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

Offline Henri

  • Full Member
  • ***
  • Posts: 133
Re: loop through list
« Reply #4 on: May 18, 2018, 01:10:33 PM »
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

Offline raven

  • Jr. Member
  • **
  • Posts: 5
Re: loop through list
« Reply #5 on: May 18, 2018, 01:38:15 PM »
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?

Offline col

  • Sr. Member
  • ****
  • Posts: 364
Re: loop through list
« Reply #6 on: May 18, 2018, 01:51:01 PM »
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?
Code: [Select]

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?
Any bugs in my code are proof of its hand-coded nature.
https://github.com/davecamp

Offline Henri

  • Full Member
  • ***
  • Posts: 133
Re: loop through list
« Reply #7 on: May 18, 2018, 03:08:29 PM »
@Raven

This is exactly what my example does.

I'll try again with more commentary:
Code: BlitzMax
  1. 'Show all. Loop through every item.
  2. For Local i:Item = EachIn list
  3.    
  4.         'Insert item handling code here
  5.         Print "Item:  " + i.id
  6.        
  7.         'Store component reference to temporary handle
  8.         ii = i.component
  9.        
  10.         While ii        ' While there is valid component available. If not, then while-loop is never executed.
  11.                
  12.                 'Going through every component. Insert your component handling code here
  13.                 Print "Component:" + ii.id
  14.                
  15.                 'Store next component.
  16.                 'While part checks if the component is valid, or have we reach the end of all the components of the current parent item
  17.                 ii = ii.component
  18.         Wend
  19.        
  20.         'Go to next item
  21. Next
  22.  

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

Offline raven

  • Jr. Member
  • **
  • Posts: 5
Re: loop through list
« Reply #8 on: May 18, 2018, 03:33:06 PM »
thanks for the replies.

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

Offline Henri

  • Full Member
  • ***
  • Posts: 133
Re: loop through list
« Reply #9 on: May 18, 2018, 04:19:25 PM »
On my test code I get somewhere over 500 000 cycles before erroring.

Test:
Code: BlitzMax
  1. Global count:Int
  2. Global pos:Long
  3.  
  4. Const LIMIT:Int = 100000
  5.  
  6. test()
  7.  
  8. Function test()
  9.         PollSystem()
  10.         count:+ 1
  11.        
  12.         If count = limit Then
  13.                 count = 0; pos:+ 1
  14.                 Print pos
  15.         EndIf
  16.        
  17.         test()
  18. EndFunction
  19.  

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

Offline col

  • Sr. Member
  • ****
  • Posts: 364
Re: loop through list
« Reply #10 on: May 19, 2018, 07:46:25 AM »
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.
Any bugs in my code are proof of its hand-coded nature.
https://github.com/davecamp

Offline raven

  • Jr. Member
  • **
  • Posts: 5
Re: loop through list
« Reply #11 on: May 27, 2018, 10:21:44 PM »
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:

Code: [Select]
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?

Offline Derron

  • Hero Member
  • *****
  • Posts: 1163
Re: loop through list
« Reply #12 on: May 28, 2018, 06:25:24 AM »
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

Offline TomToad

  • Sr. Member
  • ****
  • Posts: 287
Re: loop through list
« Reply #13 on: May 28, 2018, 02:03:38 PM »
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.
Code: [Select]
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
  1. SuperStrict
  2. Type TItem
  3.         Field id:String
  4.         Field Children:TList = CreateList()
  5.        
  6.         'Constructor
  7.         Function Create:TItem(id:String)
  8.                 Local Item:TItem = New TItem
  9.                 Item.id = id
  10.                 Return Item
  11.         End Function
  12.        
  13.         'Adds a component to the child list
  14.         Method AddComponent(Component:TItem)
  15.                 Children.AddLast(Component)
  16.         End Method
  17.        
  18.         'Process this item
  19.         Method Process()
  20.                 Print id
  21.         End Method
  22.        
  23.         'recursively process each child after processing this item
  24.         Method ProcessAll()
  25.                 Process()
  26.                 For Local Item:TItem = EachIn Children
  27.                         If Item <> Self Then Item.ProcessAll()
  28.                 Next
  29.         End Method
  30.        
  31. End Type
  32.  
  33. Local List:TList = CreateList()
  34.  
  35. 'create all the items
  36. Local Item1:TItem = TItem.Create("Item1")
  37. Local Item2:TItem = TItem.Create("Item2")
  38. Local Component1:TItem = TItem.Create("  Component1")
  39. Local Component2:TItem = TITem.Create("  Component2")
  40. Local Component3:TItem = TItem.Create("  Component3")
  41. Local ComponentA:TItem = TItem.Create("    ComponentA")
  42.  
  43. 'create the heirarchy
  44. List.AddLast(Item1)
  45. List.AddLast(Item2)
  46. Item1.AddComponent(Component1)
  47. Item1.AddComponent(Component2)
  48. Item1.AddComponent(Component3)
  49. Component2.AddComponent(ComponentA)
  50.  
  51. Print "~nProcess using recursion"
  52. For Local Item:TItem = EachIn List
  53.         Item.ProcessAll()
  54. Next
  55.  
  56. Print "~nProcess without recursion"
  57. Local Stack:TList = CreateList() 'create a stack
  58.  
  59. 'function to push all children onto stack.  Children are pushed in
  60. '  reversed order so they will be removed in order
  61. Function PushChildren(Stack:TList,Children:TList)
  62.         If Not Children.IsEmpty()
  63.                 Local Link:TLink = Children.LastLink()
  64.                 While Link._value <> Link
  65.                         Stack.AddLast(Link._value)
  66.                         Link = Link._pred
  67.                 Wend
  68.         End If
  69. End Function
  70.  
  71. For Local Item:TItem = EachIn List
  72.         Print Item.id
  73.        
  74.         'push all children onto the stack in reverse order
  75.         PushChildren(Stack,Item.Children)
  76.        
  77.         'Process the stack
  78.         While Not Stack.IsEmpty()
  79.                 Local Child:TItem = Item(Stack.RemoveLast())
  80.                 PushChildren(Stack,Child.Children)
  81.                 Child.Process()
  82.         Wend
  83. Next   
  84.  

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

Offline Henri

  • Full Member
  • ***
  • Posts: 133
Re: loop through list
« Reply #14 on: May 28, 2018, 02:32:41 PM »
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