=========================================
Module "Set::IntegerFast" Version 1.1
=========================================
--------------------------------------------------------------------------------
Extension package for Perl 5.001m (should work with Perl 5.000 and up as well)
--------------------------------------------------------------------------------
Legal stuff:
------------
Copyright (c) 1995 by Steffen Beyer. All rights reserved.
This package is free software; you can redistribute it and/or
modify it under the same terms as Perl itself.
What does it do:
----------------
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 , 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!
How to install it:
------------------
Please unpack and build this package OUTSIDE the Perl source and distribution
tree!!
1) Change directory to the directory that has been created by unpacking this
package ("Set-IntegerFast-1.1").
2) Type "perl5 Makefile.PL" (or whatever the name and path of your Perl 5
binary is).
This will create a "Makefile" with the appropriate parameters for your
system (for instance, where the install directories are, and so on).
3) Type "make".
This will create a dynamically linkable library file that will be linked
to Perl later, at runtime, provided your system supports dynamic linking.
Please refer to the MakeMaker documentation for instructions on how
to build a new Perl with statically linked libraries (invoke "perldoc
ExtUtils::MakeMaker" for this), if your system DOESN'T support dynamic
linking!
(Note, however, that I didn't test this since my system does support
dynamic linking.)
Should you encounter any compiler warnings or errors (like the redefini-
tion of certain types already defined by your system), please contact
me by mail at 'sb@sdm.de', sending me your compiler output (both STDOUT
and STDERR). Thank you!
Should you get the error messages
IntegerFast.c: 15: Unable to find include file 'EXTERN.h'.
IntegerFast.c: 16: Unable to find include file 'perl.h'.
IntegerFast.c: 17: Unable to find include file 'XSUB.h'.
then edit the file Makefile.PL and change the line
'INC' => '', # e.g., '-I/opt/pkg/perl5.001m/dist'
in such a way that it points to your Perl 5 distribution tree, e.g.,
'INC' => '-I/usr/ctr/dlt/private/perl/perl5.001m',
or the like, and start over with the generation of the Makefile at 2).
4) Now issue "make test".
The output should look somewhat like this:
PERL_DL_NONLAZY=1 /opt/bin/perl5 -I./blib/sun4-sunos -I./blib
-I/opt/lib/perl5.001m/sun4-sunos -I/opt/lib/perl5.001m -e
'use Test::Harness qw(&runtests $verbose); $verbose=0; runtests @ARGV;'
t/*.t
t/f000..............ok
t/f001..............ok
t/f002..............ok
t/f003..............ok
t/f004..............ok
t/f005..............ok
t/f006..............ok
t/f007..............ok
t/f008..............ok
t/f009..............ok
t/f010..............ok
All tests successful.
Files=11, Tests=2506, 6 secs ( 4.68 cusr 0.75 csys = 5.43 cpu)
5) You will have to manually copy the man page "Set::IntegerFast.3" to your
man directory, probably one of "/usr/lang/man/cat3", "/usr/local/man/cat3",
"/usr/man/cat3", or the like (consult your MANPATH environment variable).
(The current version of MakeMaker doesn't yet support the copying of the
man pages to their destination directory.)
If, however, you have installed a newer version of Makemaker which
supports installing of the man pages, you can skip this step as it's
automatically taken care of by the "make install" in the next step.
You can also first try "make install", and if it doesn't install the
man page, copy it manually.
6) Finally, type "make install".
7) Now you may try to run the "demo". Start it with "perl5 demo" (or what-
ever the name and path of your Perl 5 binary is).
It will ask you to enter a number which will serve as an upper limit for
the calculation of all prime numbers up to that limit, using the algorithm
known as "The Seave of Erathostenes".
On my machine (SUN SPARCstation 20/61), calculating all the prime numbers
up to one million takes about 1 minute 30 seconds to 2 minutes, depending
on the load.
8) Enjoy!
Version history:
----------------
Version 1.0 was the initial release.
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).
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.
Thanks:
-------
Many thanks to Jarkko Hietaniemi for his suggestions while I was developing
this package!
Many thanks also to the people of the perl5-porters
mailing list, specifically:
Andreas Koenig
Tim Bunce
Jarkko Hietaniemi
Felix Gallo
Mark A Biggar
Nick Ing-Simmons
John Macdonald
for discussing and clarifying the naming and other issues of this package!
Also many thanks to David Thompson for reporting a
problem he encountered concerning the inclusion of the Perl distribution
into the search path for h-files together with his solution. (That's the
most pleasant kind of problem report, of course! ;-) )
Final note:
-----------
Please report any comments, problems, suggestions, findings, complaints,
questions, insights, compliments or donations ;-) and so on to:
sb@sdm.de (Steffen Beyer)
Yours sincerely,
--
Steffen Beyer
mailto:sb@sdm.de |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.