Question on Lists
BlitzMax Forums/BlitzMax Beginners Area/Question on Lists
| ||
My question is, can a list be iterated/looped through backwards?
For Local foo:BaType = EachIn fooList
InterestingFunction(foo)
Next
The only solution I can think of is to reverse the list, iterate through it, and then reverse it again. Which doesn't seem very efficient. Or go back through, and reverse all my logic to allow for only iterating through a list forwards. Any help/tips appreciated! |
| ||
| You can use TLinks to start at the end and work back to the beginning. [edit] Quick and dirty example: Strict Local list:TList = New TList For Local n:Int = 1 To 10 list.addlast(String(n)) Next Local link:TLink link = list.lastlink() Repeat Print String(link._value) link = link.prevlink() Until link = Null Last edited 2011 |
| ||
| quick and dirty: reverse the list. very efficient: do what GFK says wasteful but possibly easy to read later: treat the list like an array by accessing the elements by their location with ValueAtIndex(). going one wasteful step further, convert the list to an array and then access locations... long story short, there's no built in way, GFK's post would be the most efficient, but the "native" approach (i.e. not digging into the links themselves) would probably be to reverse the list and go through that. I wouldn't expect that to be too prohibitively slow, though it will obviously depend on the size of your list and how critical speed really is for you... working with copies of lists can be handy by the by: e.g. if you need to remove things from a list as you go through it. loop through a copy of the list and when you find something that needs removing, pop it out of the master list. Since you're iterating a different list you can make changes to the original... this can also be used sometimes in multithreaded applications to not have to lock a list for the entire time spent looping through it, so long as you keep in mind that the copy is only a snap shot of the list from when the iteration started... I seem to have rambled, hope GFKs answer was the one you were looking for :0) |
| ||
| Thanks for the explanation ima747, I do appreciate it. I will probably use GfK's approach for what I'm doing. So thanks for that clear example GfK! I'm starting off with quite a basic retro style game from the Spectrum, so speed isn't a great issue, and I currently have 7 lists each with 30 links, so I probably could do any of these and not notice a difference. I have done some Flash and am used to using their slow but flexible arrays (which are nothing like normal/real arrays really). I haven't really seen much use of linked lists in AS3. I've heard people doing C++ talk about them. I thought I would get some practice in by using them on my simple project. Cheers again. |
| ||
| You should use a While loop rather than a Repeat loop?? What happens if the list is empty? (I don't know, does the link come out Null) Also use the method Value() rather than accessing the field _value directly. Nicer that way. You can also use list.Reverse() to reverse that list and list2 = list.Reversed() to make a second list of the same objects but reversed. They are slow operations. But if the list won't be modified anymore and you need to go backwards often, you could use them. Last edited 2011 Last edited 2011 |
| ||
| I'm not sure a 2nd copy of the list would be that helpful, because I'm changing the order of the links every update: removing the back one and putting it on the front. If I wasn't planning on changing the order of the contained objects so much I would probably just use an array. So wouldn't the 2nd list be in a different order than a reversed order of the first after I've changed some links? Last edited 2011 |
| ||
| So wouldn't the 2nd list be in a different order than a reversed order of the first after I've changed some links? Yes, it would. Its daft to maintain two separate lists when you can do the job [much easier] with one. You should use a While loop rather than a Repeat loop?? What happens if the list is empty? Probably, unless you know for sure the list isn't going to be empty at that point. Otherwise you'll get an attempt to reference null object error with my code as is.Last edited 2011 |
| ||
| One possible longer term solution would be to extend TList and TListEnumerator You could create a property on the list that determines the iteration order and then your new TListEnumerator would check this and act accordingly. Only useful if you're likely to do this a lot. |
| ||
| To be honest, if I knew more about lists before I began and knew you could only iterate through them forwards, then I would have done my logic with that in mind. At this point I think I'll work around that rather than reversing the logic (maybe I'll refactor it later). My lists always have something in them currently, but I think I'll need to animate them being emptied, so I'll keep the null exception in mind. Thanks for the heads up! |
| ||
| http://www.blitzmax.com/Community/posts.php?topic=82916#935611 |
| ||
| removing the back one and putting it on the front. Why not remove the front one and put it on back? |
| ||
| Because that's the reverse of what I need, and would cause the game element to go backwards. Also, I need to start with the back of the List so that it's drawn behind what's in front. I could reverse both of these things, but then the data and code is harder to understand. |
| ||
| Is it a drawing list? Make a compare function to sort them by y coordinate and descending sort the list each frame. I do it in my big game and there is no performance problem with hundreds of units. |
| ||
| http://www.blitzmax.com/codearcs/codearcs.php?code=1807 it allows local list:TListF = new TListF for blah:yourtype = eachin list.From(start:TLink,howMany:int=-1) or for blah:yourtype = eachin list.ReverseFrom(start:TLink,howMany:int=-1) or for blah:TLink = eachin list.LinksFrom(start:TLink,howMany:int=-1) if howMany is -1 then it will continue to the end or the begining as in the case of ReverseFrom. |
   |