The full version of the List Library is well on it's way. You can chart the progress at Quest Stuff. (Not that anyone is dying to get their hands on it - Google Sites just had a cool feature I had to try out.)

One major change from the lite version is that all lists are now "indexed". (Not sure if that is the right term, but it's what I'm sticking to for now.) What this means is that you can leave off the processing of a list mid-stride and return to it at a later time. For instance, this is possible:

afterturn {
    set string <item; $GetNext(SomeList)$>
    if (#item# <> OBJECT_INVALID) then {
        'process here
    else {
        set string <item; $GetFirst(SomeList)$>
        'process here
    }
}

SomeList could be a list of NPC's who each get to take turns producing ambient behaviour. (You don't want them acting all at once, so you limit NPC actions to one per turn.) Or SomeList could be a list of yet other lists that you only want to process individually in order to avoid lag.

The method employed above (GetNext, GetFirst, etc.) is taken from Bioware's Neverwinter Nights SDK, Aurora. Anyone who has scripted in Aurora will recognize the OBJECT_INVALID keyword, which, in the case of the list library, is a special string that is returned when one attempts to move beyond the last or first item in a list. (You can step through a list backwards with GetLast and GetPrevious.)

If anyone cares to, I would appreciate feedback about what is being implemented at the moment. Currently there are 70 functions, procedures, and actions that can manipulate and/or query a list for information. I realize that the majority of folks on these forums don't hand script anything, so really I'm making an appeal to a small subset of you.

Some new features:

[list]random shuffling
removing of duplicates
sorting
swapping items[/list:u]

If anyone can think of anything that would be cool to implement that's not on the progress sheet, just let me know. I'm willing to collaborate as well, so if you want to go ahead and code a handy routine, feel free. (If you want to do this, take a look at the source for the lite version: there are standard debugging statements that "cushion" every routine. You can put those in yourself, or I can modify any ASL you write to include them.)

After it is completed I'd also like to keep the library open to those who would like to optimize it or make additions and/or suggestions. I guess we'll just have to see how useful any scripters out there deem the library to be. (Could be a wasted effort on my part, but I think it's fun in any case!) The documentation will take some time to write. I'm also going to include a small game to highlight some of the features. It won't be a "game" in the traditional sense: I'll probably implement a textual mp3 player, or something that intuitively uses lists. (Heck, I could probably create a real - albeit hackish - music player that let's you add and remove actual songs from your hard drive. )

What advantage does that have over just keeping track of the index? (And it looks like you can only have one iterator per list.)

Aurora probably does things that way because it uses a linked list architecture underneath.

I wasn't sure if calling the lists "indexed" was the right term or not. What I'm doing behind the scenes is just recording the current "position" of each list for recall and incremental stepping. Is that what you mean by "keeping track of the index"? If so, then yes - it is easier! I hid the manipulation of the index position because it is faster to just assign an item to a variable with $GetNext(ListObject)$ than it is to...

[list]* increment the index
* check if the position is valid
* assign the returned item at the new position[/list:u]

...each and every time a scripter wants the next item in a list.

Aurora probably does things that way because it uses a linked list architecture underneath.

Yeah, I guess linked lists make sense for that - I never really thought about it before. I haven't had occassion to use linked lists all that much (in C (have to build 'em yourself, don't you?), or C# - ArrayList?). Probably because I'm not exactly a professional programmer - there is so much to learn!

In any case, the lists in the list library dynamically resize like a linked list. (Yes, I realize it's all done with properties, but if the effect is the same, who cares?)

What sort of complexity guarantees does your system have?

Okay, now you made me go look up "complexity guarantees", which was a little hard to find.

I'm assuming what you mean by that term is, "what guarantees can I make against the algorithmic complexity of the library." So, for instance, how long would it take to retrieve any given item as the size of a list increases (does it behave in constant time, do the steps increase linearly, quadratically, etc.).

Simple answer: I haven't thought about that at all. Perhaps when the library comes out you could tell me - or I could email the incomplete source to you.

I do know that large iterations in Quest cause lag, no matter what you're doing. I expressly made it possible (which wasn't hard) to store lists within lists, so that one could process a long list in more manageable "chunks" if lag became an issue. A little lag ain't so bad, but anything more than half a second or so seems to bug me.

Man, you're really stretching my poor brain.

Overcat wrote:I wasn't sure if calling the lists "indexed" was the right term or not. What I'm doing behind the scenes is just recording the current "position" of each list for recall and incremental stepping. Is that what you mean by "keeping track of the index"? If so, then yes - it is easier! I hid the manipulation of the index position because it is faster to just assign an item to a variable with $GetNext(ListObject)$ than it is to...

[list]* increment the index
* check if the position is valid
* assign the returned item at the new position[/list:u]

...each and every time a scripter wants the next item in a list.

From my experience in C / C++, keeping track of the index would be a matter of:

for (i = 0; i < LIST.size; ++ i) {
  // Do stuff with LIST[i]
}

Or doing it with iterators (which is closer to your method) would be

for (iter = LIST.begin(); iter != LIST.end(); ++ iter) {
  // Do stuff with *iter
}

Both methods have the advantage that you can have multiple iterators running over one list at a time.

Both methods have the advantage that you can have multiple iterators running over one list at a time.

Yeah, the GetNext, GetPrevious, etc. functions only allow one iterator, since there is only one property (in my scheme) that keeps track of the current position of any given list on an object. I implemented them so one could incrementally step through a list between player "turns". For instance, the GetCurrent function will always return the item currently being pointed to by the index property of a given list. (You can still use these functions to iterate through a list in one go.)

You can have multiple iterators on a list with a for-loop:

for <i; 1; $ListLength(SomeObject; SomeList)$> {
    for <n; 1; $ListLength(SomeObject; SomeList)$> {
        set string <str; $GetByPosition(SomeObject; %i%; SomeList)$>
        set string <str2; $GetByPosition(SomeObject; %n%; SomeList)$>
        'do stuff with #str# and #str2#
    }
}

That is rather unwieldy, so...

do <SetActiveList(SomeObject; SomeList)>
for <i; 1; $ListLength(SomeObject)$> {
    for <n; 1; $ListLength(SomeObject)$> {
        set string <str; $GetByPosition(SomeObject; %i%)$>
        set string <str2; $GetByPosition(SomeObject; %n%)$>
        'do stuff with #str# and #str2#
    }
}

But for one iterator, it is better (in my opinion) to...

set string <str; $GetFirst(SomeObject)$>
repeat until (#str# = OBJECT_INVALID) {
    'do stuff with #str#
    set <str; $GetNext(SomeObject)$>
}

That, in contrast to how one would have to do it without interfacing with the functions of the list library (assuming my scheme for storing lists is at work)...

for <i; 1; $objectproperty(SomeObject; no#ListName#)$>
    set string <str; $objectproperty(SomeObject; #ListName#_%i%)$>
    'do stuff with #str#
}

As part of the aim of the library is ease of use, I think I would have a much easier time explaining to a newbie scripter how to work with lists using GetFirst and GetNext than with the jabberwocky immediately above. Then again, it may be that the only ones who ever attempt to use the list library are those who are already at a sufficient level of understanding to read that jabberwocky with ease. In any case, I find GetFirst and GetNext much more readable! (One can employ the same syntax to run backwards through the list, too, with GetLast and GetPrevious.)