Algorithm-BitVector
view release on metacpan or search on metacpan
lib/Algorithm/BitVector.pm view on Meta::CPAN
sub _iter {
my $self = shift;
my $pos = 0;
$self->{_iterator} = BitVecIterator->new($self, $pos) unless $self->{_iter_called};
&{$self->{_iterator}->next()};
}
{
# This inner class needed for implementing iterator overloading:
package BitVecIterator;
sub new {
my $self = [ $_[1], $_[2] ];
bless $self, $_[0];
$_[1]->{_iter_called} = 1;
return $self;
}
sub next {
my $self = shift;
my $bitvec = $self->[0];
# The anonymous subroutine that follows is a closure over the variables
# incorporated in it:
return sub {
if ($self->[1] >= $bitvec->{size}) {
delete $bitvec->{_iter_called};
return;
}
my $bit = $bitvec->get_bit($self->[1]);
$self->[1] = $self->[1] + 1;
return $bit;
}
}
}
# for the overloading of the numification operator:
sub _int {
my $self = shift;
return $self->int_value();
}
## Divides an even-sized bitvector into two and returns the two halves as a
## list of two bitvectors.
sub divide_into_two {
my $self = shift;
die "Abort: The divide_into_two() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
die "The bitvector to be divided must have even number of bits: $!"
if $self->{size} % 2;
my @outlist1 = ();
foreach my $i (0..$self->{size} / 2 - 1) {
push @outlist1, $self->get_bit($i);
}
my @outlist2 = ();
foreach my $i ( ($self->{size} / 2) .. ($self->{size} - 1) ) {
push @outlist2, $self->get_bit($i);
}
return Algorithm::BitVector->new( bitlist => \@outlist1 ),
Algorithm::BitVector->new( bitlist => \@outlist2 );
}
## Permute a bitvector according to the indices shown in the second argument list.
## Return the permuted bitvector as a new bitvector.
sub permute {
my $self = shift;
die "Abort: The permute() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $permute_list = shift;
die "Bad permutation index in your permutation list"
if max(@$permute_list) > $self->{size} - 1;
my @outlist = ();
foreach my $index (@$permute_list) {
push @outlist, $self->get_bit($index);
}
return Algorithm::BitVector->new( bitlist => \@outlist );
}
## Unpermute the bitvector according to the permutation list supplied as the
## second argument. If you first permute a bitvector by using permute() and
## then unpermute() it using the same permutation list, you will get back the
## original bitvector.
sub unpermute {
my $self = shift;
die "Abort: The unpermute() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $permute_list = shift;
die "Bad permutation index in your permutation list: $!"
if max(@$permute_list) > $self->{size} - 1;
die "Size of the permute list for unpermuting not consistent with the size of the bet vector:$!"
unless $self->{size} == @$permute_list;
my $out_bv = Algorithm::BitVector->new( size => $self->{size} );
foreach my $i (0..@$permute_list-1) {
$out_bv->set_bit( $permute_list->[$i], $self->get_bit($i) );
}
return $out_bv;
}
## Write the bitvector to the file object file_out. (A file object is returned
## by a call to open()). Since all file I/O is byte oriented, the bitvector must
## be multiple of 8 bits. Each byte treated as MSB first (0th index).
sub write_to_file {
my $self = shift;
die "Abort: The write_to_file() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $file_out = shift;
my $err_str = "Only a bitvector whose length is a multiple of 8 can " .
"be written to a file. Use the padding functions to satisfy " .
"this constraint.";
$self->{FILEOUT} = $file_out unless $self->{FILEOUT};
die $err_str if $self->{size} % 8;
for my $byte (0..$self->{size}/8 - 1){
my $value = 0;
foreach my $bit (0..7) {
$value += $self->get_bit( $byte*8+(7 - $bit) ) << $bit;
}
syswrite $file_out, chr($value), 1;
}
}
## For closing a file object that was used for reading the bits into one or more
## BitVector objects.
sub close_file_handle {
my $self = shift;
die "Abort: The close_file_handle() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
die "No open file currently associated with the file handle: $!"
unless $self->{FILEIN};
close $self->{FILEIN};
}
## Return the integer value of a bitvector. If the original integer from which the
## bitvector was constructed is a Math::BigInt object, then return the string
## representation of the integer value.
sub int_value {
my $self = shift;
die "Abort: The int() method invoked on an object that is " .
lib/Algorithm/BitVector.pm view on Meta::CPAN
my $new_str = "$self" . ('0' x $n);
my $new_bitvec = Algorithm::BitVector->new( bitstring => $new_str );
$self->{size} = length $new_str;
$self->{_vector} = $new_bitvec->{_vector};
return $self;
}
## Resets a previously created BitVector to either all zeros or all ones
## depending on the argument val.
sub reset {
my $self = shift;
my $val = shift;
die "Incorrect argument to reset(): $!" unless ($val == 0) or ($val == 1);
my $reset_bv = Algorithm::BitVector->new( bitstring => ("$val" x $self->{size}) );
$self->{_vector} = $reset_bv->{_vector};
}
## Return the number of bits set in a BitVector instance.
sub count_bits {
my $self = shift;
return reduce {$a + $b} split //, "$self";
}
## Changes the bit pattern associated with a previously constructed BitVector
## instance. The allowable modes for changing the internally stored bit pattern
## are the same as for the constructor.
sub set_value {
my $self = shift;
my $reset_bv = Algorithm::BitVector->new( @_ );
$self->{_vector} = $reset_bv->{_vector};
$self->{size} = $reset_bv->{size};
}
## This method for counting the set bits is much faster for sparse bitvectors.
## Note, however, that count_bits() may work much faster for dense-packed
## bitvectors.
sub count_bits_sparse {
my $self = shift;
my $num = 0;
foreach my $intval (@{$self->{_vector}}) {
next if $intval == 0;
my ($c, $iv) = (0, $intval);
while ($iv > 0) {
$iv = $iv & ($iv - 1);
$c++;
}
$num += $c;
}
return $num;
}
## Computes the Jaccard similarity coefficient between two bitvectors
sub jaccard_similarity {
my $self = shift;
my $other = shift;
die "Jaccard called on two zero vectors --- NOT ALLOWED: $!"
if (int($self) == 0) && (int($other) == 0);
die "Jaccard called on vectors of unequal size --- NOT ALLOWED: $!"
if $self->{size} != $other->{size};
my $intersection = $self & $other;
my $union = $self | $other;
return $intersection->count_bits_sparse() / $union->count_bits_sparse();
}
## Computes the Jaccard distance between two bitvectors
sub jaccard_distance {
my $self = shift;
my $other = shift;
die "Jaccard called on vectors of unequal size --- NOT ALLOWED: $!"
if $self->{size} != $other->{size};
return 1 - $self->jaccard_similarity( $other );
}
## Computes the Hamming distance between two bitvectors
sub hamming_distance {
my $self = shift;
my $other = shift;
die "hamming_distance() called on vectors of unequal size --- NOT ALLOWED: $!"
if $self->{size} != $other->{size};
my $diff = $self ^ $other;
return $diff->count_bits_sparse();
}
## This method calculates the position of the next set bit at or after the current
## position index. It returns -1 if there is no next set bit. Logic based on the
## contributions by Jason Allum and John Gleeson to the Python version of this
## module.
sub next_set_bit {
my $self = shift;
my $from_index = shift || 0;
die "The from_index must be nonnegative: $!" unless $from_index >= 0;
my $i = $from_index;
my $v = $self->{_vector};
my $l = scalar @$v;
my $o = $i >> 4;
my $s = $i & 0x0F;
$i = $o << 4;
while ($o < $l) {
my $h = $v->[$o];
if ($h) {
$i += $s;
my $m = 1 << $s;
while ($m != (1 << 0x10)) {
return $i if $h & $m;
$m <<= 1;
$i += 1;
}
} else {
$i += 0x10;
}
$s = 0;
$o += 1;
}
return -1;
}
## For a bit that is set at the argument 'position', this method returns how many
## bits are set to the left of that bit. For example, in the bit pattern
## 000101100100, a call to this method with position set to 9 will return 4.
sub rank_of_bit_set_at_index {
my $self = shift;
my $position = shift;
lib/Algorithm/BitVector.pm view on Meta::CPAN
if (($remainder_highest_power < $mod_highest_power) or (int($remainder) == 0)) {
last;
} else {
my $exponent_shift = $remainder_highest_power - $mod_highest_power;
$quotient->set_bit($quotient->{size} - $exponent_shift - 1, 1);
my $quotient_mod_product = $mod->deep_copy();
$quotient_mod_product->pad_from_left($remainder->{size} - $mod->{size});
$quotient_mod_product->shift_left($exponent_shift);
$remainder ^= $quotient_mod_product;
}
}
if ($remainder->{size} > $n) {
$remainder = Algorithm::BitVector->new(
# bitlist => $remainder->get_bit([$remainder->{size}-$n .. $remainder->{size}-1]));
bitlist => $remainder->get_bit([$remainder->{size}-$n .. $remainder->{size}]));
}
return ($quotient, $remainder);
}
## Multiplies a bitvector with the bitvector b in GF(2^n) finite field with the
## modulus bit pattern set to mod
sub gf_multiply_modular {
my $self = shift;
my $b = shift;
my $mod = shift;
my $n = shift;
my $a_copy = $self->deep_copy();
my $b_copy = $b->deep_copy();
my $product = $a_copy->gf_multiply($b_copy);
my ($quotient, $remainder) = $product->gf_divide_by_modulus($mod, $n);
return $remainder
}
## Returns the multiplicative inverse of a vector in the GF(2^n) finite field
## with the modulus polynomial set to mod
sub gf_MI {
my $num = shift;
my $mod = shift;
my $n = shift;
my ($NUM, $MOD) = ($num->deep_copy(), $mod->deep_copy());
my $x = Algorithm::BitVector->new( size => $mod->{size} );
my $x_old = Algorithm::BitVector->new( intVal => 1, size => $mod->{size} );
my $y = Algorithm::BitVector->new( intVal => 1, size => $mod->{size} );
my $y_old = Algorithm::BitVector->new( size => $mod->{size} );
my ($quotient, $remainder);
while (int($mod)) {
($quotient, $remainder) = $num->gf_divide_by_modulus($mod, $n);
($num, $mod) = ($mod, $remainder);
($x, $x_old) = ($x_old ^ $quotient->gf_multiply($x), $x);
($y, $y_old) = ($y_old ^ $quotient->gf_multiply($y), $y);
}
if (int($num) != 1) {
return "NO MI. However, the GCD of $NUM and $MOD is $num\n";
} else {
my $z = $x_old ^ $MOD;
($quotient, $remainder) = $z->gf_divide_by_modulus($MOD, $n);
return $remainder;
}
}
## Returns a list of the consecutive runs of 1's and 0's in the bitvector.
## Each run is either a string of all 1's or a string of all 0's.
sub runs {
my $self = shift;
die "An empty vector has no runs" if $self->{size} == 0;
my @allruns = ();
my $run = '';
my $previous_bit = $self->get_bit(0);
if ($previous_bit == 0) {
$run = '0';
} else {
$run = '1';
}
my @bitlist = split //, "$self";
shift @bitlist;
foreach my $bit (@bitlist) {
if (($bit == 0) && ($previous_bit == 0)) {
$run .= '0';
} elsif (($bit == 1) && ($previous_bit == 0)) {
push @allruns, $run;
$run = '1';
} elsif (($bit == 0) && ($previous_bit == 1)) {
push @allruns, $run;
$run = '0';
} else {
$run .= '1';
}
$previous_bit = $bit;
}
push @allruns, $run;
return @allruns
}
## This method returns the "canonical" form of a BitVector instance that is obtained by
## circularly rotating the bit pattern through all possible shifts and returning the
## pattern with the maximum number of leading zeros. This is also the minimum int value
## version of a bit pattern. This method is useful in the "Local Binary Pattern"
## algorithm for characterizing image textures. If you are curious as to how, see my
## tutorial on "Measuring Texture and Color in Images."
sub min_canonical {
my $self = shift;
my @intvals_for_circular_shifts = map {int($self << 1)} 0 .. $self->length();
my $min_int_val = min @intvals_for_circular_shifts;
return Algorithm::BitVector->new( intVal => $min_int_val, size => $self->length() );
}
## Check if the integer value of the bitvector is a prime through the Miller-Rabin
## probabilistic test of primality. If not found to be a composite, estimate the
## probability of the bitvector being a prime using this test.
sub test_for_primality {
my $p = int(shift);
die "\nThe primality test method test_for_primality() is intended for only " .
"small integers --- integers that are relatively small in relation to " .
"the largest integer that can fit Perl's 4-byte int representation:$!"
if $p > 0x7f_ff_ff_ff;
return "is NOT a prime" if $p == 1;
my @probes = (2,3,5,7,11,13,17);
foreach my $a (@probes) {
return "is a prime" if $a == $p;
}
return "is NOT a prime" if any {$p % $_ == 0} @probes;
lib/Algorithm/BitVector.pm view on Meta::CPAN
for cryptography and hash functions.
This module stores the bits of a bitvector in 16-bit unsigned shorts. As you can see
in the constructor code for C<new()>, after resolving the arguments with which the
constructor is called, the very first thing the constructor does is to figure out how
many of those 2-byte shorts it needs for the bits. That does not imply that the size
of a bit array that is stored in a bitvector must be a multiple of 16. B<A bitvector
can be of any size whatsoever.> The C<Algorithm::BitVector> class keeps track of the
number of bits through its C<size> instance variable.
Note that, except for one case, the constructor must be called with a single keyword
argument, which determines how the bitvector will be constructed. The single
exception to this rule is for the keyword argument C<intVal> which you would normally
use for constructing a bitvector from an integer. The additional option you can
supply with C<intVal> is C<size>. When both C<intVal> and C<size> are specified in a
constructor call, you get a bitvector of the specified size provided the value
supplied for C<size> is larger than what it takes to accommodate the bits for the
C<intVal> integer.
In addition to constructing bitvectors from integers, this module can also construct
bitvectors from bit strings, from ASCII text strings, from hex strings, from a list
of bits, and from the contents of a file. With regards to constructing bitvectors
from integers, the module can construct very large bitvectors from very large
integers stored as C<Math::BigInt> objects.
=head1 OVERLOADED OPERATORS
The following C<use overload> declaration in the module gives the list of the
overloaded operators. Since C<fallback> is set to 1, several other operators become
overloaded by autogeneration from those shown below. For example, overloading of the
3-way numerical comparison operator C<< <=> >> automatically overloads the C<< < >>,
C<< <= >>, C<< > >>, C<< >= >>, C<< == >>, and C<< != >> operators.
use overload '+' => '_add',
'""' => '_str',
'0+' => '_int',
'~' => '_invert',
'|' => '_or',
'&' => '_and',
'^' => '_xor',
'<=>' => '_compare',
'<<' => '_lshift',
'>>' => '_rshift',
'<>' => '_iter',
'fallback' => 1;
It is B<important> to remember that the overloadings for the `C<<< << >>>' and `C<<<
>> >>>' operators are for B<circular> left and right shifts (their usual meaning as
bitwise operators is for non-circular shifts). This was done because the
applications for which this module is intended is more likely to use circular shifts
of bit fields than non-circular shifts. You can still carry out non-circular shifts
by calling the methods C<shift_left()> and C<shift_right()> as illustrated elsewhere
in this documentation.
Another B<important> thing to bear in mind is the overloading of the `C<+>' operator.
It is B<NOT> addition. On the other hand, it is a concatenation of the two operand
bitvectors. This was done to keep the usage of this operator the same as in the
Python version of this module.
By virtue of how the operators are overloaded, you can make the calls listed in the
rest of this section. To illustrate these calls, I will use the following two bit
vectors:
$bv1 = Algorithm::BitVector->new( bitstring => "111000" );
$bv2 = Algorithm::BitVector->new( bitstring => "000101000" );
These two bitvectors are intentionally of different lengths to illustrate what role
the size differences play in how the various operators work.
=over 4
=item B<Concatenating two bitvectors:>
$bv3 = $bv1 + $bv2; # 111000000101000
The concatenation of two bitvectors is returned as a new bitvector. This is made
possible by the overload definition for the C<+> operator.
Note that the following also works:
print $bv1 . "hello"; # 111000hello
In this case, Perl implicitly converts the left operand of the `.' operator into a
string (which is made possible by the overloading for the stringification operator in
this module) and then returns the result as a string.
=item B<Creating the string representation of a bitvector:>
print "$bv1"; # 111000
This is made possible for the overload definition for the C<""> operator.
=item B<Converting a bitvector to its integer value:>
print int($bv1); # 56
This is made possible by the overload definition for the C<0+> operator.
=item B<Inverting a bitvector>
$bv3 = ~ $bv1;
print $bv3; # 000111
This is made possible by the overload definition for the C<~> operator. The original
bitvector on which this unary operator is invoked remains unchanged.
=item B<Taking logical OR of two bitvectors:>
$bv3 = $bv1 | $bv2; # 000111000
When two bitvectors are of unequal length (as is the case here), the shorter vector
is zero-padded on the left to equalize their lengths before the application of the
logical operation. If this auto-padding property is not something you want, you
should check the lengths of the argument bitvectors in your own script before
invoking this operator. The result of the logical OR operation is returned as a new
bitvector. The two operand bitvectors remain unchanged.
=item B<Taking logical AND of two bitvectors:>
$bv3 = $bv1 & $bv2; # 000101000
lib/Algorithm/BitVector.pm view on Meta::CPAN
$bv = Algorithm::BitVector->new( size => 13 ); # 0000000000000
=item B<Constructing a bitvector from an integer value:>
$bv = Algorithm::BitVector->new( intVal => 5006 ); # 1001110001110
The module returns the smallest possible bitvector that would accommodate the
integer value provided with the C<intVal> option.
=item B<Constructing a bitvector by specifying both the size and the integer values:>
As mentioned, with the C<intVal> option, you get the smallest possible bitvector
that can be generated from that integer. If you want a I<larger> bitvector, you can
also supply the C<size> option as shown below:
$bv = Algorithm::BitVector->new( intVal => 5006, size => 16 ); # 0001001110001110
If the value supplied for the C<size> option in such a call is not larger than the
smallest bit array that represents the C<intVal> value, the constructor will throw an
exception.
=item B<Constructing a bitvector from a very large integer:>
use Math::BigInt;
$x = Math::BigInt->new('12345678901234567890123456789012345678901234567890');
$bv = Algorithm::BitVector->new( intVal => $x );
#1000011100100111111101100011011010011010101011111000001111001010000\
#10101000000100110011101000111101011111000110001111111000110010110110\
#01110001111110000101011010010
=item B<Constructing a bitvector from a bit string:>
$bv = Algorithm::BitVector->new( bitstring => '00110011' ); # 00110011
=item B<Constructing a bitvector from an ASCII text string:>
$bv = Algorithm::BitVector->new( textstring => "hello\n" );
# 011010000110010101101100011011000110111100001010
=item B<Constructing a bitvector from a hex string:>
$bv = Algorithm::BitVector->new( hexstring => "68656c6c6f" );
# 0110100001100101011011000110110001101111
=item B<Constructing a bitvector from a bit list:>
$bv = Algorithm::BitVector->new( bitlist => [1, 1, 0, 1] ); # 1101
=item B<Constructing a bitvector from the contents of a disk file:>
$bv = Algorithm::BitVector->new( filename => 'testinput1.txt' );
print "$bv\n"; # Nothing to show yet
$bv1 = $bv->read_bits_from_file(64); # Now you have a bitvector from the
# first 64 bits
Note that it takes two calls to create bitvectors from the contents of a file. The
first merely creates an empty bitvector just to set the necessary file handle for
reading the file. It is the second call in which you invoke the method
C<read_bits_from_file()> that actually returns a bitvector from the bits read from
the file. Each call to C<read_bits_from_file()> in this manner spits out a new bit
vector.
=back
=head1 METHODS
=head3 close_file_handle()
=over 4
When you construct bitvectors by block scanning a disk file, after you are done, you
can call this method to close the file handle that was created to read the file:
$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
## your code to read bit blocks for constructing bitvectors goes here
$bv->close_file_handle();
The constructor call in the first statement opens a file handle for reading the bits.
It is this file handle that is closed by calling C<close_file_handle()>,
=back
=head3 count_bits()
=over 4
$bv = Algorithm::BitVector->new( intVal => 45, size => 16 );
print $bv->count_bits(); # 4
This method returns an integer value which is the number of bits set to 1 in the
bitvector on which the method is invoked.
=back
=head3 count_bits_sparse()
=over 4
Say you have a bitvector with two million bits:
$bv = Algorithm::BitVector->new( size => 2000000 );
and you happen to set its individual bits by
$bv->set_bit(345234, 1);
$bv->set_bit(233, 1);
$bv->set_bit(243, 1);
$bv->set_bit(18, 1);
$bv->set_bit(785, 1);
The following call returns the number of bits set in the bitvector:
print $bv->count_bits_sparse(); # 5
For very long bitvectors, as in the example here, this method will work much faster
than the C<count_bits()> method. However, for dense bitvectors, I expect
C<count_bits()> to work faster.
lib/Algorithm/BitVector.pm view on Meta::CPAN
($bv1, $bv2) = $bv->divide_into_two(); # say $bv = 0000000000101101
print "$bv1\n"; # 00000000
print "$bv2\n"; # 00101101
Divides an even sized bitvector into two bitvectors, each of size half of the
bitvector on which this method is invoked. Throws an exception when invoked on a
bitvector that is not even sized.
=back
=head3 gcd()
=over 4
This method uses the Euclid's algorithm to return the Greatest Common Divisor of the
integer values represented by the two bitvectors. The following example shows a call
to C<gcd()> returning the GCD of the integer values of the bitvectors C<$bv1> and
C<$bv2>.
$bv1 = Algorithm::BitVector->new( bitstring => '01100110' ); # 102
$bv2 = Algorithm::BitVector->new( bitstring => '011010' ); # 26
$gcd = $bv1->gcd( $bv2 ); # 10
print int($gcd); # 2
The result returned by C<gcd()> is a bitvector.
=back
=head3 gen_random_bits()
=over 4
$bv = Algorithm::BitVector->new( intVal => 0 );
$bv = $bv->gen_random_bits(16); # 1100111001010101
The call to C<gen_random_bits()> returns a bitvector whose bits are randomly
generated. The number of bits in the returned bitvector equals the argument integer.
=back
=head3 get_bit()
=over 4
This method gives you array-like access to the individual bits of a bitvector.
$bv = Algorithm::BitVector->new( bitstring => '10111' );
print $bv->get_bit(0); # 1 (the first bit)
print $bv->get_bit(1); # 0
print $bv->get_bit(4); # 1 (the last bit)
Negative values for the index scan a bitvector from right to left, with the C<-1>
index standing for the last (meaning the right-most) bit in the vector:
print $bv->get_bit(-1); # 1 (the last bit)
print $bv->get_bit(-2); # 1
print $bv->get_bit(-5); # 1 (the first bit)
The C<get_bit()> can also return a slice of a bitvector if the argument to the
method is an anonymous array of the index range you desire, as in the second
statement below:
$bv = Algorithm::BitVector->new( bitstring => "10111011");
my $arr = $bv->get_bit( [3..7] );
print "@$arr\n"; # 1 1 0 1 1
In this example, we want C<get_bit()> to return all bits at positions indexed 3
through 7, both ends inclusive. Note that the slice is returned as an array of bits.
=back
=head3 get_bitvector_in_ascii()
=over 4
$bv = Algorithm::BitVector->new( textstring => "hello" );
print "$bv\n"; # 0110100001100101011011000110110001101111
print $bv->get_bitvector_in_ascrii(); # hello
The method returns a string of ASCII characters by converting successive 8-bit slices
of the bitvector into an ASCII character. It throws an exception if the size of the
bit pattern is not a multiple of 8. Calling this method to create a text-based print
representation of a bit vector makes sense only if you don't expect to see any
unprintable characters in the successive 8-bit slices of the bitvector. Let's say
you have created a bitvector from a text string using the appropriate constructor
call. Subsequently, you encrypted this text string. Next, you or someone else
decrypts the encrypted bit stream. Since what comes out at the decryption end must
be the original text string, it would make sense to invoke this method to recover the
original text.
=back
=head3 get_bitvector_in_hex()
=over 4
Assuming that length of your bitvector is a multiple of 4, this methods returns a
hex representation of the bit pattern:
$bv = Algorithm::BitVector->new(bitstring => "0110100001100101011011000110110001101111");
print $bv->get_bitvector_in_hex(); # 68656c6c6f
The hex representation is returned in the form if a string of hex characters. This
method throws an exception if the size of the bitvector is not a multiple of 4.
=back
=head3 get_slice()
=over 4
You can use this method to get a slice of a BitVector that is within a specified range.
You can specify the index range with the usual range operator in Perl. If the index
range is, say, '5..11', the method will return all bits at index values 5 through 10.
my $bv9 = Algorithm::BitVector->new( intVal => 63437, size => 16 );
print "BitVector for testing get_slice(): $bv9\n"; # 1111011111001101
my $slice_bv = $bv9->get_slice( [5..11] );
print "slice BitVector for index values 5 through 10: $slice_bv\n"; # 111110
lib/Algorithm/BitVector.pm view on Meta::CPAN
file.
=back
=head3 reset()
=over 4
You can reset a previously constructed bitvector all either all 1's or all 0's by
calling this method:
$bv = Algorithm::BitVector->new( intVal => 203, size => 8 );
print $bv; # 11001011
$bv->reset(1);
print $bv; # 11111111
$bv->reset(0);
print $bv; # 00000000
What the method accomplishes can be thought of as in-place resetting of the bits. The
method does not return anything.
=back
=head3 reverse()
=over 4
Given a bitvector, you can construct a bitvector with all the bits reversed, in the
sense that what was left-to-right earlier now becomes right-to-left, as in
$bv = Algorithm::BitVector->new( bitstring => '01100001' );
print $bv->reverse(); # 10000110
A call to this method returns a new bitvector whose bits are in reverse order in
relation to the bits in the bitvector on which the method is called.
=back
=head3 runs()
=over 4
This method returns an array of runs of 1's and 0's in a bitvector:
$bv = Algorithm::BitVector->new( bitlist => [1,1,1,0,0,1] );
my @bvruns = $bv->runs();
print "@bvruns\n"; # 111 00 1
Each element of the array that is returned by C<runs()> is a string of either 1's or
0's.
=back
=head3 set_bit()
=over 4
With array-like indexing, you can use this method to set the individual bits of a
previously constructed bitvector. Both positive and negative values are allowed for
the bit position index. The method takes two explicit arguments, the first for the
position of the bit you want to set and the second for the value of the bit.
$bv = Algorithm::BitVector->new( bitstring => '1111' );
$bv->set_bit(0,0); # set the first bit to 0
$bv->set_bit(1,0); # set the next bit to 0
print $bv; # 0011
$bv->set_bit(-1,0); # set the last bit to 0
$bv->set_bit(-2,0); # set the bit before the last bit to 0
print $bv; # 0000
=back
=head3 set_slice()
=over 4
You can set a slice in a given BitVector by calling this method. It takes two
arguments, with the first argument as the range of the position index values at which
you want to set the bits and the second argument the bit values at those positions.
$bv = Algorithm::BitVector->new( intVal => 63437, size => 16 );
$values_bv = Algorithm::BitVector->new( bitlist => [1,1,1,1] );
$bv->set_slice( [4..8], $values_bv );
print "BitVector after set_slice(): $bv\n"; # 1111111111001101
When specifying the index values with the range operator in the form C<i..j>, you
would be setting the bits at the positions C<i> through C<j-1>.
=back
=head3 set_value()
=over 4
This method can be used to change the bit pattern associated with a previously
constructed bitvector:
$bv = Algorithm::BitVector->new( intVal => 7, size => 16 );
print $bv; # 0000000000000111
$bv->set_value( intVal => 45 );
print $bv; # 101101
You can think of this method as carrying out an in-place resetting of the bit array
in a bitvector. The method does not return anything.
=back
=head3 shift_left()
=over 4
If you want to shift a bitvector non-circularly to the left, this is the method to
call:
$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
$bv->shift_left(3);
print $bv; # 001000
$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
$bv->shift_left(3)->shift_right(3);
print $bv; # 000001
As the bitvector is shifted non-circularly to the left, the exposed bit positions on
the right are filled with zeros. Note that the method returns the bitvector object
on which it is invoked. That is the reason why the chained invocation of the method
in the fifth statement above works.
=back
=head3 shift_right()
=over 4
If you want to shift a bitvector non-circularly to the right, this is the method to
call:
$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
$bv->shift_right(3);
print $bv; # 000111
$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
( run in 0.422 second using v1.01-cache-2.11-cpan-39bf76dae61 )