Path: usenet.cise.ufl.edu!usenet.eel.ufl.edu!gatech!csulb.edu!hammer.uoregon.edu!news-xfer.netaxs.com!newsfeeds.sol.net!mr.net!visi.com!news.maxwell.syr.edu!news.bc.net!info.ucla.edu!nnrp.info.ucla.edu!psgrain!news.rain.net!news.teleport.com!not-for-mail
From:
[email protected] (Steffen Beyer)
Newsgroups: comp.lang.perl.announce,comp.lang.perl.modules
Subject: ANNOUNCE: Set-IntegerFast 3.1
Followup-To: comp.lang.perl.modules
Date: 22 Jan 1997 15:52:04 GMT
Organization: sd&m GmbH & Co. KG Munich, Germany
Lines: 325
Sender: -yp- @gadget.cscaper.com
Approved:
[email protected] (comp.lang.perl.announce)
Message-ID: <
[email protected]>
Reply-To:
[email protected] (Steffen Beyer)
NNTP-Posting-Host: gadget.cscaper.com
X-Disclaimer: The "Approved" header verifies header information for article transmission and does not imply approval of content.
Xref: usenet.cise.ufl.edu comp.lang.perl.announce:95 comp.lang.perl.modules:1433
I am sorry to have to announce ;-)
=========================================
Package "Set-IntegerFast" Version 3.1
=========================================
due to a little bug in version 3.0.
Contents of this message:
-------------------------
- Who should upgrade?
- Legal stuff
- Features
- Requirements
- What does it do
- Credits
- Where to find
- Final note
Who should upgrade?
-------------------
Anyone who encountered the error message
"Set::IntegerFast failed to auto-configure:
The types 'unit' and 'size_t' differ in size!"
when starting the module (first "use" after its build).
(This error causes all tests of "make test" to fail!)
This only applies to very few machines; for instance machines
with 64 bits of integer arithmetic and 64 bits of memory address
space.
Who never saw this error message on his machine will also never have
problems with this bug.
Legal stuff:
------------
Copyright (c) 1995, 1996, 1997 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.
Features:
---------
* "lib_set.c":
+ efficient (fast) handling of bit vectors and set operations,
auto-configuring for using machine word as basic storage unit
(most efficient!)
(C library, completely independent of Perl)
* "Set::IntegerFast":
+ efficient (fast) object-oriented methods for handling sets
of integers (intervals from zero to some positive integer)
(Perl XSUBs in C, uses "lib_set.c")
* "Set::IntegerRange":
+ object-oriented methods for handling sets of integers
(arbitrary intervals)
(in Perl, uses "Set::IntegerFast")
+ overloaded arithmetic and relational operators
for still more ease of use
(in Perl, uses first part of "Set::IntegerRange")
* "Math::MatrixBool":
+ object-oriented methods for handling matrices of booleans
(Boolean Algebra)
(in Perl, uses "Set::IntegerFast")
+ overloaded arithmetic and relational operators
for still more ease of use
(in Perl, uses first part of "Math::MatrixBool")
+ computes reflexive transitive closure using Kleene's
algorithm (essential for solving path-problem in graphs)
+ this is mainly an example application to help you build
your own (using "Set::IntegerFast")
* "Math::MatrixReal":
+ object-oriented methods for handling matrices of reals
(for demonstration purposes only)
(in Perl, independent stand-alone module)
+ overloaded arithmetic and relational operators
allow you to use this data type (almost) like
any other built-in Perl data type
+ features another implementation of Kleene's algorithm to
compute the minimal costs for all paths in a graph with
weighted edges (the "weights" being the costs associated
with each edge)
+ allows to solve linear equation systems using an efficient
algorithm known as "L-R-decomposition" and several approxi-
mative (iterative) methods
+ allows you to convert a matrix into a string (in a nice,
human-readable format) and to read it back in later (for
instance from a file!), or using the shell-like "here-
document" syntax (among other possibilities):
$matrix = Math::MatrixReal->new_from_string(<<"MATRIX");
[ 3 2 0 ]
[ 0 3 2 ]
[ $c1 $c2 $c3 ]
MATRIX
* "DFA::Kleene":
+ still another implementation of Kleene's algorithm to compute
the language accepted by a Deterministic Finite Automaton
(for demonstration purposes only)
(in Perl, independent stand-alone module)
* "Graph::Kruskal":
+ implementation of Kruskal's efficient algorithm for Minimal
Spanning Trees in graphs in O( n * ld(n) )
(for demonstration purposes only)
(in Perl, independent stand-alone module)
+ example of an algorithm relying heavily on sets which uses
a different (fascinating!) representation for sets than the
"Set::IntegerFast" module (see the Graph::Kruskal(3) man page!)
* "Kleene.pod":
+ a short introduction into the theory behind Kleene's algorithm
Requirements:
-------------
Perl version 5.000 or higher, a C compiler capable of the ANSI C standard (!)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
What does it do:
----------------
The base module of this package, "Set::IntegerFast", allows you to create
sets of arbitrary size (only limited by the size of a machine word and avai-
lable memory on your system) of an interval of positive integers starting
with zero, to dynamically change the size of such sets 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 module (negative indices are no obstacle), despite
the fact that only intervals of positive integers (from zero to some posi-
tive integer) are supported directly.
Please refer to the Set::IntegerFast(3) man page and the "Set::IntegerRange"
module to see how this can be done!
The module 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 module, however) is Kruskal's algorithm for
minimal spanning trees in graphs. (That algorithm is included in this dis-
tribution as a Perl module for those interested. Please refer to the
Graph::Kruskal(3) man page for more details!)
Another famous algorithm using sets is the "Seave of Erathostenes" for
calculating prime numbers, which is included here as a demo program
(see "Set/primes.pl").
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 library 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 module is primarily designed for efficiency and not for a
comfortable user interface (the latter can be added by additional modules,
as shown by the "Set::IntegerRange" and "Math::MatrixBool" modules).
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).
(Please refer to the "Set::IntegerRange" module in this package to see how!)
Sets in this module 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 module 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 anyway).
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 module (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 an
overview of the complexity of each method!
Note that the C library in this package ("lib_set.c") is designed in such
a way that it may be used independently from Perl and this Perl extension
module. (!)
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 module, all bounds and type checking (which should be absolutely
fool-proof, by the way!) is done in the XS subroutines.
For more details on the modules in this package, please refer to their
respective man pages!
Credits:
--------
Many special thanks to Larry Schwimmer <
[email protected]> for
reporting the bug related to 64 bit machines and finding where an implicit
assumption of 32 bit integers was hidden, and for testing the new version
on his machine!
Where to find:
--------------
At the usual ftp sites for Perl (CPAN = "Comprehensive Perl Archive Network"):
The file
Set-IntegerFast-3.1.tar.gz
can be found in directory
.../CPAN/authors/id/STBEY/
or
.../CPAN/modules/by-category/06_Data_Type_Utilities/Set/
or
.../CPAN/modules/by-module/Set/
(See "The Perl 5 Module List" by Tim Bunce and Andreas Koenig
in news:comp.lang.perl.modules for a list of CPAN ftp servers)
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:
[email protected] (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 <
[email protected]> (+49 89) 63812-244 fax -150
| | | | software design & management GmbH & Co. KG
| | | | Thomas-Dehler-Str. 27, 81737 Munich, Germany.
