Re: Formal ADT Definition...

[Mike Griebling <grieblm@trt.allied.com>]

>    Well, but that's the whole point of my original mail... :-) It is
> interesting that there are lots of books using Stack as an example for
> formal ADT specs, but that even with something as simple as Set, playing
> the formalism gets somewhat more complicated.

So, you're just interested in a mathematical challenge?  I'm more interested
in getting a working implementation out there for people to use.
 
>    Anyway, thanks for the offer. I actually have a pretty well thought-out
> implementation plan which I also posted to the OOC list. Have you read it?
> What do you think of this "sorted array" approach? IMHO it leads to very
> efficient operations as long as the set remains static after an initial
> "build-up phase".

My application wouldn't neatly fit into this paradigm.  I'm basically using
a Set to implement general-purpose operations so the set elements are
built and used with roughly equal frequency.  My implementation is a bounded
set implemented as an array of SETs.  It is the most straight-forward
implementation (also used in the various Oberon systems) and probably
the fastest for use in bounded applications.  In my view, a bounded set
implementation would account for probably 95% of all the uses around (ie.
register allocation, fixed number arithmetic, etc.).  At the moment I'm
hard-pressed to think of a use for unbounded sets -- although you certainly
must know of some.

>    However we should probably have a more general Set implementation too,
> that allows arbitrary operations in arbitrary order. Any ideas for
> implementing that efficiently? Maybe we should look into tree structures,
> eg. AVL or red-black?

I see there being a need for several set modules:

UnboundedSet -- slower but allows any set element
BoundedSet   -- highly efficient for fixed sizes

If OOC ever gets used in a multi-threaded application (as I'm hoping to do)
we would need further subclasses of:

SequentialUnboundedSet -- standard UnboundedSet
SharedUnboundedSet     -- locked UnboundedSet
SequentialBoundedSet   -- standard BoundedSet
SharedBoundedSet       -- locked BoundedSet

I'm not sure why you feel that tree structures are needed.  Is this just
to make the ordering of the set elements (in a sparse configuration)
simpler?  Perhaps, as you say, hashing might be a better solution to get
a sparse array packed into an array of SETs.  Then set operations would be
as fast as with bounded sets (i.e., 32-bits at a time) and individual set
element access would be optimized with the hash function.  Another advantage
might be that the BoundedSet could then be largely reused for the
UnboundedSet implementation.

The shared set implementations obviously would need a built-in mutex or
semaphore to guarantee non-conflicting access to a set instance.  Other
than that, all operations would be identical.

Michael G.