=head1 NAME
Bit::Vector - Efficient bit vector, set of integers and "big int" math library
=head1 SYNOPSIS
=head2 OVERLOADED OPERATORS
See L.
=head2 MORE STRING IMPORT/EXPORT
See L.
=head2 CLASS METHODS
Version
$version = Bit::Vector->Version();
Word_Bits
$bits = Bit::Vector->Word_Bits(); # bits in a machine word
Long_Bits
$bits = Bit::Vector->Long_Bits(); # bits in an unsigned long
new
$vector = Bit::Vector->new($bits); # bit vector constructor
@veclist = Bit::Vector->new($bits,$count);
new_Hex
$vector = Bit::Vector->new_Hex($bits,$string);
new_Bin
$vector = Bit::Vector->new_Bin($bits,$string);
new_Dec
$vector = Bit::Vector->new_Dec($bits,$string);
new_Enum
$vector = Bit::Vector->new_Enum($bits,$string);
Concat_List
$vector = Bit::Vector->Concat_List(@vectors);
=head2 OBJECT METHODS
new
$vec2 = $vec1->new($bits); # alternative call of constructor
@veclist = $vec->new($bits,$count);
Shadow
$vec2 = $vec1->Shadow(); # new vector, same size but empty
Clone
$vec2 = $vec1->Clone(); # new vector, exact duplicate
Concat
$vector = $vec1->Concat($vec2);
Concat_List
$vector = $vec1->Concat_List($vec2,$vec3,...);
Size
$bits = $vector->Size();
Resize
$vector->Resize($bits);
$vector->Resize($vector->Size()+5);
$vector->Resize($vector->Size()-5);
Copy
$vec2->Copy($vec1);
Empty
$vector->Empty();
Fill
$vector->Fill();
Flip
$vector->Flip();
Primes
$vector->Primes(); # Sieve of Erathostenes
Reverse
$vec2->Reverse($vec1);
Interval_Empty
$vector->Interval_Empty($min,$max);
Interval_Fill
$vector->Interval_Fill($min,$max);
Interval_Flip
$vector->Interval_Flip($min,$max);
Interval_Reverse
$vector->Interval_Reverse($min,$max);
Interval_Scan_inc
if (($min,$max) = $vector->Interval_Scan_inc($start))
Interval_Scan_dec
if (($min,$max) = $vector->Interval_Scan_dec($start))
Interval_Copy
$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);
Interval_Substitute
$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);
is_empty
if ($vector->is_empty())
is_full
if ($vector->is_full())
equal
if ($vec1->equal($vec2))
Lexicompare (unsigned)
if ($vec1->Lexicompare($vec2) == 0)
if ($vec1->Lexicompare($vec2) != 0)
if ($vec1->Lexicompare($vec2) < 0)
if ($vec1->Lexicompare($vec2) <= 0)
if ($vec1->Lexicompare($vec2) > 0)
if ($vec1->Lexicompare($vec2) >= 0)
Compare (signed)
if ($vec1->Compare($vec2) == 0)
if ($vec1->Compare($vec2) != 0)
if ($vec1->Compare($vec2) < 0)
if ($vec1->Compare($vec2) <= 0)
if ($vec1->Compare($vec2) > 0)
if ($vec1->Compare($vec2) >= 0)
to_Hex
$string = $vector->to_Hex();
from_Hex
$vector->from_Hex($string);
to_Bin
$string = $vector->to_Bin();
from_Bin
$vector->from_Bin($string);
to_Dec
$string = $vector->to_Dec();
from_Dec
$vector->from_Dec($string);
to_Enum
$string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19"
from_Enum
$vector->from_Enum($string);
Bit_Off
$vector->Bit_Off($index);
Bit_On
$vector->Bit_On($index);
bit_flip
$bit = $vector->bit_flip($index);
bit_test
contains
$bit = $vector->bit_test($index);
$bit = $vector->contains($index);
if ($vector->bit_test($index))
if ($vector->contains($index))
Bit_Copy
$vector->Bit_Copy($index,$bit);
LSB (least significant bit)
$vector->LSB($bit);
MSB (most significant bit)
$vector->MSB($bit);
lsb (least significant bit)
$bit = $vector->lsb();
msb (most significant bit)
$bit = $vector->msb();
rotate_left
$carry = $vector->rotate_left();
rotate_right
$carry = $vector->rotate_right();
shift_left
$carry = $vector->shift_left($carry);
shift_right
$carry = $vector->shift_right($carry);
Move_Left
$vector->Move_Left($bits); # shift left "$bits" positions
Move_Right
$vector->Move_Right($bits); # shift right "$bits" positions
Insert
$vector->Insert($offset,$bits);
Delete
$vector->Delete($offset,$bits);
increment
$carry = $vector->increment();
decrement
$carry = $vector->decrement();
inc
$overflow = $vec2->inc($vec1);
dec
$overflow = $vec2->dec($vec1);
add
$carry = $vec3->add($vec1,$vec2,$carry);
($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);
subtract
$carry = $vec3->subtract($vec1,$vec2,$carry);
($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);
Neg
Negate
$vec2->Neg($vec1);
$vec2->Negate($vec1);
Abs
Absolute
$vec2->Abs($vec1);
$vec2->Absolute($vec1);
Sign
if ($vector->Sign() == 0)
if ($vector->Sign() != 0)
if ($vector->Sign() < 0)
if ($vector->Sign() <= 0)
if ($vector->Sign() > 0)
if ($vector->Sign() >= 0)
Multiply
$vec3->Multiply($vec1,$vec2);
Divide
$quot->Divide($vec1,$vec2,$rest);
GCD (Greatest Common Divisor)
$vecgcd->GCD($veca,$vecb);
$vecgcd->GCD($vecx,$vecy,$veca,$vecb);
Power
$vec3->Power($vec1,$vec2);
Block_Store
$vector->Block_Store($buffer);
Block_Read
$buffer = $vector->Block_Read();
Word_Size
$size = $vector->Word_Size(); # number of words in "$vector"
Word_Store
$vector->Word_Store($offset,$word);
Word_Read
$word = $vector->Word_Read($offset);
Word_List_Store
$vector->Word_List_Store(@words);
Word_List_Read
@words = $vector->Word_List_Read();
Word_Insert
$vector->Word_Insert($offset,$count);
Word_Delete
$vector->Word_Delete($offset,$count);
Chunk_Store
$vector->Chunk_Store($chunksize,$offset,$chunk);
Chunk_Read
$chunk = $vector->Chunk_Read($chunksize,$offset);
Chunk_List_Store
$vector->Chunk_List_Store($chunksize,@chunks);
Chunk_List_Read
@chunks = $vector->Chunk_List_Read($chunksize);
Index_List_Remove
$vector->Index_List_Remove(@indices);
Index_List_Store
$vector->Index_List_Store(@indices);
Index_List_Read
@indices = $vector->Index_List_Read();
Or
Union
$vec3->Or($vec1,$vec2);
$set3->Union($set1,$set2);
And
Intersection
$vec3->And($vec1,$vec2);
$set3->Intersection($set1,$set2);
AndNot
Difference
$vec3->AndNot($vec1,$vec2);
$set3->Difference($set1,$set2);
Xor
ExclusiveOr
$vec3->Xor($vec1,$vec2);
$set3->ExclusiveOr($set1,$set2);
Not
Complement
$vec2->Not($vec1);
$set2->Complement($set1);
subset
if ($set1->subset($set2)) # true if $set1 is subset of $set2
Norm
$norm = $set->Norm();
$norm = $set->Norm2();
$norm = $set->Norm3();
Min
$min = $set->Min();
Max
$max = $set->Max();
Multiplication
$matrix3->Multiplication($rows3,$cols3,
$matrix1,$rows1,$cols1,
$matrix2,$rows2,$cols2);
Product
$matrix3->Product($rows3,$cols3,
$matrix1,$rows1,$cols1,
$matrix2,$rows2,$cols2);
Closure
$matrix->Closure($rows,$cols);
Transpose
$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);
=head1 IMPORTANT NOTES
=over 2
=item *
Method naming conventions
Method names completely in lower case indicate a boolean return value.
(Except for the bit vector constructor method "C", of course.)
=item *
Boolean values
Boolean values in this module are always a numeric zero ("C<0>") for
"false" and a numeric one ("C<1>") for "true".
=item *
Negative numbers
All numeric input parameters passed to any of the methods in this module
are regarded as being B (as opposed to the contents of the
bit vectors themselves, which are usually considered to be B).
As a consequence, whenever you pass a negative number as an argument to
some method of this module, it will be treated as a (usually very large)
positive number due to its internal two's complement binary representation,
usually resulting in an "index out of range" error message and program
abortion.
=item *
Bit order
Note that bit vectors are stored least order bit and least order word first
internally.
I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0 in the
array of machine words representing the bit vector.
(Where word #0 comes first in memory, i.e., it is stored at the least memory
address in the allocated block of memory holding the given bit vector.)
Note however that machine words can be stored least order byte first or last,
depending on your system's implementation.
When you are exporting or importing a whole bit vector at once using the
methods "C" and "C" (the only time in this
module where this could make any difference), however, a conversion to and
from "least order byte first" order is automatically supplied.
In other words, what "C" provides and what "C"
expects is always in "least order byte first" order, regardless of the order
in which words are stored internally on your machine.
This is to make sure that what you export on one machine using "C"
can always be read in correctly with "C" on a different machine.
Note further that whenever bit vectors are converted to and from (binary or
hexadecimal) strings, the B bit is always the B
one, and the B bit is always the B bit.
This is because in our western culture, numbers are always represented in this
way (least significant to most significant digits go from right to left).
Of course this requires an internal reversion of order, which the corresponding
conversion methods perform automatically (without any additional overhead, it's
just a matter of starting the internal loop at the bottom or the top end).
=item *
"Word" related methods
Note that all methods whose names begin with "C" are
B!
They depend on the size (number of bits) of an "unsigned int" (C type) on
your machine.
Therefore, you should only use these methods if you are B
that portability of your code is not an issue!
Note that you can use arbitrarily large chunks (i.e., fragments of bit vectors)
of up to 32 bits B using the methods whose names begin with
"C".
=item *
Chunk sizes
Note that legal chunk sizes for all methods whose names begin with "C"
range from "C<1>" to "CLong_Bits();>" bits ("C<0>" is B
allowed!).
In order to make your programs portable, however, you shouldn't use chunk sizes
larger than 32 bits, since this is the minimum size of an "unsigned long"
(C type) on all systems, as prescribed by S.
=item *
Matching sizes
In general, for methods involving several bit vectors at the same time, all
bit vector arguments must have identical sizes (number of bits), or a fatal
"size mismatch" error will occur.
Exceptions from this rule are the methods "C", "C",
"C", "C" and "C", where no
conditions at all are imposed on the size of their bit vector arguments.
In method "C", all three bit vector arguments must in principle
obey the rule of matching sizes, but the bit vector in which the result of
the multiplication is to be stored may be larger than the two bit vector
arguments containing the factors for the multiplication.
In method "C", the bit vector for the result must be the same
size or greater than the base of the exponentiation term. The exponent
can be any size.
=item *
Index ranges
All indices for any given bits must lie between "C<0>" and
"C<$vector-ESize()-1>", or a fatal "index out of range"
error will occur.
=item *
Object persistence
Since version 6.5, "Bit::Vector" objects can be serialized
and de-serialized automatically with "Storable", out-of-the-box,
without requiring any further user action for this to work.
This is also true for nested data structures (since version 6.8).
See the L documentation for more details.
=back
=head1 DESCRIPTION
=head2 OVERLOADED OPERATORS
See L.
=head2 MORE STRING IMPORT/EXPORT
See L.
=head2 CLASS METHODS
=over 2
=item *
C<$version = Bit::Vector-EVersion();>
Returns the current version number of this module.
=item *
C<$bits = Bit::Vector-EWord_Bits();>
Returns the number of bits of an "unsigned int" (C type)
on your machine.
(An "unsigned int" is also called a "machine word",
hence the name of this method.)
=item *
C<$bits = Bit::Vector-ELong_Bits();>
Returns the number of bits of an "unsigned long" (C type)
on your machine.
=item *
C<$vector = Bit::Vector-Enew($bits);>
This is the bit vector constructor method.
Call this method to create a new bit vector containing "C<$bits>"
bits (with indices ranging from "C<0>" to "C<$bits-1>").
Note that - in contrast to previous versions - bit vectors
of length zero (i.e., with C<$bits = 0>) are permitted now.
The method returns a reference to the newly created bit vector.
A new bit vector is always initialized so that all bits are cleared
(turned off).
An exception will be raised if the method is unable to allocate the
necessary memory.
Note that if you specify a negative number for "C<$bits>" it will be
interpreted as a large positive number due to its internal two's
complement binary representation.
In such a case, the bit vector constructor method will obediently attempt
to create a bit vector of that size, probably resulting in an exception,
as explained above.
=item *
C<@veclist = Bit::Vector-Enew($bits,$count);>
You can also create more than one bit vector at a time if you specify the
optional second parameter "C<$count>".
The method returns a list of "C<$count>" bit vectors which all have the
same number of bits "C<$bits>" (and which are all initialized, i.e.,
all bits are cleared).
If "C<$count>" is zero, an empty list is returned.
If "C<$bits>" is zero, a list of null-sized bit vectors is returned.
Note again that if you specify a negative number for "C<$count>" it will
be interpreted as a large positive number due to its internal two's
complement binary representation.
In such a case, the bit vector constructor method will obediently attempt
to create that many bit vectors, probably resulting in an exception ("out
of memory").
=item *
C<$vector = Bit::Vector-Enew_Hex($bits,$string);>
This method is an alternative constructor which allows you to create
a new bit vector object (with "C<$bits>" bits) and to initialize it
all in one go.
The method internally first calls the bit vector constructor method
"C" and then passes the given string to the method "C".
However, this method is more efficient than performing these two steps
separately: First because in this method, the memory area occupied by
the new bit vector is not initialized to zeros (which is pointless in
this case), and second because it saves you from the associated overhead
of one additional method invocation.
An exception will be raised if the necessary memory cannot be allocated
(see the description of the method "C" immediately above for
possible causes) or if the given string cannot be converted successfully
(see the description of the method "C" further below for
details).
In the latter case, the memory occupied by the new bit vector is
released first (i.e., "free"d) before the exception is actually
raised.
=item *
C<$vector = Bit::Vector-Enew_Bin($bits,$string);>
This method is an alternative constructor which allows you to create
a new bit vector object (with "C<$bits>" bits) and to initialize it
all in one go.
The method internally first calls the bit vector constructor method
"C" and then passes the given string to the method "C".
However, this method is more efficient than performing these two steps
separately: First because in this method, the memory area occupied by
the new bit vector is not initialized to zeros (which is pointless in
this case), and second because it saves you from the associated overhead
of one additional method invocation.
An exception will be raised if the necessary memory cannot be allocated
(see the description of the method "C" above for possible causes)
or if the given string cannot be converted successfully (see the
description of the method "C" further below for details).
In the latter case, the memory occupied by the new bit vector is
released first (i.e., "free"d) before the exception is actually
raised.
=item *
C<$vector = Bit::Vector-Enew_Dec($bits,$string);>
This method is an alternative constructor which allows you to create
a new bit vector object (with "C<$bits>" bits) and to initialize it
all in one go.
The method internally first calls the bit vector constructor method
"C" and then passes the given string to the method "C".
However, this method is more efficient than performing these two steps
separately: First because in this method, "C" does not initialize
the memory area occupied by the new bit vector with zeros (which is
pointless in this case, because "C" will do it anyway),
and second because it saves you from the associated overhead of one
additional method invocation.
An exception will be raised if the necessary memory cannot be allocated
(see the description of the method "C" above for possible causes)
or if the given string cannot be converted successfully (see the
description of the method "C" further below for details).
In the latter case, the memory occupied by the new bit vector is
released first (i.e., "free"d) before the exception is actually
raised.
=item *
C<$vector = Bit::Vector-Enew_Enum($bits,$string);>
This method is an alternative constructor which allows you to create
a new bit vector object (with "C<$bits>" bits) and to initialize it
all in one go.
The method internally first calls the bit vector constructor method
"C" and then passes the given string to the method "C".
However, this method is more efficient than performing these two steps
separately: First because in this method, "C" does not initialize
the memory area occupied by the new bit vector with zeros (which is
pointless in this case, because "C" will do it anyway),
and second because it saves you from the associated overhead of one
additional method invocation.
An exception will be raised if the necessary memory cannot be allocated
(see the description of the method "C" above for possible causes)
or if the given string cannot be converted successfully (see the
description of the method "C" further below for details).
In the latter case, the memory occupied by the new bit vector is
released first (i.e., "free"d) before the exception is actually
raised.
=item *
C<$vector = Bit::Vector-EConcat_List(@vectors);>
This method creates a new vector containing all bit vectors from the
argument list in concatenated form.
The argument list may contain any number of arguments (including
zero); the only condition is that all arguments must be bit vectors.
There is no condition concerning the length (in number of bits) of
these arguments.
The vectors from the argument list are not changed in any way.
If the argument list is empty or if all arguments have length zero,
the resulting bit vector will also have length zero.
Note that the B bit vector from the argument list will
become the B significant part of the resulting bit vector,
and the B bit vector from the argument list will
become the B significant part of the resulting bit vector.
=back
=head2 OBJECT METHODS
=over 2
=item *
C<$vec2 = $vec1-Enew($bits);>
C<@veclist = $vec-Enew($bits);>
This is an alternative way of calling the bit vector constructor method.
Vector "C<$vec1>" (or "C<$vec>") is not affected by this, it just serves
as an anchor for the method invocation mechanism.
In fact B class methods in this module can be called this way,
even though this is probably considered to be "politically incorrect"
by OO ("object-orientation") aficionados. ;-)
So even if you are too lazy to type "C>" instead of
"C<$vec1-E>" (and even though laziness is - allegedly - a programmer's
virtue C<:-)>), maybe it is better not to use this feature if you don't
want to get booed at. ;-)
=item *
C<$vec2 = $vec1-EShadow();>
Creates a B bit vector "C<$vec2>" of the B as "C<$vec1>"
but which is B.
Just like a shadow that has the same shape as the object it
originates from, but is flat and has no volume, i.e., contains
nothing.
=item *
C<$vec2 = $vec1-EClone();>
Creates a B bit vector "C<$vec2>" of the B as "C<$vec1>"
which is an B of "C<$vec1>".
=item *
C<$vector = $vec1-EConcat($vec2);>
This method returns a new bit vector object which is the result of the
concatenation of the contents of "C<$vec1>" and "C<$vec2>".
Note that the contents of "C<$vec1>" become the B significant part
of the resulting bit vector, and "C<$vec2>" the B significant part.
If both bit vector arguments have length zero, the resulting bit vector
will also have length zero.
=item *
C<$vector = $vec1-EConcat_List($vec2,$vec3,...);>
This is an alternative way of calling this (class) method as an
object method.
The method returns a new bit vector object which is the result of
the concatenation of the contents of C<$vec1 . $vec2 . $vec3 . ...>
See the section "class methods" above for a detailed description of
this method.
Note that the argument list may be empty and that all arguments
must be bit vectors if it isn't.
=item *
C<$bits = $vector-ESize();>
Returns the size (number of bits) the given vector was created with
(or "C"d to).
=item *
C<$vector-EResize($bits);>
Changes the size of the given vector to the specified number of bits.
This method allows you to change the size of an existing bit vector,
preserving as many bits from the old vector as will fit into the
new one (i.e., all bits with indices smaller than the minimum of the
sizes of both vectors, old and new).
If the number of machine words needed to store the new vector is smaller
than or equal to the number of words needed to store the old vector, the
memory allocated for the old vector is reused for the new one, and only
the relevant book-keeping information is adjusted accordingly.
This means that even if the number of bits increases, new memory is not
necessarily being allocated (i.e., if the old and the new number of bits
fit into the same number of machine words).
If the number of machine words needed to store the new vector is greater
than the number of words needed to store the old vector, new memory is
allocated for the new vector, the old vector is copied to the new one,
the remaining bits in the new vector are cleared (turned off) and the old
vector is deleted, i.e., the memory that was allocated for it is released.
(An exception will be raised if the method is unable to allocate the
necessary memory for the new vector.)
As a consequence, if you decrease the size of a given vector so that
it will use fewer machine words, and increase it again later so that it
will use more words than immediately before but still less than the
original vector, new memory will be allocated anyway because the
information about the size of the original vector is lost whenever
you resize it.
Note also that if you specify a negative number for "C<$bits>" it will
be interpreted as a large positive number due to its internal two's
complement binary representation.
In such a case, "Resize()" will obediently attempt to create a bit
vector of that size, probably resulting in an exception, as explained
above.
Finally, note that - in contrast to previous versions - resizing a bit
vector to a size of zero bits (length zero) is now permitted.
=item *
C<$vec2-ECopy($vec1);>
Copies the contents of bit vector "C<$vec1>" to bit vector "C<$vec2>".
The previous contents of bit vector "C<$vec2>" get overwritten, i.e.,
are lost.
Both vectors must exist beforehand, i.e., this method does not B
any new bit vector object.
The two vectors may be of any size.
If the source bit vector is larger than the target, this method will copy
as much of the least significant bits of the source vector as will fit into
the target vector, thereby discarding any extraneous most significant bits.
BEWARE that this causes a brutal cutoff in the middle of your data, and it
will also leave you with an almost unpredictable sign if subsequently the
number in the target vector is going to be interpreted as a number! (You
have been warned!)
If the target bit vector is larger than the source, this method fills up
the remaining most significant bits in the target bit vector with either
0's or 1's, depending on the sign (= the most significant bit) of the
source bit vector. This is also known as "sign extension".
This makes it possible to copy numbers from a smaller bit vector into
a larger one while preserving the number's absolute value as well as
its sign (due to the two's complement binary representation of numbers).
=item *
C<$vector-EEmpty();>
Clears all bits in the given vector.
=item *
C<$vector-EFill();>
Sets all bits in the given vector.
=item *
C<$vector-EFlip();>
Flips (i.e., complements) all bits in the given vector.
=item *
C<$vector-EPrimes();>
Clears the given bit vector and sets all bits whose
indices are prime numbers.
This method uses the algorithm known as the "Sieve of
Erathostenes" internally.
=item *
C<$vec2-EReverse($vec1);>
This method copies the given vector "C<$vec1>" to
the vector "C<$vec2>", thereby reversing the order
of all bits.
I.e., the least significant bit of "C<$vec1>" becomes the
most significant bit of "C<$vec2>", whereas the most
significant bit of "C<$vec1>" becomes the least
significant bit of "C<$vec2>", and so forth
for all bits in between.
Note that in-place processing is also possible, i.e.,
"C<$vec1>" and "C<$vec2>" may be identical.
(Internally, this is the same as
C<$vec1-EInterval_Reverse(0,$vec1-ESize()-1);>.)
=item *
C<$vector-EInterval_Empty($min,$max);>
Clears all bits in the interval C<[$min..$max]> (including both limits)
in the given vector.
"C<$min>" and "C<$max>" may have the same value; this is the same
as clearing a single bit with "C" (but less efficient).
Note that C<$vector-EInterval_Empty(0,$vector-ESize()-1);>
is the same as C<$vector-EEmpty();> (but less efficient).
=item *
C<$vector-EInterval_Fill($min,$max);>
Sets all bits in the interval C<[$min..$max]> (including both limits)
in the given vector.
"C<$min>" and "C<$max>" may have the same value; this is the same
as setting a single bit with "C" (but less efficient).
Note that C<$vector-EInterval_Fill(0,$vector-ESize()-1);>
is the same as C<$vector-EFill();> (but less efficient).
=item *
C<$vector-EInterval_Flip($min,$max);>
Flips (i.e., complements) all bits in the interval C<[$min..$max]>
(including both limits) in the given vector.
"C<$min>" and "C<$max>" may have the same value; this is the same
as flipping a single bit with "C" (but less efficient).
Note that C<$vector-EInterval_Flip(0,$vector-ESize()-1);>
is the same as C<$vector-EFlip();> and
C<$vector-EComplement($vector);>
(but less efficient).
=item *
C<$vector-EInterval_Reverse($min,$max);>
Reverses the order of all bits in the interval C<[$min..$max]>
(including both limits) in the given vector.
I.e., bits "C<$min>" and "C<$max>" swap places, and so forth
for all bits in between.
"C<$min>" and "C<$max>" may have the same value; this has no
effect whatsoever, though.
=item *
CInterval_Scan_inc($start))>
Returns the minimum and maximum indices of the next contiguous block
of set bits (i.e., bits in the "on" state).
The search starts at index "C<$start>" (i.e., C<"$min" E= "$start">)
and proceeds upwards (i.e., C<"$max" E= "$min">), thus repeatedly
increments the search pointer "C<$start>" (internally).
Note though that the contents of the variable (or scalar literal value)
"C<$start>" is B altered. I.e., you have to set it to the desired
value yourself prior to each call to "C" (see also
the example given below).
Actually, the bit vector is not searched bit by bit, but one machine
word at a time, in order to speed up execution (which means that this
method is quite efficient).
An empty list is returned if no such block can be found.
Note that a single set bit (surrounded by cleared bits) is a valid
block by this definition. In that case the return values for "C<$min>"
and "C<$max>" are the same.
Typical use:
$start = 0;
while (($start < $vector->Size()) &&
(($min,$max) = $vector->Interval_Scan_inc($start)))
{
$start = $max + 2;
# do something with $min and $max
}
=item *
CInterval_Scan_dec($start))>
Returns the minimum and maximum indices of the next contiguous block
of set bits (i.e., bits in the "on" state).
The search starts at index "C<$start>" (i.e., C<"$max" E= "$start">)
and proceeds downwards (i.e., C<"$min" E= "$max">), thus repeatedly
decrements the search pointer "C<$start>" (internally).
Note though that the contents of the variable (or scalar literal value)
"C<$start>" is B altered. I.e., you have to set it to the desired
value yourself prior to each call to "C" (see also
the example given below).
Actually, the bit vector is not searched bit by bit, but one machine
word at a time, in order to speed up execution (which means that this
method is quite efficient).
An empty list is returned if no such block can be found.
Note that a single set bit (surrounded by cleared bits) is a valid
block by this definition. In that case the return values for "C<$min>"
and "C<$max>" are the same.
Typical use:
$start = $vector->Size() - 1;
while (($start >= 0) &&
(($min,$max) = $vector->Interval_Scan_dec($start)))
{
$start = $min - 2;
# do something with $min and $max
}
=item *
C<$vec2-EInterval_Copy($vec1,$offset2,$offset1,$length);>
This method allows you to copy a stretch of contiguous bits (starting
at any position "C<$offset1>" you choose, with a length of "C<$length>"
bits) from a given "source" bit vector "C<$vec1>" to another position
"C<$offset2>" in a "target" bit vector "C<$vec2>".
Note that the two bit vectors "C<$vec1>" and "C<$vec2>" do B
need to have the same (matching) size!
Consequently, any of the two terms "C<$offset1 + $length>" and
"C<$offset2 + $length>" (or both) may exceed the actual length
of its corresponding bit vector ("C<$vec1-ESize()>" and
"C<$vec2-ESize()>", respectively).
In such a case, the "C<$length>" parameter is automatically reduced
internally so that both terms above are bounded by the number of bits
of their corresponding bit vector.
This may even result in a length of zero, in which case nothing is
copied at all.
(Of course the value of the "C<$length>" parameter, supplied by you
in the initial method call, may also be zero right from the start!)
Note also that "C<$offset1>" and "C<$offset2>" must lie within the
range "C<0>" and, respectively, "C<$vec1-ESize()-1>" or
"C<$vec2-ESize()-1>", or a fatal "offset out of range" error
will occur.
Note further that "C<$vec1>" and "C<$vec2>" may be identical, i.e.,
you may copy a stretch of contiguous bits from one part of a given
bit vector to another part.
The source and the target interval may even overlap, in which case
the copying is automatically performed in ascending or descending
order (depending on the direction of the copy - downwards or upwards
in the bit vector, respectively) to handle this situation correctly,
i.e., so that no bits are being overwritten before they have been
copied themselves.
=item *
C<$vec2-EInterval_Substitute($vec1,$off2,$len2,$off1,$len1);>
This method is (roughly) the same for bit vectors (i.e., arrays
of booleans) as what the "splice" function in Perl is for lists
(i.e., arrays of scalars).
(See L for more details about this function.)
The method allows you to substitute a stretch of contiguous bits
(defined by a position (offset) "C<$off1>" and a length of "C<$len1>"
bits) from a given "source" bit vector "C<$vec1>" for a different
stretch of contiguous bits (defined by a position (offset) "C<$off2>"
and a length of "C<$len2>" bits) in another, "target" bit vector
"C<$vec2>".
Note that the two bit vectors "C<$vec1>" and "C<$vec2>" do B
need to have the same (matching) size!
Note further that "C<$off1>" and "C<$off2>" must lie within the
range "C<0>" and, respectively, "C<$vec1-ESize()>" or
"C<$vec2-ESize()>", or a fatal "offset out of range" error
will occur.
Alert readers will have noticed that these upper limits are B
"C<$vec1-ESize()-1>" and "C<$vec2-ESize()-1>", as they would
be for any other method in this module, but that these offsets may
actually point to one position B of the corresponding
bit vector.
This is necessary in order to make it possible to B a given
stretch of bits to the target bit vector instead of B
something in it.
For reasons of symmetry and generality, the same applies to the offset
in the source bit vector, even though such an offset (one position past
the end of the bit vector) does not serve any practical purpose there
(but does not cause any harm either).
(Actually this saves you from the need of testing for this special case,
in certain circumstances.)
Note that whenever the term "C<$off1 + $len1>" exceeds the size
"C<$vec1-ESize()>" of bit vector "C<$vec1>" (or if "C<$off2 + $len2>"
exceeds "C<$vec2-ESize()>"), the corresponding length ("C<$len1>"
or "C<$len2>", respectively) is automatically reduced internally
so that "C<$off1 + $len1 E= $vec1-ESize()>" (and
"C<$off2 + $len2 E= $vec2-ESize()>") holds.
(Note that this does B alter the intended result, even though
this may seem counter-intuitive at first!)
This may even result in a length ("C<$len1>" or "C<$len2>") of zero.
A length of zero for the interval in the B