User:LepreKhaun Resident/Stack Implementations using Json Arrays

[NOTE: Since I refrain from rearranging the flamingos in front of your trailer home, you are expected to extend the courtesy and leave comments, suggested improvements, corrections of fact or your own personal preferences ONLY on the Discussion Pages within my Name Space. Thank you!]

Three Stack Implementations using Json Arrays

The Stack is a much used abstract data type with properties that make it invalualabe for recursive operations. It is known as a LIFO, Last-In-First-Out, data type with some elementary operations; PUSH (which adds a Value to the Stack), POP (which retrieves the last Value added to it) and PEEK (which "looks" at the last Value added to the top of the stack without removing it). Additionally, a SIZE_OF method is handy to see how many Values are currently held within the Stack; one doesn't want to POP a Value when there are no Values there to be POPPED, which would result in a condition known as "underflow".

It might be noted here that a Value need not be really "removed" from the Stack when it is POPPED, but the size of the Stack is simply decreased. This is because the size of the Stack is used as a pointer to the top of the Stack and the Value can be safely ignored from then on since it's no longer "within" the Stack and it'll be overwritten by a new Value whenever the length gets back up to that point again.

Here are three Stack implementations of increasing complexity. The first is simply one global Stack which may be accessed anywhere within the script.

<lsl>///////////////// // STACK METHODS FOR ONE GLOBAL STACK ////////////////

// Global stack declaration and initialization string ourStack = "[]"; // SIZE_OF the stack may be had by simply checking this integer stackSize = 0;

// Takes a (string)item and appends it to stack PUSH (string ITEM) { ourStack = llJsonSetValue(ourStack, [stackSize++], ITEM); }

// "Removes" and returns the top of the stack string POP () { if (stackSize) return llJsonGetValue(ourStack, [--stackSize]); else return ""; }

// Just "looks" at the top of the stack // and returns item string PEEK () { if (stackSize) return llJsonGetValue(ourStack, [(stackSize-1)]); else return ""; }

///////////////// // end STACK METHODS FOR GLOBAL STACK ////////////////</lsl>

The second implementation forms a Stack as needed, which is then held and sent to its methods (geek term for a function that is object specific) in it's entirity. This may be preferred over the third implementation in that there is no global(s) used, however the passing by reference of an entire stack for each operation may outweigh that and the third implementation may prove better in some cases.

In this and the next implementation, the size of the Stack is the first element within the array, making the indexing for its Values one-based instead of zero-based. In other words, the last element (top of the Stack) will now be found with length_of_array instead of length_of_array-1 with length_of_array always to be found at index 0.

<lsl>///////////////// // STACK METHODS FOR MULTIPLE STACKS ////////////////

// returns a JSON_ARRAY as a Stack Object string stINIT () { return "[0]"; }

// returns the number of items in stack integer stSIZE_OF (string jsonST) { return (integer)llJsonGetValue(jsonST, [0]); }

// Takes [stack, item] and appends item to stack // (Could be written using two parameters instead of a list) string stPUSH (list jsonST_ITEM) { string jsonST = llList2String(jsonST_ITEM, 0); string item = llList2String(jsonST_ITEM, 1); integer size = stSIZE_OF(jsonST);

jsonST = llJsonSetValue(jsonST, [0], (string)++size)); return llJsonSetValue(jsonST, [size], item); }

// "Removes" the top of the stack // and returns a list of [stack, item] list stPOP (string jsonST) { integer size = stSIZE_OF(jsonST); // Check for "underflow" condition... if (size) { string item = llJsonGetValue(jsonST, [size]); // set stack pointer to one less return [llJsonSetValue(jsonST, [0], --size), item]; } else { return [jsonST, ""]; } }

// Just "looks" at the top of the stack // and returns item string stPEEK (string jsonST) { integer size = stSIZE_OF(jsonST); if (size) { return llJsonGetValue(jsonST, [size]); } else { return ""; } } ///////////////// // end -- STACK METHODS FOR MULTIPLE STACKS ////////////////</lsl>

In this final implementation, we'll use integers as (primitive) "pointers", holding and passing them instead of entire stacks. This encapsulates the concept of Stack and almost completely decouples them from the rest of the code, a good thing. In other words, if we decided at some point that a Stack could be better represented as a Json object, we'd only need to change these methods as given here, anything else calling them would not need to be touched.

<lsl>///////////////// // STACK METHODS FOR MULTIPLE STACKS USING "POINTERS" WITHIN A GLOBAL STACK "OBJECT" ////////////////

// Global declaration and initialization of ourStacks as a Stacks object // Index 0 is used to determine next available stack "pointer" ourStacks = "[0]";

// initialation of a new Stack // returns a "pointer" to a new stack integer getNewStackPtr() { integer numberOfStacks = llJsonGetValue(ourStacks, [0]); ourStacks = llJsonSetValue (ourStacks, [JSON_APPEND], "[0]"); ourStacks = llJsonSetValue (ourStacks, [0]), ++numberOfStacks); return numberOfStacks; }

// returns the number of items in a stack integer stPtrSIZE_OF (integer stPtr) { return (integer)llJsonGetValue(ourStacks, [stPtr, 0]); }

// Takes [stackPointer, item] and appends item to stack stPtrPUSH (list stPtr_ITEM) { integer stPtr = llList2Integer(stPtr_ITEM, 0); string item = llList2String(stPtr_ITEM, 1); integer size = stPtrSIZE_OF(stPtr);

ourStacks = llJsonSetValue(ourStacks, [stPtr, 0], (string)++size)); ourStacks = llJsonSetValue(ourStacks, [stPtr, size], item); }

// "Removes" the top of the stack // and returns [stackPointer, item] string stPtrPOP (integer stPtr) { integer size = stPtrSIZE_OF(stPtr); // Avoid "underflow" condition. if (size) { string item = llJsonGetValue(ourStacks, [stPtr, size]); // set stack pointer to one less ourStacks = llJsonSetValue(ourStacks, [stPtr, 0], --size); return item; } else { return ""; } }

// Just "looks" at the top of a stack // and returns item string stPtrPEEK (integer stPtr) { if (stPtrSIZE_OF(stPtr)) { return llJsonGetValue(ourStacks, [stPtr, stPtrSIZE_OF(stPtr)]); } else { return ""; } } ///////////////// // end STACK METHODS FOR MULTIPLE STACKS USING "POINTERS" WITHIN A GLOBAL STACK "OBJECT" ////////////////</lsl>

---

== More Json Tips, Tricks and Coding Examples ==