Ralf S. Engelschall > lcwa > Bit::Vector

Download:
lcwa-1.0.0.tar.gz

Dependencies

Annotate this POD

Related Modules

Math::BigInt
Date::Calc
Data::Dumper
Test::More
Math::BigFloat
Inline::C
Date::Manip
Rose::DB
Math::BigInt::GMP
XML::Parser
more...
By perlmonks.org

CPAN RT

New  3
Open  0
View/Report Bugs
Module Version: 4.2   Source  

NAME ^

Bit::Vector - bit vectors of arbitrary length (base class)

Versatile implementation of bit vectors of arbitrary length with efficient and easy-to-use methods for various applications, especially sets.

Base class for all applications and classes using bit vectors as their underlying data type.

Provides overloaded arithmetic and relational operators for maximum comfort.

For an analysis of the time complexity of the methods implemented in this module, please refer to the file "COMPLEXITY" in the "Bit::Vector" distribution directory!

SYNOPSIS ^

METHODS IMPLEMENTED IN C (fastest)

  Version
      $version = Bit::Vector::Version(); # version of "Vector.xs"

  new
      $vector = new Bit::Vector($elements);
      $vector = Bit::Vector->new($elements);
      $vector = $any_vector->new($elements);

  Resize
      $vector->Resize($elements);

  Size
      $elements = $vector->Size();

  Empty
      $vector->Empty();

  Fill
      $vector->Fill();

  Flip
      $vector->Flip();

  Interval_Empty
      $vector->Interval_Empty($min,$max);

  Interval_Fill
      $vector->Interval_Fill($min,$max);

  Interval_Flip
      $vector->Interval_Flip($min,$max);

  Interval_Scan_inc
      while (($min,$max) = $vector->Interval_Scan_inc($start))

  Interval_Scan_dec
      while (($min,$max) = $vector->Interval_Scan_dec($start))

  Bit_Off
      $vector->Bit_Off($index);
      $vector->Delete($index);           # (deprecated)

  Bit_On
      $vector->Bit_On($index);
      $vector->Insert($index);           # (deprecated)

  bit_flip
      $bit = $vector->bit_flip($index);
      if ($vector->bit_flip($index))
      $bit = $vector->flip($index);      # (deprecated)
      if ($vector->flip($index))         # (deprecated)

  bit_test
      $bit = $vector->bit_test($index);
      if ($vector->bit_test($index))
      $bit = $vector->contains($index);
      if ($vector->contains($index))
      $bit = $vector->in($index);        # (deprecated)
      if ($vector->in($index))           # (deprecated)

  is_empty
      if ($vector->is_empty())

  is_full
      if ($vector->is_full())

  equal
      if ($vector1->equal($vector2))

  lexorder
      if ($vector1->lexorder($vector2))

  Compare
      $cmp = $vector1->Compare($vector2);

  Copy
      $vector1->Copy($vector2);

  rotate_left
      $carry_out = $vector->rotate_left();

  rotate_right
      $carry_out = $vector->rotate_right();

  shift_left
      $carry_out = $vector->shift_left($carry_in);

  shift_right
      $carry_out = $vector->shift_right($carry_in);

  Move_Left
      $vector->Move_Left($bits);

  Move_Right
      $vector->Move_Right($bits);

  increment
      $carry = $vector->increment();

  decrement
      $carry = $vector->decrement();

  to_String
      $string = $vector->to_String();    # e.g., "A08A28AC"

  from_string
      $ok = $vector->from_string($string);

  Union
      $set1->Union($set2,$set3);         # in-place is possible!

  Intersection
      $set1->Intersection($set2,$set3);  # in-place is possible!

  Difference
      $set1->Difference($set2,$set3);    # in-place is possible!

  ExclusiveOr
      $set1->ExclusiveOr($set2,$set3);   # in-place is possible!

  Complement
      $set1->Complement($set2);          # in-place is possible!

  subset
      if ($set1->subset($set2))
      if ($set1->inclusion($set2))       # (deprecated)

  Norm
      $norm = $set->Norm();

  Min
      $min = $set->Min();

  Max
      $max = $set->Max();

  Multiplication
      $matrix1->Multiplication($rows1,$cols1,
      $matrix2,$rows2,$cols2,
      $matrix3,$rows3,$cols3);

  Closure
      $matrix->Closure($rows,$cols);

METHODS IMPLEMENTED IN PERL

  Version
      $version = $Bit::Vector::VERSION;  # version of "Vector.pm"

  Shadow
      $other_vector = $some_vector->Shadow();

  Clone
      $twin_vector = $some_vector->Clone();

  new_from_String
      eval { $vector = Bit::Vector->new_from_String($string); };

  to_ASCII
      $string = $vector->to_ASCII();     # e.g., "2,3,5-7,11,13-19"

  from_ASCII
      eval { $vector->from_ASCII($string); };

OVERLOADED OPERATORS (slowest)

      # "$index" is a number or a Perl scalar variable containing a
      # number which represents the set containing only that element:

  Emptyness
      if ($vector) # if not empty
      if (! $vector) # if empty
      unless ($vector) # if empty

  Equality
      if ($vector1 == $vector2)
      if ($vector1 != $vector2)
      if ($vector == $index)
      if ($vector != $index)

  Lexical Comparison
      $cmp = $vector1 cmp $vector2;
      if ($vector1 lt $vector2)
      if ($vector1 le $vector2)
      if ($vector1 gt $vector2)
      if ($vector1 ge $vector2)
      if ($vector1 eq $vector2)
      if ($vector1 ne $vector2)
      $cmp = $vector cmp $index;
      if ($vector lt $index)
      if ($vector le $index)
      if ($vector gt $index)
      if ($vector ge $index)
      if ($vector eq $index)
      if ($vector ne $index)

  Move Left
      $vector1 = $vector2 << $bits;
      $vector <<= $bits;

  Move Right
      $vector1 = $vector2 >> $bits;
      $vector >>= $bits;

  Increment
      ++$vector;
      $vector++;

  Decrement
      --$vector;
      $vector--;

  String Conversion
      $string = "$vector";
      print "\$vector = '$vector'\n";

  Union
      $set1 = $set2 + $set3;
      $set1 += $set2;
      $set1 = $set2 | $set3;
      $set1 |= $set2;
      $vector1 = $vector2 + $index;
      $vector += $index;
      $vector1 = $vector2 | $index;
      $vector |= $index;

  Intersection
      $set1 = $set2 * $set3;
      $set1 *= $set2;
      $set1 = $set2 & $set3;
      $set1 &= $set2;
      $vector1 = $vector2 * $index;
      $vector *= $index;
      $vector1 = $vector2 & $index;
      $vector &= $index;

  Difference
      $set1 = $set2 - $set3;
      $set1 -= $set2;
      $set1 = $set2 - $set1;
      $vector1 = $vector2 - $index;
      $vector1 = $index - $vector2;
      $vector -= $index;

  ExclusiveOr
      $set1 = $set2 ^ $set3;
      $set1 ^= $set2;
      $vector1 = $vector2 ^ $index;
      $vector ^= $index;

  Complement
      $set1 = -$set2;
      $set1 = ~$set2;
      $set = -$set;
      $set = ~$set;

  Subset Relationship
      if ($set1 <= $set2)

  True Subset Relationship
      if ($set1 < $set2)

  Superset Relationship
      if ($set1 >= $set2)

  True Superset Relationship
      if ($set1 > $set2)

  Norm
      $norm = abs($set);

IMPORTANT NOTES ^

GENERAL HINTS

METHODS IMPLEMENTED IN C

METHODS IMPLEMENTED IN PERL

OVERLOADED OPERATORS

DESCRIPTION ^

This class 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 Set::IntegerRange(3) 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 Graph::Kruskal(3) in this distribution.)

Another famous algorithm using bit vectors is the "Sieve 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!

SEE ALSO ^

Set::IntegerFast(3), Set::IntegerRange(3), Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3).

perl(1), perlsub(1), perlmod(1), perlref(1), perlobj(1), perlbot(1), perltoot(1), perlxs(1), perlxstut(1), perlguts(1), overload(3).

VERSION ^

This man page documents "Bit::Vector" version 4.2.

AUTHOR ^

Steffen Beyer <sb@sdm.de>.

COPYRIGHT ^

Copyright (c) 1995, 1996, 1997 by Steffen Beyer. All rights reserved.

LICENSE ^

This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

syntax highlighting: