DSA Data

A DSA manipulates integers.  Mostly non-negative integers but you can also use negative integers if you are careful.  An integer can be used to represent other things.  One of the things that is commonly represented by an integer is a dungeon location.  A dungeon location is encoded into an integer as follows:

    integer = (((position * 64) + level) * 32 + x) * 32  + y

Or, if you can think in bits, this is an 18-bit integer with 2 bits for position, 6 bits for level, 5 bits for x, and 5 bits for y.

There are three main places where integers can be placed for safe-keeping and/or manipulation:
  1. The Stack.
  2. The Array.
  3. The Parameters.
The Stack
The Stack is the primary data-storage device.  It operates like the stack of plates at the cafeteria.  You put plates on top of the stack and take them off in reverse order.  The DSA stack takes 32-bit integers rather than plates.  It can hold up to 100 integers.  All computations and most operations either put numbers onto the stack, take number off the stack, or both. 

Arithmetic operations are the simplest examples of how the stack is used.  To add two integers together, for example, you put both of them onto the stack and then you say to add them.  The adding operation takes two integers from the stack, adds them together, and puts the result back onto the stack.  The definition of the addition operator looks like this:

    &+ <x y ... x+y>

This shows that the operation is named '&+' (this is what you write to cause an addition to occur).  Between the two broken brackets is the definition of the operation.  It shows that before the operation there should be two integers on the stack ( referred to as 'x' and 'y' for convenience) and after the operation is complete the sum of the two integers will be on the stack.  A few things to notice here:
  1. The definition of '&+' does not show what might be on the stack underneath the 'x' and 'y'.  There may be something else, but it is ignored by the addition operation.  Whatever is there, if anything, is ignored and unchanged.
  2. The top of the stack is to the right side.  In other words, in our example, 'y' is on the top and 'x' is just below it.
  3. '&+' (the addition operation) 'consumed' its operands (or inputs).  The two numbers it was supposed to add were removed.  This is a very general principle.  Almost without exception an operation will remove its operands from the stack before placing any result onto the stack.  Many operations require no operands.  Many provide no results.  Many are designed only to rearrange the entries on the stack.  Lots of possibilities but the definition always shows exactly how the entries on the stack are affected.
  4. The stack is empty when a DSA starts its work.  Any entries left on the stack when the DSA 'exits' will be removed.  So the stack can only hold data temporarily during the execution of one DSA.
The integers on the stack are usually treated as signed numbers.  That is they take on negative or positive values and arithmetic operations treat them just as you learned to treat numbers in school.  They are 32-bit integers and can take on values from about -2000000000 to +2000000000.  Putting an integer onto the stack is commonly referred to a 'pushing' it onto the stack (think of the stack of plates and push it down to make room for another plate).  Taking an integer off the stack is commonly called 'popping' it off.

The Array

The stack is quite sufficient for any needed operations.  But it is a pain to use.  The number you need always seems to be five or six deep and difficult to get.  Moreover, the depth of the thing you need keeps changing as you push and pop things from the top of the stack.  So it is always necessary to keep track of what is where.  To help solve this problem we have available an array of numbers where you can store things and have them stay in one place, easy to access.  This array is like a filing cabinet with 100 drawers.  You can put a number into a drawer at any time and take it out at any time.  The drawers are numbered from zero to ninety-nine.  Each drawer contains a single 32-bit number, exactly the same as a number on the stack.  In fact, the only way to put a number into a drawer is to first place it on the stack and then 'Store' it into a drawer.  Likewise you retreive it by 'Fetching' it onto the stack. 

Fetching a number from the array (from a drawer) does not 'Remove' it from the array.  It copies the number and pushes the copy onto the stack.  Like the stack, the array is empty when a DSA first begins execution.  (empty in the sense that its contents are undefined.  If you 'Fetch' from it you will get something....likely garbage.)  So the array is used for temporary storage during a single execution of a DSA.  Although it is not necessary it is very handy for complicated programs.

The Parameters

Each instance of a DSA has two parameters that can be treated as 'Locations' in the dungeon or as simple integers.  Usually, these parameters are only used to tell the DSA what door to open, pit to close, etc.  But the DSA can also change them by 'Storing' numbers into them.  This is useful if something must be remembered from one execution of the DSA until the next execution.  The parameters provide permanent memory.  One of them might be used to keep track of how many times the DSA has received a particular message, for example.

Beware:  Each parameter is capable of holding only small, non-negative integers.  To be precise, each can hold an integer between 0 and 262143.  If you try to put a larger integer into a parameter, it will be truncated to 18 bits which is the same as storing the remainder after division by 262144.

Return to Index