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

[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

[monkey0506]

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]

You're BAD!!In a good way.

[monkey0506]

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.

[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.

[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]

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

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

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]

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.

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! 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?

[Crimson Wizard]

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.

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.

[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!

[Monsieur OUXX]

I'd like to devise a simple way to make this module as easy as possible to adapt to any custom struct.
(Note 1: by "any custom struct" I'm not talking about the ones you black-flagged, i.e. the ones that have a temporary life, like File* and such)
(Note 2: I'm not talking about the universal stack "Stack", which aims at storing all types at once, but more something like StringCache_t, which aims at storing one specific type at a time. Only then, why not, include that manually in "Stack" if necessary, to make it even more universal)

For example:
- In the module, I'd put a #define CUSTOMTYPE AnyCustomType
- Everywhere in the module, you (Monkey) only always use CUSTOMTYPE as argument to functions, or return value, etc.
- Then the end-user can import this script as many times as he wants (under a different name each time, e.g. MyStruct1Stack, MyStruct2Stack, etc.)  ...
- ...And in each import, he only changes the define line to #define CUSTOMTYPE MyStruct1, or #define CUSTOMTYPE MyStruct2, etc.
(I think this would be possible only thanks to the newer #define that can overwrite the previous definition each time you redefine it -- or am I mistaken?)



Any dirty trick like the one I described above is welcome, the goal is simply to be able to implement as many custom stacks as possible with as little human intervention as possible.
What do you think? Simpliicty is the master word here.



===========

also, an unrelated question: why did you define Grow and set_Capacity as extenders?

[monkey0506]

I've deleted a rather large post that I had typed up, so please bear with me on this, but in order to be stored into a Stack instance, you have to have some way of referring back to the individual instances of your custom struct type. There are two ways of doing this:

• Provide serialization methods for your struct to "stringify" it.
  
• Make your struct a "managed struct" and use pointers to it (NOTE: this method only works if your struct does not store any pointers, including Strings).
  
  If you provide serialization methods, then then you do not modify the Stack functions at all:
  
  

  Code: ags

  StackData Serialize(this MyStruct*)
  {
    String buffer = String.Format("%d,%f...", this.myInt, this.myFloat);
    return StackData.StringToData(buffer);
  }
  
  bool Deserialize(this MyStruct*, StackData data)
  {
    // explode the CSV string....
    this.myInt = iValue;
    this.myFloat = fValue;
  }

  
  
  However, if your struct does not store any pointers, you can simply use extender methods to Push/Pop your type directly:
  
  

  Code: ags

  bool PushMyStack(this Stack*, MyStack *value, int index, bool insert)
  {
    bool result = this.PushInt(value.myInt, index, insert);
    result = ((result) && (this.PushFloat(value.myFloat, index + 1, insert)); // TODO: check if index is SCR_NO_VALUE first....
    // ...TODO: lazy eval if any push op fails?
    return result;
  }
  
  MyStack* PopMyStack(this Stack*, int index, bool remove)
  {
    MyStack *result = new MyStack;
    result.myInt = this.PopInt(index, remove);
    result.myFloat = this.PopFloat(index + 1, remove); // TODO: check if index is SCR_NO_VALUE or if removing items, update offset appropriately
    return result;
  }

  
  
  

  also, an unrelated question: why did you define Grow and set_Capacity as extenders?

  
  Grow was implemented as an extender for simplicity and logical grouping. Simplicity in that it's simpler to not have to type the import line, and also in that it's simpler to type "this" than "StringCache". Logical grouping, meaning, keeping it grouped together with the StringCache_t type, as AGS does not have namespaces except for struct namespaces.
  
  set_Capacity was defined as an extender for the purpose of hiding the method. It could easily be imported by any script, but there's really no need to do so as the Capacity attribute is writable. See the wiki article on attributes, particularly, the section on extenders. The point is just to not have the function listed in the script header, and thereby not have it show up in autocomplete or be automatically imported.

[Monsieur OUXX]

I still can't get my head around the AGs language restrictions.
Let me make sure I understand: if my custom struct contains, let's say, a GUI*, then I'm screwed? Because:
- if I go down the "managed struct" path, then it's forbidden to use pointers,
- and if I go down the stringify road, then I cannot stringify a GUI*.
Or can I? I believe the whole purpose of your Stack struct is to not stringify the built-in types, like GUI*.

[Crimson Wizard]

- and if I go down the stringify road, then I cannot stringify a GUI*.
Or can I? I believe the whole purpose of your Stack struct is to not stringify the built-in types, like GUI*.

You could use GUI's ID number, I believe.

[monkey0506]

Yes, most things can be stringified in some meaningful way. If you have to store a GUI*, then you could stringify it by using the GUI.ID. If you don't mind having a separate script for your struct definition though, you could do this:

Code: ags

// header

autoptr managed struct Thing
{
  import attribute GUI *TheGUI; // attributes are still okay, because they're functions, not actual pointers!
  protected int guiID; // int defaults to 0, so this will be GUI.ID + 1 instead -- 0 will be null GUI*
  // blah
};

import bool PushThing(this Stack*, Thing thing, int index=SCR_NO_VALUE, bool insert=true);
import Thing PopThing(this Stack*, int index=SCR_NO_VALUE, bool remove=true);

Code: ags

// script

GUI* get_TheGUI(this Thing*)
{
  if (this.guiID == 0)
  {
    return null;
  }
  return gui[this.guiID - 1];
}

void set_TheGUI(this Thing*, GUI *value)
{
  if (value == null)
  {
    this.guiID = 0;
  }
  else
  {
    this.guiID = value.ID + 1;
  }
}

bool PushThing(this Stack*, Thing thing, int index, bool insert)
{
  this.PushGUI(thing.get_TheGUI(), index, insert); // inside THIS SCRIPT ONLY, we must use the accessor functions directly
  // ...
  return true; // TODO: return correct result based on whether all members were pushed
}

Thing PopThing(this Stack*, int index, bool remove)
{
  Thing thing = new Thing;
  thing.set_TheGUI(this.PopGUI(index, remove));
  // ...
  return thing;
}

Code: ags

// some other script

Thing myThing = new Thing;
myThing.TheGUI = gMyThingGUI;
Stack stack;
stack.PushThing(myThing);
// ...

[Monsieur OUXX]

OK thanks a lot to both of you.
Monkey, would you mind post in that other thread from yesterday where I ask the meaning of autoptr? Thanks.

EDIT: Oh, you already did.

[Monsieur OUXX]

Warning: the module does not compile in AGS 3.4 (patch 2), because the array "inventory" does not exist anymore.
I haven't found a workaround yet.

[Crimson Wizard]

Warning: the module does not compile in AGS 3.4 (patch 2), because the array "inventory" does not exist anymore.
I haven't found a workaround yet.

You must create at least 1 inventory item to make it appear. This does not relate to particular version of AGS.

We have an issue in the tracker:
http://www.adventuregamestudio.co.uk/forums/index.php?issue=683.0

[monkey0506]

I'm proud to announce that all versions of this module are now available on Github:

https://github.com/monkey0506/ags-module-stack/releases

Version history between minor versions is now easier to visualize, and new releases are automatically built courtesy of Travis CI.