MODULE: Stack v2.0 - Vectorized generic stacks - Updated 25 January 2015

Started by monkey0506, Sat 21/03/2009 01:10:47

Previous topic - Next topic

monkey0506

Now presenting the Stack module, which introduces vectorized, generic stacks for all your data storage needs!

stack: Works very similarly to the way an array works. Stores a set of data within a single variable.

vectorized: Means that the size of the stacks does not need to be predefined anywhere. They will grow/shrink as needed. Great for memory management and dynamic scripting.

generic: Means that the stacks do not conform to any one specific data type. You can push any/all of the following types onto a stack:
  • int
  • float
  • String
  • Character
  • InventoryItem
  • GUI
  • GUIControl
The included documentation includes a full function list and some example scripts. What are you waiting for? Download it now, fool!

Requires AGS 3.4.0.3 (Alpha) or later

ALL VERSIONS of this module are now available on Github.

Upon request, other data types (such as Hotspot, Object, etc.) could be made available. The requested data must be able to be interpreted as one of the basic data types (int, float, or String) however or the request will be rejected (i.e., File, Overlay, etc. would be out). Anything requiring a persisting pointer would also be rejected (DynamicSprite, Overlay, etc.).

25 January 2015:

The Stack module v2.0 is out! Get it while you can!

21 August 2009:

Uploaded v1.3 which is more bug fixing. Specifically String.Format has a limit on the length of the returned String, so where applicable I've replaced it with instances of String.Append (which has no limit). Further I modified the way that stack objects get pushed in to make it more secure. Previously if you pushed the same stack copy onto a stack multiple times it could potentially corrupt the internal data structure. This version completely resolves that possibility.

29 March 2009:

Uploaded v1.2a which is just a quick bug fix. Stack::GetItemsArray would request a zero-sized array which AGS doesn't like for some reason so I just put a quick check to prevent that. I also retro-conned the information below which suggested it was written today. It wasn't. :=

28 March 2009:

Uploaded v1.2 of the module which includes:

- The new functions Stack.GetItemsArray, File.WriteStack, File.ReadStackBack, and Stack.LoadFromFile.
- Improved formatting of Stack::Copy to further prevent fatal error-inducing collisions.
- Bug fix for Stack.Push where if you were specifying an index the ItemCount was still getting increased.
- Adds the data type eStackDataInvalid to denote when the data stored is not valid StackData.

Trent R

Monkey, you're a bloody genius. Just the other day I was thinking how nice it would be to have a String queue, and now I have it. Started skimming through the manual and found that it supported FIFO. Awesome work.


~Trent
To give back to the AGS community, I can get you free, full versions of commercial software. Recently, Paint Shop Pro X, and eXPert PDF Pro 6. Please PM me for details.


Current Project: The Wanderer
On Hold: Hero of the Rune

monkey0506

#2
Of course it supports FIFO, what sort of madman do you take me for? := It also supports FILO and Random, and also you can specify an exact index as well. All Stacks default to FILO.

Glad to hear it's working well for you Trent.

This started off as just a way of killing time at work. I opened up a Wordpad and whenever I had downtime I just started typing. Being the complete nerd that I am, I was very strict to conforming to valid code although I had no way of testing it, and what's more, no way of saving the document (as per my employer's confidentiality policies regarding our customer's information). Eventually I started realizing that this was actually a viable idea for a module and brought it (the idea) home with me. Hours upon hours of debugging later, and here we are! 8)

Dualnames

Worked on Strangeland, Primordia, Hob's Barrow, The Cat Lady, Mage's Initiation, Until I Have You, Downfall, Hunie Pop, and every game in the Wadjet Eye Games catalogue (porting)

monkey0506

#4
Glad to hear you like it!

Edit: Uploaded v1.2 of the module. In complete defiance of the scientific method, I was changing several things at once which was causing the problems. Starting back at v1.0 and taking one thing at a time allowed me to successfully debug the code. Funny the way that works. :P

Dualnames

It's really weird to add that I just passed a subject on my university dealing with stacks.. on microprocessors..well, good job there again.
Worked on Strangeland, Primordia, Hob's Barrow, The Cat Lady, Mage's Initiation, Until I Have You, Downfall, Hunie Pop, and every game in the Wadjet Eye Games catalogue (porting)

Crimson Wizard

I tried to use it in the AGS 3.2 RC project and it gave me a compiler error:

Stack.asc(50): Error (line 50): undefined symbol 'inventory'

BTW, do I understand correctly that it allows to push different types in one stack? Because I would like to use it to store custom structs and I'll have to push all the struct data in there, which consists of different types of variables.


EDIT: Yearg, heh, funny. It looks like I have to create at least 1 inventory item and 1 gui item (and maybe somethng else) for those inventory/gui arrays to work in scripts.
Looks rather like AGS bug.

monkey0506

Well I've actually brought that up to Chris before, but I don't specifically recall whether he said he considered it a bug or not. Basically, as you said, the inventory and gui arrays don't exist at all unless there is at least 1 member of their respective types available. The same is also true of the dialog array. I think the rest are safe...you must have at least one character and the hotspot, region, and object arrays are all statically sized.

To answer your question, yes, a single stack can contain data of multiple types. As I revealed (in the spoiler text) above, the StackData type is really just a String, but I'm also storing additional information about the data and such so it's not intended for use as a raw string value.

If you take a look at the Stack Extension Guide there's information on how you can create functions to interoperate directly with the built-in functions. To briefly touch on how to do this, I'll copy the example from said guide here:

Code: ags
// Stack.ash
enum StackDataType {
  // all of our other types
  eStackDataCharacterStat = 'x' // we must add a new key to our enum to extend it to a new type
};

// CharacterStats.ash (just an example)
struct CharacterStats { // an example struct
  int HP;
  int MP;
  int XP;
  import StackData ToStackData(); // our custom conversion function
  import bool LoadFromStackData(StackData data); // custom loading function
};

// CharacterStats.asc
import StackDataFormat; // grab this from Stack.asc (it is exported, but not globally imported)
// we need to use this for our data conversion

StackData CharacterStats::ToStackData() {
  StackData type = StackData.Format(StackDataFormat, eStackDataCharacterStat);
  return StackData.Format("%s%d,%d,%d", type, this.HP, this.MP, this.XP);
}

bool CharacterStats::LoadFromStackData(StackData data) {
  if ((data == null) || (data.GetType() != eStackDataCharacterStat)) return false;
  data = data.Substring(StackDataFormat.Length - 1, data.Length);
  String buffer = data.Substring(0, data.IndexOf(","));
  this.HP = buffer.AsInt;
  data = data.Substring(buffer.Length + 1, data.Length);
  buffer = data.Substring(0, data.IndexOf(","));
  this.MP = buffer.AsInt;
  data = data.Substring(buffer.Length + 1, data.Length);
  this.XP = data.AsInt;
  return true;
}

// example usage
CharacterStats csEgo;
csEgo.HP = 100;
csEgo.MP = 15;
csEgo.XP = 0;

// serialize the data into a stack
Stack s;
s.Push(csEgo.ToStackData());

// unload the data back from a stack
csEgo.LoadFromStackData(s.Pop());


Another way of doing it would be to simply push/pop each individual property, but as you can see scripting up a couple of quick conversion functions makes it much easier to push/pop custom structs. :=

Hope this helps. Be sure to let me know if you have any further questions or comments.

Crimson Wizard

Quote from: monkey_05_06 on Fri 18/12/2009 04:36:20
Another way of doing it would be to simply push/pop each individual property, but as you can see scripting up a couple of quick conversion functions makes it much easier to push/pop custom structs. :=
Yes, actually this was really useful tip!

Couple of notes though

Quote from: monkey_05_06 on Fri 18/12/2009 04:36:20
Code: ags
// Stack.ash
enum StackDataType {
  // all of our other types
  eStackDataCharacterStat = 'x' // we must add a new key to our enum to extend it to a new type
};


I guess it isn't actually important to edit Stack.ash, you can just put this new definition in your own script either in a new enum or as #define


Quote from: monkey_05_06 on Fri 18/12/2009 04:36:20
Code: ags

// CharacterStats.asc
import StackDataFormat; // grab this from Stack.asc (it is exported, but not globally imported)
// we need to use this for our data conversion

It should be import String StackDataFormat, otherwise error is given.

monkey0506

You're right that it's not strictly necessary for the enumerated value to be contained in Stack.ash, but I strongly recommend that you at least look to see what values are there. The module expects each data type to have its own unique identifier which is interpreted as a char. If two data types have the same identifier defined there is no way to distinguish one from the other which could result in invalid conversions, potentially a fatal operation when working with custom struct types.

And your right, I forgot to include the type in that import statement. Sorry about that.

One further note, the format of the StackData you work with is actually very lenient. The only requirement is that you do something such as:

Code: ags
  StackData type = StackData.Format(StackDataFormat, UNIQUE_TYPE_IDENTIFIER_CHAR_VALUE);
  return StackData.Format("%sDATA", type);


Where UNIQUE_TYPE_IDENTIFIER_CHAR_VALUE of course would generally be the enumerated value assigned to the data type you are working with. The DATA portion can be (string) formatted however you want. The only (string) values reserved by the module are:
"**STACKDATA**"
"**STACKDATA:"
"**STACKDATA STACK:"
"**STACKDATA NULL STRING**"
So as long as you don't have anything like that, feel free to store the data however you'd like. If you need to store a non-basic type, just check out the module code to see how I processed the conversion. I've actually been working on a method of serializing the more complex types (such as DynamicSprite and Overlay) but for now there's no way of storing anything that requires a persistent pointer like that. ;)

In any case, thanks for the feedback. It's nice to know somebody finds this stuff useful. :)

Crimson Wizard

Monkey, I was actually trying to understand internal module algorythms, and found them way too complex. I can be wrong, ofcourse, or missing something; but I usually prefer most simple way to do things (which are not always perfectly safe, perhaps), and your code there makes me shudder :). I have already tested this Stack in my "Shooting Gallery" tech demo, and so far it never slowed it down, even though game required reading/writing Stack elements every single tick. So, it's not that module works slow. It's just that I don't understand why it should be so complex.

My main doubt is related to the method of spawning a dynamic array and populating it with elements from Data String every time Stack needs to read or write an element. Couldn't you just find a corresponding substring from the Data String directly and use it?
I tried to write my own "vector" module with "lighter" implementation (as mentioned above), and it seem to work nicely... what do I miss? if anything?

PS. BTW, I wrote 2 "classes" for user-friendly reading and writing of custom structs from/into String. I wonder, if you can find it a possibly useful contribution to your module?

Monsieur OUXX

Quote from: Crimson Wizard on Sun 20/06/2010 08:49:10
I tried to write my own "vector" module with "lighter" implementation (as mentioned above), and it seem to work nicely... what do I miss? if anything?

PS. BTW, I wrote 2 "classes" for user-friendly reading and writing of custom structs from/into String. I wonder, if you can find it a possibly useful contribution to your module?

Post what you have! :-)

PS: don't expect answers from Monkey, he just DOESN'T HAVE the Internet.  :)
 

monkey0506

Hey CW, just saw your post here. It's true that the Stack module isn't highly optimized. The reasoning behind popping the entire array every time was actually a simple matter of convenience for me. Seeing as items can be added/removed dynamically from any index, storing static indices in the items wouldn't work. So the alternative would be to use an implementation of my IndexOfNth function (see StringPlus module). That would definitely create less overhead.

As I said, it was never optimized though. So yes, it could be made better, but my primary point of focus was functionality vs. speed and doing it the way I did was easier at the time. ;D

Edit: In my work with the List module I've actually managed to get Push/Pop working pretty nicely with my StringPlus module's IndexOfNth function (local copy provided if the module is not included). I'm doing some more work with that first, but I plan to release an updated version of this module as well. Also, there was already some new functionality that I was planning on incorporating but for some reason never got around to releasing.

monkey0506

As part of my on-going effort to definitively prove that there is nothing that I won't code when it comes to AGS, I made a new version of this module! ;-D And then, I decided it was crap, so I rewrote it again to be 1000% better than the aforementioned version which is now lost forever to the sands of time!

The biggest news is that this version of the module is FAST* because I can use dynamic arrays in structs now. The current limitations on managed structs led me to some suboptimal code when working with Strings, but I can pretty consistently push one million ints (the current max size for a dynamic array btw) into a Stack in a single for loop in only about 30 seconds! By way of comparison, with v1.3 I tried pushing a measly ten thousand ints into a Stack and the program froze for more than half an hour before I force-closed it with Task Manager. I can push ten thousand ints with this version in under a second.

To really optimize the speed, I made it possible to set the capacity of a Stack (setting the size of the underlying dynamic array) and avoid additional copying. Considering how much unnecessary copying was taking place in v1.3 of this module, anyone who actually used the older module should be quite happy with the improvements I've made.

Anyway, download link.

*To be fair, it's not native code "fast", but I don't think many people are going to be trying to push hundreds of thousands of items at once in a single frame of their game...

Dualnames

So, wait, i wanna ask something, would processing the stack be faster than currently processing a huge array?
Worked on Strangeland, Primordia, Hob's Barrow, The Cat Lady, Mage's Initiation, Until I Have You, Downfall, Hunie Pop, and every game in the Wadjet Eye Games catalogue (porting)

Crimson Wizard

Quote from: Dualnames on Mon 26/01/2015 08:38:53
So, wait, i wanna ask something, would processing the stack be faster than currently processing a huge array?
Of course not.

monkey0506

It wouldn't be faster than processing an array because all that the module is doing is processing arrays. :P

However, if you want a type-generic container class that automatically grows as needed, then this still fits that description (which is what it is designed for).

Dualnames

Damn, I thought you somehow broke a thing and made a dream come true. Oh well.
Worked on Strangeland, Primordia, Hob's Barrow, The Cat Lady, Mage's Initiation, Until I Have You, Downfall, Hunie Pop, and every game in the Wadjet Eye Games catalogue (porting)

ollj

After coding ags script for 6 months i finally understand how this module does its things (since managed structs and attributes in ags are a bit tricky), and its a pretty good example for advanced ags scripting.

But why did ypu make each StackData instance store a float, even if it doesnt store any significant float, that seems so inefficient for the sake of speed and flexibility.

floats are just too different from the other datatypes, that can be more easily enumerated with an int, used as pointer.

You might aswell make a float buffer array to point at, just like you made a string buffer array.

the .AsString property could also return Character.Name; Object.Name; String.Format("&d",i); String.Format("&f",f);

monkey0506

Pooling floats seems very much the worse option in this case. Attempting to keep a unique pool would require using some arbitrary epsilon and a lot of floating-point comparisons. Not keeping a unique pool would require adding an item to the pool every time a float is converted into StackData -- and note that AGS lacks destructors! The pool would never be able to release an item without an explicit function call placed by the user. Memory conservation would not even be guaranteed by pooling the floats, as if the total number of floats converted into StackData exceeded the number of StackData objects currently in existence (despite the lack of destructors, the objects are still destroyed if they go out of scope with no references to them), then there would effectively be a memory leak (memory reserved that is never again referenced by the program, which is never freed until the program terminates). No, I don't think that this is a better solution. Perhaps I could mangle floats and store them in some combination of StackData.Type, StackData._idata, and StackData._scacheID. The question, then, I think, would be whether it's worth conserving 4 bytes of memory (per StackData instance) to have to reconstruct floating-point values... something like:

Code: ags
return (IntToFloat(this._idata) + (IntToFloat(this._scacheID) / 1000000));


Floating-point division every time the value is retrieved? Ugh!

I still just don't think it would be worth reclaiming 4 bytes of memory per StackData object (1 KB per 256 StackData objects). You would have to have well over 200K StackData objects at any given time for that to amount to a single MB of "lost" memory. You could have a million StackData objects and have "lost" less than 4 MB of available RAM. This is hugely insignificant.


As for the suggestion to use the AsString property as a sort of "ToString" conversion method, I actually like the idea. I could easily see reimplementing the "StrictTypes" setting to allow that behavior to be toggled.

Thank you for your feedback. While I don't agree on the float issue, it is appreciated! :=

SMF spam blocked by CleanTalk