lib/bitvector/README.txt

   1                     =====================================
   2                       Package "Bit::Vector" Version 6.4
   3                     =====================================
   4
   5
   6 This package is available for download either from my web site at
   7
   8                   http://www.engelschall.com/u/sb/download/
   9
  10 or from any CPAN (= "Comprehensive Perl Archive Network") mirror server:
  11
  12                http://www.perl.com/CPAN/authors/id/S/ST/STBEY/
  13
  14
  15 Abstract:
  16 ---------
  17
  18 Bit::Vector is an efficient C library which allows you to handle
  19 bit vectors, sets (of integers), "big integer arithmetic" and
  20 boolean matrices, all of arbitrary sizes.
  21
  22 The library is efficient (in terms of algorithmical complexity)
  23 and therefore fast (in terms of execution speed) for instance
  24 through the widespread use of divide-and-conquer algorithms.
  25
  26 The package also includes an object-oriented Perl module for
  27 accessing the C library from Perl, and optionally features
  28 overloaded operators for maximum ease of use.
  29
  30 The C library can nevertheless be used stand-alone, without Perl.
  31
  32
  33 What's new in version 6.4:
  34 --------------------------
  35
  36  +  Added compiler directives for C++.
  37  +  Improved the method "Norm()".
  38  +  Removed "Carp::Clan" from the distribution (available separately).
  39  +  Added "Bit::Vector::String" for generic string import/export functions.
  40  +  Added a new test file "t/40__auxiliary.t" for "Bit::Vector::String".
  41  +  Fixed a bug in method "Copy()" concerning sign (MSB) extension.
  42
  43
  44 Legal issues:
  45 -------------
  46
  47 This package with all its parts is
  48
  49 Copyright (c) 1995 - 2004 by Steffen Beyer.
  50 All rights reserved.
  51
  52 This package is free software; you can use, modify and redistribute
  53 it under the same terms as Perl itself, i.e., under the terms of
  54 the "Artistic License" or the "GNU General Public License".
  55
  56 The C library at the core of this Perl module can additionally
  57 be used, modified and redistributed under the terms of the
  58 "GNU Library General Public License".
  59
  60 Please refer to the files "Artistic.txt", "GNU_GPL.txt" and
  61 "GNU_LGPL.txt" in this distribution, respectively, for details!
  62
  63
  64 Prerequisites:
  65 --------------
  66
  67 Perl version 5.000 or higher, and an ANSI C compiler. (!)
  68                                      ^^^^^^
  69 Module "Carp::Clan" version 5.0 or higher.
  70
  71 Note that in order to compile Perl modules which contain
  72 C (and/or XS) code (such as this one), you always HAVE
  73 to use the very same compiler your Perl itself was compiled
  74 with.
  75
  76 Many vendors nowadays ship their operating system already
  77 comprising a precompiled version of Perl. Many times the
  78 compilers used to compile this version of Perl are not
  79 available to or not usually used by the users of these
  80 operating systems.
  81
  82 In such cases building this module (or any other Perl
  83 module containing C and/or XS code) will not work. You
  84 will either have to get the compiler which was used to
  85 compile Perl itself (see for example the section "Compiler:"
  86 in the output of the command "perl -V"), or to build
  87 your own Perl with the compiler of your choice (which
  88 also allows you to take advantage of the various compile-
  89 time switches Perl offers).
  90
  91 Note that Sun Solaris and Red Hat Linux frequently were
  92 reported to suffer from this kind of problem.
  93
  94 Moreover, you usually cannot build any modules under
  95 Windows 95/98 since the Win 95/98 command shell doesn't
  96 support the "&&" operator. You will need the Windows NT
  97 command shell ("cmd.exe") or the "4DOS" shell to be
  98 installed on your Windows 95/98 system first. Note that
  99 Windows NT and Windows 2000 are not affected and just
 100 work fine. I don't know about Windows XP, however.
 101
 102 Note that ActiveState provides precompiled binaries of
 103 this module for their Win32 port of Perl ("ActivePerl")
 104 on their web site, which you should be able to install
 105 simply by typing "ppm install Bit-Vector" in your MS-DOS
 106 command shell (but note the "-" instead of "::" in the
 107 package name!). This also works under Windows 95/98 (!).
 108
 109 If your firewall prevents "ppm" from downloading
 110 this package, you can also download it manually from
 111 http://www.activestate.com/ppmpackages/5.005/zips/ or
 112 http://www.activestate.com/ppmpackages/5.6/zips/.
 113 Follow the installation instructions included in
 114 the "zip" archive.
 115
 116
 117 Note to CPAN Testers:
 118 ---------------------
 119
 120 After completion, version 6.4 of this module has already
 121 been tested successfully with the following configurations:
 122
 123   Perl 5.005_03  -  FreeBSD 4.1.1-RELEASE (with "dlopen() relative paths" patch)
 124   Perl 5.6.0     -  FreeBSD 4.1.1-RELEASE
 125   Perl 5.6.1     -  FreeBSD 4.1.1-RELEASE
 126   Perl 5.7.0     -  FreeBSD 4.1.1-RELEASE
 127   Perl 5.7.1     -  FreeBSD 4.1.1-RELEASE
 128   Perl 5.7.2     -  FreeBSD 4.1.1-RELEASE
 129   Perl 5.8.0     -  FreeBSD 4.1.1-RELEASE
 130   Perl 5.8.4     -  FreeBSD 4.10-BETA
 131   Perl 5.8.0     -  Windows 2000 & MS VC++ 6.0 (native Perl build)
 132
 133
 134 Installation:
 135 -------------
 136
 137 Please see the file "INSTALL.txt" in this distribution for instructions
 138 on how to install this package.
 139
 140 It is essential that you read this file since one of the special cases
 141 described in it might apply to you, especially if you are running Perl
 142 under Windows.
 143
 144
 145 Changes over previous versions:
 146 -------------------------------
 147
 148 Please refer to the file "CHANGES.txt" in this distribution for a more
 149 detailed version history log.
 150
 151
 152 Documentation:
 153 --------------
 154
 155 The documentation of this package is included in POD format (= "Plain
 156 Old Documentation") in the files with the extension ".pod" in this
 157 distribution, the human-readable markup-language standard for Perl
 158 documentation.
 159
 160 By building this package, this documentation will automatically be
 161 converted into man pages, which will automatically be installed in
 162 your Perl tree for further reference through the installation process,
 163 where they can be accessed by the commands "man Bit::Vector" (Unix)
 164 and "perldoc Bit::Vector" (Unix and Win32 alike), for example.
 165
 166 Available man pages:
 167
 168     Bit::Vector(3)
 169     Bit::Vector::Overload(3)
 170     Bit::Vector::String(3)
 171
 172 If Perl is not available on your system, you can also read the ".pod"
 173 files
 174
 175     ./Vector.pod
 176     ./lib/Bit/Vector/Overload.pod
 177     ./lib/Bit/Vector/String.pod
 178
 179 directly.
 180
 181
 182 What does it do:
 183 ----------------
 184
 185 This package implements bit vectors of arbitrary size and provides efficient
 186 methods for handling them.
 187
 188 This goes far beyond the built-in capabilities of Perl for handling bit
 189 vectors (compare with the method list below!).
 190
 191 Moreover, the C core of this package can be used "stand-alone" in other
 192 C applications; Perl is not necessarily required.
 193
 194 The main module of this package is intended to serve as a base class for
 195 other applications or application classes, such as implementing sets or
 196 performing big integer arithmetic.
 197
 198 All methods are implemented in C internally for maximum performance.
 199
 200 An add-on module (named "Bit::Vector::Overload") provides overloaded
 201 arithmetic and relational operators for maximum ease of use (Perl only).
 202
 203 Note that there is (of course) a little speed penalty to pay for
 204 overloaded operators. If speed is crucial, use the "Bit::Vector"
 205 module alone!
 206
 207 Another module, "Bit::Vector::String", offers additional methods
 208 for generic string export and import (also Perl only).
 209
 210 This package is useful for a large range of different tasks:
 211
 212   -  For example for implementing sets and performing set operations
 213      (like union, difference, intersection, complement, check for subset
 214      relationship etc.),
 215
 216   -  as a basis for many efficient algorithms, for instance the
 217      "Sieve of Erathostenes" (for calculating prime numbers),
 218
 219      (The complexities of the methods in this package are usually either
 220       O(1) or O(n/b), where "b" is the number of bits in a machine word
 221       on your system.)
 222
 223   -  for shift registers of arbitrary length (for example for cyclic
 224      redundancy checksums),
 225
 226   -  to calculate "look-ahead", "first" and "follow" character sets
 227      for parsers and compiler-compilers,
 228
 229   -  for graph algorithms,
 230
 231   -  for efficient storage and retrieval of status information,
 232
 233   -  for performing text synthesis ruled by boolean expressions,
 234
 235   -  for "big integer" arithmetic with arbitrarily large integers,
 236
 237   -  for manipulations of chunks of bits of arbitrary size,
 238
 239   -  for bitwise processing of audio CD wave files,
 240
 241   -  to convert formats of data files,
 242
 243 and more.
 244
 245 (A number of example applications is available from my web site at
 246 http://www.engelschall.com/u/sb/download/.)
 247
 248 A large number of import/export methods allow you to access individual
 249 bits, contiguous ranges of bits, machine words, arbitrary chunks of
 250 bits, lists (arrays) of chunks of bits or machine words and a whole
 251 bit vector at once (for instance for blockwrite/-read to and from
 252 a file).
 253
 254 You can also import and export the contents of a bit vector in binary,
 255 hexadecimal and decimal representation as well as ".newsrc" style
 256 enumerations.
 257
 258 Note that this package is specifically designed for efficiency, which is
 259 also the reason why its methods are implemented in C.
 260
 261 To further increase execution speed, the package doesn't use bytes as its
 262 basic storage unit, but rather uses machine words, assuming that a machine
 263 word is the most efficiently handled size of all scalar types on all
 264 machines (that's what the ANSI C standard proposes and assumes anyway).
 265
 266 In order to achieve this, it automatically determines the number of bits
 267 in a machine word on your system and then adjusts its internal configuration
 268 constants accordingly.
 269
 270 The greater the size of this basic storage unit, the better the complexity
 271 (= execution speed) of the methods in this package, but also the greater the
 272 average waste of unused bits in the last word.
 273
 274 The range of available methods is exceptionally large for this kind of library;
 275 in detail:
 276
 277 Version()                Word_Bits()              Long_Bits()
 278 new()                    new_Hex()                new_Bin()
 279 new_Dec()                new_Enum()               Shadow()
 280 Clone()                  Concat()                 Concat_List()
 281 Size()                   Resize()                 Copy()
 282 Empty()                  Fill()                   Flip()
 283 Primes()                 Reverse()                Interval_Empty()
 284 Interval_Fill()          Interval_Flip()          Interval_Reverse()
 285 Interval_Scan_inc()      Interval_Scan_dec()      Interval_Copy()
 286 Interval_Substitute()    is_empty()               is_full()
 287 equal()                  Lexicompare()            Compare()
 288 to_Hex()                 from_Hex()               to_Bin()
 289 from_Bin()               to_Dec()                 from_Dec()
 290 to_Enum()                from_Enum()              Bit_Off()
 291 Bit_On()                 bit_flip()               bit_test()
 292 Bit_Copy()               LSB()                    MSB()
 293 lsb()                    msb()                    rotate_left()
 294 rotate_right()           shift_left()             shift_right()
 295 Move_Left()              Move_Right()             Insert()
 296 Delete()                 increment()              decrement()
 297 inc()                    dec()                    add()
 298 subtract()               Negate()                 Absolute()
 299 Sign()                   Multiply()               Divide()
 300 GCD()                    Power()                  Block_Store()
 301 Block_Read()             Word_Size()              Word_Store()
 302 Word_Read()              Word_List_Store()        Word_List_Read()
 303 Word_Insert()            Word_Delete()            Chunk_Store()
 304 Chunk_Read()             Chunk_List_Store()       Chunk_List_Read()
 305 Index_List_Remove()      Index_List_Store()       Index_List_Read()
 306 Union()                  Intersection()           Difference()
 307 ExclusiveOr()            Complement()             subset()
 308 Norm()                   Min()                    Max()
 309 Multiplication()         Product()                Closure()
 310 Transpose()
 311
 312
 313 Note to C developers:
 314 ---------------------
 315
 316 Note again that the C library at the core of this module can also be
 317 used stand-alone (i.e., it contains no inter-dependencies whatsoever
 318 with Perl).
 319
 320 The library itself consists of three files: "BitVector.c", "BitVector.h"
 321 and "ToolBox.h".
 322
 323 Just compile "BitVector.c" (which automatically includes "ToolBox.h")
 324 and link the resulting output file "BitVector.o" with your application,
 325 which in turn should include "ToolBox.h" and "BitVector.h" (in this order).
 326
 327
 328 Example applications:
 329 ---------------------
 330
 331 See the module "Set::IntRange" for an easy-to-use module for sets
 332 of integers within arbitrary ranges.
 333
 334 See the module "Math::MatrixBool" for an efficient implementation
 335 of boolean matrices and boolean matrix operations.
 336
 337 (Both modules are also available from my web site at
 338 http://www.engelschall.com/u/sb/download/ or any CPAN server.)
 339
 340 See the file "SetObject.pl" in the "examples" subdirectory of this
 341 distribution for a way to emulate the "Set::Object" module from CPAN
 342 using "Bit::Vector" - this is a way to perform set operations on sets
 343 of arbitrary objects (any Perl objects or Perl data structures you want!).
 344
 345 An application relying crucially on this "Bit::Vector" module is "Slice",
 346 a tool for generating different document versions out of a single
 347 master file, ruled by boolean expressions ("include english version
 348 of text plus examples but not ...").
 349
 350 (See also http://www.engelschall.com/sw/slice/.)
 351
 352 This tool is itself part of another tool, "Website META Language" ("WML"),
 353 which allows you to generate and maintain large web sites.
 354
 355 Among many other features, it allows you to define your own HTML tags which
 356 will be expanded either at generation or at run time, depending on your
 357 choice.
 358
 359 (See also http://www.engelschall.com/sw/wml/.)
 360
 361 Both tools are written by Ralf S. Engelschall.
 362
 363
 364 Credits:
 365 --------
 366
 367 Please refer to the file "CREDITS.txt" in this distribution for a list
 368 of contributors.
 369
 370
 371 Author's note:
 372 --------------
 373
 374 If you have any questions, suggestions or need any assistance, please
 375 let me know!
 376
 377 Please do send feedback, this is essential for improving this module
 378 according to your needs!
 379
 380 I hope you will find this module useful. Enjoy!
 381
 382 Yours,
 383 --
 384   Steffen Beyer <sb@engelschall.com> http://www.engelschall.com/u/sb/
 385   "There is enough for the need of everyone in this world, but not
 386    for the greed of everyone." - Mohandas Karamchand "Mahatma" Gandhi