Updating between two linked lists?

[spacesurfer]

I have a question rather complicated to explain and since English isn't my native language I hope I'll be able to explain it in an understandable way. It's more programming question in general - not strictly related to PureBasic and I am not sure even if it could be done.

Here's the problem:

We have two linked lists and two update procedures, for an example:

Code: Select all

Structure first_struct
  x.b
  y.b
  something.w
EndStructure

Structure second_struct
  x.b
  y.b
  other.i
EndStructure

Global NewList first_list.first_struct()
Global NewList second_list.second_struct()

Procedure create_new_second_list_element(x.b, y.b, info.w)
  
  ;do something
  
EndProcedure

Procedure update_first_list()
  
  ForEach first_list()
    
    If condition
      create_new_second_list_element(first_list()\x, first_list()\y, info)
    EndIf
    
    ;do something (calculate new values)
    
    ;update x, y
    first_list()\x = new_x_value
    first_list()\y = new_y_value
    
    ;check if the element has to be destroyed
    If condition
      DeleteElement(first_list())
    EndIf
    
  Next first_list()
  
EndProcedure

Procedure update_second_list()
  
  ForEach second_list()
    
    ; *******************************************************************
    ; <problem start>
    ; *******************************************************************
    ; If x or y values of the element from the first_list() from which
    ; was created very this element of the second_list() have changed,
    ; update the x and y values of this element in the second_list()
    ; according To the new x And y values of the first_list()'s element
    ; from which it was created
    
    ; If the element from the first_list() from which was created very
    ; this element of the second_list() has been meanwhile destroyed,
    ; destroy ALL corresponding elements from the second_list() too
    ; *******************************************************************
    ; <problem end>
    ; *******************************************************************
    
    ; NOTE:
    ; Since during each call of the update_first_list() there is a
    ; possibility of creating new second_list() elements,
    ; it is possible that many elements from the second_list() are
    ; created upon the same element from the first_list()
    ; So, if for the example one of the elements from the first_list()
    ; 'created' 4 elements in the second_list(), if that element from
    ; the first_list() has been destroyed, we have to destoy all 4
    ; elements from the second_list() created upon the element from
    ; the first_list()
    ; Or to say in a more simple way:
    ; The elements from the second_list() must 'know' to which element
    ; from the first_list() they belong
    
    ;do something
    
  Next second_list()
  
EndProcedure

;main control loop
Repeat
  
  ;process window events etc.
  
  update_first_list()
  update_second_list()
  
ForEver

I know every element from the first_list() could have the unique ID so it could be sent as info when calling the create_new_second_list_element() but we would then inside the update_second_list(), for every element of the second_list(), have to loop thru the whole first_list() so I wonder if there is another solution :-/

Is maybe possible to pass the pointer to the element from the first_list() when creating the new element from the second_list()? That way, every element from the second_list() would have the pointer to his corresponding element upon which it was created.

However I am not sure what happens when some element from the first_list() is destroyed? Do all remaining elements keep their adresses unchanged (so we don't have to change the pointers) or can, after deleting an element from the linked list, some other elements' addresses change?

And even if above could be done - what to do after some element from the first_list() is destroyed? How to identify all corresponding elements from the second_list() that have to be destroyed too? :-/

I hope I've managed to explain the problem in more or less understandable way.

[Zach]

I think your idea of using some kind of ID might be the way to go.. But I also am very inexperienced in solving problems like this so take it with a grain of salt.

What if you used a Structured List for the second list?

The idea being, you make your normal entry in the second list, based on the first as usual

BUT the second list is using a structure so it has an extra field, which you could use to store the name (or value?) of the element from the first list it came from..

So let's say you have a list with some values.. We will assume the lists are already created and populated to save on typing...

This is pseudo code

Code: Select all

;// Your first list has  some items stored in it
;//  Apple, Orange, Butter, Milk

;// You add Apple and Milk to your second list

List2() = Apple
List2()\Parent=List1("Apple")
List2() = Milk
List2()\Parent=List1("Milk")


;// So now you have List1 with some items, and List2 which was some items from List1
;// But now you delete Apple from List1() 

;// Now in your update procedure  for List2()  you execute a check to see if   List2()\Parent   exists in List1()
;// If you see that  the item from List2()\Parent, no longer exists in List1() then you execute a procedure to remove that value.

Again... its pseudo code, just to show the logic of the example. But checking List1() shouldn't take a huge amount of time to check for 1 value, I would think?
You could also do it with Maps, which are very fast as well if you wanted.

I don't know if its possible, or efficient, doing it this way... But I thought I would try and offer a solution anyway.

[void]

Is maybe possible to pass the pointer to the element from the first_list() when creating the new element from the second_list()? That way, every element from the second_list() would have the pointer to his corresponding element upon which it was created.

You'll definitely want to do this; every 2nd list element should know what 1st list element it is attached to.

However I am not sure what happens when some element from the first_list() is destroyed? Do all remaining elements keep their adresses unchanged (so we don't have to change the pointers) or can, after deleting an element from the linked list, some other elements' addresses change?

The elements keep their addresses. Internally, the linked list keeps its own references for next/previous hidden from the data you interact with, and handles insertions/deletions silently for integrity within a single list. However..

And even if above could be done - what to do after some element from the first_list() is destroyed? How to identify all corresponding elements from the second_list() that have to be destroyed too? :-/

You have two choices. One, you can do a search in the second list for all dependant elements when an element from the first list is removed, or two, you can put a list in each list element in the 1st list containing entries for all 2nd list elements inheriting from 1st list elements.

Remember, you need to maintain the list on a 1st list element BOTH when adding AND removing elements in EITHER list.

Nested lists are kind of awkward, but they're probably the most correct and performant way of handling this problem; the extra bookkeeping is programmer-time thought that saves a good bit of execution time. Just document what you're doing very carefully so that if you have to look at the code again 6 months later, you don't have to stop and figure it out all over again.

[spacesurfer]

Again... its pseudo code, just to show the logic of the example. But checking List1() shouldn't take a huge amount of time to check for 1 value, I would think?
You could also do it with Maps, which are very fast as well if you wanted.

I don't know if its possible, or efficient, doing it this way... But I thought I would try and offer a solution anyway.

That would be assigning the unique ID to the elements of the first list. As I said, I was thinking about that but there has to be some more efficient algorithm. Let's imagine the first list contains only 50 elements and let's suppose each element could during its lifecycle generate 7-8 elements in the second linked list. That would be about 400 elements in the second list so we would have to start 50 loops thru the second list of 400 elements to update the data.

To delete the elements in the second list we'd do the opposite (a loop thru the first list for the each element from the second one). We could spare some time when deleting the elements from the second list - after identifiing the ID of the destroyed element from the first list, all corresponding elements could be deleted in just one pass thru the second list (we might use push/pop list position to continue the loop after deleting child elements).

In the case of 50 loops thru the second list, we'd always have to finish all 50*400 checks but in the case of 400 loops thru the first list we could (since IDs in the first list are unique), after finding the coresponding ID, stop the inner loop and update all remaining elements in the second list.

I think it isn't so easy to immediately clearly see the most optimal way, however, this approach 'sounds' very slow :-/

[Danilo]

Can you include the 2nd list in the 1st list? Deleting an element in the 1st list would
destroy all elements in the sub-list too.

Code: Select all

Structure second_struct
  x.b
  y.b
  other.i
EndStructure

Structure first_struct
  x.b
  y.b
  something.w
  
  List Second.second_struct()
EndStructure

Global NewList first_list.first_struct()

For i = 1 To 10
    AddElement( first_list() )
    For j = 1 To 10
        AddElement( first_list()\Second() )
        first_list()\Second()\x = i*j
    Next
Next



ForEach first_list()
    ForEach first_list()\Second()
        Debug first_list()\Second()\x
    Next
    Debug "----"
Next

[spacesurfer]

The elements keep their addresses. Internally, the linked list keeps its own references for next/previous hidden from the data you interact with, and handles insertions/deletions silently for integrity within a single list. However..

That's a good news.

You have two choices. One, you can do a search in the second list for all dependant elements when an element from the first list is removed, or two, you can put a list in each list element in the 1st list containing entries for all 2nd list elements inheriting from 1st list elements.

Remember, you need to maintain the list on a 1st list element BOTH when adding AND removing elements in EITHER list.

Yes, you are right - we have to put one more linked list of pointers inside the structure of the fist list elements to keep the track of the child elements. I thought we could put just the references to the parent entries into the second list so we could check if the parent element has changed when we are looping thru the second list but then, after deleting the parent element, the pointer would point to some random location so the information about the destroyed element from the first list would be lost.

Thank you very much for answering me!

[spacesurfer]

Can you include the 2nd list in the 1st list? Deleting an element in the 1st list would
destroy all elements in the sub-list too.

That would be great from that point of view. However, then we'd have lost the ability to loop thru the second list (since it wouldn't exist). It is important to have an easy and fast access to the elements of the second list and even to be able to update it with some elements not related to the first list.