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:
- The Stack.
- The Array.
- 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:
- 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.
- 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.
- '&+' (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.
- 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.