[M3devel] New OrdSets generic package
Rodney M. Bates
rodney_bates at lcwb.coop
Mon Jul 16 18:45:58 CEST 2012
Now checked in inside m3-libs/ordsets, OrdSets is a generic interface and module
for dynamically-sized sets of large-range ordinal types, in functional style.
From comments in OrdSets.ig:
(* This interface provides operations on sets whose members are of an ordinal
type. It is written in a functional style. It never mutates a set value,
(except for some internal lazy computation--not visible to clients), and
thus it sometimes is able to share heap objects.
Its primary use pattern is where the set values can have widely
varying sizes, you want a very large maximum size limit, but many
of the sets are expected to be much smaller than the maximum. For
this to happen, you probably want to instantiate only with INTEGER
or WIDECHAR. It will work with LONGINT, but only if its target-machine-
dependent range is a subrange of INTEGER. There is no space or time
performance benefit to instantiating with a subrange of the base type.
If this does not fit your needs, you probably want to use
Modula-3's builtin set type, or some other package.
The set representations occupy variable-sized heap objects, just
sufficient for the set value. In the most general case, these use
heap-allocated open arrays of machine words, with one bit per
actual set member, plus some overhead, of course.
If you compile with a later CM3 Modula-3 compiler and garbage
collector that tolerate misaligned "pseudo" pointers, i.e, with the
least significant bit set to one, you can set a boolean constant in
the corresponding module OrdSets.mg. This will cause it to utilize
this Modula-3 implementation feature to store sufficiently small set
values entirely within the pointer word, avoiding the high space and
time overheads of heap allocation. The CM3 5-8 compiler is sufficient.
SRC M3, PM3, EZM3, and earlier CM3 versions are not. As of 2012-7-15,
Pickles do not handle these. Enable this with DoPseudoPointers, in
OrdSets.mg.
*)
More information about the M3devel
mailing list