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