========================================= Module "Set::IntegerFast" Version 2.0 ========================================= ------------------------------------------------------------------------------ Extension Module for Perl 5.003 (should work with Perl 5.000 and up as well) ------------------------------------------------------------------------------ Legal stuff: ------------ Copyright (c) 1996 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. Requirements: ------------- Perl version 5.000 or higher, a compiler complying with ANSI C standards (!). ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ What are the most important differences between versions 1.x and 2.x: --------------------------------------------------------------------- 1) The standard calling convention for the object constructor method is supported now, i.e. $set = Set::IntegerFast::Create($elements); is _gone_ and is replaced by $set = new Set::IntegerFast($elements); (and also including all other possibilities of calling a class method offered by Perl) 2) The object destructor method has also changed its name: $set->Destroy(); is also _gone_ and replaced by $set->DESTROY(); Note however that you don't need to call this method explicitly anymore (!) - Perl will do it automatically for you when the last reference to your set is deleted, for instance through assigning a different value to the Perl variable containing the reference to your set, like in "$set = 0;". 3) The man page is no separate file anymore, it is now included in the file "IntegerFast.pm" in POD format, where it will automatically be found and installed in your "man" directory by "make install". 4) A wrapper module named "Set::IntegerRange" has been added to this package which allows you to use sets of integers in an *arbitrary* interval (instead of from zero to some positive integer). What does it do: ---------------- This package allows you to create sets of arbitrary size (only limited by the size of a machine word (minimum) and available memory on your system (maximum)) of an interval of positive integers starting with zero, to dynamically change the size of such a set 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, symmetric 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. Note that it is extremely easy to implement sets of arbitrary intervals of integers using this package (negative indices are no obstacle), despite the fact that only intervals of positive integers (from zero to some positive integer) are supported directly. Please refer to the Set::IntegerFast(3) and Set::IntegerRange(3) man page to see how this is done! The package is mainly intended for mathematical or algorithmical computa- tions. There are also a number of efficient algorithms that rely on sets. An example of such an efficient algorithm (which uses a different repre- sentation for sets than this package, however) is Kruskal's algorithm for minimal spanning trees in graphs. (That algorithm is included in this dis- tribution as a Perl program (thoroughly commented) for those interested) Another famous algorithm using sets is the "Seave of Erathostenes" for calculating prime numbers, which is included here as a demo program. An 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", for instance). (That's 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) Therefore, this package is designed for efficiency and not for a fancy user interface. 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 biasing the whole range with an offset). (See the "Set::IntegerRange.pm" module in this package for more details) 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 machine (that's what the C standard proposes and assumes). In order to achieve this, it automatically determines the number of bits in a machine word on your system and then adjusts its internal constants accordingly. The greater the size of this basic storage unit, the better the complexity of the methods in this package (but also the greater the average waste of unused bits in the last word). See the section on COMPLEXITY in the Set::IntegerFast(3) man page for a detailed analysis of the complexity of each method! Note that the C part of this package ("lib_set.c") is designed in such a way that it may be used independently from Perl and this Perl extension module as a C library. For this, you can use the file "lib_set.o" exactly as it is produced when building this module! It contains no references to Perl, and it doesn't need any Perl header files in order to compile. (It only needs "lib_defs.h" and some system header files) Note however that this C library does not perform any bounds checking whatsoever! (This is left to your application!) (See the corresponding explanation in the file "lib_set.c" for more details and the file "IntegerFast.xs" for an example of how this can be done!) In this package, all bounds and type checking (which should be absolutely fool-proof, by the way!) is done in the XS subroutines. For more details, see the Set::IntegerFast(3) man page! Preliminary steps for use with Perl prior to version 5.002: ----------------------------------------------------------- Edit the file "Makefile.PL" in this package and change the line 'VERSION_FROM' => 'IntegerFast.pm', to 'VERSION' => '2.0', Then edit the file "IntegerFast.pm" and change the line bootstrap Set::IntegerFast $VERSION; to bootstrap Set::IntegerFast; Finally, edit the file "IntegerFast.xs" and delete the line PROTOTYPES: DISABLE 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-2.0/"). 2) Type "perl 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 redefi- nition of certain types already defined by your system), please contact me by mail at , sending me your compiler output (both STDOUT and STDERR). Thank you! ====================================================================== Be aware that you need a C compiler which supports ANSI C in order to successfully compile this package! ====================================================================== Also note that problems may arise with the c89 compiler of HP, although it allegedly supports ANSI C! I recommend the GNU gcc compiler, which is available for free on the Internet. (HP users are strongly recommended to install the GNU assembler GAS first before installing GNU gcc) 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.003/dist' in such a way that it points to your Perl 5 distribution tree, e.g., 'INC' => '-I/usr/ctr/dlt/private/perl/perl5.003', 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 /usr/bin/perl -I./blib/arch -I./blib/lib -I/e/www/sw/pkg/perl/lib/i386-freebsd/5.003 -I/e/www/sw/pkg/perl/lib -e 'use Test::Harness qw(&runtests $verbose); $verbose=0; runtests @ARGV;' t/*.t t/00____version.....ok t/01________new.....ok t/02____destroy.....ok t/03_operations.....ok t/04__functions.....ok t/05_____primes.....ok t/06__inclusion.....ok t/07___lexorder.....ok t/08_____resize.....ok t/09_parameters.....ok All tests successful. Files=10, Tests=3012, 2 secs ( 3.62 cusr 0.50 csys = 4.12 cpu) (Note that these tests test the "Set::IntegerFast" module ONLY; the "Set::IntegerRange" module is currently NOT tested because of its simplicity!) 5) At last, type "make install". 6) Now you can try to run the "demo". Start it with "perl 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. 7) Enjoy! Version history: ---------------- Version 1.0 was the initial release. Version 1.1 offered a new "Resize" method which allows you to change the size of an existing set while keeping the information it contains (as much of it as will fit into the new set) and fixed some errors in the documen- tation (the methods Create, Empty, Fill and Copy had complexity n/8 and not n/b) by changing the implementation of these methods (so that they now have complexity n/b). The interface of the C routines was made more consistent (the pointer to the set is now always the first argument) and a few more paragraphs were added to the documentation. The method "ExclusiveOr" (which calculates the symmetric difference X = (Y + Z) \ (Y * Z) of two sets Y and Z) was also added in this version. Version 1.1 broke with the next new release of Perl, version 5.002 (problems with the "Destroy" method and "bad free() ignored" warnings that caused some of the tests in "make test" to fail). Version 2.0 fixes the problem that appeared with Perl 5.002 in version 1.1. As a matter of fact, version 2.0 is a complete rewrite of the XSUB part of this package. The C part of the package ("lib_set.c") has also been slightly changed; the functions "lexorder" and "Compare" are handled more efficiently now (complexity 1..n/b instead of 1..n/8). Parameter types have been adjusted to reflect their nature as those integers that the sets of this package are all about. The documentation has been completely rewritten and ported to POD format. A new module (in fact a "wrapper" module for the "Set::IntegerFast" module) named "Set::IntegerRange" has been added in version 2.0 of this package which allows you to use sets of integers in an *arbitrary* interval (instead of from zero to some positive integer). Known bugs: ----------- Beware that calling the set object constructor method with the explicit name of a non-existing class, like in $set = Set::IntegerFast::new('nonsense',$elements); will produce CORE DUMPS as soon as Perl tries to DESTROY the object so created IF (and only if) SUBCLASSING IS ENABLED! This can only be prevented if there is a "package nonsense;" declaration somewhere in the program which is in effect when Perl tries or is forced to destroy the object! Example: package main; $set = Set::IntegerFast::new('nonsense',$elements); package nonsense; @ISA = qw(Set::IntegerFast); $main::set = 0; package main; # rest of your program... Thanks: ------- Many thanks to Andreas Koenig for his efforts as upload-manager for the CPAN, his patience, and lots of good advice and suggestions! Thank you for doing such a tremendous (and time- consuming) job!! Also many thanks to David Jenkins for reviewing the first version of this README file and the man page. Many thanks to Jarkko Hietaniemi for his suggestions while I was developing the first release of 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 ("Unable to find include file ...") and for suggesting a solution for this problem. (That's the most pleasant kind of problem report, of course! ;-) ) Many thanks to Rob Johnson for an improved algorithm for computing binomials with always integer intermediate results (and numbers never getting too big)! Thanks to Banchong Harangsri for reporting the problem of the version 1.1 of this module with Perl 5.002! Special thanks to Dean Roehrich for his assistance in trying to find the cause of and a remedy for the above problem! Final note: ----------- If you need any assistance or have any comments, problems, suggestions, findings, complaints, questions, insights, compliments or donations to give ;-) then please don't hesitate to send me a mail: sb@sdm.de (Steffen Beyer) In fact I'd be glad if you could drop me an e-mail when you are using this package, so I can see how much interest exists in it and how much time is reasonable to spend on its further development. Therefore, I would also be glad to know what you liked and what you disliked about this package! And I would also be very interested to know what your application is in which you found this package to be useful, just to get an idea what can all be done with it and in which direction it should be developed further. Many thanks in advance!! With kind regards, -- |s |d &|m | Steffen Beyer (+49 89) 63812-244 fax -150 | | | | software design & management GmbH & Co. KG | | | | Thomas-Dehler-Str. 27, 81737 Munich, Germany.