Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | |
2 | =head1 NAME | |
3 | ||
4 | Bit::Vector - Efficient bit vector, set of integers and "big int" math library | |
5 | ||
6 | =head1 SYNOPSIS | |
7 | ||
8 | =head2 OVERLOADED OPERATORS | |
9 | ||
10 | See L<Bit::Vector::Overload(3)>. | |
11 | ||
12 | =head2 CLASS METHODS | |
13 | ||
14 | Version | |
15 | $version = Bit::Vector->Version(); | |
16 | ||
17 | Word_Bits | |
18 | $bits = Bit::Vector->Word_Bits(); # bits in a machine word | |
19 | ||
20 | Long_Bits | |
21 | $bits = Bit::Vector->Long_Bits(); # bits in an unsigned long | |
22 | ||
23 | new | |
24 | $vector = Bit::Vector->new($bits); # bit vector constructor | |
25 | ||
26 | new_Hex | |
27 | $vector = Bit::Vector->new_Hex($bits,$string); | |
28 | ||
29 | new_Bin | |
30 | $vector = Bit::Vector->new_Bin($bits,$string); | |
31 | ||
32 | new_Dec | |
33 | $vector = Bit::Vector->new_Dec($bits,$string); | |
34 | ||
35 | new_Enum | |
36 | $vector = Bit::Vector->new_Enum($bits,$string); | |
37 | ||
38 | Concat_List | |
39 | $vector = Bit::Vector->Concat_List(@vectors); | |
40 | ||
41 | =head2 OBJECT METHODS | |
42 | ||
43 | new | |
44 | $vec2 = $vec1->new($bits); # alternative call of constructor | |
45 | ||
46 | Shadow | |
47 | $vec2 = $vec1->Shadow(); # new vector, same size but empty | |
48 | ||
49 | Clone | |
50 | $vec2 = $vec1->Clone(); # new vector, exact duplicate | |
51 | ||
52 | Concat | |
53 | $vector = $vec1->Concat($vec2); | |
54 | ||
55 | Concat_List | |
56 | $vector = $vec1->Concat_List($vec2,$vec3,...); | |
57 | ||
58 | Size | |
59 | $bits = $vector->Size(); | |
60 | ||
61 | Resize | |
62 | $vector->Resize($bits); | |
63 | $vector->Resize($vector->Size()+5); | |
64 | $vector->Resize($vector->Size()-5); | |
65 | ||
66 | Copy | |
67 | $vec2->Copy($vec1); | |
68 | ||
69 | Empty | |
70 | $vector->Empty(); | |
71 | ||
72 | Fill | |
73 | $vector->Fill(); | |
74 | ||
75 | Flip | |
76 | $vector->Flip(); | |
77 | ||
78 | Primes | |
79 | $vector->Primes(); # Sieve of Erathostenes | |
80 | ||
81 | Reverse | |
82 | $vec2->Reverse($vec1); | |
83 | ||
84 | Interval_Empty | |
85 | $vector->Interval_Empty($min,$max); | |
86 | ||
87 | Interval_Fill | |
88 | $vector->Interval_Fill($min,$max); | |
89 | ||
90 | Interval_Flip | |
91 | $vector->Interval_Flip($min,$max); | |
92 | ||
93 | Interval_Reverse | |
94 | $vector->Interval_Reverse($min,$max); | |
95 | ||
96 | Interval_Scan_inc | |
97 | if (($min,$max) = $vector->Interval_Scan_inc($start)) | |
98 | ||
99 | Interval_Scan_dec | |
100 | if (($min,$max) = $vector->Interval_Scan_dec($start)) | |
101 | ||
102 | Interval_Copy | |
103 | $vec2->Interval_Copy($vec1,$offset2,$offset1,$length); | |
104 | ||
105 | Interval_Substitute | |
106 | $vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1); | |
107 | ||
108 | is_empty | |
109 | if ($vector->is_empty()) | |
110 | ||
111 | is_full | |
112 | if ($vector->is_full()) | |
113 | ||
114 | equal | |
115 | if ($vec1->equal($vec2)) | |
116 | ||
117 | Lexicompare (unsigned) | |
118 | if ($vec1->Lexicompare($vec2) == 0) | |
119 | if ($vec1->Lexicompare($vec2) != 0) | |
120 | if ($vec1->Lexicompare($vec2) < 0) | |
121 | if ($vec1->Lexicompare($vec2) <= 0) | |
122 | if ($vec1->Lexicompare($vec2) > 0) | |
123 | if ($vec1->Lexicompare($vec2) >= 0) | |
124 | ||
125 | Compare (signed) | |
126 | if ($vec1->Compare($vec2) == 0) | |
127 | if ($vec1->Compare($vec2) != 0) | |
128 | if ($vec1->Compare($vec2) < 0) | |
129 | if ($vec1->Compare($vec2) <= 0) | |
130 | if ($vec1->Compare($vec2) > 0) | |
131 | if ($vec1->Compare($vec2) >= 0) | |
132 | ||
133 | to_Hex | |
134 | $string = $vector->to_Hex(); | |
135 | ||
136 | from_Hex | |
137 | $vector->from_Hex($string); | |
138 | ||
139 | to_Bin | |
140 | $string = $vector->to_Bin(); | |
141 | ||
142 | from_Bin | |
143 | $vector->from_Bin($string); | |
144 | ||
145 | to_Dec | |
146 | $string = $vector->to_Dec(); | |
147 | ||
148 | from_Dec | |
149 | $vector->from_Dec($string); | |
150 | ||
151 | to_Enum | |
152 | $string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19" | |
153 | ||
154 | from_Enum | |
155 | $vector->from_Enum($string); | |
156 | ||
157 | Bit_Off | |
158 | $vector->Bit_Off($index); | |
159 | ||
160 | Bit_On | |
161 | $vector->Bit_On($index); | |
162 | ||
163 | bit_flip | |
164 | $bit = $vector->bit_flip($index); | |
165 | ||
166 | bit_test, contains | |
167 | $bit = $vector->bit_test($index); | |
168 | $bit = $vector->contains($index); | |
169 | if ($vector->bit_test($index)) | |
170 | if ($vector->contains($index)) | |
171 | ||
172 | Bit_Copy | |
173 | $vector->Bit_Copy($index,$bit); | |
174 | ||
175 | LSB (least significant bit) | |
176 | $vector->LSB($bit); | |
177 | ||
178 | MSB (most significant bit) | |
179 | $vector->MSB($bit); | |
180 | ||
181 | lsb (least significant bit) | |
182 | $bit = $vector->lsb(); | |
183 | ||
184 | msb (most significant bit) | |
185 | $bit = $vector->msb(); | |
186 | ||
187 | rotate_left | |
188 | $carry = $vector->rotate_left(); | |
189 | ||
190 | rotate_right | |
191 | $carry = $vector->rotate_right(); | |
192 | ||
193 | shift_left | |
194 | $carry = $vector->shift_left($carry); | |
195 | ||
196 | shift_right | |
197 | $carry = $vector->shift_right($carry); | |
198 | ||
199 | Move_Left | |
200 | $vector->Move_Left($bits); # shift left "$bits" positions | |
201 | ||
202 | Move_Right | |
203 | $vector->Move_Right($bits); # shift right "$bits" positions | |
204 | ||
205 | Insert | |
206 | $vector->Insert($offset,$bits); | |
207 | ||
208 | Delete | |
209 | $vector->Delete($offset,$bits); | |
210 | ||
211 | increment | |
212 | $carry = $vector->increment(); | |
213 | ||
214 | decrement | |
215 | $carry = $vector->decrement(); | |
216 | ||
217 | inc | |
218 | $overflow = $vec2->inc($vec1); | |
219 | ||
220 | dec | |
221 | $overflow = $vec2->dec($vec1); | |
222 | ||
223 | add | |
224 | $carry = $vec3->add($vec1,$vec2,$carry); | |
225 | ($carry,$overflow) = $vec3->add($vec1,$vec2,$carry); | |
226 | ||
227 | subtract | |
228 | $carry = $vec3->subtract($vec1,$vec2,$carry); | |
229 | ($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry); | |
230 | ||
231 | Negate | |
232 | $vec2->Negate($vec1); | |
233 | ||
234 | Absolute | |
235 | $vec2->Absolute($vec1); | |
236 | ||
237 | Sign | |
238 | if ($vector->Sign() == 0) | |
239 | if ($vector->Sign() != 0) | |
240 | if ($vector->Sign() < 0) | |
241 | if ($vector->Sign() <= 0) | |
242 | if ($vector->Sign() > 0) | |
243 | if ($vector->Sign() >= 0) | |
244 | ||
245 | Multiply | |
246 | $vec3->Multiply($vec1,$vec2); | |
247 | ||
248 | Divide | |
249 | $quot->Divide($vec1,$vec2,$rest); | |
250 | ||
251 | GCD (Greatest Common Divisor) | |
252 | $vec3->GCD($vec1,$vec2); | |
253 | ||
254 | Power | |
255 | $vec3->Power($vec1,$vec2); | |
256 | ||
257 | Block_Store | |
258 | $vector->Block_Store($buffer); | |
259 | ||
260 | Block_Read | |
261 | $buffer = $vector->Block_Read(); | |
262 | ||
263 | Word_Size | |
264 | $size = $vector->Word_Size(); # number of words in "$vector" | |
265 | ||
266 | Word_Store | |
267 | $vector->Word_Store($offset,$word); | |
268 | ||
269 | Word_Read | |
270 | $word = $vector->Word_Read($offset); | |
271 | ||
272 | Word_List_Store | |
273 | $vector->Word_List_Store(@words); | |
274 | ||
275 | Word_List_Read | |
276 | @words = $vector->Word_List_Read(); | |
277 | ||
278 | Word_Insert | |
279 | $vector->Word_Insert($offset,$count); | |
280 | ||
281 | Word_Delete | |
282 | $vector->Word_Delete($offset,$count); | |
283 | ||
284 | Chunk_Store | |
285 | $vector->Chunk_Store($chunksize,$offset,$chunk); | |
286 | ||
287 | Chunk_Read | |
288 | $chunk = $vector->Chunk_Read($chunksize,$offset); | |
289 | ||
290 | Chunk_List_Store | |
291 | $vector->Chunk_List_Store($chunksize,@chunks); | |
292 | ||
293 | Chunk_List_Read | |
294 | @chunks = $vector->Chunk_List_Read($chunksize); | |
295 | ||
296 | Index_List_Remove | |
297 | $vector->Index_List_Remove(@indices); | |
298 | ||
299 | Index_List_Store | |
300 | $vector->Index_List_Store(@indices); | |
301 | ||
302 | Index_List_Read | |
303 | @indices = $vector->Index_List_Read(); | |
304 | ||
305 | Union | |
306 | $set3->Union($set1,$set2); | |
307 | ||
308 | Intersection | |
309 | $set3->Intersection($set1,$set2); | |
310 | ||
311 | Difference | |
312 | $set3->Difference($set1,$set2); | |
313 | ||
314 | ExclusiveOr | |
315 | $set3->ExclusiveOr($set1,$set2); | |
316 | ||
317 | Complement | |
318 | $set2->Complement($set1); | |
319 | ||
320 | subset | |
321 | if ($set1->subset($set2)) # true if $set1 is subset of $set2 | |
322 | ||
323 | Norm | |
324 | $norm = $set->Norm(); | |
325 | ||
326 | Min | |
327 | $min = $set->Min(); | |
328 | ||
329 | Max | |
330 | $max = $set->Max(); | |
331 | ||
332 | Multiplication | |
333 | $matrix3->Multiplication($rows3,$cols3, | |
334 | $matrix1,$rows1,$cols1, | |
335 | $matrix2,$rows2,$cols2); | |
336 | ||
337 | Product | |
338 | $matrix3->Product($rows3,$cols3, | |
339 | $matrix1,$rows1,$cols1, | |
340 | $matrix2,$rows2,$cols2); | |
341 | ||
342 | Closure | |
343 | $matrix->Closure($rows,$cols); | |
344 | ||
345 | Transpose | |
346 | $matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1); | |
347 | ||
348 | =head1 IMPORTANT NOTES | |
349 | ||
350 | =over 2 | |
351 | ||
352 | =item * | |
353 | ||
354 | Method naming conventions | |
355 | ||
356 | Method names completely in lower case indicate a boolean return value. | |
357 | ||
358 | (Except for the bit vector constructor method "C<new()>", of course.) | |
359 | ||
360 | =item * | |
361 | ||
362 | Boolean values | |
363 | ||
364 | Boolean values in this module are always a numeric zero ("C<0>") for | |
365 | "false" and a numeric one ("C<1>") for "true". | |
366 | ||
367 | =item * | |
368 | ||
369 | Negative numbers | |
370 | ||
371 | All numeric input parameters passed to any of the methods in this module | |
372 | are regarded as being B<UNSIGNED> (as opposed to the contents of the | |
373 | bit vectors themselves, which are usually considered to be B<SIGNED>). | |
374 | ||
375 | As a consequence, whenever you pass a negative number as an argument to | |
376 | some method of this module, it will be treated as a (usually very large) | |
377 | positive number due to its internal two's complement binary representation, | |
378 | usually resulting in an "index out of range" error message and program | |
379 | abortion. | |
380 | ||
381 | =item * | |
382 | ||
383 | Bit order | |
384 | ||
385 | Note that bit vectors are stored least order bit and least order word first | |
386 | internally. | |
387 | ||
388 | I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0 in the | |
389 | array of machine words representing the bit vector. | |
390 | ||
391 | (Where word #0 comes first in memory, i.e., it is stored at the least memory | |
392 | address in the allocated block of memory holding the given bit vector.) | |
393 | ||
394 | Note however that machine words can be stored least order byte first or last, | |
395 | depending on your system's implementation. | |
396 | ||
397 | When you are exporting or importing a whole bit vector at once using the | |
398 | methods "C<Block_Read()>" and "C<Block_Store()>" (the only time in this | |
399 | module where this could make any difference), however, a conversion to and | |
400 | from "least order byte first" order is automatically supplied. | |
401 | ||
402 | In other words, what "C<Block_Read()>" provides and what "C<Block_Store()>" | |
403 | expects is always in "least order byte first" order, regardless of the order | |
404 | in which words are stored internally on your machine. | |
405 | ||
406 | This is to make sure that what you export on one machine using "C<Block_Read()>" | |
407 | can always be read in correctly with "C<Block_Store()>" on a different machine. | |
408 | ||
409 | Note further that whenever bit vectors are converted to and from (binary or | |
410 | hexadecimal) strings, the B<RIGHTMOST> bit is always the B<LEAST SIGNIFICANT> | |
411 | one, and the B<LEFTMOST> bit is always the B<MOST SIGNIFICANT> bit. | |
412 | ||
413 | This is because in our western culture, numbers are always represented in this | |
414 | way (least significant to most significant digits go from right to left). | |
415 | ||
416 | Of course this requires an internal reversion of order, which the corresponding | |
417 | conversion methods perform automatically (without any additional overhead, it's | |
418 | just a matter of starting the internal loop at the bottom or the top end). | |
419 | ||
420 | =item * | |
421 | ||
422 | "Word" related methods | |
423 | ||
424 | Note that all methods whose names begin with "C<Word_>" are | |
425 | B<MACHINE-DEPENDENT>! | |
426 | ||
427 | They depend on the size (number of bits) of an "unsigned int" (C type) on | |
428 | your machine. | |
429 | ||
430 | Therefore, you should only use these methods if you are B<ABSOLUTELY CERTAIN> | |
431 | that portability of your code is not an issue! | |
432 | ||
433 | Note that you can use arbitrarily large chunks (i.e., fragments of bit vectors) | |
434 | of up to 32 bits B<IN A PORTABLE WAY> using the methods whose names begin with | |
435 | "C<Chunk_>". | |
436 | ||
437 | =item * | |
438 | ||
439 | Chunk sizes | |
440 | ||
441 | Note that legal chunk sizes for all methods whose names begin with "C<Chunk_>" | |
442 | range from "C<1>" to "C<Bit::Vector-E<gt>Long_Bits();>" bits ("C<0>" is B<NOT> | |
443 | allowed!). | |
444 | ||
445 | In order to make your programs portable, however, you shouldn't use chunk sizes | |
446 | larger than 32 bits, since this is the minimum size of an "unsigned long" | |
447 | (C type) on all systems, as prescribed by S<ANSI C>. | |
448 | ||
449 | =item * | |
450 | ||
451 | Matching sizes | |
452 | ||
453 | In general, for methods involving several bit vectors at the same time, all | |
454 | bit vector arguments must have identical sizes (number of bits), or a fatal | |
455 | "size mismatch" error will occur. | |
456 | ||
457 | Exceptions from this rule are the methods "C<Concat()>", "C<Concat_List()>", | |
458 | "C<Copy()>", "C<Interval_Copy()>" and "C<Interval_Substitute()>", where no | |
459 | conditions at all are imposed on the size of their bit vector arguments. | |
460 | ||
461 | In method "C<Multiply()>", all three bit vector arguments must in principle | |
462 | obey the rule of matching sizes, but the bit vector in which the result of | |
463 | the multiplication is to be stored may be larger than the two bit vector | |
464 | arguments containing the factors for the multiplication. | |
465 | ||
466 | In method "C<Power()>", the bit vector for the result must be the same | |
467 | size or greater than the base of the exponentiation term. The exponent | |
468 | can be any size. | |
469 | ||
470 | =item * | |
471 | ||
472 | Index ranges | |
473 | ||
474 | All indices for any given bits must lie between "C<0>" and | |
475 | "C<$vector-E<gt>Size()-1>", or a fatal "index out of range" | |
476 | error will occur. | |
477 | ||
478 | =back | |
479 | ||
480 | =head1 DESCRIPTION | |
481 | ||
482 | =head2 OVERLOADED OPERATORS | |
483 | ||
484 | See L<Bit::Vector::Overload(3)>. | |
485 | ||
486 | =head2 CLASS METHODS | |
487 | ||
488 | =over 2 | |
489 | ||
490 | =item * | |
491 | ||
492 | C<$version = Bit::Vector-E<gt>Version();> | |
493 | ||
494 | Returns the current version number of this module. | |
495 | ||
496 | =item * | |
497 | ||
498 | C<$bits = Bit::Vector-E<gt>Word_Bits();> | |
499 | ||
500 | Returns the number of bits of an "unsigned int" (C type) | |
501 | on your machine. | |
502 | ||
503 | (An "unsigned int" is also called a "machine word", | |
504 | hence the name of this method.) | |
505 | ||
506 | =item * | |
507 | ||
508 | C<$bits = Bit::Vector-E<gt>Long_Bits();> | |
509 | ||
510 | Returns the number of bits of an "unsigned long" (C type) | |
511 | on your machine. | |
512 | ||
513 | =item * | |
514 | ||
515 | C<$vector = Bit::Vector-E<gt>new($bits);> | |
516 | ||
517 | This is the bit vector constructor method. | |
518 | ||
519 | Call this method to create a new bit vector containing "C<$bits>" | |
520 | bits (with indices ranging from "C<0>" to "C<$bits-1>"). | |
521 | ||
522 | Note that - in contrast to previous versions - bit vectors | |
523 | of length zero (i.e., with C<$bits = 0>) are permitted now. | |
524 | ||
525 | The method returns a reference to the newly created bit vector. | |
526 | ||
527 | A new bit vector is always initialized so that all bits are cleared | |
528 | (turned off). | |
529 | ||
530 | An exception will be raised if the method is unable to allocate the | |
531 | necessary memory. | |
532 | ||
533 | Note that if you specify a negative number for "C<$bits>" it will be | |
534 | interpreted as a large positive number due to its internal two's | |
535 | complement binary representation. | |
536 | ||
537 | In such a case, the bit vector constructor method will obediently attempt | |
538 | to create a bit vector of that size, probably resulting in an exception, | |
539 | as explained above. | |
540 | ||
541 | =item * | |
542 | ||
543 | C<$vector = Bit::Vector-E<gt>new_Hex($bits,$string);> | |
544 | ||
545 | This method is an alternative constructor which allows you to create | |
546 | a new bit vector object (with "C<$bits>" bits) and to initialize it | |
547 | all in one go. | |
548 | ||
549 | The method is more efficient than performing these two steps separately | |
550 | first because in this method, the memory area occupied by the new bit | |
551 | vector is not initialized to zeros (which is pointless in this case), | |
552 | and second because it saves you from the associated overhead of one | |
553 | additional method invocation. | |
554 | ||
555 | The method first calls the bit vector constructor method "C<new()>" | |
556 | internally, and then passes the given string to the method "C<from_Hex()>". | |
557 | ||
558 | An exception will be raised if the necessary memory cannot be allocated | |
559 | (see the description of the method "C<new()>" immediately above for | |
560 | possible causes) or if the given string cannot be converted successfully | |
561 | (see the description of the method "C<from_Hex()>" further below for | |
562 | details). | |
563 | ||
564 | In the latter case, the memory occupied by the new bit vector is | |
565 | released first (i.e., "free"d) before the exception is actually | |
566 | raised. | |
567 | ||
568 | =item * | |
569 | ||
570 | C<$vector = Bit::Vector-E<gt>new_Bin($bits,$string);> | |
571 | ||
572 | This method is an alternative constructor which allows you to create | |
573 | a new bit vector object (with "C<$bits>" bits) and to initialize it | |
574 | all in one go. | |
575 | ||
576 | The method is more efficient than performing these two steps separately | |
577 | first because in this method, the memory area occupied by the new bit | |
578 | vector is not initialized to zeros (which is pointless in this case), | |
579 | and second because it saves you from the associated overhead of one | |
580 | additional method invocation. | |
581 | ||
582 | The method first calls the bit vector constructor method "C<new()>" | |
583 | internally, and then passes the given string to the method "C<from_Bin()>". | |
584 | ||
585 | An exception will be raised if the necessary memory cannot be allocated | |
586 | (see the description of the method "C<new()>" above for possible causes) | |
587 | or if the given string cannot be converted successfully (see the | |
588 | description of the method "C<from_Bin()>" further below for details). | |
589 | ||
590 | In the latter case, the memory occupied by the new bit vector is | |
591 | released first (i.e., "free"d) before the exception is actually | |
592 | raised. | |
593 | ||
594 | =item * | |
595 | ||
596 | C<$vector = Bit::Vector-E<gt>new_Dec($bits,$string);> | |
597 | ||
598 | This method is an alternative constructor which allows you to create | |
599 | a new bit vector object (with "C<$bits>" bits) and to initialize it | |
600 | all in one go. | |
601 | ||
602 | The method is more efficient than performing these two steps separately | |
603 | first because in this method, the memory area occupied by the new bit | |
604 | vector is not initialized to zeros (which is pointless in this case), | |
605 | and second because it saves you from the associated overhead of one | |
606 | additional method invocation. | |
607 | ||
608 | The method first calls the bit vector constructor method "C<new()>" | |
609 | internally, and then passes the given string to the method "C<from_Dec()>". | |
610 | ||
611 | An exception will be raised if the necessary memory cannot be allocated | |
612 | (see the description of the method "C<new()>" above for possible causes) | |
613 | or if the given string cannot be converted successfully (see the | |
614 | description of the method "C<from_Dec()>" further below for details). | |
615 | ||
616 | In the latter case, the memory occupied by the new bit vector is | |
617 | released first (i.e., "free"d) before the exception is actually | |
618 | raised. | |
619 | ||
620 | =item * | |
621 | ||
622 | C<$vector = Bit::Vector-E<gt>new_Enum($bits,$string);> | |
623 | ||
624 | This method is an alternative constructor which allows you to create | |
625 | a new bit vector object (with "C<$bits>" bits) and to initialize it | |
626 | all in one go. | |
627 | ||
628 | The method is more efficient than performing these two steps separately | |
629 | first because in this method, the memory area occupied by the new bit | |
630 | vector is not initialized to zeros (which is pointless in this case), | |
631 | and second because it saves you from the associated overhead of one | |
632 | additional method invocation. | |
633 | ||
634 | The method first calls the bit vector constructor method "C<new()>" | |
635 | internally, and then passes the given string to the method "C<from_Enum()>". | |
636 | ||
637 | An exception will be raised if the necessary memory cannot be allocated | |
638 | (see the description of the method "C<new()>" above for possible causes) | |
639 | or if the given string cannot be converted successfully (see the | |
640 | description of the method "C<from_Enum()>" further below for details). | |
641 | ||
642 | In the latter case, the memory occupied by the new bit vector is | |
643 | released first (i.e., "free"d) before the exception is actually | |
644 | raised. | |
645 | ||
646 | =item * | |
647 | ||
648 | C<$vector = Bit::Vector-E<gt>Concat_List(@vectors);> | |
649 | ||
650 | This method creates a new vector containing all bit vectors from the | |
651 | argument list in concatenated form. | |
652 | ||
653 | The argument list may contain any number of arguments (including | |
654 | zero); the only condition is that all arguments must be bit vectors. | |
655 | ||
656 | There is no condition concerning the length (in number of bits) of | |
657 | these arguments. | |
658 | ||
659 | The vectors from the argument list are not changed in any way. | |
660 | ||
661 | If the argument list is empty or if all arguments have length zero, | |
662 | the resulting bit vector will also have length zero. | |
663 | ||
664 | Note that the B<RIGHTMOST> bit vector from the argument list will | |
665 | become the B<LEAST> significant part of the resulting bit vector, | |
666 | and the B<LEFTMOST> bit vector from the argument list will | |
667 | become the B<MOST> significant part of the resulting bit vector. | |
668 | ||
669 | =back | |
670 | ||
671 | =head2 OBJECT METHODS | |
672 | ||
673 | =over 2 | |
674 | ||
675 | =item * | |
676 | ||
677 | C<$vec2 = $vec1-E<gt>new($bits);> | |
678 | ||
679 | This is an alternative way of calling the bit vector constructor method. | |
680 | ||
681 | Vector "C<$vec1>" is not affected by this, it just serves as an anchor | |
682 | for the method invocation mechanism. | |
683 | ||
684 | In fact B<ALL> class methods in this module can be called this way, | |
685 | even though this is probably considered to be "politically incorrect" | |
686 | by OO ("object-orientation") aficionados. ;-) | |
687 | ||
688 | So even if you are too lazy to type "C<Bit::Vector-E<gt>>" instead of | |
689 | "C<$vec1-E<gt>>" (and even though laziness is - allegedly - a programmer's | |
690 | virtue C<:-)>), maybe it is better not to use this feature if you don't | |
691 | want to get booed at. ;-) | |
692 | ||
693 | =item * | |
694 | ||
695 | C<$vec2 = $vec1-E<gt>Shadow();> | |
696 | ||
697 | Creates a B<NEW> bit vector "C<$vec2>" of the B<SAME SIZE> as "C<$vec1>" | |
698 | but which is B<EMPTY>. | |
699 | ||
700 | Just like a shadow that has the same shape as the object it | |
701 | originates from, but is flat and has no volume, i.e., contains | |
702 | nothing. | |
703 | ||
704 | =item * | |
705 | ||
706 | C<$vec2 = $vec1-E<gt>Clone();> | |
707 | ||
708 | Creates a B<NEW> bit vector "C<$vec2>" of the B<SAME SIZE> as "C<$vec1>" | |
709 | which is an B<EXACT COPY> of "C<$vec1>". | |
710 | ||
711 | =item * | |
712 | ||
713 | C<$vector = $vec1-E<gt>Concat($vec2);> | |
714 | ||
715 | This method returns a new bit vector object which is the result of the | |
716 | concatenation of the contents of "C<$vec1>" and "C<$vec2>". | |
717 | ||
718 | Note that the contents of "C<$vec1>" become the B<MOST> significant part | |
719 | of the resulting bit vector, and "C<$vec2>" the B<LEAST> significant part. | |
720 | ||
721 | If both bit vector arguments have length zero, the resulting bit vector | |
722 | will also have length zero. | |
723 | ||
724 | =item * | |
725 | ||
726 | C<$vector = $vec1-E<gt>Concat_List($vec2,$vec3,...);> | |
727 | ||
728 | This is an alternative way of calling this (class) method as an | |
729 | object method. | |
730 | ||
731 | The method returns a new bit vector object which is the result of | |
732 | the concatenation of the contents of C<$vec1 . $vec2 . $vec3 . ...> | |
733 | ||
734 | See the section "class methods" above for a detailed description of | |
735 | this method. | |
736 | ||
737 | Note that the argument list may be empty and that all arguments | |
738 | must be bit vectors if it isn't. | |
739 | ||
740 | =item * | |
741 | ||
742 | C<$bits = $vector-E<gt>Size();> | |
743 | ||
744 | Returns the size (number of bits) the given vector was created with | |
745 | (or "C<Resize()>"d to). | |
746 | ||
747 | =item * | |
748 | ||
749 | C<$vector-E<gt>Resize($bits);> | |
750 | ||
751 | Changes the size of the given vector to the specified number of bits. | |
752 | ||
753 | This method allows you to change the size of an existing bit vector, | |
754 | preserving as many bits from the old vector as will fit into the | |
755 | new one (i.e., all bits with indices smaller than the minimum of the | |
756 | sizes of both vectors, old and new). | |
757 | ||
758 | If the number of machine words needed to store the new vector is smaller | |
759 | than or equal to the number of words needed to store the old vector, the | |
760 | memory allocated for the old vector is reused for the new one, and only | |
761 | the relevant book-keeping information is adjusted accordingly. | |
762 | ||
763 | This means that even if the number of bits increases, new memory is not | |
764 | necessarily being allocated (i.e., if the old and the new number of bits | |
765 | fit into the same number of machine words). | |
766 | ||
767 | If the number of machine words needed to store the new vector is greater | |
768 | than the number of words needed to store the old vector, new memory is | |
769 | allocated for the new vector, the old vector is copied to the new one, | |
770 | the remaining bits in the new vector are cleared (turned off) and the old | |
771 | vector is deleted, i.e., the memory that was allocated for it is released. | |
772 | ||
773 | (An exception will be raised if the method is unable to allocate the | |
774 | necessary memory for the new vector.) | |
775 | ||
776 | As a consequence, if you decrease the size of a given vector so that | |
777 | it will use fewer machine words, and increase it again later so that it | |
778 | will use more words than immediately before but still less than the | |
779 | original vector, new memory will be allocated anyway because the | |
780 | information about the size of the original vector is lost whenever | |
781 | you resize it. | |
782 | ||
783 | Note also that if you specify a negative number for "C<$bits>" it will | |
784 | be interpreted as a large positive number due to its internal two's | |
785 | complement binary representation. | |
786 | ||
787 | In such a case, "Resize()" will obediently attempt to create a bit | |
788 | vector of that size, probably resulting in an exception, as explained | |
789 | above. | |
790 | ||
791 | Finally, note that - in contrast to previous versions - resizing a bit | |
792 | vector to a size of zero bits (length zero) is now permitted. | |
793 | ||
794 | =item * | |
795 | ||
796 | C<$vec2-E<gt>Copy($vec1);> | |
797 | ||
798 | Copies the contents of bit vector "C<$vec1>" to bit vector "C<$vec2>". | |
799 | ||
800 | The previous contents of bit vector "C<$vec2>" get overwritten, i.e., | |
801 | are lost. | |
802 | ||
803 | Both vectors must exist beforehand, i.e., this method does not B<CREATE> | |
804 | any new bit vector object. | |
805 | ||
806 | The two vectors may be of any size. | |
807 | ||
808 | If the source bit vector is larger than the target, this method will copy | |
809 | as much of the least significant bits of the source vector as will fit into | |
810 | the target vector, thereby discarding any extraneous most significant bits. | |
811 | ||
812 | BEWARE that this causes a brutal cutoff in the middle of your data, and it | |
813 | will also leave you with an almost unpredictable sign if subsequently the | |
814 | number in the target vector is going to be interpreted as a number! (You | |
815 | have been warned!) | |
816 | ||
817 | If the target bit vector is larger than the source, this method fills up | |
818 | the remaining most significant bits in the target bit vector with either | |
819 | 0's or 1's, depending on the sign (= the most significant bit) of the | |
820 | source bit vector. | |
821 | ||
822 | This makes it possible to copy numbers from a smaller bit vector into | |
823 | a larger one while preserving the number's absolute value as well as | |
824 | its sign (due to the two's complement binary representation of numbers). | |
825 | ||
826 | =item * | |
827 | ||
828 | C<$vector-E<gt>Empty();> | |
829 | ||
830 | Clears all bits in the given vector. | |
831 | ||
832 | =item * | |
833 | ||
834 | C<$vector-E<gt>Fill();> | |
835 | ||
836 | Sets all bits in the given vector. | |
837 | ||
838 | =item * | |
839 | ||
840 | C<$vector-E<gt>Flip();> | |
841 | ||
842 | Flips (i.e., complements) all bits in the given vector. | |
843 | ||
844 | =item * | |
845 | ||
846 | C<$vector-E<gt>Primes();> | |
847 | ||
848 | Clears the given bit vector and sets all bits whose | |
849 | indices are prime numbers. | |
850 | ||
851 | This method uses the algorithm known as the "Sieve of | |
852 | Erathostenes" internally. | |
853 | ||
854 | =item * | |
855 | ||
856 | C<$vec2-E<gt>Reverse($vec1);> | |
857 | ||
858 | This method copies the given vector "C<$vec1>" to | |
859 | the vector "C<$vec2>", thereby reversing the order | |
860 | of all bits. | |
861 | ||
862 | I.e., the least significant bit of "C<$vec1>" becomes the | |
863 | most significant bit of "C<$vec2>", whereas the most | |
864 | significant bit of "C<$vec1>" becomes the least | |
865 | significant bit of "C<$vec2>", and so forth | |
866 | for all bits in between. | |
867 | ||
868 | Note that in-place processing is also possible, i.e., | |
869 | "C<$vec1>" and "C<$vec2>" may be identical. | |
870 | ||
871 | (Internally, this is the same as | |
872 | C<$vec1-E<gt>Interval_Reverse(0,$vec1-E<gt>Size()-1);>.) | |
873 | ||
874 | =item * | |
875 | ||
876 | C<$vector-E<gt>Interval_Empty($min,$max);> | |
877 | ||
878 | Clears all bits in the interval C<[$min..$max]> (including both limits) | |
879 | in the given vector. | |
880 | ||
881 | "C<$min>" and "C<$max>" may have the same value; this is the same | |
882 | as clearing a single bit with "C<Bit_Off()>" (but less efficient). | |
883 | ||
884 | Note that C<$vector-E<gt>Interval_Empty(0,$vector-E<gt>Size()-1);> | |
885 | is the same as C<$vector-E<gt>Empty();> (but less efficient). | |
886 | ||
887 | =item * | |
888 | ||
889 | C<$vector-E<gt>Interval_Fill($min,$max);> | |
890 | ||
891 | Sets all bits in the interval C<[$min..$max]> (including both limits) | |
892 | in the given vector. | |
893 | ||
894 | "C<$min>" and "C<$max>" may have the same value; this is the same | |
895 | as setting a single bit with "C<Bit_On()>" (but less efficient). | |
896 | ||
897 | Note that C<$vector-E<gt>Interval_Fill(0,$vector-E<gt>Size()-1);> | |
898 | is the same as C<$vector-E<gt>Fill();> (but less efficient). | |
899 | ||
900 | =item * | |
901 | ||
902 | C<$vector-E<gt>Interval_Flip($min,$max);> | |
903 | ||
904 | Flips (i.e., complements) all bits in the interval C<[$min..$max]> | |
905 | (including both limits) in the given vector. | |
906 | ||
907 | "C<$min>" and "C<$max>" may have the same value; this is the same | |
908 | as flipping a single bit with "C<bit_flip()>" (but less efficient). | |
909 | ||
910 | Note that C<$vector-E<gt>Interval_Flip(0,$vector-E<gt>Size()-1);> | |
911 | is the same as C<$vector-E<gt>Flip();> and | |
912 | C<$vector-E<gt>Complement($vector);> | |
913 | (but less efficient). | |
914 | ||
915 | =item * | |
916 | ||
917 | C<$vector-E<gt>Interval_Reverse($min,$max);> | |
918 | ||
919 | Reverses the order of all bits in the interval C<[$min..$max]> | |
920 | (including both limits) in the given vector. | |
921 | ||
922 | I.e., bits "C<$min>" and "C<$max>" swap places, and so forth | |
923 | for all bits in between. | |
924 | ||
925 | "C<$min>" and "C<$max>" may have the same value; this has no | |
926 | effect whatsoever, though. | |
927 | ||
928 | =item * | |
929 | ||
930 | C<if (($min,$max) = $vector-E<gt>Interval_Scan_inc($start))> | |
931 | ||
932 | Returns the minimum and maximum indices of the next contiguous block | |
933 | of set bits (i.e., bits in the "on" state). | |
934 | ||
935 | The search starts at index "C<$start>" (i.e., C<"$min" E<gt>= "$start">) | |
936 | and proceeds upwards (i.e., C<"$max" E<gt>= "$min">), thus repeatedly | |
937 | increments the search pointer "C<$start>" (internally). | |
938 | ||
939 | Note though that the contents of the variable (or scalar literal value) | |
940 | "C<$start>" is B<NOT> altered. I.e., you have to set it to the desired | |
941 | value yourself prior to each call to "C<Interval_Scan_inc()>" (see also | |
942 | the example given below). | |
943 | ||
944 | Actually, the bit vector is not searched bit by bit, but one machine | |
945 | word at a time, in order to speed up execution (which means that this | |
946 | method is quite efficient). | |
947 | ||
948 | An empty list is returned if no such block can be found. | |
949 | ||
950 | Note that a single set bit (surrounded by cleared bits) is a valid | |
951 | block by this definition. In that case the return values for "C<$min>" | |
952 | and "C<$max>" are the same. | |
953 | ||
954 | Typical use: | |
955 | ||
956 | $start = 0; | |
957 | while (($start < $vector->Size()) && | |
958 | (($min,$max) = $vector->Interval_Scan_inc($start))) | |
959 | { | |
960 | $start = $max + 2; | |
961 | ||
962 | # do something with $min and $max | |
963 | } | |
964 | ||
965 | =item * | |
966 | ||
967 | C<if (($min,$max) = $vector-E<gt>Interval_Scan_dec($start))> | |
968 | ||
969 | Returns the minimum and maximum indices of the next contiguous block | |
970 | of set bits (i.e., bits in the "on" state). | |
971 | ||
972 | The search starts at index "C<$start>" (i.e., C<"$max" E<lt>= "$start">) | |
973 | and proceeds downwards (i.e., C<"$min" E<lt>= "$max">), thus repeatedly | |
974 | decrements the search pointer "C<$start>" (internally). | |
975 | ||
976 | Note though that the contents of the variable (or scalar literal value) | |
977 | "C<$start>" is B<NOT> altered. I.e., you have to set it to the desired | |
978 | value yourself prior to each call to "C<Interval_Scan_dec()>" (see also | |
979 | the example given below). | |
980 | ||
981 | Actually, the bit vector is not searched bit by bit, but one machine | |
982 | word at a time, in order to speed up execution (which means that this | |
983 | method is quite efficient). | |
984 | ||
985 | An empty list is returned if no such block can be found. | |
986 | ||
987 | Note that a single set bit (surrounded by cleared bits) is a valid | |
988 | block by this definition. In that case the return values for "C<$min>" | |
989 | and "C<$max>" are the same. | |
990 | ||
991 | Typical use: | |
992 | ||
993 | $start = $vector->Size() - 1; | |
994 | while (($start >= 0) && | |
995 | (($min,$max) = $vector->Interval_Scan_dec($start))) | |
996 | { | |
997 | $start = $min - 2; | |
998 | ||
999 | # do something with $min and $max | |
1000 | } | |
1001 | ||
1002 | =item * | |
1003 | ||
1004 | C<$vec2-E<gt>Interval_Copy($vec1,$offset2,$offset1,$length);> | |
1005 | ||
1006 | This method allows you to copy a stretch of contiguous bits (starting | |
1007 | at any position "C<$offset1>" you choose, with a length of "C<$length>" | |
1008 | bits) from a given "source" bit vector "C<$vec1>" to another position | |
1009 | "C<$offset2>" in a "target" bit vector "C<$vec2>". | |
1010 | ||
1011 | Note that the two bit vectors "C<$vec1>" and "C<$vec2>" do B<NOT> | |
1012 | need to have the same (matching) size! | |
1013 | ||
1014 | Consequently, any of the two terms "C<$offset1 + $length>" and | |
1015 | "C<$offset2 + $length>" (or both) may exceed the actual length | |
1016 | of its corresponding bit vector ("C<$vec1-E<gt>Size()>" and | |
1017 | "C<$vec2-E<gt>Size()>", respectively). | |
1018 | ||
1019 | In such a case, the "C<$length>" parameter is automatically reduced | |
1020 | internally so that both terms above are bounded by the number of bits | |
1021 | of their corresponding bit vector. | |
1022 | ||
1023 | This may even result in a length of zero, in which case nothing is | |
1024 | copied at all. | |
1025 | ||
1026 | (Of course the value of the "C<$length>" parameter, supplied by you | |
1027 | in the initial method call, may also be zero right from the start!) | |
1028 | ||
1029 | Note also that "C<$offset1>" and "C<$offset2>" must lie within the | |
1030 | range "C<0>" and, respectively, "C<$vec1-E<gt>Size()-1>" or | |
1031 | "C<$vec2-E<gt>Size()-1>", or a fatal "offset out of range" error | |
1032 | will occur. | |
1033 | ||
1034 | Note further that "C<$vec1>" and "C<$vec2>" may be identical, i.e., | |
1035 | you may copy a stretch of contiguous bits from one part of a given | |
1036 | bit vector to another part. | |
1037 | ||
1038 | The source and the target interval may even overlap, in which case | |
1039 | the copying is automatically performed in ascending or descending | |
1040 | order (depending on the direction of the copy - downwards or upwards | |
1041 | in the bit vector, respectively) to handle this situation correctly, | |
1042 | i.e., so that no bits are being overwritten before they have been | |
1043 | copied themselves. | |
1044 | ||
1045 | =item * | |
1046 | ||
1047 | C<$vec2-E<gt>Interval_Substitute($vec1,$off2,$len2,$off1,$len1);> | |
1048 | ||
1049 | This method is (roughly) the same for bit vectors (i.e., arrays | |
1050 | of booleans) as what the "splice" function in Perl is for lists | |
1051 | (i.e., arrays of scalars). | |
1052 | ||
1053 | (See L<perlfunc/splice> for more details about this function.) | |
1054 | ||
1055 | The method allows you to substitute a stretch of contiguous bits | |
1056 | (defined by a position (offset) "C<$off1>" and a length of "C<$len1>" | |
1057 | bits) from a given "source" bit vector "C<$vec1>" for a different | |
1058 | stretch of contiguous bits (defined by a position (offset) "C<$off2>" | |
1059 | and a length of "C<$len2>" bits) in another, "target" bit vector | |
1060 | "C<$vec2>". | |
1061 | ||
1062 | Note that the two bit vectors "C<$vec1>" and "C<$vec2>" do B<NOT> | |
1063 | need to have the same (matching) size! | |
1064 | ||
1065 | Note further that "C<$off1>" and "C<$off2>" must lie within the | |
1066 | range "C<0>" and, respectively, "C<$vec1-E<gt>Size()>" or | |
1067 | "C<$vec2-E<gt>Size()>", or a fatal "offset out of range" error | |
1068 | will occur. | |
1069 | ||
1070 | Alert readers will have noticed that these upper limits are B<NOT> | |
1071 | "C<$vec1-E<gt>Size()-1>" and "C<$vec2-E<gt>Size()-1>", as they would | |
1072 | be for any other method in this module, but that these offsets may | |
1073 | actually point to one position B<PAST THE END> of the corresponding | |
1074 | bit vector. | |
1075 | ||
1076 | This is necessary in order to make it possible to B<APPEND> a given | |
1077 | stretch of bits to the target bit vector instead of B<REPLACING> | |
1078 | something in it. | |
1079 | ||
1080 | For reasons of symmetry and generality, the same applies to the offset | |
1081 | in the source bit vector, even though such an offset (one position past | |
1082 | the end of the bit vector) does not serve any practical purpose there | |
1083 | (but does not cause any harm either). | |
1084 | ||
1085 | (Actually this saves you from the need of testing for this special case, | |
1086 | in certain circumstances.) | |
1087 | ||
1088 | Note that whenever the term "C<$off1 + $len1>" exceeds the size | |
1089 | "C<$vec1-E<gt>Size()>" of bit vector "C<$vec1>" (or if "C<$off2 + $len2>" | |
1090 | exceeds "C<$vec2-E<gt>Size()>"), the corresponding length ("C<$len1>" | |
1091 | or "C<$len2>", respectively) is automatically reduced internally | |
1092 | so that "C<$off1 + $len1 E<lt>= $vec1-E<gt>Size()>" (and | |
1093 | "C<$off2 + $len2 E<lt>= $vec2-E<gt>Size()>") holds. | |
1094 | ||
1095 | (Note that this does B<NOT> alter the intended result, even though | |
1096 | this may seem counter-intuitive at first!) | |
1097 | ||
1098 | This may even result in a length ("C<$len1>" or "C<$len2>") of zero. | |
1099 | ||
1100 | A length of zero for the interval in the B<SOURCE> bit vector | |
1101 | ("C<$len1 == 0>") means that the indicated stretch of bits in | |
1102 | the target bit vector (starting at position "C<$off2>") is to | |
1103 | be replaced by B<NOTHING>, i.e., is to be B<DELETED>. | |
1104 | ||
1105 | A length of zero for the interval in the B<TARGET> bit vector | |
1106 | ("C<$len2> == 0") means that B<NOTHING> is replaced, and that the | |
1107 | stretch of bits from the source bit vector is simply B<INSERTED> | |
1108 | into the target bit vector at the indicated position ("C<$off2>"). | |
1109 | ||
1110 | If both length parameters are zero, nothing is done at all. | |
1111 | ||
1112 | Note that in contrast to any other method in this module (especially | |
1113 | "C<Interval_Copy()>", "C<Insert()>" and "C<Delete()>"), this method | |
1114 | B<IMPLICITLY> and B<AUTOMATICALLY> adapts the length of the resulting | |
1115 | bit vector as needed, as given by | |
1116 | ||
1117 | $size = $vec2->Size(); # before | |
1118 | $size += $len1 - $len2; # after | |
1119 | ||
1120 | (The only other method in this module that changes the size of a bit | |
1121 | vector is the method "C<Resize()>".) | |
1122 | ||
1123 | In other words, replacing a given interval of bits in the target bit | |
1124 | vector with a longer or shorter stretch of bits from the source bit | |
1125 | vector, or simply inserting ("C<$len2 == 0>") a stretch of bits into | |
1126 | or deleting ("C<$len1 == 0>") an interval of bits from the target bit | |
1127 | vector will automatically increase or decrease, respectively, the size | |
1128 | of the target bit vector accordingly. | |
1129 | ||
1130 | For the sake of generality, this may even result in a bit vector with | |
1131 | a size of zero (containing no bits at all). | |
1132 | ||
1133 | This is also the reason why bit vectors of length zero are permitted | |
1134 | in this module in the first place, starting with version 5.0. | |
1135 | ||
1136 | Finally, note that "C<$vec1>" and "C<$vec2>" may be identical, i.e., | |
1137 | in-place processing is possible. | |
1138 | ||
1139 | (If you think about that for a while or if you look at the code, | |
1140 | you will see that this is far from trivial!) | |
1141 | ||
1142 | =item * | |
1143 | ||
1144 | C<if ($vector-E<gt>is_empty())> | |
1145 | ||
1146 | Tests whether the given bit vector is empty, i.e., whether B<ALL> of | |
1147 | its bits are cleared (in the "off" state). | |
1148 | ||
1149 | In "big integer" arithmetic, this is equivalent to testing whether | |
1150 | the number stored in the bit vector is zero ("C<0>"). | |
1151 | ||
1152 | Returns "true" ("C<1>") if the bit vector is empty and "false" ("C<0>") | |
1153 | otherwise. | |
1154 | ||
1155 | Note that this method also returns "true" ("C<1>") if the given bit | |
1156 | vector has a length of zero, i.e., if it contains no bits at all. | |
1157 | ||
1158 | =item * | |
1159 | ||
1160 | C<if ($vector-E<gt>is_full())> | |
1161 | ||
1162 | Tests whether the given bit vector is full, i.e., whether B<ALL> of | |
1163 | its bits are set (in the "on" state). | |
1164 | ||
1165 | In "big integer" arithmetic, this is equivalent to testing whether | |
1166 | the number stored in the bit vector is minus one ("-1"). | |
1167 | ||
1168 | Returns "true" ("C<1>") if the bit vector is full and "false" ("C<0>") | |
1169 | otherwise. | |
1170 | ||
1171 | If the given bit vector has a length of zero (i.e., if it contains | |
1172 | no bits at all), this method returns "false" ("C<0>"). | |
1173 | ||
1174 | =item * | |
1175 | ||
1176 | C<if ($vec1-E<gt>equal($vec2))> | |
1177 | ||
1178 | Tests the two given bit vectors for equality. | |
1179 | ||
1180 | Returns "true" ("C<1>") if the two bit vectors are exact | |
1181 | copies of one another and "false" ("C<0>") otherwise. | |
1182 | ||
1183 | =item * | |
1184 | ||
1185 | C<$cmp = $vec1-E<gt>Lexicompare($vec2);> | |
1186 | ||
1187 | Compares the two given bit vectors, which are | |
1188 | regarded as B<UNSIGNED> numbers in binary representation. | |
1189 | ||
1190 | The method returns "C<-1>" if the first bit vector is smaller | |
1191 | than the second bit vector, "C<0>" if the two bit vectors are | |
1192 | exact copies of one another and "C<1>" if the first bit vector | |
1193 | is greater than the second bit vector. | |
1194 | ||
1195 | =item * | |
1196 | ||
1197 | C<$cmp = $vec1-E<gt>Compare($vec2);> | |
1198 | ||
1199 | Compares the two given bit vectors, which are | |
1200 | regarded as B<SIGNED> numbers in binary representation. | |
1201 | ||
1202 | The method returns "C<-1>" if the first bit vector is smaller | |
1203 | than the second bit vector, "C<0>" if the two bit vectors are | |
1204 | exact copies of one another and "C<1>" if the first bit vector | |
1205 | is greater than the second bit vector. | |
1206 | ||
1207 | =item * | |
1208 | ||
1209 | C<$string = $vector-E<gt>to_Hex();> | |
1210 | ||
1211 | Returns a hexadecimal string representing the given bit vector. | |
1212 | ||
1213 | Note that this representation is quite compact, in that it only | |
1214 | needs at most twice the number of bytes needed to store the bit | |
1215 | vector itself, internally. | |
1216 | ||
1217 | Note also that since a hexadecimal digit is always worth four bits, | |
1218 | the length of the resulting string is always a multiple of four bits, | |
1219 | regardless of the true length (in bits) of the given bit vector. | |
1220 | ||
1221 | Finally, note that the B<LEAST> significant hexadecimal digit is | |
1222 | located at the B<RIGHT> end of the resulting string, and the B<MOST> | |
1223 | significant digit at the B<LEFT> end. | |
1224 | ||
1225 | =item * | |
1226 | ||
1227 | C<$vector-E<gt>from_Hex($string);> | |
1228 | ||
1229 | Allows to read in the contents of a bit vector from a hexadecimal | |
1230 | string, such as returned by the method "C<to_Hex()>" (see above). | |
1231 | ||
1232 | Remember that the least significant bits are always to the right of a | |
1233 | hexadecimal string, and the most significant bits to the left. Therefore, | |
1234 | the string is actually read in from right to left while the bit vector | |
1235 | is filled accordingly, 4 bits at a time, starting with the least significant | |
1236 | bits and going upward to the most significant bits. | |
1237 | ||
1238 | If the given string contains less hexadecimal digits than are needed | |
1239 | to completely fill the given bit vector, the remaining (most significant) | |
1240 | bits are all cleared. | |
1241 | ||
1242 | This also means that, even if the given string does not contain enough digits | |
1243 | to completely fill the given bit vector, the previous contents of the | |
1244 | bit vector are erased completely. | |
1245 | ||
1246 | If the given string is longer than it needs to fill the given bit vector, | |
1247 | the superfluous characters are simply ignored. | |
1248 | ||
1249 | (In fact they are ignored completely - they are not even checked for | |
1250 | proper syntax. See also below for more about that.) | |
1251 | ||
1252 | This behaviour is intentional so that you may read in the string | |
1253 | representing one bit vector into another bit vector of different | |
1254 | size, i.e., as much of it as will fit. | |
1255 | ||
1256 | If during the process of reading the given string any character is | |
1257 | encountered which is not a hexadecimal digit, a fatal syntax error | |
1258 | ensues ("input string syntax error"). | |
1259 | ||
1260 | =item * | |
1261 | ||
1262 | C<$string = $vector-E<gt>to_Bin();> | |
1263 | ||
1264 | Returns a binary string representing the given bit vector. | |
1265 | ||
1266 | Example: | |
1267 | ||
1268 | $vector = Bit::Vector->new(8); | |
1269 | $vector->Primes(); | |
1270 | $string = $vector->to_Bin(); | |
1271 | print "'$string'\n"; | |
1272 | ||
1273 | This prints: | |
1274 | ||
1275 | '10101100' | |
1276 | ||
1277 | (Bits #7, #5, #3 and #2 are set.) | |
1278 | ||
1279 | Note that the B<LEAST> significant bit is located at the B<RIGHT> | |
1280 | end of the resulting string, and the B<MOST> significant bit at | |
1281 | the B<LEFT> end. | |
1282 | ||
1283 | =item * | |
1284 | ||
1285 | C<$vector-E<gt>from_Bin($string);> | |
1286 | ||
1287 | This method allows you to read in the contents of a bit vector from a | |
1288 | binary string, such as returned by the method "C<to_Bin()>" (see above). | |
1289 | ||
1290 | Note that this method assumes that the B<LEAST> significant bit is located at | |
1291 | the B<RIGHT> end of the binary string, and the B<MOST> significant bit at the | |
1292 | B<LEFT> end. Therefore, the string is actually read in from right to left | |
1293 | while the bit vector is filled accordingly, one bit at a time, starting with | |
1294 | the least significant bit and going upward to the most significant bit. | |
1295 | ||
1296 | If the given string contains less binary digits ("C<0>" and "C<1>") than are | |
1297 | needed to completely fill the given bit vector, the remaining (most significant) | |
1298 | bits are all cleared. | |
1299 | ||
1300 | This also means that, even if the given string does not contain enough digits | |
1301 | to completely fill the given bit vector, the previous contents of the | |
1302 | bit vector are erased completely. | |
1303 | ||
1304 | If the given string is longer than it needs to fill the given bit vector, | |
1305 | the superfluous characters are simply ignored. | |
1306 | ||
1307 | (In fact they are ignored completely - they are not even checked for | |
1308 | proper syntax. See also below for more about that.) | |
1309 | ||
1310 | This behaviour is intentional so that you may read in the string | |
1311 | representing one bit vector into another bit vector of different | |
1312 | size, i.e., as much of it as will fit. | |
1313 | ||
1314 | If during the process of reading the given string any character is | |
1315 | encountered which is not either "C<0>" or "C<1>", a fatal syntax error | |
1316 | ensues ("input string syntax error"). | |
1317 | ||
1318 | =item * | |
1319 | ||
1320 | C<$string = $vector-E<gt>to_Dec();> | |
1321 | ||
1322 | This method returns a string representing the contents of the given bit | |
1323 | vector converted to decimal (base C<10>). | |
1324 | ||
1325 | Note that this method assumes the given bit vector to be B<SIGNED> (and | |
1326 | to contain a number in two's complement binary representation). | |
1327 | ||
1328 | Consequently, whenever the most significant bit of the given bit vector | |
1329 | is set, the number stored in it is regarded as being B<NEGATIVE>. | |
1330 | ||
1331 | The resulting string can be fed into "C<from_Dec()>" (see below) in order | |
1332 | to copy the contents of this bit vector to another one (or to restore the | |
1333 | contents of this one). This is not advisable, though, since this would be | |
1334 | very inefficient (there are much more efficient methods for storing and | |
1335 | copying bit vectors in this module). | |
1336 | ||
1337 | Note that such conversion from binary to decimal is inherently slow | |
1338 | since the bit vector has to be repeatedly divided by C<10> with remainder | |
1339 | until the quotient becomes C<0> (each remainder in turn represents a single | |
1340 | decimal digit of the resulting string). | |
1341 | ||
1342 | This is also true for the implementation of this method in this module, | |
1343 | even though a considerable effort has been made to speed it up: instead of | |
1344 | repeatedly dividing by C<10>, the bit vector is repeatedly divided by the | |
1345 | largest power of C<10> that will fit into a machine word. The remainder is | |
1346 | then repeatedly divided by C<10> using only machine word arithmetics, which | |
1347 | is much faster than dividing the whole bit vector ("divide and rule" principle). | |
1348 | ||
1349 | According to my own measurements, this resulted in an 8-fold speed increase | |
1350 | over the straightforward approach. | |
1351 | ||
1352 | Still, conversion to decimal should be used only where absolutely necessary. | |
1353 | ||
1354 | Keep the resulting string stored in some variable if you need it again, | |
1355 | instead of converting the bit vector all over again. | |
1356 | ||
1357 | Beware that if you set the configuration for overloaded operators to | |
1358 | "output=decimal", this method will be called for every bit vector | |
1359 | enclosed in double quotes! | |
1360 | ||
1361 | =item * | |
1362 | ||
1363 | C<$vector-E<gt>from_Dec($string);> | |
1364 | ||
1365 | This method allows you to convert a given decimal number, which may be | |
1366 | positive or negative, into two's complement binary representation, which | |
1367 | is then stored in the given bit vector. | |
1368 | ||
1369 | The decimal number should always be provided as a string, to avoid possible | |
1370 | truncation (due to the limited precision of integers in Perl) or formatting | |
1371 | (due to Perl's use of scientific notation for large numbers), which would | |
1372 | lead to errors. | |
1373 | ||
1374 | If the binary representation of the given decimal number is too big to fit | |
1375 | into the given bit vector (if the given bit vector does not contain enough | |
1376 | bits to hold it), a fatal "numeric overflow error" occurs. | |
1377 | ||
1378 | If the input string contains other characters than decimal digits (C<0-9>) | |
1379 | and an optional leading sign ("C<+>" or "C<->"), a fatal "input string | |
1380 | syntax error" occurs. | |
1381 | ||
1382 | Beware that large positive numbers which cause the most significant bit to | |
1383 | be set (e.g. "255" in a bit vector with 8 bits) will be printed as negative | |
1384 | numbers when converted back to decimal using the method "to_Dec()" (e.g. | |
1385 | "-1", in our example), because numbers with the most significant bit set | |
1386 | are considered to be negative in two's complement binary representation. | |
1387 | ||
1388 | Note also that while it is possible to thusly enter negative numbers as | |
1389 | large positive numbers (e.g. "255" for "-1" in a bit vector with 8 bits), | |
1390 | the contrary isn't, i.e., you cannot enter "-255" for "+1", in our example. | |
1391 | A fatal "numeric overflow error" will occur if you try to do so. | |
1392 | ||
1393 | If possible program abortion is unwanted or intolerable, use | |
1394 | "C<eval>", like this: | |
1395 | ||
1396 | eval { $vector->from_Dec("1152921504606846976"); }; | |
1397 | if ($@) | |
1398 | { | |
1399 | # an error occurred | |
1400 | } | |
1401 | ||
1402 | There are four possible error messages: | |
1403 | ||
1404 | if ($@ =~ /item is not a string/) | |
1405 | ||
1406 | if ($@ =~ /input string syntax error/) | |
1407 | ||
1408 | if ($@ =~ /numeric overflow error/) | |
1409 | ||
1410 | if ($@ =~ /unable to allocate memory/) | |
1411 | ||
1412 | Note that the conversion from decimal to binary is costly in terms of | |
1413 | processing time, since a lot of multiplications have to be carried out | |
1414 | (in principle, each decimal digit must be multiplied with the binary | |
1415 | representation of the power of C<10> corresponding to its position in | |
1416 | the decimal number, i.e., 1, 10, 100, 1000, 10000 and so on). | |
1417 | ||
1418 | This is not as time consuming as the opposite conversion, from binary | |
1419 | to decimal (where successive divisions have to be carried out, which | |
1420 | are even more expensive than multiplications), but still noticeable. | |
1421 | ||
1422 | Again (as in the case of "C<to_Dec()>"), the implementation of this | |
1423 | method in this module uses the principle of "divide and rule" in order | |
1424 | to speed up the conversion, i.e., as many decimal digits as possible | |
1425 | are first accumulated (converted) in a machine word and only then | |
1426 | stored in the given bit vector. | |
1427 | ||
1428 | Even so, use this method only where absolutely necessary if speed is | |
1429 | an important consideration in your application. | |
1430 | ||
1431 | Beware that if you set the configuration for overloaded operators to | |
1432 | "input=decimal", this method will be called for every scalar operand | |
1433 | you use! | |
1434 | ||
1435 | =item * | |
1436 | ||
1437 | C<$string = $vector-E<gt>to_Enum();> | |
1438 | ||
1439 | Converts the given bit vector or set into an enumeration of single | |
1440 | indices and ranges of indices (".newsrc" style), representing the | |
1441 | bits that are set ("C<1>") in the bit vector. | |
1442 | ||
1443 | Example: | |
1444 | ||
1445 | $vector = Bit::Vector->new(20); | |
1446 | $vector->Bit_On(2); | |
1447 | $vector->Bit_On(3); | |
1448 | $vector->Bit_On(11); | |
1449 | $vector->Interval_Fill(5,7); | |
1450 | $vector->Interval_Fill(13,19); | |
1451 | print "'", $vector->to_Enum(), "'\n"; | |
1452 | ||
1453 | which prints | |
1454 | ||
1455 | '2,3,5-7,11,13-19' | |
1456 | ||
1457 | If the given bit vector is empty, the resulting string will | |
1458 | also be empty. | |
1459 | ||
1460 | Note, by the way, that the above example can also be written | |
1461 | a little handier, perhaps, as follows: | |
1462 | ||
1463 | Bit::Vector->Configuration("out=enum"); | |
1464 | $vector = Bit::Vector->new(20); | |
1465 | $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19); | |
1466 | print "'$vector'\n"; | |
1467 | ||
1468 | =item * | |
1469 | ||
1470 | C<$vector-E<gt>from_Enum($string);> | |
1471 | ||
1472 | This method first empties the given bit vector and then tries to | |
1473 | set the bits and ranges of bits specified in the given string. | |
1474 | ||
1475 | The string "C<$string>" must only contain unsigned integers | |
1476 | or ranges of integers (two unsigned integers separated by a | |
1477 | dash "-"), separated by commas (","). | |
1478 | ||
1479 | All other characters are disallowed (including white space!) | |
1480 | and will lead to a fatal "input string syntax error". | |
1481 | ||
1482 | In each range, the first integer (the lower limit of the range) | |
1483 | must always be less than or equal to the second integer (the | |
1484 | upper limit), or a fatal "minimum > maximum index" error occurs. | |
1485 | ||
1486 | All integers must lie in the permitted range for the given | |
1487 | bit vector, i.e., they must lie between "C<0>" and | |
1488 | "C<$vector-E<gt>Size()-1>". | |
1489 | ||
1490 | If this condition is not met, a fatal "index out of range" | |
1491 | error occurs. | |
1492 | ||
1493 | If possible program abortion is unwanted or intolerable, use | |
1494 | "C<eval>", like this: | |
1495 | ||
1496 | eval { $vector->from_Enum("2,3,5-7,11,13-19"); }; | |
1497 | if ($@) | |
1498 | { | |
1499 | # an error occurred | |
1500 | } | |
1501 | ||
1502 | There are four possible error messages: | |
1503 | ||
1504 | if ($@ =~ /item is not a string/) | |
1505 | ||
1506 | if ($@ =~ /input string syntax error/) | |
1507 | ||
1508 | if ($@ =~ /index out of range/) | |
1509 | ||
1510 | if ($@ =~ /minimum > maximum index/) | |
1511 | ||
1512 | Note that the order of the indices and ranges is irrelevant, | |
1513 | i.e., | |
1514 | ||
1515 | eval { $vector->from_Enum("11,5-7,3,13-19,2"); }; | |
1516 | ||
1517 | results in the same vector as in the example above. | |
1518 | ||
1519 | Ranges and indices may also overlap. | |
1520 | ||
1521 | This is because each (single) index in the string is passed | |
1522 | to the method "C<Bit_On()>", internally, and each range to | |
1523 | the method "C<Interval_Fill()>". | |
1524 | ||
1525 | This means that the resulting bit vector is just the union | |
1526 | of all the indices and ranges specified in the given string. | |
1527 | ||
1528 | =item * | |
1529 | ||
1530 | C<$vector-E<gt>Bit_Off($index);> | |
1531 | ||
1532 | Clears the bit with index "C<$index>" in the given vector. | |
1533 | ||
1534 | =item * | |
1535 | ||
1536 | C<$vector-E<gt>Bit_On($index);> | |
1537 | ||
1538 | Sets the bit with index "C<$index>" in the given vector. | |
1539 | ||
1540 | =item * | |
1541 | ||
1542 | C<$vector-E<gt>bit_flip($index)> | |
1543 | ||
1544 | Flips (i.e., complements) the bit with index "C<$index>" | |
1545 | in the given vector. | |
1546 | ||
1547 | Moreover, this method returns the B<NEW> state of the | |
1548 | bit in question, i.e., it returns "C<0>" if the bit is | |
1549 | cleared or "C<1>" if the bit is set (B<AFTER> flipping it). | |
1550 | ||
1551 | =item * | |
1552 | ||
1553 | C<if ($vector-E<gt>bit_test($index))> | |
1554 | ||
1555 | Returns the current state of the bit with index "C<$index>" | |
1556 | in the given vector, i.e., returns "C<0>" if it is cleared | |
1557 | (in the "off" state) or "C<1>" if it is set (in the "on" state). | |
1558 | ||
1559 | =item * | |
1560 | ||
1561 | C<$vector-E<gt>Bit_Copy($index,$bit);> | |
1562 | ||
1563 | Sets the bit with index "C<$index>" in the given vector either | |
1564 | to "C<0>" or "C<1>" depending on the boolean value "C<$bit>". | |
1565 | ||
1566 | =item * | |
1567 | ||
1568 | C<$vector-E<gt>LSB($bit);> | |
1569 | ||
1570 | Allows you to set the least significant bit in the given bit | |
1571 | vector to the value given by the boolean parameter "C<$bit>". | |
1572 | ||
1573 | This is a (faster) shortcut for "C<$vector-E<gt>Bit_Copy(0,$bit);>". | |
1574 | ||
1575 | =item * | |
1576 | ||
1577 | C<$vector-E<gt>MSB($bit);> | |
1578 | ||
1579 | Allows you to set the most significant bit in the given bit | |
1580 | vector to the value given by the boolean parameter "C<$bit>". | |
1581 | ||
1582 | This is a (faster) shortcut for | |
1583 | "C<$vector-E<gt>Bit_Copy($vector-E<gt>Size()-1,$bit);>". | |
1584 | ||
1585 | =item * | |
1586 | ||
1587 | C<$bit = $vector-E<gt>lsb();> | |
1588 | ||
1589 | Returns the least significant bit of the given bit vector. | |
1590 | ||
1591 | This is a (faster) shortcut for "C<$bit = $vector-E<gt>bit_test(0);>". | |
1592 | ||
1593 | =item * | |
1594 | ||
1595 | C<$bit = $vector-E<gt>msb();> | |
1596 | ||
1597 | Returns the most significant bit of the given bit vector. | |
1598 | ||
1599 | This is a (faster) shortcut for | |
1600 | "C<$bit = $vector-E<gt>bit_test($vector-E<gt>Size()-1);>". | |
1601 | ||
1602 | =item * | |
1603 | ||
1604 | C<$carry_out = $vector-E<gt>rotate_left();> | |
1605 | ||
1606 | carry MSB vector: LSB | |
1607 | out: | |
1608 | +---+ +---+---+---+--- ---+---+---+---+ | |
1609 | | | <---+--- | | | | ... | | | | <---+ | |
1610 | +---+ | +---+---+---+--- ---+---+---+---+ | | |
1611 | | | | |
1612 | +------------------------------------------------+ | |
1613 | ||
1614 | The least significant bit (LSB) is the bit with index "C<0>", the most | |
1615 | significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>". | |
1616 | ||
1617 | =item * | |
1618 | ||
1619 | C<$carry_out = $vector-E<gt>rotate_right();> | |
1620 | ||
1621 | MSB vector: LSB carry | |
1622 | out: | |
1623 | +---+---+---+--- ---+---+---+---+ +---+ | |
1624 | +---> | | | | ... | | | | ---+---> | | | |
1625 | | +---+---+---+--- ---+---+---+---+ | +---+ | |
1626 | | | | |
1627 | +------------------------------------------------+ | |
1628 | ||
1629 | The least significant bit (LSB) is the bit with index "C<0>", the most | |
1630 | significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>". | |
1631 | ||
1632 | =item * | |
1633 | ||
1634 | C<$carry_out = $vector-E<gt>shift_left($carry_in);> | |
1635 | ||
1636 | carry MSB vector: LSB carry | |
1637 | out: in: | |
1638 | +---+ +---+---+---+--- ---+---+---+---+ +---+ | |
1639 | | | <--- | | | | ... | | | | <--- | | | |
1640 | +---+ +---+---+---+--- ---+---+---+---+ +---+ | |
1641 | ||
1642 | The least significant bit (LSB) is the bit with index "C<0>", the most | |
1643 | significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>". | |
1644 | ||
1645 | =item * | |
1646 | ||
1647 | C<$carry_out = $vector-E<gt>shift_right($carry_in);> | |
1648 | ||
1649 | carry MSB vector: LSB carry | |
1650 | in: out: | |
1651 | +---+ +---+---+---+--- ---+---+---+---+ +---+ | |
1652 | | | ---> | | | | ... | | | | ---> | | | |
1653 | +---+ +---+---+---+--- ---+---+---+---+ +---+ | |
1654 | ||
1655 | The least significant bit (LSB) is the bit with index "C<0>", the most | |
1656 | significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>". | |
1657 | ||
1658 | =item * | |
1659 | ||
1660 | C<$vector-E<gt>Move_Left($bits);> | |
1661 | ||
1662 | Shifts the given bit vector left by "C<$bits>" bits, i.e., inserts "C<$bits>" | |
1663 | new bits at the lower end (least significant bit) of the bit vector, moving | |
1664 | all other bits up by "C<$bits>" places, thereby losing the "C<$bits>" most | |
1665 | significant bits. | |
1666 | ||
1667 | The inserted new bits are all cleared (set to the "off" state). | |
1668 | ||
1669 | This method does nothing if "C<$bits>" is equal to zero. | |
1670 | ||
1671 | Beware that the whole bit vector is cleared B<WITHOUT WARNING> if | |
1672 | "C<$bits>" is greater than or equal to the size of the given bit vector! | |
1673 | ||
1674 | In fact this method is equivalent to | |
1675 | ||
1676 | for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); } | |
1677 | ||
1678 | except that it is much more efficient (for "C<$bits>" greater than or | |
1679 | equal to the number of bits in a machine word on your system) than | |
1680 | this straightforward approach. | |
1681 | ||
1682 | =item * | |
1683 | ||
1684 | C<$vector-E<gt>Move_Right($bits);> | |
1685 | ||
1686 | Shifts the given bit vector right by "C<$bits>" bits, i.e., deletes the | |
1687 | "C<$bits>" least significant bits of the bit vector, moving all other bits | |
1688 | down by "C<$bits>" places, thereby creating "C<$bits>" new bits at the upper | |
1689 | end (most significant bit) of the bit vector. | |
1690 | ||
1691 | These new bits are all cleared (set to the "off" state). | |
1692 | ||
1693 | This method does nothing if "C<$bits>" is equal to zero. | |
1694 | ||
1695 | Beware that the whole bit vector is cleared B<WITHOUT WARNING> if | |
1696 | "C<$bits>" is greater than or equal to the size of the given bit vector! | |
1697 | ||
1698 | In fact this method is equivalent to | |
1699 | ||
1700 | for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); } | |
1701 | ||
1702 | except that it is much more efficient (for "C<$bits>" greater than or | |
1703 | equal to the number of bits in a machine word on your system) than | |
1704 | this straightforward approach. | |
1705 | ||
1706 | =item * | |
1707 | ||
1708 | C<$vector-E<gt>Insert($offset,$bits);> | |
1709 | ||
1710 | This method inserts "C<$bits>" fresh new bits at position "C<$offset>" | |
1711 | in the given bit vector. | |
1712 | ||
1713 | The "C<$bits>" most significant bits are lost, and all bits starting | |
1714 | with bit number "C<$offset>" up to and including bit number | |
1715 | "C<$vector-E<gt>Size()-$bits-1>" are moved up by "C<$bits>" places. | |
1716 | ||
1717 | The now vacant "C<$bits>" bits starting at bit number "C<$offset>" | |
1718 | (up to and including bit number "C<$offset+$bits-1>") are then set | |
1719 | to zero (cleared). | |
1720 | ||
1721 | Note that this method does B<NOT> increase the size of the given bit | |
1722 | vector, i.e., the bit vector is B<NOT> extended at its upper end to | |
1723 | "rescue" the "C<$bits>" uppermost (most significant) bits - instead, | |
1724 | these bits are lost forever. | |
1725 | ||
1726 | If you don't want this to happen, you have to increase the size of the | |
1727 | given bit vector B<EXPLICITLY> and B<BEFORE> you perform the "Insert" | |
1728 | operation, with a statement such as the following: | |
1729 | ||
1730 | $vector->Resize($vector->Size() + $bits); | |
1731 | ||
1732 | Or use the method "C<Interval_Substitute()>" instead of "C<Insert()>", | |
1733 | which performs automatic growing and shrinking of its target bit vector. | |
1734 | ||
1735 | Note also that "C<$offset>" must lie in the permitted range between | |
1736 | "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range" | |
1737 | error will occur. | |
1738 | ||
1739 | If the term "C<$offset + $bits>" exceeds "C<$vector-E<gt>Size()-1>", | |
1740 | all the bits starting with bit number "C<$offset>" up to bit number | |
1741 | "C<$vector-E<gt>Size()-1>" are simply cleared. | |
1742 | ||
1743 | =item * | |
1744 | ||
1745 | C<$vector-E<gt>Delete($offset,$bits);> | |
1746 | ||
1747 | This method deletes, i.e., removes the bits starting at position | |
1748 | "C<$offset>" up to and including bit number "C<$offset+$bits-1>" | |
1749 | from the given bit vector. | |
1750 | ||
1751 | The remaining uppermost bits (starting at position "C<$offset+$bits>" | |
1752 | up to and including bit number "C<$vector-E<gt>Size()-1>") are moved | |
1753 | down by "C<$bits>" places. | |
1754 | ||
1755 | The now vacant uppermost (most significant) "C<$bits>" bits are then | |
1756 | set to zero (cleared). | |
1757 | ||
1758 | Note that this method does B<NOT> decrease the size of the given bit | |
1759 | vector, i.e., the bit vector is B<NOT> clipped at its upper end to | |
1760 | "get rid of" the vacant "C<$bits>" uppermost bits. | |
1761 | ||
1762 | If you don't want this, i.e., if you want the bit vector to shrink | |
1763 | accordingly, you have to do so B<EXPLICITLY> and B<AFTER> the "Delete" | |
1764 | operation, with a couple of statements such as these: | |
1765 | ||
1766 | $size = $vector->Size(); | |
1767 | if ($bits > $size) { $bits = $size; } | |
1768 | $vector->Resize($size - $bits); | |
1769 | ||
1770 | Or use the method "C<Interval_Substitute()>" instead of "C<Delete()>", | |
1771 | which performs automatic growing and shrinking of its target bit vector. | |
1772 | ||
1773 | Note also that "C<$offset>" must lie in the permitted range between | |
1774 | "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range" | |
1775 | error will occur. | |
1776 | ||
1777 | If the term "C<$offset + $bits>" exceeds "C<$vector-E<gt>Size()-1>", | |
1778 | all the bits starting with bit number "C<$offset>" up to bit number | |
1779 | "C<$vector-E<gt>Size()-1>" are simply cleared. | |
1780 | ||
1781 | =item * | |
1782 | ||
1783 | C<$carry = $vector-E<gt>increment();> | |
1784 | ||
1785 | This method increments the given bit vector. | |
1786 | ||
1787 | Note that this method regards bit vectors as being unsigned, | |
1788 | i.e., the largest possible positive number is directly | |
1789 | followed by the smallest possible (or greatest possible, | |
1790 | speaking in absolute terms) negative number: | |
1791 | ||
1792 | before: 2 ^ (b-1) - 1 (= "0111...1111") | |
1793 | after: 2 ^ (b-1) (= "1000...0000") | |
1794 | ||
1795 | where "C<b>" is the number of bits of the given bit vector. | |
1796 | ||
1797 | The method returns "false" ("C<0>") in all cases except when a | |
1798 | carry over occurs (in which case it returns "true", i.e., "C<1>"), | |
1799 | which happens when the number "1111...1111" is incremented, | |
1800 | which gives "0000...0000" plus a carry over to the next higher | |
1801 | (binary) digit. | |
1802 | ||
1803 | This can be used for the terminating condition of a "while" loop, | |
1804 | for instance, in order to cycle through all possible values the | |
1805 | bit vector can assume. | |
1806 | ||
1807 | =item * | |
1808 | ||
1809 | C<$carry = $vector-E<gt>decrement();> | |
1810 | ||
1811 | This method decrements the given bit vector. | |
1812 | ||
1813 | Note that this method regards bit vectors as being unsigned, | |
1814 | i.e., the smallest possible (or greatest possible, speaking | |
1815 | in absolute terms) negative number is directly followed by | |
1816 | the largest possible positive number: | |
1817 | ||
1818 | before: 2 ^ (b-1) (= "1000...0000") | |
1819 | after: 2 ^ (b-1) - 1 (= "0111...1111") | |
1820 | ||
1821 | where "C<b>" is the number of bits of the given bit vector. | |
1822 | ||
1823 | The method returns "false" ("C<0>") in all cases except when a | |
1824 | carry over occurs (in which case it returns "true", i.e., "C<1>"), | |
1825 | which happens when the number "0000...0000" is decremented, | |
1826 | which gives "1111...1111" minus a carry over to the next higher | |
1827 | (binary) digit. | |
1828 | ||
1829 | This can be used for the terminating condition of a "while" loop, | |
1830 | for instance, in order to cycle through all possible values the | |
1831 | bit vector can assume. | |
1832 | ||
1833 | =item * | |
1834 | ||
1835 | C<$overflow = $vec2-E<gt>inc($vec1);> | |
1836 | ||
1837 | This method copies the contents of bit vector "C<$vec1>" to bit | |
1838 | vector "C<$vec2>" and increments the copy (not the original). | |
1839 | ||
1840 | If by incrementing the number its sign becomes invalid, the return | |
1841 | value ("overflow" flag) will be true ("C<1>"), or false ("C<0>") | |
1842 | if not. (See the description of the method "add()" below for | |
1843 | a more in-depth explanation of what "overflow" means). | |
1844 | ||
1845 | Note that in-place operation is also possible, i.e., "C<$vec1>" | |
1846 | and "C<$vec2>" may be identical. | |
1847 | ||
1848 | =item * | |
1849 | ||
1850 | C<$overflow = $vec2-E<gt>dec($vec1);> | |
1851 | ||
1852 | This method copies the contents of bit vector "C<$vec1>" to bit | |
1853 | vector "C<$vec2>" and decrements the copy (not the original). | |
1854 | ||
1855 | If by decrementing the number its sign becomes invalid, the return | |
1856 | value ("overflow" flag) will be true ("C<1>"), or false ("C<0>") | |
1857 | if not. (See the description of the method "subtract()" below | |
1858 | for a more in-depth explanation of what "overflow" means). | |
1859 | ||
1860 | Note that in-place operation is also possible, i.e., "C<$vec1>" | |
1861 | and "C<$vec2>" may be identical. | |
1862 | ||
1863 | =item * | |
1864 | ||
1865 | C<$carry = $vec3-E<gt>add($vec1,$vec2,$carry);> | |
1866 | ||
1867 | C<($carry,$overflow) = $vec3-E<gt>add($vec1,$vec2,$carry);> | |
1868 | ||
1869 | This method adds the two numbers contained in bit vector "C<$vec1>" | |
1870 | and "C<$vec2>" with carry "C<$carry>" and stores the result in | |
1871 | bit vector "C<$vec3>". | |
1872 | ||
1873 | I.e., | |
1874 | $vec3 = $vec1 + $vec2 + $carry | |
1875 | ||
1876 | Note that the "C<$carry>" parameter is a boolean value, i.e., | |
1877 | only its least significant bit is taken into account. (Think of | |
1878 | it as though "C<$carry &= 1;>" was always executed internally.) | |
1879 | ||
1880 | In scalar context, the method returns a boolean value which | |
1881 | indicates if a carry over (to the next higher bit position) | |
1882 | has occured. In list context, the method returns the carry | |
1883 | and the overflow flag (in this order). | |
1884 | ||
1885 | The overflow flag is true ("C<1>") if the sign (i.e., the most | |
1886 | significant bit) of the result is wrong. This can happen when | |
1887 | adding two very large positive numbers or when adding two (by | |
1888 | their absolute value) very large negative numbers. See also | |
1889 | further below. | |
1890 | ||
1891 | The carry in- and output is needed mainly for cascading, i.e., | |
1892 | to add numbers that are fragmented into several pieces. | |
1893 | ||
1894 | Example: | |
1895 | ||
1896 | # initialize | |
1897 | ||
1898 | for ( $i = 0; $i < $n; $i++ ) | |
1899 | { | |
1900 | $a[$i] = Bit::Vector->new($bits); | |
1901 | $b[$i] = Bit::Vector->new($bits); | |
1902 | $c[$i] = Bit::Vector->new($bits); | |
1903 | } | |
1904 | ||
1905 | # fill @a and @b | |
1906 | ||
1907 | # $a[ 0 ] is low order part, | |
1908 | # $a[$n-1] is high order part, | |
1909 | # and same for @b | |
1910 | ||
1911 | # add | |
1912 | ||
1913 | $carry = 0; | |
1914 | for ( $i = 0; $i < $n; $i++ ) | |
1915 | { | |
1916 | $carry = $c[$i]->add($a[$i],$b[$i],$carry); | |
1917 | } | |
1918 | ||
1919 | Note that it makes no difference to this method whether the numbers | |
1920 | in "C<$vec1>" and "C<$vec2>" are unsigned or signed (i.e., in two's | |
1921 | complement binary representation). | |
1922 | ||
1923 | Note however that the return value (carry flag) is not meaningful | |
1924 | when the numbers are B<SIGNED>. | |
1925 | ||
1926 | Moreover, when the numbers are signed, a special type of error can | |
1927 | occur which is commonly called an "overflow error". | |
1928 | ||
1929 | An overflow error occurs when the sign of the result (its most | |
1930 | significant bit) is flipped (i.e., falsified) by a carry over | |
1931 | from the next-lower bit position ("MSB-1"). | |
1932 | ||
1933 | In fact matters are a bit more complicated than that: the overflow | |
1934 | flag is set to "true" whenever there is a carry over from bit | |
1935 | position MSB-1 to the most significant bit (MSB) but no carry | |
1936 | over from the MSB to the output carry flag, or vice-versa, i.e., | |
1937 | when there is no carry over from bit position MSB-1 to the most | |
1938 | significant bit (MSB) but a carry over to the output carry flag. | |
1939 | ||
1940 | Thus the overflow flag is the result of an exclusive-or operation | |
1941 | between incoming and outgoing carry over at the most significant | |
1942 | bit position. | |
1943 | ||
1944 | =item * | |
1945 | ||
1946 | C<$carry = $vec3-E<gt>subtract($vec1,$vec2,$carry);> | |
1947 | ||
1948 | C<($carry,$overflow) = $vec3-E<gt>subtract($vec1,$vec2,$carry);> | |
1949 | ||
1950 | This method subtracts the two numbers contained in bit vector | |
1951 | "C<$vec1>" and "C<$vec2>" with carry "C<$carry>" and stores the | |
1952 | result in bit vector "C<$vec3>". | |
1953 | ||
1954 | I.e., | |
1955 | $vec3 = $vec1 - $vec2 - $carry | |
1956 | ||
1957 | Note that the "C<$carry>" parameter is a boolean value, i.e., | |
1958 | only its least significant bit is taken into account. (Think of | |
1959 | it as though "C<$carry &= 1;>" was always executed internally.) | |
1960 | ||
1961 | In scalar context, the method returns a boolean value which | |
1962 | indicates if a carry over (to the next higher bit position) | |
1963 | has occured. In list context, the method returns the carry | |
1964 | and the overflow flag (in this order). | |
1965 | ||
1966 | The overflow flag is true ("C<1>") if the sign (i.e., the most | |
1967 | significant bit) of the result is wrong. This can happen when | |
1968 | subtracting a very large negative number from a very large | |
1969 | positive number or vice-versa. See also further below. | |
1970 | ||
1971 | The carry in- and output is needed mainly for cascading, i.e., | |
1972 | to subtract numbers that are fragmented into several pieces. | |
1973 | ||
1974 | Example: | |
1975 | ||
1976 | # initialize | |
1977 | ||
1978 | for ( $i = 0; $i < $n; $i++ ) | |
1979 | { | |
1980 | $a[$i] = Bit::Vector->new($bits); | |
1981 | $b[$i] = Bit::Vector->new($bits); | |
1982 | $c[$i] = Bit::Vector->new($bits); | |
1983 | } | |
1984 | ||
1985 | # fill @a and @b | |
1986 | ||
1987 | # $a[ 0 ] is low order part, | |
1988 | # $a[$n-1] is high order part, | |
1989 | # and same for @b | |
1990 | ||
1991 | # subtract | |
1992 | ||
1993 | $carry = 0; | |
1994 | for ( $i = 0; $i < $n; $i++ ) | |
1995 | { | |
1996 | $carry = $c[$i]->subtract($a[$i],$b[$i],$carry); | |
1997 | } | |
1998 | ||
1999 | Note that it makes no difference to this method whether the numbers | |
2000 | in "C<$vec1>" and "C<$vec2>" are unsigned or signed (i.e., in two's | |
2001 | complement binary representation). | |
2002 | ||
2003 | Note however that the return value (carry flag) is not meaningful | |
2004 | when the numbers are B<SIGNED>. | |
2005 | ||
2006 | Moreover, when the numbers are signed, a special type of error can | |
2007 | occur which is commonly called an "overflow error". | |
2008 | ||
2009 | An overflow error occurs when the sign of the result (its most | |
2010 | significant bit) is flipped (i.e., falsified) by a carry over | |
2011 | from the next-lower bit position ("MSB-1"). | |
2012 | ||
2013 | In fact matters are a bit more complicated than that: the overflow | |
2014 | flag is set to "true" whenever there is a carry over from bit | |
2015 | position MSB-1 to the most significant bit (MSB) but no carry | |
2016 | over from the MSB to the output carry flag, or vice-versa, i.e., | |
2017 | when there is no carry over from bit position MSB-1 to the most | |
2018 | significant bit (MSB) but a carry over to the output carry flag. | |
2019 | ||
2020 | Thus the overflow flag is the result of an exclusive-or operation | |
2021 | between incoming and outgoing carry over at the most significant | |
2022 | bit position. | |
2023 | ||
2024 | =item * | |
2025 | ||
2026 | C<$vec2-E<gt>Negate($vec1);> | |
2027 | ||
2028 | This method calculates the two's complement of the number in bit | |
2029 | vector "C<$vec1>" and stores the result in bit vector "C<$vec2>". | |
2030 | ||
2031 | Calculating the two's complement of a given number in binary representation | |
2032 | consists of inverting all bits and incrementing the result by one. | |
2033 | ||
2034 | This is the same as changing the sign of the given number from "C<+>" to | |
2035 | "C<->" or vice-versa. In other words, applying this method twice on a given | |
2036 | number yields the original number again. | |
2037 | ||
2038 | Note that in-place processing is also possible, i.e., "C<$vec1>" and | |
2039 | "C<$vec2>" may be identical. | |
2040 | ||
2041 | Most importantly, beware that this method produces a counter-intuitive | |
2042 | result if the number contained in bit vector "C<$vec1>" is C<2 ^ (n-1)> | |
2043 | (i.e., "1000...0000"), where "C<n>" is the number of bits the given bit | |
2044 | vector contains: The negated value of this number is the number itself! | |
2045 | ||
2046 | =item * | |
2047 | ||
2048 | C<$vec2-E<gt>Absolute($vec1);> | |
2049 | ||
2050 | Depending on the sign (i.e., the most significant bit) of the number in | |
2051 | bit vector "C<$vec1>", the contents of bit vector "C<$vec1>" are copied | |
2052 | to bit vector "C<$vec2>" either with the method "C<Copy()>" (if the number | |
2053 | in bit vector "C<$vec1>" is positive), or with "C<Negate()>" (if the number | |
2054 | in bit vector "C<$vec1>" is negative). | |
2055 | ||
2056 | In other words, this method calculates the absolute value of the number | |
2057 | in bit vector "C<$vec1>" and stores the result in bit vector "C<$vec2>". | |
2058 | ||
2059 | Note that in-place processing is also possible, i.e., "C<$vec1>" and | |
2060 | "C<$vec2>" may be identical. | |
2061 | ||
2062 | Most importantly, beware that this method produces a counter-intuitive | |
2063 | result if the number contained in bit vector "C<$vec1>" is C<2 ^ (n-1)> | |
2064 | (i.e., "1000...0000"), where "C<n>" is the number of bits the given bit | |
2065 | vector contains: The absolute value of this number is the number itself, | |
2066 | even though this number is still negative by definition (the most | |
2067 | significant bit is still set)! | |
2068 | ||
2069 | =item * | |
2070 | ||
2071 | C<$sign = $vector-E<gt>Sign();> | |
2072 | ||
2073 | This method returns "C<0>" if all bits in the given bit vector are cleared, | |
2074 | i.e., if the given bit vector contains the number "C<0>", or if the given | |
2075 | bit vector has a length of zero (contains no bits at all). | |
2076 | ||
2077 | If not all bits are cleared, this method returns "C<-1>" if the most | |
2078 | significant bit is set (i.e., if the bit vector contains a negative | |
2079 | number), or "C<1>" otherwise (i.e., if the bit vector contains a | |
2080 | positive number). | |
2081 | ||
2082 | =item * | |
2083 | ||
2084 | C<$vec3-E<gt>Multiply($vec1,$vec2);> | |
2085 | ||
2086 | This method multiplies the two numbers contained in bit vector "C<$vec1>" | |
2087 | and "C<$vec2>" and stores the result in bit vector "C<$vec3>". | |
2088 | ||
2089 | Note that this method regards its arguments as B<SIGNED>. | |
2090 | ||
2091 | If you want to make sure that a large number can never be treated as being | |
2092 | negative by mistake, make your bit vectors at least one bit longer than the | |
2093 | largest number you wish to represent, right from the start, or proceed as | |
2094 | follows: | |
2095 | ||
2096 | $msb1 = $vec1->msb(); | |
2097 | $msb2 = $vec2->msb(); | |
2098 | $vec1->Resize($vec1->Size()+1); | |
2099 | $vec2->Resize($vec2->Size()+1); | |
2100 | $vec3->Resize($vec3->Size()+1); | |
2101 | $vec1->MSB($msb1); | |
2102 | $vec2->MSB($msb2); | |
2103 | $vec3->Multiply($vec1,$vec2); | |
2104 | ||
2105 | Note also that all three bit vector arguments must in principle obey the | |
2106 | rule of matching sizes, but that the bit vector "C<$vec3>" may be larger | |
2107 | than the two factors "C<$vec1>" and "C<$vec2>". | |
2108 | ||
2109 | In fact multiplying two binary numbers with "C<n>" bits may yield a result | |
2110 | which is at most "C<2n>" bits long. | |
2111 | ||
2112 | Therefore, it is usually a good idea to let bit vector "C<$vec3>" have | |
2113 | twice the size of bit vector "C<$vec1>" and "C<$vec2>", unless you are | |
2114 | absolutely sure that the result will fit into a bit vector of the same | |
2115 | size as the two factors. | |
2116 | ||
2117 | If you are wrong, a fatal "numeric overflow error" will occur. | |
2118 | ||
2119 | Finally, note that in-place processing is possible, i.e., "C<$vec3>" | |
2120 | may be identical with "C<$vec1>" or "C<$vec2>", or both. | |
2121 | ||
2122 | =item * | |
2123 | ||
2124 | C<$quot-E<gt>Divide($vec1,$vec2,$rest);> | |
2125 | ||
2126 | This method divides the two numbers contained in bit vector "C<$vec1>" | |
2127 | and "C<$vec2>" and stores the quotient in bit vector "C<$quot>" and | |
2128 | the remainder in bit vector "C<$rest>". | |
2129 | ||
2130 | I.e., | |
2131 | $quot = $vec1 / $vec2; # div | |
2132 | $rest = $vec1 % $vec2; # mod | |
2133 | ||
2134 | Therefore, "C<$quot>" and "C<$rest>" must be two B<DISTINCT> bit vectors, | |
2135 | or a fatal "result vector(s) must be distinct" error will occur. | |
2136 | ||
2137 | Note also that a fatal "division by zero error" will occur if "C<$vec2>" | |
2138 | is equal to zero. | |
2139 | ||
2140 | Note further that this method regards its arguments as B<SIGNED>. | |
2141 | ||
2142 | If you want to make sure that a large number can never be treated as being | |
2143 | negative by mistake, make your bit vectors at least one bit longer than the | |
2144 | largest number you wish to represent, right from the start, or proceed as | |
2145 | follows: | |
2146 | ||
2147 | $msb1 = $vec1->msb(); | |
2148 | $msb2 = $vec2->msb(); | |
2149 | $vec1->Resize($vec1->Size()+1); | |
2150 | $vec2->Resize($vec2->Size()+1); | |
2151 | $quot->Resize($quot->Size()+1); | |
2152 | $rest->Resize($rest->Size()+1); | |
2153 | $vec1->MSB($msb1); | |
2154 | $vec2->MSB($msb2); | |
2155 | $quot->Divide($vec1,$vec2,$rest); | |
2156 | ||
2157 | Finally, note that in-place processing is possible, i.e., "C<$quot>" | |
2158 | may be identical with "C<$vec1>" or "C<$vec2>" or both, and "C<$rest>" | |
2159 | may also be identical with "C<$vec1>" or "C<$vec2>" or both, as long | |
2160 | as "C<$quot>" and "C<$rest>" are distinct. (!) | |
2161 | ||
2162 | =item * | |
2163 | ||
2164 | C<$vec3-E<gt>GCD($vec1,$vec2);> | |
2165 | ||
2166 | This method calculates the "Greatest Common Divisor" of the two numbers | |
2167 | contained in bit vector "C<$vec1>" and "C<$vec2>" and stores the result | |
2168 | in bit vector "C<$vec3>". | |
2169 | ||
2170 | The method uses Euklid's algorithm internally: | |
2171 | ||
2172 | int GCD(int a, int b) | |
2173 | { | |
2174 | int t; | |
2175 | ||
2176 | while (b != 0) | |
2177 | { | |
2178 | t = a % b; /* = remainder of (a div b) */ | |
2179 | a = b; | |
2180 | b = t; | |
2181 | } | |
2182 | return(a); | |
2183 | } | |
2184 | ||
2185 | Note that a fatal "division by zero error" will occur if any of the two | |
2186 | numbers is equal to zero. | |
2187 | ||
2188 | Note also that this method regards its two arguments as B<SIGNED> but | |
2189 | that it actually uses the B<ABSOLUTE VALUE> of its two arguments internally, | |
2190 | i.e., the B<RESULT> of this method will B<ALWAYS> be B<POSITIVE>. | |
2191 | ||
2192 | =item * | |
2193 | ||
2194 | C<$vec3-E<gt>Power($vec1,$vec2);> | |
2195 | ||
2196 | This method calculates the exponentiation of base "C<$vec1>" elevated to | |
2197 | the "C<$vec2>" power, i.e., "C<$vec1 ** $vec2>", and stores the result | |
2198 | in bit vector "C<$vec3>". | |
2199 | ||
2200 | The method uses an efficient divide-and-conquer algorithm: | |
2201 | ||
2202 | Suppose the exponent is (decimal) 13, for example. The binary | |
2203 | representation of this exponent is "1101". | |
2204 | ||
2205 | This means we want to calculate | |
2206 | ||
2207 | $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * | |
2208 | $vec1 * $vec1 * $vec1 * $vec1 * | |
2209 | $vec1 | |
2210 | ||
2211 | That is, "C<$vec1>" multiplied with itself 13 times. The grouping | |
2212 | into lines above is no coincidence. The first line comprises 8 | |
2213 | factors, the second contains 4, and the last line just one. This | |
2214 | just happens to be the binary representation of 13. C<;-)> | |
2215 | ||
2216 | We then calculate a series of squares (of squares of squares...) of | |
2217 | the base, i.e., | |
2218 | ||
2219 | $power[0] = $vec1; | |
2220 | $power[1] = $vec1 * $vec1; | |
2221 | $power[2] = $power[1] * $power[1]; | |
2222 | $power[3] = $power[2] * $power[2]; | |
2223 | etc. | |
2224 | ||
2225 | To calculate the power of our example, we simply initialize our result | |
2226 | with 1 and consecutively multiply it with the items of the series of | |
2227 | powers we just calculated, if the corresponding bit of the binary | |
2228 | representation of the exponent is set: | |
2229 | ||
2230 | $result = 1; | |
2231 | $result *= $power[0] if ($vec2 & 1); | |
2232 | $result *= $power[1] if ($vec2 & 2); | |
2233 | $result *= $power[2] if ($vec2 & 4); | |
2234 | $result *= $power[3] if ($vec2 & 8); | |
2235 | etc. | |
2236 | ||
2237 | The bit vector "C<$vec3>" must be of the same size as the base | |
2238 | "C<$vec1>" or greater. "C<$vec3>" and "C<$vec1>" may be the same | |
2239 | vector (i.e., in-place calculation as in "C<$vec1 **= $vec2;>" is | |
2240 | possible), but "C<$vec3>" and "C<$vec2>" must be distinct. Finally, | |
2241 | the exponent "C<$vec2>" must be positive. A fatal error occurs if | |
2242 | any of these conditions is not met. | |
2243 | ||
2244 | =item * | |
2245 | ||
2246 | C<$vector-E<gt>Block_Store($buffer);> | |
2247 | ||
2248 | This method allows you to load the contents of a given bit vector in | |
2249 | one go. | |
2250 | ||
2251 | This is useful when you store the contents of a bit vector in a file, | |
2252 | for instance (using method "C<Block_Read()>"), and when you want to | |
2253 | restore the previously saved bit vector. | |
2254 | ||
2255 | For this, "C<$buffer>" B<MUST> be a string (B<NO> automatic conversion | |
2256 | from numeric to string is provided here as would normally in Perl!) | |
2257 | containing the bit vector in "low order byte first" order. | |
2258 | ||
2259 | If the given string is shorter than what is needed to completely fill | |
2260 | the given bit vector, the remaining (most significant) bytes of the | |
2261 | bit vector are filled with zeros, i.e., the previous contents of the | |
2262 | bit vector are always erased completely. | |
2263 | ||
2264 | If the given string is longer than what is needed to completely fill | |
2265 | the given bit vector, the superfluous bytes are simply ignored. | |
2266 | ||
2267 | See L<perlfunc/sysread> for how to read in the contents of "C<$buffer>" | |
2268 | from a file prior to passing it to this method. | |
2269 | ||
2270 | =item * | |
2271 | ||
2272 | C<$buffer = $vector-E<gt>Block_Read();> | |
2273 | ||
2274 | This method allows you to export the contents of a given bit vector in | |
2275 | one block. | |
2276 | ||
2277 | This is useful when you want to save the contents of a bit vector for | |
2278 | later, for instance in a file. | |
2279 | ||
2280 | The advantage of this method is that it allows you to do so in the | |
2281 | compactest possible format, in binary. | |
2282 | ||
2283 | The method returns a Perl string which contains an exact copy of the | |
2284 | contents of the given bit vector in "low order byte first" order. | |
2285 | ||
2286 | See L<perlfunc/syswrite> for how to write the data from this string | |
2287 | to a file. | |
2288 | ||
2289 | =item * | |
2290 | ||
2291 | C<$size = $vector-E<gt>Word_Size();> | |
2292 | ||
2293 | Each bit vector is internally organized as an array of machine words. | |
2294 | ||
2295 | The methods whose names begin with "Word_" allow you to access this | |
2296 | internal array of machine words. | |
2297 | ||
2298 | Note that because the size of a machine word may vary from system to | |
2299 | system, these methods are inherently B<MACHINE-DEPENDENT>! | |
2300 | ||
2301 | Therefore, B<DO NOT USE> these methods unless you are absolutely certain | |
2302 | that portability of your code is not an issue! | |
2303 | ||
2304 | You have been warned! | |
2305 | ||
2306 | To be machine-independent, use the methods whose names begin with "C<Chunk_>" | |
2307 | instead, with chunk sizes no greater than 32 bits. | |
2308 | ||
2309 | The method "C<Word_Size()>" returns the number of machine words that the | |
2310 | internal array of words of the given bit vector contains. | |
2311 | ||
2312 | This is similar in function to the term "C<scalar(@array)>" for a Perl array. | |
2313 | ||
2314 | =item * | |
2315 | ||
2316 | C<$vector-E<gt>Word_Store($offset,$word);> | |
2317 | ||
2318 | This method allows you to store a given value "C<$word>" at a given | |
2319 | position "C<$offset>" in the internal array of words of the given | |
2320 | bit vector. | |
2321 | ||
2322 | Note that "C<$offset>" must lie in the permitted range between "C<0>" | |
2323 | and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out of range" | |
2324 | error will occur. | |
2325 | ||
2326 | This method is similar in function to the expression | |
2327 | "C<$array[$offset] = $word;>" for a Perl array. | |
2328 | ||
2329 | =item * | |
2330 | ||
2331 | C<$word = $vector-E<gt>Word_Read($offset);> | |
2332 | ||
2333 | This method allows you to access the value of a given machine word | |
2334 | at position "C<$offset>" in the internal array of words of the given | |
2335 | bit vector. | |
2336 | ||
2337 | Note that "C<$offset>" must lie in the permitted range between "C<0>" | |
2338 | and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out of range" | |
2339 | error will occur. | |
2340 | ||
2341 | This method is similar in function to the expression | |
2342 | "C<$word = $array[$offset];>" for a Perl array. | |
2343 | ||
2344 | =item * | |
2345 | ||
2346 | C<$vector-E<gt>Word_List_Store(@words);> | |
2347 | ||
2348 | This method allows you to store a list of values "C<@words>" in the | |
2349 | internal array of machine words of the given bit vector. | |
2350 | ||
2351 | Thereby the B<LEFTMOST> value in the list ("C<$words[0]>") is stored | |
2352 | in the B<LEAST> significant word of the internal array of words (the | |
2353 | one with offset "C<0>"), the next value from the list ("C<$words[1]>") | |
2354 | is stored in the word with offset "C<1>", and so on, as intuitively | |
2355 | expected. | |
2356 | ||
2357 | If the list "C<@words>" contains fewer elements than the internal | |
2358 | array of words of the given bit vector contains machine words, | |
2359 | the remaining (most significant) words are filled with zeros. | |
2360 | ||
2361 | If the list "C<@words>" contains more elements than the internal | |
2362 | array of words of the given bit vector contains machine words, | |
2363 | the superfluous values are simply ignored. | |
2364 | ||
2365 | This method is comparable in function to the expression | |
2366 | "C<@array = @words;>" for a Perl array. | |
2367 | ||
2368 | =item * | |
2369 | ||
2370 | C<@words = $vector-E<gt>Word_List_Read();> | |
2371 | ||
2372 | This method allows you to retrieve the internal array of machine | |
2373 | words of the given bit vector all at once. | |
2374 | ||
2375 | Thereby the B<LEFTMOST> value in the returned list ("C<$words[0]>") | |
2376 | is the B<LEAST> significant word from the given bit vector, and the | |
2377 | B<RIGHTMOST> value in the returned list ("C<$words[$#words]>") is | |
2378 | the B<MOST> significant word of the given bit vector. | |
2379 | ||
2380 | This method is similar in function to the expression | |
2381 | "C<@words = @array;>" for a Perl array. | |
2382 | ||
2383 | =item * | |
2384 | ||
2385 | C<$vector-E<gt>Word_Insert($offset,$count);> | |
2386 | ||
2387 | This method inserts "C<$count>" empty new machine words at position | |
2388 | "C<$offset>" in the internal array of words of the given bit vector. | |
2389 | ||
2390 | The "C<$count>" most significant words are lost, and all words starting | |
2391 | with word number "C<$offset>" up to and including word number | |
2392 | "C<$vector-E<gt>Word_Size()-$count-1>" are moved up by "C<$count>" places. | |
2393 | ||
2394 | The now vacant "C<$count>" words starting at word number "C<$offset>" | |
2395 | (up to and including word number "C<$offset+$count-1>") are then set | |
2396 | to zero (cleared). | |
2397 | ||
2398 | Note that this method does B<NOT> increase the size of the given bit | |
2399 | vector, i.e., the bit vector is B<NOT> extended at its upper end to | |
2400 | "rescue" the "C<$count>" uppermost (most significant) words - instead, | |
2401 | these words are lost forever. | |
2402 | ||
2403 | If you don't want this to happen, you have to increase the size of the | |
2404 | given bit vector B<EXPLICITLY> and B<BEFORE> you perform the "Insert" | |
2405 | operation, with a statement such as the following: | |
2406 | ||
2407 | $vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits()); | |
2408 | ||
2409 | Note also that "C<$offset>" must lie in the permitted range between | |
2410 | "C<0>" and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out | |
2411 | of range" error will occur. | |
2412 | ||
2413 | If the term "C<$offset + $count>" exceeds "C<$vector-E<gt>Word_Size()-1>", | |
2414 | all the words starting with word number "C<$offset>" up to word number | |
2415 | "C<$vector-E<gt>Word_Size()-1>" are simply cleared. | |
2416 | ||
2417 | =item * | |
2418 | ||
2419 | C<$vector-E<gt>Word_Delete($offset,$count);> | |
2420 | ||
2421 | This method deletes, i.e., removes the words starting at position | |
2422 | "C<$offset>" up to and including word number "C<$offset+$count-1>" | |
2423 | from the internal array of machine words of the given bit vector. | |
2424 | ||
2425 | The remaining uppermost words (starting at position "C<$offset+$count>" | |
2426 | up to and including word number "C<$vector-E<gt>Word_Size()-1>") are | |
2427 | moved down by "C<$count>" places. | |
2428 | ||
2429 | The now vacant uppermost (most significant) "C<$count>" words are then | |
2430 | set to zero (cleared). | |
2431 | ||
2432 | Note that this method does B<NOT> decrease the size of the given bit | |
2433 | vector, i.e., the bit vector is B<NOT> clipped at its upper end to | |
2434 | "get rid of" the vacant "C<$count>" uppermost words. | |
2435 | ||
2436 | If you don't want this, i.e., if you want the bit vector to shrink | |
2437 | accordingly, you have to do so B<EXPLICITLY> and B<AFTER> the "Delete" | |
2438 | operation, with a couple of statements such as these: | |
2439 | ||
2440 | $bits = $vector->Size(); | |
2441 | $count *= Bit::Vector->Word_Bits(); | |
2442 | if ($count > $bits) { $count = $bits; } | |
2443 | $vector->Resize($bits - $count); | |
2444 | ||
2445 | Note also that "C<$offset>" must lie in the permitted range between | |
2446 | "C<0>" and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out | |
2447 | of range" error will occur. | |
2448 | ||
2449 | If the term "C<$offset + $count>" exceeds "C<$vector-E<gt>Word_Size()-1>", | |
2450 | all the words starting with word number "C<$offset>" up to word number | |
2451 | "C<$vector-E<gt>Word_Size()-1>" are simply cleared. | |
2452 | ||
2453 | =item * | |
2454 | ||
2455 | C<$vector-E<gt>Chunk_Store($chunksize,$offset,$chunk);> | |
2456 | ||
2457 | This method allows you to set more than one bit at a time with | |
2458 | different values. | |
2459 | ||
2460 | You can access chunks (i.e., ranges of contiguous bits) between | |
2461 | one and at most "C<Bit::Vector-E<gt>Long_Bits()>" bits wide. | |
2462 | ||
2463 | In order to be portable, though, you should never use chunk sizes | |
2464 | larger than 32 bits. | |
2465 | ||
2466 | If the given "C<$chunksize>" does not lie between "C<1>" and | |
2467 | "C<Bit::Vector-E<gt>Long_Bits()>", a fatal "chunk size out of range" | |
2468 | error will occur. | |
2469 | ||
2470 | The method copies the "C<$chunksize>" least significant bits | |
2471 | from the value "C<$chunk>" to the given bit vector, starting at | |
2472 | bit position "C<$offset>" and proceeding upwards until bit number | |
2473 | "C<$offset+$chunksize-1>". | |
2474 | ||
2475 | (I.e., bit number "C<0>" of "C<$chunk>" becomes bit number "C<$offset>" | |
2476 | in the given bit vector, and bit number "C<$chunksize-1>" becomes | |
2477 | bit number "C<$offset+$chunksize-1>".) | |
2478 | ||
2479 | If the term "C<$offset+$chunksize-1>" exceeds "C<$vector-E<gt>Size()-1>", | |
2480 | the corresponding superfluous (most significant) bits from "C<$chunk>" | |
2481 | are simply ignored. | |
2482 | ||
2483 | Note that "C<$offset>" itself must lie in the permitted range between | |
2484 | "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range" | |
2485 | error will occur. | |
2486 | ||
2487 | This method (as well as the other "C<Chunk_>" methods) is useful, for | |
2488 | example, when you are reading in data in chunks of, say, 8 bits, which | |
2489 | you need to access later, say, using 16 bits at a time (like audio CD | |
2490 | wave files, for instance). | |
2491 | ||
2492 | =item * | |
2493 | ||
2494 | C<$chunk = $vector-E<gt>Chunk_Read($chunksize,$offset);> | |
2495 | ||
2496 | This method allows you to read the values of more than one bit at | |
2497 | a time. | |
2498 | ||
2499 | You can read chunks (i.e., ranges of contiguous bits) between | |
2500 | one and at most "C<Bit::Vector-E<gt>Long_Bits()>" bits wide. | |
2501 | ||
2502 | In order to be portable, though, you should never use chunk sizes | |
2503 | larger than 32 bits. | |
2504 | ||
2505 | If the given "C<$chunksize>" does not lie between "C<1>" and | |
2506 | "C<Bit::Vector-E<gt>Long_Bits()>", a fatal "chunk size out of range" | |
2507 | error will occur. | |
2508 | ||
2509 | The method returns the "C<$chunksize>" bits from the given bit vector | |
2510 | starting at bit position "C<$offset>" and proceeding upwards until | |
2511 | bit number "C<$offset+$chunksize-1>". | |
2512 | ||
2513 | (I.e., bit number "C<$offset>" of the given bit vector becomes bit number | |
2514 | "C<0>" of the returned value, and bit number "C<$offset+$chunksize-1>" | |
2515 | becomes bit number "C<$chunksize-1>".) | |
2516 | ||
2517 | If the term "C<$offset+$chunksize-1>" exceeds "C<$vector-E<gt>Size()-1>", | |
2518 | the non-existent bits are simply not returned. | |
2519 | ||
2520 | Note that "C<$offset>" itself must lie in the permitted range between | |
2521 | "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range" | |
2522 | error will occur. | |
2523 | ||
2524 | =item * | |
2525 | ||
2526 | C<$vector-E<gt>Chunk_List_Store($chunksize,@chunks);> | |
2527 | ||
2528 | This method allows you to fill the given bit vector with a list of | |
2529 | data packets ("chunks") of any size ("C<$chunksize>") you like | |
2530 | (within certain limits). | |
2531 | ||
2532 | In fact the given "C<$chunksize>" must lie in the range between "C<1>" | |
2533 | and "C<Bit::Vector-E<gt>Long_Bits()>", or a fatal "chunk size out of | |
2534 | range" error will occur. | |
2535 | ||
2536 | In order to be portable, though, you should never use chunk sizes | |
2537 | larger than 32 bits. | |
2538 | ||
2539 | The given bit vector is thereby filled in ascending order: The first | |
2540 | chunk from the list (i.e., "C<$chunks[0]>") fills the "C<$chunksize>" | |
2541 | least significant bits, the next chunk from the list ("C<$chunks[1]>") | |
2542 | fills the bits number "C<$chunksize>" to number "C<2*$chunksize-1>", | |
2543 | the third chunk ("C<$chunks[2]>") fills the bits number "C<2*$chunksize>", | |
2544 | to number "C<3*$chunksize-1>", and so on. | |
2545 | ||
2546 | If there a less chunks in the list than are needed to fill the entire | |
2547 | bit vector, the remaining (most significant) bits are cleared, i.e., | |
2548 | the previous contents of the given bit vector are always erased completely. | |
2549 | ||
2550 | If there are more chunks in the list than are needed to fill the entire | |
2551 | bit vector, and/or if a chunk extends beyond "C<$vector-E<gt>Size()-1>" | |
2552 | (which happens whenever "C<$vector-E<gt>Size()>" is not a multiple of | |
2553 | "C<$chunksize>"), the superfluous chunks and/or bits are simply ignored. | |
2554 | ||
2555 | The method is useful, for example (and among many other applications), | |
2556 | for the conversion of packet sizes in a data stream. | |
2557 | ||
2558 | This method can also be used to store an octal string in a given | |
2559 | bit vector: | |
2560 | ||
2561 | $vector->Chunk_List_Store(3, split(//, reverse $string)); | |
2562 | ||
2563 | Note however that unlike the conversion methods "C<from_Hex()>", | |
2564 | "C<from_Bin()>", "C<from_Dec()>" and "C<from_Enum()>", | |
2565 | this statement does not include any syntax checking, i.e., | |
2566 | it may fail silently, without warning. | |
2567 | ||
2568 | To perform syntax checking, add the following statements: | |
2569 | ||
2570 | if ($string =~ /^[0-7]+$/) | |
2571 | { | |
2572 | # okay, go ahead with conversion as shown above | |
2573 | } | |
2574 | else | |
2575 | { | |
2576 | # error, string contains other than octal characters | |
2577 | } | |
2578 | ||
2579 | Another application is to store a repetitive pattern in a given | |
2580 | bit vector: | |
2581 | ||
2582 | $pattern = 0xDEADBEEF; | |
2583 | $length = 32; # = length of $pattern in bits | |
2584 | $size = $vector->Size(); | |
2585 | $factor = int($size / $length); | |
2586 | if ($size % $length) { $factor++; } | |
2587 | $vector->Chunk_List_Store($length, ($pattern) x $factor); | |
2588 | ||
2589 | =item * | |
2590 | ||
2591 | C<@chunks = $vector-E<gt>Chunk_List_Read($chunksize);> | |
2592 | ||
2593 | This method allows you to access the contents of the given bit vector in | |
2594 | form of a list of data packets ("chunks") of a size ("C<$chunksize>") | |
2595 | of your choosing (within certain limits). | |
2596 | ||
2597 | In fact the given "C<$chunksize>" must lie in the range between "C<1>" | |
2598 | and "C<Bit::Vector-E<gt>Long_Bits()>", or a fatal "chunk size out of | |
2599 | range" error will occur. | |
2600 | ||
2601 | In order to be portable, though, you should never use chunk sizes | |
2602 | larger than 32 bits. | |
2603 | ||
2604 | The given bit vector is thereby read in ascending order: The | |
2605 | "C<$chunksize>" least significant bits (bits number "C<0>" to | |
2606 | "C<$chunksize-1>") become the first chunk in the returned list | |
2607 | (i.e., "C<$chunks[0]>"). The bits number "C<$chunksize>" to | |
2608 | "C<2*$chunksize-1>" become the next chunk in the list | |
2609 | ("C<$chunks[1]>"), and so on. | |
2610 | ||
2611 | If "C<$vector-E<gt>Size()>" is not a multiple of "C<$chunksize>", | |
2612 | the last chunk in the list will contain fewer bits than "C<$chunksize>". | |
2613 | ||
2614 | B<BEWARE> that for large bit vectors and/or small values of "C<$chunksize>", | |
2615 | the number of returned list elements can be extremely large! B<BE CAREFUL!> | |
2616 | ||
2617 | You could blow up your application with lack of memory (each list element | |
2618 | is a full-grown Perl scalar, internally, with an associated memory overhead | |
2619 | for its administration!) or at least cause a noticeable, more or less | |
2620 | long-lasting "freeze" of your application! | |
2621 | ||
2622 | Possible applications: | |
2623 | ||
2624 | The method is especially useful in the conversion of packet sizes in | |
2625 | a data stream. | |
2626 | ||
2627 | This method can also be used to convert a given bit vector to a string | |
2628 | of octal numbers: | |
2629 | ||
2630 | $string = reverse join('', $vector->Chunk_List_Read(3)); | |
2631 | ||
2632 | =item * | |
2633 | ||
2634 | C<$vector-E<gt>Index_List_Remove(@indices);> | |
2635 | ||
2636 | This method allows you to specify a list of indices of bits which | |
2637 | should be turned off in the given bit vector. | |
2638 | ||
2639 | In fact this method is a shortcut for | |
2640 | ||
2641 | foreach $index (@indices) | |
2642 | { | |
2643 | $vector->Bit_Off($index); | |
2644 | } | |
2645 | ||
2646 | In contrast to all other import methods in this module, this method | |
2647 | does B<NOT> clear the given bit vector before processing its list | |
2648 | of arguments. | |
2649 | ||
2650 | Instead, this method allows you to accumulate the results of various | |
2651 | consecutive calls. | |
2652 | ||
2653 | (The same holds for the method "C<Index_List_Store()>". As a | |
2654 | consequence, you can "wipe out" what you did using the method | |
2655 | "C<Index_List_Remove()>" by passing the identical argument list | |
2656 | to the method "C<Index_List_Store()>".) | |
2657 | ||
2658 | =item * | |
2659 | ||
2660 | C<$vector-E<gt>Index_List_Store(@indices);> | |
2661 | ||
2662 | This method allows you to specify a list of indices of bits which | |
2663 | should be turned on in the given bit vector. | |
2664 | ||
2665 | In fact this method is a shortcut for | |
2666 | ||
2667 | foreach $index (@indices) | |
2668 | { | |
2669 | $vector->Bit_On($index); | |
2670 | } | |
2671 | ||
2672 | In contrast to all other import methods in this module, this method | |
2673 | does B<NOT> clear the given bit vector before processing its list | |
2674 | of arguments. | |
2675 | ||
2676 | Instead, this method allows you to accumulate the results of various | |
2677 | consecutive calls. | |
2678 | ||
2679 | (The same holds for the method "C<Index_List_Remove()>". As a | |
2680 | consequence, you can "wipe out" what you did using the method | |
2681 | "C<Index_List_Store()>" by passing the identical argument list | |
2682 | to the method "C<Index_List_Remove()>".) | |
2683 | ||
2684 | =item * | |
2685 | ||
2686 | C<@indices = $vector-E<gt>Index_List_Read();> | |
2687 | ||
2688 | This method returns a list of Perl scalars. | |
2689 | ||
2690 | The list contains one scalar for each set bit in the given | |
2691 | bit vector. | |
2692 | ||
2693 | B<BEWARE> that for large bit vectors, this can result in a literally | |
2694 | overwhelming number of list elements! B<BE CAREFUL!> You could run | |
2695 | out of memory or slow down your application considerably! | |
2696 | ||
2697 | Each scalar contains the number of the index corresponding to | |
2698 | the bit in question. | |
2699 | ||
2700 | These indices are always returned in ascending order. | |
2701 | ||
2702 | If the given bit vector is empty (contains only cleared bits) | |
2703 | or if it has a length of zero (if it contains no bits at all), | |
2704 | the method returns an empty list. | |
2705 | ||
2706 | This method can be useful, for instance, to obtain a list of | |
2707 | prime numbers: | |
2708 | ||
2709 | $limit = 1000; # or whatever | |
2710 | $vector = Bit::Vector->new($limit+1); | |
2711 | $vector->Primes(); | |
2712 | @primes = $vector->Index_List_Read(); | |
2713 | ||
2714 | =item * | |
2715 | ||
2716 | C<$set3-E<gt>Union($set1,$set2);> | |
2717 | ||
2718 | This method calculates the union of "C<$set1>" and "C<$set2>" and stores | |
2719 | the result in "C<$set3>". | |
2720 | ||
2721 | This is usually written as "C<$set3 = $set1 u $set2>" in set theory | |
2722 | (where "u" is the "cup" operator). | |
2723 | ||
2724 | (On systems where the "cup" character is unavailable this operator | |
2725 | is often denoted by a plus sign "+".) | |
2726 | ||
2727 | In-place calculation is also possible, i.e., "C<$set3>" may be identical | |
2728 | with "C<$set1>" or "C<$set2>" or both. | |
2729 | ||
2730 | =item * | |
2731 | ||
2732 | C<$set3-E<gt>Intersection($set1,$set2);> | |
2733 | ||
2734 | This method calculates the intersection of "C<$set1>" and "C<$set2>" and | |
2735 | stores the result in "C<$set3>". | |
2736 | ||
2737 | This is usually written as "C<$set3 = $set1 n $set2>" in set theory | |
2738 | (where "n" is the "cap" operator). | |
2739 | ||
2740 | (On systems where the "cap" character is unavailable this operator | |
2741 | is often denoted by an asterisk "*".) | |
2742 | ||
2743 | In-place calculation is also possible, i.e., "C<$set3>" may be identical | |
2744 | with "C<$set1>" or "C<$set2>" or both. | |
2745 | ||
2746 | =item * | |
2747 | ||
2748 | C<$set3-E<gt>Difference($set1,$set2);> | |
2749 | ||
2750 | This method calculates the difference of "C<$set1>" less "C<$set2>" and | |
2751 | stores the result in "C<$set3>". | |
2752 | ||
2753 | This is usually written as "C<$set3 = $set1 \ $set2>" in set theory | |
2754 | (where "\" is the "less" operator). | |
2755 | ||
2756 | In-place calculation is also possible, i.e., "C<$set3>" may be identical | |
2757 | with "C<$set1>" or "C<$set2>" or both. | |
2758 | ||
2759 | =item * | |
2760 | ||
2761 | C<$set3-E<gt>ExclusiveOr($set1,$set2);> | |
2762 | ||
2763 | This method calculates the symmetric difference of "C<$set1>" and "C<$set2>" | |
2764 | and stores the result in "C<$set3>". | |
2765 | ||
2766 | This can be written as "C<$set3 = ($set1 u $set2) \ ($set1 n $set2)>" in set | |
2767 | theory (the union of the two sets less their intersection). | |
2768 | ||
2769 | When sets are implemented as bit vectors then the above formula is | |
2770 | equivalent to the exclusive-or between corresponding bits of the two | |
2771 | bit vectors (hence the name of this method). | |
2772 | ||
2773 | Note that this method is also much more efficient than evaluating the | |
2774 | above formula explicitly since it uses a built-in machine language | |
2775 | instruction internally. | |
2776 | ||
2777 | In-place calculation is also possible, i.e., "C<$set3>" may be identical | |
2778 | with "C<$set1>" or "C<$set2>" or both. | |
2779 | ||
2780 | =item * | |
2781 | ||
2782 | C<$set2-E<gt>Complement($set1);> | |
2783 | ||
2784 | This method calculates the complement of "C<$set1>" and stores the result | |
2785 | in "C<$set2>". | |
2786 | ||
2787 | In "big integer" arithmetic, this is equivalent to calculating the one's | |
2788 | complement of the number stored in the bit vector "C<$set1>" in binary | |
2789 | representation. | |
2790 | ||
2791 | In-place calculation is also possible, i.e., "C<$set2>" may be identical | |
2792 | with "C<$set1>". | |
2793 | ||
2794 | =item * | |
2795 | ||
2796 | C<if ($set1-E<gt>subset($set2))> | |
2797 | ||
2798 | Returns "true" ("C<1>") if "C<$set1>" is a subset of "C<$set2>" | |
2799 | (i.e., completely contained in "C<$set2>") and "false" ("C<0>") | |
2800 | otherwise. | |
2801 | ||
2802 | This means that any bit which is set ("C<1>") in "C<$set1>" must | |
2803 | also be set in "C<$set2>", but "C<$set2>" may contain set bits | |
2804 | which are not set in "C<$set1>", in order for the condition | |
2805 | of subset relationship to be true between these two sets. | |
2806 | ||
2807 | Note that by definition, if two sets are identical, they are | |
2808 | also subsets (and also supersets) of each other. | |
2809 | ||
2810 | =item * | |
2811 | ||
2812 | C<$norm = $set-E<gt>Norm();> | |
2813 | ||
2814 | Returns the norm (number of bits which are set) of the given vector. | |
2815 | ||
2816 | This is equivalent to the number of elements contained in the given | |
2817 | set. | |
2818 | ||
2819 | =item * | |
2820 | ||
2821 | C<$min = $set-E<gt>Min();> | |
2822 | ||
2823 | Returns the minimum of the given set, i.e., the minimum of all | |
2824 | indices of all set bits in the given bit vector "C<$set>". | |
2825 | ||
2826 | If the set is empty (no set bits), plus infinity (represented | |
2827 | by the constant "MAX_LONG" on your system) is returned. | |
2828 | ||
2829 | (This constant is usually S<2 ^ (n-1) - 1>, where "C<n>" is the | |
2830 | number of bits of an unsigned long on your machine.) | |
2831 | ||
2832 | =item * | |
2833 | ||
2834 | C<$max = $set-E<gt>Max();> | |
2835 | ||
2836 | Returns the maximum of the given set, i.e., the maximum of all | |
2837 | indices of all set bits in the given bit vector "C<$set>". | |
2838 | ||
2839 | If the set is empty (no set bits), minus infinity (represented | |
2840 | by the constant "MIN_LONG" on your system) is returned. | |
2841 | ||
2842 | (This constant is usually S<-(2 ^ (n-1) - 1)> or S<-(2 ^ (n-1))>, | |
2843 | where "C<n>" is the number of bits of an unsigned long on your machine.) | |
2844 | ||
2845 | =item * | |
2846 | ||
2847 | C<$m3-E<gt>Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);> | |
2848 | ||
2849 | This method multiplies two boolean matrices (stored as bit vectors) | |
2850 | "C<$m1>" and "C<$m2>" and stores the result in matrix "C<$m3>". | |
2851 | ||
2852 | The method uses the binary "xor" operation ("C<^>") as the boolean | |
2853 | addition operator ("C<+>"). | |
2854 | ||
2855 | An exception is raised if the product of the number of rows and | |
2856 | columns of any of the three matrices differs from the actual size | |
2857 | of their underlying bit vector. | |
2858 | ||
2859 | An exception is also raised if the numbers of rows and columns | |
2860 | of the three matrices do not harmonize in the required manner: | |
2861 | ||
2862 | rows3 == rows1 | |
2863 | cols3 == cols2 | |
2864 | cols1 == rows2 | |
2865 | ||
2866 | This method is used by the module "Math::MatrixBool". | |
2867 | ||
2868 | See L<Math::MatrixBool(3)> for details. | |
2869 | ||
2870 | =item * | |
2871 | ||
2872 | C<$m3-E<gt>Product($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);> | |
2873 | ||
2874 | This method multiplies two boolean matrices (stored as bit vectors) | |
2875 | "C<$m1>" and "C<$m2>" and stores the result in matrix "C<$m3>". | |
2876 | ||
2877 | This special method uses the binary "or" operation ("C<|>") as the | |
2878 | boolean addition operator ("C<+>"). | |
2879 | ||
2880 | An exception is raised if the product of the number of rows and | |
2881 | columns of any of the three matrices differs from the actual size | |
2882 | of their underlying bit vector. | |
2883 | ||
2884 | An exception is also raised if the numbers of rows and columns | |
2885 | of the three matrices do not harmonize in the required manner: | |
2886 | ||
2887 | rows3 == rows1 | |
2888 | cols3 == cols2 | |
2889 | cols1 == rows2 | |
2890 | ||
2891 | This method is used by the module "Math::MatrixBool". | |
2892 | ||
2893 | See L<Math::MatrixBool(3)> for details. | |
2894 | ||
2895 | =item * | |
2896 | ||
2897 | C<$matrix-E<gt>Closure($rows,$cols);> | |
2898 | ||
2899 | This method calculates the reflexive transitive closure of the | |
2900 | given boolean matrix (stored as a bit vector) using Kleene's | |
2901 | algoritm. | |
2902 | ||
2903 | (See L<Math::Kleene(3)> for a brief introduction into the | |
2904 | theory behind Kleene's algorithm.) | |
2905 | ||
2906 | The reflexive transitive closure answers the question whether | |
2907 | a path exists between any two vertices of a graph whose edges | |
2908 | are given as a matrix: | |
2909 | ||
2910 | If a (directed) edge exists going from vertex "i" to vertex "j", | |
2911 | then the element in the matrix with coordinates (i,j) is set to | |
2912 | "C<1>" (otherwise it remains set to "C<0>"). | |
2913 | ||
2914 | If the edges are undirected, the resulting matrix is symmetric, | |
2915 | i.e., elements (i,j) and (j,i) always contain the same value. | |
2916 | ||
2917 | The matrix representing the edges of the graph only answers the | |
2918 | question whether an B<EDGE> exists between any two vertices of | |
2919 | the graph or not, whereas the reflexive transitive closure | |
2920 | answers the question whether a B<PATH> (a series of adjacent | |
2921 | edges) exists between any two vertices of the graph! | |
2922 | ||
2923 | Note that the contents of the given matrix are modified by | |
2924 | this method, so make a copy of the initial matrix in time | |
2925 | if you are going to need it again later. | |
2926 | ||
2927 | An exception is raised if the given matrix is not quadratic, | |
2928 | i.e., if the number of rows and columns of the given matrix | |
2929 | is not identical. | |
2930 | ||
2931 | An exception is also raised if the product of the number of | |
2932 | rows and columns of the given matrix differs from the actual | |
2933 | size of its underlying bit vector. | |
2934 | ||
2935 | This method is used by the module "Math::MatrixBool". | |
2936 | ||
2937 | See L<Math::MatrixBool(3)> for details. | |
2938 | ||
2939 | =item * | |
2940 | ||
2941 | C<$matrix2-E<gt>Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);> | |
2942 | ||
2943 | This method calculates the transpose of a boolean matrix "C<$matrix1>" | |
2944 | (stored as a bit vector) and stores the result in matrix "C<$matrix2>". | |
2945 | ||
2946 | The transpose of a boolean matrix, representing the edges of a graph, | |
2947 | can be used for finding the strongly connected components of that graph. | |
2948 | ||
2949 | An exception is raised if the product of the number of rows and | |
2950 | columns of any of the two matrices differs from the actual size | |
2951 | of its underlying bit vector. | |
2952 | ||
2953 | An exception is also raised if the following conditions are not | |
2954 | met: | |
2955 | ||
2956 | rows2 == cols1 | |
2957 | cols2 == rows1 | |
2958 | ||
2959 | Note that in-place processing ("C<$matrix1>" and "C<$matrix2>" are | |
2960 | identical) is only possible if the matrix is quadratic. Otherwise, | |
2961 | a fatal "matrix is not quadratic" error will occur. | |
2962 | ||
2963 | This method is used by the module "Math::MatrixBool". | |
2964 | ||
2965 | See L<Math::MatrixBool(3)> for details. | |
2966 | ||
2967 | =back | |
2968 | ||
2969 | =head1 SEE ALSO | |
2970 | ||
2971 | Bit::Vector::Overload(3), Set::IntRange(3), | |
2972 | Math::MatrixBool(3), Math::MatrixReal(3), | |
2973 | DFA::Kleene(3), Math::Kleene(3), | |
2974 | Graph::Kruskal(3). | |
2975 | ||
2976 | perl(1), perlsub(1), perlmod(1), perlref(1), | |
2977 | perlobj(1), perlbot(1), perltoot(1), perlxs(1), | |
2978 | perlxstut(1), perlguts(1), overload(3). | |
2979 | ||
2980 | =head1 VERSION | |
2981 | ||
2982 | This man page documents "Bit::Vector" version 6.1. | |
2983 | ||
2984 | =head1 AUTHOR | |
2985 | ||
2986 | Steffen Beyer | |
2987 | mailto:sb@engelschall.com | |
2988 | http://www.engelschall.com/u/sb/download/ | |
2989 | ||
2990 | =head1 COPYRIGHT | |
2991 | ||
2992 | Copyright (c) 1995 - 2001 by Steffen Beyer. All rights reserved. | |
2993 | ||
2994 | =head1 LICENSE | |
2995 | ||
2996 | This package is free software; you can redistribute it and/or | |
2997 | modify it under the same terms as Perl itself, i.e., under the | |
2998 | terms of the "Artistic License" or the "GNU General Public License". | |
2999 | ||
3000 | The C library at the core of this Perl module can additionally | |
3001 | be redistributed and/or modified under the terms of the "GNU | |
3002 | Library General Public License". | |
3003 | ||
3004 | Please refer to the files "Artistic.txt", "GNU_GPL.txt" and | |
3005 | "GNU_LGPL.txt" in this distribution for details! | |
3006 | ||
3007 | =head1 DISCLAIMER | |
3008 | ||
3009 | This package is distributed in the hope that it will be useful, | |
3010 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
3011 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
3012 | ||
3013 | See the "GNU General Public License" for more details. | |
3014 |