Linked Lists?

#1 Linked lists are mostly moot in languages that have dynamically sizable arrays...

What exactly are you trying to implement?

Gary (-;

#2 Some people are old skool, and prefer

while(obj->next!=null){...}

Im not one of them :)

I don't know of any scripting languages that support linked lists, since pointers aren't standard fare in those types of languages (then again, I'm probably wrong, like I always am, and somebody will point out a language that does support pointers & linked lists :)

Torquescript supports arrays, I can't think of anything that that lists would solve yet arrays wouldn't

#3 Actually, pointers is arguably all that torquescript has for objects. But instead of calling them pointers, they're called IDs.

$something = new Object() {some stuff};

If you do echo($something);, you'll see that it's just a number... actually, the id of the new Object.

Perl has references [prefix a \ on things], which is arguably also the same as pointers...

Gary (-;

#4 The closest thing you'll find is probably a SimGroup or SimSet.

new SimSet(MySet) {};

%myObj = new SimObject() {};
MySet.add(%myObj);

%count = MySet.getCount();
for(%i = 0; %i < %count; %i++)
   MySet.getObject(%i).doSomething();

%myObj.delete(); // deletes the obj and removes from set automatically

#5 To go into actual detail, a scripting language (particularly TScript) provides sufficient overhead that the drawbacks of using resizable arrays are pretty negligable compared to an implementation of linked lists. Add to this the fact that the arrays in question are arrays of references/pointers, not of the actual entity objects themselves. Thus the copy operations for adding/removing from the list are, while not as trivial as a pointer swap, not terribly large.

That being said, I wasn't aware that TScript actually had resizable arrays as an object. I thought it could have arrays, but I didn't know it had operations like "insert" and "delete" that automatically do the shifting of elements necessary to make it work.

Personally, though, I prefer putting things like "a list of entities" and so forth in code rather than script. It lets code manage the list and provides accessors and so forth to find entities or iterate over them.

BTW, you don't need pointers to have linked lists. As long as you have the concept of a reference to an object that may or may not yet exist, you have everything you need to construct a list.

#6 See, I knew somebody would prove me wrong. I prefer arrays myself, but thats not to say I haven't written my own single and doublely linked list classes back in college :) Bug testing and tracing code always took more than one sheet of paper.

As far as the solution to james' problem, I'm not that familiar with the core innerworkings of T2D yet, though I am coming along.

#7 Thanks for all the information! I thought about using an array but I didn't see any insert or delete operations.. if the operations existed it would probably be fast enough.. but I wouldn't want to implement those in TorqueScript.. surely they would be too slow.

That is why I wanted a linked list.. insert/remove is O(1) whereas in an array it is O(n).. and I don't need to be able to access things by index. So a linked list seems more appropriate to me.

However I don't actually need a linked list. I just need a way to store all my objects, iterate through them, and quickly remove any object.

SimSet looks like it will do what I want... is there any documentation available to T2D owners? I can't find any.

Thanks everyone

#8 I created my own dynamic array in script, which does copy elements to shift them etc, and it performs fine. Of course, I'm not sticking that into a loop or anything, and the number of elements are pretty small generally, but I've noticed no particular problem because of it.

I did this to replace SimSets because they don't preserve the order of the elements, and I needed to.

TorqueScript is lacking in some very fundamental ways, basic datatypes being one of them. *shrugs* Just do what you can to work around it. The engine still kicks all kinds of ass. :)

#9 Yeah, it definitely depends on the number of elements that you are dealing with and how often you are inserting/removing. But the thought of doing it purely in script still makes me cringe for some reason ;-).. I guess I haven't been using TorqueScript long enough to have a feel for how fast/slow it actually is. We'll see once I start doing AI whether or not I have to do some stuff in C++.

I have been doing some basic stuff with SimSet and it seems to work perfectly for what I want. I don't need to preserve the order of elements so it is fine for me.

Thanks

#10 Also, the T2D Vectors are the mathematical types of vectors, not the container form that Java uses. They prove to be quite handy pretty often.

#11 As an FYI, a SimSet is designed to handle almost all of the requirements of a linked list within the scripting environment (with the possible exception of ordering, which can be enforced with some work).

I can't think of any implementation requirement that would absolutely require a linked list instead of a SimSet, and SimSet handles all of the low level work of the data class itself.

#12 Yes, that is what I am finding.. SimSet is actually easier than using a linked list would be. I just didn't know about it before Robert pointed it out. Thanks!

But can someone explain how it is implemented? Because I can't find it in the docs.. basically I would like to know how fast all the functions are. I'm working with a fairly small number of objects right now, so speed isn't currently an issue. But I would still like to know how well it scales.. just a general idea.. big-Oh would be fine.

Thanks for the help

#13 It's basically a very smart linked list, with some of the safe referencing, deletion notification, and other protective functionality implemented as well. It is implemented in /engine/console/simBase.cc/h.

#14 On a side note:
If you're at all familiar with C++ and STL, after enabling STL (search the resources), its fairly easy to create a script object wrapper for an STL template instance of linked lists, maps etc of type string (which can be object ids or char strings etc). I'm not going to get into a discussion about the merits of STL over Simsets/Simgroups. I'm simply pointing out that you could use STL to obtain your desired objective. It may be overkill to use STL for linked lists, but hash tables are ever so nice... I personally use custom STL wrapper classes and am very happy with the results.

#15

Quote:I personally use custom STL wrapper classes and am very happy with the results.

That would make a nice T2D-specific resource. :)

#16 I was thinking that something like that couldn't be too hard to do. I use STL in my other games. But so far SimSet is working fine.. with looping through about 50 objects every frame, adding and removing a couple times every second.

But I'll keep it in mind for future projects or if I need it. I'm trying to keep my current project pretty simple, and do everything in script if possible.