Hey there, iarwain. Have you considered making all of your lists doubly-linked? This would allow for something like a GetNextSibling and GetPrevSibling for traversing ChildLists.
Well, all the linked list are double linked ones (Previous/Next).
I believe you mean the trees instead (Child/Parent/Sibling)?
I haven't done so for two more or less valid reasons:
- the tree node structure is 16 bytes right now which is perfect for alignment/cache line friendliness
- most of the time we traverse a tree, it's either in a breadth-first or a depth-first fashion, can't think of one example where we'd do a different (reverse?) traversal.
Yes, I mean the trees. Currently, I am trying to implement a menu system in which each menu option is owned by a [MenuOptions] section. This section owns the objects that represent the menu options, which are objects. If someone goes down the menu, the next menu option is selected, FX are applied to it, and other parts of the code are changed. But if someone wants to select the previous menu option, I would have to loop through the menu to get to one option before that option, or make an array of pointers to the menu options.
Actually, the array idea sounds like it'll work just fine, and not really mess with my performance. I think I'll just do that.
Plus, I can see why you don't want to change the structure if you have it to a size that you want it at. Thanks for your time!
Yes, in that case you should probably just use your own class/structure (cMenuItem?) that you'd store on the orxObject as user data when it gets created and remove it when it gets deleted (orxObject_GetUserData()/orxObject_SetUserData()).
And inside cMenuItem you can use a orxLINKLIST_NODE for chaining your items.
That'd be one option, up to you to choose which one suits more your needs.
I have a related question. Would it be possible to let the user choose whether or not to make a given list cyclically-linked? Unless you're using a trailer node at the end of each list, I don't see that it would be a problem to allow it optionally. Of course, this is assuming that you don't have some paradigm-related problem with doing so.
Even if you cannot do this by using the orxLINKLIST API, you can easily create a cycling list manually by directly accessing the public fields in the orxLINKLIST_NODE structure and by linking the first and the last node to each other.
Comments
I believe you mean the trees instead (Child/Parent/Sibling)?
I haven't done so for two more or less valid reasons:
- the tree node structure is 16 bytes right now which is perfect for alignment/cache line friendliness
- most of the time we traverse a tree, it's either in a breadth-first or a depth-first fashion, can't think of one example where we'd do a different (reverse?) traversal.
Actually, the array idea sounds like it'll work just fine, and not really mess with my performance. I think I'll just do that.
Plus, I can see why you don't want to change the structure if you have it to a size that you want it at. Thanks for your time!
Yes, in that case you should probably just use your own class/structure (cMenuItem?) that you'd store on the orxObject as user data when it gets created and remove it when it gets deleted (orxObject_GetUserData()/orxObject_SetUserData()).
And inside cMenuItem you can use a orxLINKLIST_NODE for chaining your items.
That'd be one option, up to you to choose which one suits more your needs.
In good old C tradition, everything you see in header files you can use freely.