BCI NET 2/BCI NET 2.iso/archives/programming/e/queuestack.lha/queuestack.doc

Text File | 1995-01-27 | 14.2 KB | 407 lines

 QueueStack v2.0, from the Cheese Olfactory Workshop (written by
 Trey Van Riper) for Amiga E 3.1.

It's designed to act as both a stack and a queue.  In fact,
you could change your mind in the middle of either adding or
getting objects into the queuestack to make it act as a
stackqueue.. or whatever.  You can put anything into the
queuestack.. in fact, you could put varying types of data in
the queuestack (of course, you'll have to figure out what
you put in it yourself).  Thanks go to Amiga E as a typeless
language.

This second version adds a tremendous amount of
functionality to the queuestack in letting you iterate
through it.  As a result, procFrontToBack/procBackToFront()
have been deleted, in favor of some slightly more useful
phrases (inject/injectBackwards).

This second version also allows you to enter '0' as an item,
if you provide another value that can be used as a
replacement instead.  Unfortunately, queuestack needs some
means by which it can determine a non-valid item in order to
perform certain tests.  In the first version, '0' was that
value, however, this prevented '0' from being a value that
could be used in the queuestack (say, if you were working
with strictly integers or something).  Now you may determine
what constitutes a non-valid item (say, you don't expect to
have any integers of a value -1, then you could use -1).

Here's what the ShowModule output looks like...:

----------------------------------------------------------------------
ShowModule v1.9 (c) 1992 $#%!
now showing: "queuestack.m"
NOTE: don't use this output in your code, use the module instead.

/* this module contains 5496 bytes of code! */

/* ... and 56 reloc entries */

DEF queuestack_ctrlc
/* 2 private global variable(s) in this module */

(---) OBJECT queuestack
        new(a,b)
        addFirst(a)
        addLast(a)
        getFirst()
        getLast()
        getSize()
        addFirstQS(a)
        addLastQS(a)
        inject(a,b)
        injectBackwards(a,b)
        do(a)
        doBackwards(a)
        collect(a)
        collectBackwards(a)
        conform(a)
        detect(a)
        detectBackwards(a)
        reject(a)
        rejectBackwards(a)
        select(a)
        selectBackwards(a)
        asList()
        asListBackwards()
        asQueueStack(a)
        asQueueStackBackwards(a)
        kill()
        end()
(---) ENDOBJECT     /* SIZEOF=20 */

(---) OBJECT qsinner
(  4)   next:PTR TO qsinner
(  8)   prev:PTR TO qsinner
        new(a,b)
        inject(a,b)
        injectBackwards(a,b)
        do(a)
        doBackwards(a)
        collect(a,b)
        collectBackwards(a,b)
        conform(a)
        detect(a,b)
        detectBackwards(a,b)
        reject(a,b)
        rejectBackwards(a,b)
        select(a,b)
        selectBackwards(a,b)
        end()
(---) ENDOBJECT     /* SIZEOF=16 */

---------------------------------------------------------------------

You should ignore 'OBJECT qsinner'.  I wish I could keep this
object from appearing, but I can't.  So, ignore it and its
associated methods (PROCs).

Here are the following functions for queuestack, and how
they work:

new(a,b)

This is a constructor.  It can also somewhat act like a
destructor to reset a queuestack to NULL again (the
queuestack object is not destructed, only the elements in
the queuestack). If you pass it 'a', 'a' will be put into
the queuestack, just as addFirst() or addLast() would do.

Basically, use this function when you don't care about any
of the items in the queuestack, or when you're first
initializing a queuestack.  You MUST call this constructor
if you NEW queuestack (eg. NEW qs.new()).

If you pass new() 'b', it will set what constitutes a bad
item.  Without setting 'b', a value of '0' is assumed to be
a bad item, meaning you cannot enter an item with value '0'.
This value was chosen as the default since I guessed most
people would use queuestack for holding pointers to objects,
and no pointer holds a NIL value.  I added this parameter to
allow folks to use queuestack with integers that might
require a '0' value.

addFirst/addLast(a)

This adds 'a' into the queuestack.  If you use addFirst(),
it will put 'a' on the front of the queuestack, addLast()
will put 'a' on the end of the queuestack.  Nothing to it,
really.

getFirst/getLast()

This will retrieve an element from the queuestack.  If you
use getFirst(), the element retrieved was on the front of
the queuestack, getLast() gets elements from the end of the
queuestack.  If the queuestack is empty, however, you'll get
a zero element, and queuestack will raise an exception
("qstk").

getSize()

This will return how many elements are in the queuestack.  A
good rule of thumb while getting several elements from a
queuestack is to use getSize() to keep you from invoking an
exception:

 WHILE a.getSize()
  proc(a.getLast())
 ENDWHILE

addFirstQS/addLastQS(in:PTR TO queuestack)

These two functions allow you to combine two queuestacks
together.  The queuestack calling this method gets all the
elements in 'in', while 'in' is stripped of all its
elements.  There is currently no way to allow 'in' to keep
its elements while concatenating them to another queuestack.

Naturally, whichever function you choose will determine
whether the incoming queuestack is appended or prepended to
the current list (addFirstQS prepends, addLastQS appends).

ITERATIVE METHODS

The next few methods are iterative methods.  All of them
recurse through the queuestack.  They usually come in pairs
(where appropriate).  Those with 'Backwards' in their name
will iterate through the queuestack backwards rather than
forwards, which may be handy for certain situations.

inject/injectBackwards(a,b)

NOTE: This replaces what procFirstToLast/procLastToFirst()
did.  Note also that this method can alter the contents of
the list.  It's one of the few methods that can... perhaps
the only method that can.

These two methods allow you to iterate through the
queuestack, performing a procedure with the current element
against the previous element.

The first parameter is a procedure you've written that takes
two arguments:

    PROC a(i,j)

The first argument, 'i', will be the value of the current
item in the queuestack.  The second argument, 'j', will be
the value of the previous item in the queuestack.  Whatever
value you decide to return will become the value of the
current item.

The second parameter of 'inject()' ('b') is a starting value
to apply.  It will be passed as the second argument of the
first iteration's call to a(i,j) (eg. it will be 'j') just
to get things started.  If left out, the value assumed is
the bad item value you specified in method 'new()' (or '0'
if you didn't specify a bad item value).

do/doBackwards(a)

These methods simply iterate through the list, performing the
procedure 'a' you've passed to it.  Any value returned by
your procedure is ignored... typically, this procedure might
be used to print the contents of the queuestack.  It will
not change the queuestack.

Your procedure should take one argument (the current
element) as a parameter.

collect/collectBackwards(a)

This method returns a new queuestack where each element is a
result of procedure 'a' you pass to it.  For example, take
the following queuestack contents:

IN: 1, 2, 3, 4, 5, 6, 7, 8

Your procedure 'a' is:

PROC a(i) IS RETURN i+1

After 'collect' you would have a new queuestack:

OUT: 2, 3, 4, 5, 6, 7, 8, 9

So... out:=in.collect({a}) (where 'out:PTR TO queuestack')
would be an appropriate call.

conform(a)

This may be the only iterative function without a
'Backwards' counterpart, because it isn't appropriate.
This method performs a test of all the elements in your
queuestack to insure they conform to the procedure you pass
to it.  Your procedure should, again, take one argument (an
item in the queuestack) and return TRUE or FALSE.

detect/detectBackwards(a)

These methods return the first item in the queuestack that
fits a particular test.  'a' is a procedure taking one
argument and returning TRUE or FALSE.  If it is unable to
detect any items, it will return with whatever value you
entered as a bad item in 'new()' or '0' if no bad item was
specified.

reject/rejectBackwards(a)

These methods return a new queuestack containing any items
in the queuestack that do not pass the test you pass in
argument 'a'.  'a' is a procedure taking one argument and
returning TRUE or FALSE.  If it is unable to reject any
items, the new queuestack's getSize() will return 0.

select/selectBackwards(a)

These methods return a new queuestack containing any items
in the queuestack that pass the test you pass in argument
'a'.  'a' is a procedure taking one argument and returning
TRUE or FALSE.  If it is unable to select any items, the new
queuestack's getSize() will return 0.

NOTE: The next two entries are conversion methods.  They'll
help you integrate Amiga E with queuestack more easily.

asList/asListBackwards()

These methods will create an EList of items in the
queuestack.  Handy if you want to use queuestack to create
ListViews or something.

asQueueStack/asQueueStackBackwards(a)

These methods will add an EList to the queuestack.  Current
contents in the queuestack will not be effected.  This can
be handy when used with file requesters and other things
that generate ELists (note: do not forget Amiga E's
SetList() command to insure you're really giving QueueStack
an EList... these methods use ListLen()).

NOTE: These last two methods are deallocation methods.  Take
care how you use them.

kill()

This method will go through the queuestack, ENDing all the
items in the queuestack.  It will not END the queuestack
itself, or the instances, therefore it's strongly suggested
this be used only before ENDing the queuestack, or at least
using .new().  This was made as a convenience for people who
want to deallocate a lot of resources at one time in as
simple a way as possible.  Not recommended for integer
queuestacks <grin>.

end()

This is simply a destructor.  You shouldn't have to mess
with this.. just END your object and this function will be
invoked (as of Amiga E 3.1a).

DISTRIBUTING INFORMATION

QueueStack is FreeWare.  All I ask is that you acknowledge
that I'm the author of this routine.. nothing more.  You do
not even have to acknowledge me as the author in your
documentation.. I ask that you do not claim work I've done.

You may use this module freely in all your software (without
even having to send me a copy of it) without cost.  It's too
primal an object to require any kind of payments or any
nonsense like that, so enjoy it.

If Wooter would like, he may include this in his next
version of Amiga E to be released (e:src/pd/class or
wherever).

MOTIVATION

I wrote this object because I wanted to use it with my Quip
project.  Now that Amiga E has become so strongly Object
Oriented, I'm trying to completely rewrite my Quip program
to take advantage of the improvements to the language.  To
that end, I plan to use this object to help make my life a
little easier (although I think I only needed a queue... but
when I make an object, I try to think as far in the future
as I can).

I got the idea to make this a queuestack from reading a
SmallTalk manual.

ISSUES

Firstly, be very careful while using this tool.  You most
likely will be passing pointers to objects you've
initialized.. as such, these objects will NOT be
de-initialized or re-initialized by queuestack alone.. that
responsibility is left to you.

The iterative functions will return the pointers you passed
into it... therefore, when you END a queuestack, any
initialized items in the queuestack will NOT be ENDed... you
must remember to do that yourself by, say, qs.do({endMe}) or
qs.kill().  While Amiga E still deallocates all memory
NEWed when the program ends, this may become an issue if
you're trying to run a server or something.

Another point to make; when using any methods that create a
new queuestack, all items that are pointers to other objects
will be pointers to the SAME INVOCATION of that object
(unless, in the case of 'collect', your function returns a
new invocation of your object).  Therefore, if you end that
object while it is still in the queuestack, you may be
asking for trouble.  This can get tricky if someone does a
nqs:=qs.reject({myProc}) followed by a nqs.kill().  If none
of this makes sense, try experimenting a little bit and see
if you can figure it out <grin>.

The only potential annoyance with queuestack is a minor
amount of expense.  I traded memory for speed.  While
queuestack isn't likely to eat up GOBS of memory, there are
more memory-efficient ways of doing this same thing, however
one will likely pay a price in speed.

Each item put into queuestack will take up 16 bytes of
memory.  Eight of those bytes are used to point to the next
and the previous item in the queuestack (I needed both in
order to handle either direction quickly).  Another four is
used for storing your actual item.  The last four are used
by Amiga E to figure out where my associated procedures are
to process those items if necessary (eg END, new(),
do(), etc).

Since memory is fairly cheap these days, I didn't think
anyone would mind terribly.

Some recursion is used during the deallocation routines, so
extremely large queuestacks may cause a problem during END if
there isn't enough stack to handle it.  The routine is
pretty bare, though, so it shouldn't be much of a problem at
all.  Same thing goes for iterative routines.

FUTURE

Well, I thought I had done everything last time, but then I
realized how easy it would be to add these methods in.  I'm
sorry for a slightly lack of compatibility with the old
queuestack, but I hope I've managed to submit this newer
queuestack early enough to avoid any kinds of problems.

I may desire to create a sorted list next (via binary tree,
most likely).  If and when I do so, likely, it will contain
similiar methods to these (I had even toyed with the thought
of using a flag to change queuestack into a binary tree...
a thought that still sounds mighty nice to my twisted mind).

At the moment, I have little incentive to do so (my current
software developing needs, so far, do not include a need
to sort anything), but if someone is interested in creating
a sorted list based on these methods, please consider
sending me e-mail; perhaps our two objects could be combined
into one module, so a hapless programmer doesn't have to
remember which module to include in his code.

May the cow be with you.