Subject: ANNOUNCE: Set-IntegerFast 1.1
From: [email-masked] (Steffen Beyer)
Date: 9 Jan 1996 02:30:21 GMT
Newsgroups: comp.lang.perl.announce,comp.lang.perl.misc

I'm proud to hereby announce the new release of my "Set-IntegerFast" module
(version 1.1), which implements the data type of sets of (positive) integers,
which I have uploaded to the CPAN (= "Comprehensive Perl Archive Network").

(For a list of CPAN ftp sites, see "The Perl 5 Module List" by Tim Bunce,
posted to this same newsgroup in regular intervals.)

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

What's new in this release?

Here's an excerpt of the package's README file:

Version 1.1 offers a "Resize" method which allows you to change the size of
a set while retaining the information it contains (as much of it as possible)
and fixes some errors in the documentation (the methods Create, Empty, Fill
and Copy had complexity n/8 and not n/b, of course!) by changing the imple-
mentation of these methods (so that they now have complexity n/b, which
is much better since b is normally much greater than 8).

The interface of the C routines is more consistent now (the pointer to the
set is now always the first argument) and a few more paragraphs have been
added to the documentation.

The method "ExclusiveOr" (which calculates the symmetric difference X =
(Y + Z) \ (Y * Z) of two sets Y and Z) has also been added in this version.

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

For those who don't know this module at all, here a description:

This package lets you dynamically create sets of arbitrary (changeable!) size
(only limited by the size of a machine word and available memory on your system)
of (positive) integers and to perform all the basic operations for sets on them,
like adding or removing elements, testing for the presence of a certain element,
computing the union, intersection, difference or complement of sets, copying
sets, testing two sets for equality or inclusion, and computing the minimum,
the maximum and the norm (number of elements) of a set.

The package is mainly intended for mathematical or algorithmical computations.
There are a number of efficient algorithms that rely on sets, like, for exam-
ple, Kruskal's algorithm for minimal spanning trees in graphs (which uses a
different representation of sets (trees stored in an array), however, than
the one used by this package (bit vectors), which is included here for those
interested as a Perl program), or the "Seave of Erathostenes" for calculating
prime numbers, which is included here as a demo program.

Another important field of application is the computation of "first", "follow"
and "look-ahead" character sets for the construction of LL, SLR, LR and LALR
parsers for compilers (or a compiler-compiler, like "yacc").

(This is what the C code in this package was initially written for)

(See Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithms"
for an excellent book on efficient algorithms and the famous "Dragon Book" on
how to build compilers by Aho, Sethi, Ullman)

The package is designed for efficiency, not comfort. Therefore, it only
offers a basic functionality and leaves it up to your application to add
whatever special handling it needs (for example, negative indices can
be realized by "shifting" the whole range with an offset).

If you want a package for sets that offers more comfort for not so time-
critical tasks, consider using the module "Set::Scalar" written by Jarkko
Hietaniemi <[email-masked]>, which allows you to use all kinds of
Perl scalars as elements and offers an abundant range of methods to handle
these sets.

Sets in this package are implemented as bit vectors, and elements are positive
integers from zero to the maximum number of elements (which you specify when
creating the set) minus one.

Each element (i.e., number or "index") thus corresponds to one bit in the
bit array. Bit number 0 of word number 0 corresponds to element number 0,
element number 1 corresponds to bit number 1 of word number 0, and so on.

The package doesn't use bytes as basic storage unit, it rather uses machine
words, assuming that a machine word is the most efficiently handled size of
all scalar types on any system.

In order to achieve this, it automatically determines the number of bits
in a machine word on your system and then sets its internal basic constants
accordingly.

The greater the size of this basic storage unit, the better the complexity
of the routines in this package (but also the greater the average waste of
unused bits in the last word).

See the Set::IntegerFast(3) man page for a detailed analysis of the com-
plexity of each method!

Here a brief description of all the available methods:

     Version       returns a version string
     Create        the set object constructor
     Destroy       free() the memory occupied by a set
     Resize        change the size of a set
     Empty         delete all elements in the set
     Fill          insert all possible elements into the set
     Insert        insert a given element
     Delete        delete a given element
     in            test the presence of a given element
     Union         calculate the union of two sets   (in-place is possible)
     Intersection  calculate the intersection of two sets            (idem)
     Difference    calculate the difference of two sets ("A\B")      (idem)
     ExclusiveOr   calculate the symmetric difference of two sets    (idem)
     Complement    calculate the complement of a set (in-place is possible)
     equal         test two sets for equality relation
     inclusion     test two sets for inclusion relation
     lexorder      test two sets for lexical order relation
     Compare       compare two sets - yields -1, 0 or 1 for <, = or >
     Norm          calculate the norm (number of elements) of the set
     Min           return the minimum of the set ( min{} = +infinity )
     Max           return the maximum of the set ( max{} = -infinity )
     Copy          copy one set to another

For more details, see the Set::IntegerFast(3) man page!

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

Please let me know if you find this module useful, and please let me also
know if you encounter any problems or bugs in building or using it!

Thank you!

Yours sincerley,
--
Steffen Beyer
mailto:[email-masked]        |s  |d &|m  |  software design & management GmbH&Co.KG
phone: +49 89 63812-244 |   |   |   |  Thomas-Dehler-Str. 27
fax:   +49 89 63812-150 |   |   |   |  81737 Munich, Germany.