=====================================
Package "Bit::Vector" Version 4.0
=====================================
for Perl version 5.000 and higher
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.
Contents of this file:
----------------------
- Where to find
- Legal stuff (-> LICENSE, ARTISTIC, COPYING)
- Prerequisites
- Installation (-> INSTALL)
- Changes over previous versions (-> CHANGES)
- This distribution contains
- What does it do
- Credits (-> CREDITS)
- Author's note
Where to find:
--------------
At any CPAN ftp site (CPAN = "Comprehensive Perl Archive Network"),
the file "Bit-Vector-4.0.tar.gz" can be found in any of the following
directories:
.../CPAN/authors/id/STBEY/
.../CPAN/modules/by-category/06_Data_Type_Utilities/Bit/
.../CPAN/modules/by-module/Bit/
To find a CPAN ftp site, you can either direct your web browser to
http://www.perl.com/CPAN/modules/by-module/Bit/Bit-Vector-4.0.tar.gz
(which will automatically redirect you to a CPAN ftp server near you) or
look into "The Perl 5 Module List" by Tim Bunce and Andreas Koenig either
on USENET in the "comp.lang.perl.modules" newsgroup or at
http://www.perl.com/CPAN/modules/00modlist.long.html
You can also download this module directly from the author's web site,
where you will also find my other modules and a couple of logos describing
what the modules do:
http://sb.fluomedia.org/download/
Legal stuff:
------------
Please see the file "LICENSE" in this distribution (and the associated files
"ARTISTIC" and "COPYING") for details about the exact terms under which this
package may be used and distributed.
Prerequisites:
--------------
Perl version 5.000 or higher, a C compiler capable of the ANSI C standard (!)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Installation:
-------------
Please see the file "INSTALL" in this distribution for instructions on how
to install this package.
Changes over previous versions:
-------------------------------
Please refer to the file "CHANGES" in this distribution for a list of new
features in and for instructions on how to adapt your existing applications
to this new version.
(Basically, you just need to change "Set::IntegerFast" into "Bit::Vector"
with a global text "search & replace".)
This distribution contains:
---------------------------
* a "BitVector" C library (can be used stand-alone!)
(files "Definitions.h" and "BitVector.c")
+ efficient (fast) handling of bit vectors and sets of
integers (and more)
+ determines the size of a machine word on your system
and automatically configures itself accordingly for
maximum speed of execution
* a "Bit::Vector" base class
(files "Vector.pm", "Vector.xs", "typemap", "BitVector.h",
"Definitions.h" and "BitVector.c")
+ efficient (fast) object-oriented methods for handling
bit vectors and sets of integers (intervals from zero
to some positive integer)
+ methods for converting bit vectors in strings and
vice-versa (supports "newsrc" style sets)
+ overloaded arithmetic and relational operators for
maximum comfort
* a "Set::IntegerFast" wrapper module
(file "lib/Set/IntegerFast.pm")
+ assures backward compatibility to previous versions
* a "Set::IntegerRange" application module
(file "lib/Set/IntegerRange.pm")
+ object-oriented methods for handling sets of integers
(arbitrary intervals)
+ overloaded arithmetic and relational operators for
maximum comfort
+ methods for converting sets in strings and
vice-versa
* a "Math::MatrixBool" application module
(file "lib/Math/MatrixBool.pm")
+ object-oriented methods for handling matrices of booleans
(Boolean Algebra)
+ overloaded arithmetic and relational operators for
maximum comfort
+ computes reflexive transitive closure using Kleene's
algorithm (essential for solving path-problem in graphs)
+ methods for converting matrices in strings and
vice-versa
+ matrix multiplication and closure are actually carried out
in the "Bit::Vector" module for maximum speed of execution
Related modules (NOT derived from the "Bit::Vector" base class):
* "Math::MatrixReal"
(file "lib/Math/MatrixReal.pm")
+ object-oriented methods for handling matrices of reals
+ overloaded arithmetic and relational operators for
maximum comfort
+ allows to solve linear equation systems using an
efficient algorithm known as "LR decomposition"
and several approximative (iterative) methods
+ features an implementation of Kleene's algorithm to
compute the minimal costs for all paths in a graph
with weighted edges
+ methods for converting matrices in strings and
vice-versa
* "DFA::Kleene"
(file "lib/DFA/Kleene.pm")
+ another implementation of Kleene's algorithm to compute
the language accepted by a Deterministic Finite Automaton
* "Math::Kleene"
(file "lib/Math/Kleene.pod")
+ a man page giving a brief introduction into the theory
behind Kleene's algorithm
* "Graph::Kruskal"
(file "lib/Graph/Kruskal.pm")
+ implementation of Kruskal's efficient algorithm
for Minimal Spanning Trees in graphs O( n * ld(n) )
+ example of an efficient algorithm relying heavily on sets
(with a different representation, though, not bit vectors)
What does it do:
----------------
The base class of this distribution, "Bit::Vector", allows you to create bit
vectors and sets of arbitrary size (only limited by the size of a machine
word and available memory on your system) with indices (= elements) in the
range from zero to some positive integer, to dynamically change the size of
such bit vectors or sets and to perform a broad range of basic operations on
them, like
- adding or removing elements (setting and clearing single bits),
- testing the presence of a certain element (testing a single bit),
- setting or clearing contiguous ranges of bits,
- detecting contiguous ranges of set bits,
- copying bit vectors,
- converting a bit vector into either a compact (hexadecimal) or a
human-readable string representation (allowing you to store bit
vectors in a file, for instance),
- reading in the contents of a bit vector from a string,
- comparing two bit vectors for equality and lexical order,
- performing bitwise shift and rotation operations,
- computing the union, intersection, difference, symmetric difference
or complement of sets,
- testing two sets for equality or inclusion (subset relationship),
- computing the minimum, the maximum and the norm (number of elements)
of a set,
and more.
Note also that it is very 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 positive
integer) are supported directly.
Please refer to the "Set::IntegerRange" module (also contained in this
distribution) and its man page to see how this can be done!
The "Bit::Vector" module is mainly intended for mathematical or algorithmical
computations. There are also a number of efficient algorithms that rely on
sets (and bit vectors).
An example of such an efficient algorithm (which uses a different
representation for sets, however, not bit vectors) is Kruskal's
algorithm for minimal spanning trees in graphs.
(See the module "Graph::Kruskal" and its man page in this distribution.)
Another famous algorithm using bit vectors is the "Seave of Erathostenes"
for calculating prime numbers, which is included here as a demo program
(see the file "primes.pl" in this distribution).
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, which is the
reason why most of its methods are implemented in C.
To increase execution speed, the module doesn't use bytes as its 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
ANSI 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 configuration
constants accordingly.
The greater the size of this basic storage unit, the better the complexity
(= execution speed) of the methods in this module (but also the greater the
average waste of unused bits in the last word).
Note that the C library of this package ("BitVector.c") is designed in such
a way that it can be used independently from Perl and this Perl extension
module. (!)
For this, you can use the file "BitVector.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 "Definitions.h" and
some system header files.)
Note however that this C library does not perform any bounds checking
whatsoever! (This is your application's duty!)
(See the respective explanation in the file "BitVector.c" for more details
and the file "Vector.xs" for an example of how this can be done!)
In this module, all bounds and type checking (which should be absolutely
fool-proof, BTW!) is done in the XSUB routines (in C).
For more details about the modules in this distribution, please refer to
their respective man pages!
Credits:
--------
Please refer to the file "CREDITS" in this distribution for a list of
contributors.
Author's 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 some e-mail:
sb@fluomedia.org (Steffen Beyer)
In fact I'd be glad if you could drop me a note if you are using this
package, so I can see how much interest exists in it and in which direction
it should be developed further.
Please tell me what you liked and what you disliked about this package!
Also, I would be very interested to know what your application is in
which you found this package to be useful! (Just in order to get an idea)
Many thanks in advance!
Share and enjoy!
Yours,
--
Steffen Beyer http://sb.fluomedia.org/
"There is enough for the need of everyone in this world,
but not for the greed of everyone." - Mahatma Gandhi