| 1 | $FALSE = 0; | ||
| 2 | $TRUE = 1; | ||
| 3 | $INFINITY = 9999999999; | ||
| 4 | $TINY = 0.0000001; | ||
| 5 | |||
| 6 | |||
| 7 | sub min { | ||
| 8 | my($x, $y) = @_; | ||
| 9 | if ($x < $y) { | ||
| 10 | return $x; | ||
| 11 | } else { | ||
| 12 | return $y; | ||
| 13 | }; | ||
| 14 | }; | ||
| 15 | |||
| 16 | |||
| 17 | sub minratio { | ||
| 18 | # returns smaller of x/y or y/x | ||
| 19 | my($x, $y) = @_; | ||
| 20 | if ($x < $y) { | ||
| 21 | return $x / $y; | ||
| 22 | } else { | ||
| 23 | return $y / $x; | ||
| 24 | }; | ||
| 25 | }; | ||
| 26 | |||
| 27 | |||
| 28 | sub max { | ||
| 29 | my($x, $y) = @_; | ||
| 30 | if ($x > $y) { | ||
| 31 | return $x; | ||
| 32 | } else { | ||
| 33 | return $y; | ||
| 34 | }; | ||
| 35 | }; | ||
| 36 | |||
| 37 | |||
| 38 | sub round { | ||
| 39 | # rounds numbers to the specified precision | ||
| 40 | my($prec,$orig) = @_; | ||
| 41 | my($sign) = $orig <=> 0; | ||
| 42 | return int($orig / $prec + .5 * $sign) * $prec; | ||
| 43 | }; | ||
| 44 | |||
| 45 | |||
| 46 | sub maxar { | ||
| 47 | # returns @$arptr index with highest value, | ||
| 48 | # out of those listed in @$choice | ||
| 49 | ($arptr, $choice) = @_; | ||
| 50 | |||
| 51 | my($m, $i) = (0, 0); | ||
| 52 | while ($i <= $#$choice) { | ||
| 53 | if ($$arptr[$$choice[$i]] > $$arptr[$$choice[$m]]) { | ||
| 54 | $m = $i; | ||
| 55 | }; | ||
| 56 | $i++; | ||
| 57 | }; | ||
| 58 | return $$choice[$m]; | ||
| 59 | }; | ||
| 60 | |||
| 61 | |||
| 62 | sub minar { | ||
| 63 | # returns @$arptr index with lowest value, | ||
| 64 | # out of those listed in @$choice | ||
| 65 | ($arptr, $choice) = @_; | ||
| 66 | |||
| 67 | my($m, $i) = (0,0); | ||
| 68 | while ($i <= $#$choice) { | ||
| 69 | if ($$arptr[$$choice[$i]] < $$arptr[$$choice[$m]]) { | ||
| 70 | $m = $i; | ||
| 71 | }; | ||
| 72 | $i++; | ||
| 73 | }; | ||
| 74 | return $$choice[$m]; | ||
| 75 | }; | ||
| 76 | |||
| 77 | sub maxar_string { | ||
| 78 | # returns @$arptr index with highest value, | ||
| 79 | # out of those listed in @$choice | ||
| 80 | ($arptr, $choice) = @_; | ||
| 81 | |||
| 82 | my($m, $i) = (0, 0); | ||
| 83 | while ($i <= $#$choice) { | ||
| 84 | if ($$arptr[$$choice[$i]] gt $$arptr[$$choice[$m]]) { | ||
| 85 | $m = $i; | ||
| 86 | }; | ||
| 87 | $i++; | ||
| 88 | }; | ||
| 89 | return $$choice[$m]; | ||
| 90 | }; | ||
| 91 | |||
| 92 | |||
| 93 | sub minar_string { | ||
| 94 | # returns @$arptr index with lowest value, | ||
| 95 | # out of those listed in @$choice | ||
| 96 | ($arptr, $choice) = @_; | ||
| 97 | |||
| 98 | my($m, $i) = (0,0); | ||
| 99 | while ($i <= $#$choice) { | ||
| 100 | if ($$arptr[$$choice[$i]] lt $$arptr[$$choice[$m]]) { | ||
| 101 | $m = $i; | ||
| 102 | }; | ||
| 103 | $i++; | ||
| 104 | }; | ||
| 105 | return $$choice[$m]; | ||
| 106 | }; | ||
| 107 | |||
| 108 | sub eqar { | ||
| 109 | # boolean string array "equals" | ||
| 110 | my($ptr1, $ptr2) = @_; | ||
| 111 | my($i); | ||
| 112 | |||
| 113 | if ($#{$ptr1} != $#{$ptr2}) { | ||
| 114 | return $FALSE; | ||
| 115 | }; | ||
| 116 | for($i = 0; $i < @$ptr1; $i++) { | ||
| 117 | if ($$ptr1[$i] ne $$ptr2[$i]) { | ||
| 118 | return $FALSE; | ||
| 119 | }; | ||
| 120 | }; | ||
| 121 | |||
| 122 | return $TRUE; | ||
| 123 | }; | ||
| 124 | |||
| 125 | |||
| 126 | sub eqar_numeric { | ||
| 127 | # boolean numeric array "equals" | ||
| 128 | my($ptr1, $ptr2) = @_; | ||
| 129 | my($i); | ||
| 130 | |||
| 131 | if ($#{$ptr1} != $#{$ptr2}) { | ||
| 132 | return $FALSE; | ||
| 133 | }; | ||
| 134 | for($i = 0; $i < @$ptr1; $i++) { | ||
| 135 | if ($$ptr1[$i] != $$ptr2[$i]) { | ||
| 136 | return $FALSE; | ||
| 137 | }; | ||
| 138 | }; | ||
| 139 | |||
| 140 | return $TRUE; | ||
| 141 | }; | ||
| 142 | |||
| 143 | |||
| 144 | sub gtar_numeric { | ||
| 145 | # boolean numeric array "greather than" | ||
| 146 | my($ptr1, $ptr2) = @_; | ||
| 147 | my($i, $maxind); | ||
| 148 | |||
| 149 | $maxind = &min($#{$ptr1}, $#{$ptr2}); | ||
| 150 | for($i = 0; $i <= $maxind; $i++) { | ||
| 151 | if ($$ptr1[$i] < $$ptr2[$i]) { | ||
| 152 | return $FALSE; | ||
| 153 | }; | ||
| 154 | }; | ||
| 155 | if ($#{$ptr1} <= $#{$ptr2}) { | ||
| 156 | return $FALSE; | ||
| 157 | }; | ||
| 158 | |||
| 159 | return $TRUE; | ||
| 160 | }; | ||
| 161 | |||
| 162 | |||
| 163 | sub bynumar { | ||
| 164 | # sort subroutine: numeric arrays | ||
| 165 | my($i, $uc, $lc); | ||
| 166 | |||
| 167 | if ($#{$a} <= $#{$b}) { | ||
| 168 | $lc = $a; | ||
| 169 | $uc = $b; | ||
| 170 | } else { | ||
| 171 | $uc = $a; | ||
| 172 | $lc = $b; | ||
| 173 | } | ||
| 174 | for($i = 0; $i < @$lc; $i++) { | ||
| 175 | if ($$a[$i] < $$b[$i]) { | ||
| 176 | return -1; | ||
| 177 | } elsif ($$a[$i] > $$b[$i]) { | ||
| 178 | return 1; | ||
| 179 | }; | ||
| 180 | }; | ||
| 181 | |||
| 182 | if ($#{$a} < $#{$b}) { | ||
| 183 | return -1; | ||
| 184 | } else { | ||
| 185 | return 0; | ||
| 186 | }; | ||
| 187 | }; | ||
| 188 | |||
| 189 | sub arcopy { | ||
| 190 | # returns a copy of the array | ||
| 191 | # used for passing recursive arrays by value | ||
| 192 | my($arptr) = shift; | ||
| 193 | |||
| 194 | my(@newar); | ||
| 195 | |||
| 196 | foreach $el (@$arptr) { | ||
| 197 | if (not ref($el)) { | ||
| 198 | push(@newar, $el); | ||
| 199 | } elsif (ref($el) eq "ARRAY") { | ||
| 200 | push(@newar, &arcopy($el)); | ||
| 201 | } else { | ||
| 202 | die "Element in recursive array is a non-array reference!\n"; | ||
| 203 | }; | ||
| 204 | }; | ||
| 205 | |||
| 206 | return [@newar]; | ||
| 207 | }; | ||
| 208 | |||
| 209 | |||
| 210 | sub insar_numeric_uniq { | ||
| 211 | # inserts numeric array into sorted list of arrays | ||
| 212 | # if array already exists, only one copy is kept | ||
| 213 | # returns pointer to new list of arrays, and index of insertion | ||
| 214 | # if not unique, then index of insertion = -1 | ||
| 215 | |||
| 216 | my($ararptr, $iarptr) = @_; | ||
| 217 | my($i); | ||
| 218 | |||
| 219 | for($i = 0; $i <= $#{$ararptr}; $i++) { | ||
| 220 | if (&eqar_numeric($$ararptr[$i], $iarptr)) { | ||
| 221 | return ($ararptr, -1); # no insertion | ||
| 222 | } elsif (>ar_numeric($$ararptr[$i], $iarptr)) { | ||
| 223 | splice(@$ararptr, $i, $iarptr); | ||
| 224 | return ($ararptr, $i); | ||
| 225 | }; | ||
| 226 | }; | ||
| 227 | |||
| 228 | # greatest so far | ||
| 229 | push(@$ararptr, $iarptr); | ||
| 230 | return ($ararptr, $i+1); | ||
| 231 | }; | ||
| 232 | |||
| 233 | |||
| 234 | sub rnd { | ||
| 235 | my($min, $max) = @_; | ||
| 236 | $range = $max - $min + 1; | ||
| 237 | return int(rand() * $range + $min); | ||
| 238 | }; | ||
| 239 | |||
| 240 | |||
| 241 | sub byvalue { $val{$a} <=> $val{$b} }; | ||
| 242 | sub bynumber { $a <=> $b }; | ||
| 243 | |||
| 244 | |||
| 245 | sub isnumber { | ||
| 246 | my($x) = @_; | ||
| 247 | $z = $x; | ||
| 248 | return ($z + 0 != 0 || $x eq "0" || $x eq "0.0"); | ||
| 249 | }; | ||
| 250 | |||
| 251 | |||
| 252 | sub Log { | ||
| 253 | my($p) = @_; | ||
| 254 | |||
| 255 | if ($p == 0) | ||
| 256 | {-999999;} | ||
| 257 | else | ||
| 258 | {log($p)}; | ||
| 259 | } | ||
| 260 | |||
| 261 | sub string_lcs { | ||
| 262 | # length of longest common subsequence of two strings | ||
| 263 | # uses dynamic programming | ||
| 264 | my($str1, $str2) = @_; | ||
| 265 | my(@m, $i, $j); | ||
| 266 | |||
| 267 | my(@c1) = split('', $str1); | ||
| 268 | my(@c2) = split('', $str2); | ||
| 269 | |||
| 270 | if ($c1[0] eq $c2[0]) { | ||
| 271 | $m[0][0] = 1; | ||
| 272 | } else { | ||
| 273 | $m[0][0] = 0; | ||
| 274 | }; | ||
| 275 | for($i = 1; $i <= $#c1; $i++) { | ||
| 276 | if ($c1[$i] eq $c2[0]) { | ||
| 277 | do { | ||
| 278 | $m[$i][0] = 1; | ||
| 279 | $i++; | ||
| 280 | } until ($i > $#c1); | ||
| 281 | } else { | ||
| 282 | $m[$i][0] = 0; | ||
| 283 | }; | ||
| 284 | }; | ||
| 285 | for($j = 1; $j <= $#c2; $j++) { | ||
| 286 | if ($c1[0] eq $c2[$j]) { | ||
| 287 | do { | ||
| 288 | $m[0][$j] = 1; | ||
| 289 | $j++; | ||
| 290 | } until ($j > $#c2); | ||
| 291 | } else { | ||
| 292 | $m[0][$j] = 0; | ||
| 293 | }; | ||
| 294 | }; | ||
| 295 | for($i = 1; $i <= $#c1; $i++) { | ||
| 296 | for($j = 1; $j <= $#c2; $j++) { | ||
| 297 | if ($c1[$i] eq $c2[$j]) { | ||
| 298 | $m[$i][$j] = $m[$i-1][$j-1] + 1; | ||
| 299 | } else { | ||
| 300 | $m[$i][$j] = &max($m[$i-1][$j], $m[$i][$j-1]); | ||
| 301 | }; | ||
| 302 | }; | ||
| 303 | }; | ||
| 304 | |||
| 305 | return $m[$#c1][$#c2]; | ||
| 306 | }; | ||
| 307 | |||
| 308 | |||
| 309 | sub bsearch { | ||
| 310 | # returns index of highest element in array that | ||
| 311 | # is smaller than target | ||
| 312 | # array should be sorted in increasing order | ||
| 313 | # N.B.: if whole array is to be searched, then | ||
| 314 | # the first $min parameter should = -1. | ||
| 315 | # This way, if $$arptr[0] > $target, the | ||
| 316 | # search can return -1; | ||
| 317 | # Also, if $#$arptr < 0, returns -1; | ||
| 318 | # this version does numeric comparisons | ||
| 319 | |||
| 320 | my( $target, $min, $max, $arptr) = @_; | ||
| 321 | if ($#$arptr < 0) {return -1}; | ||
| 322 | my( $shot, $comp); | ||
| 323 | |||
| 324 | if ($min >= $max - 1) { | ||
| 325 | $comp = $$arptr[$max] <=> $target; | ||
| 326 | if ($comp < 0) { | ||
| 327 | return $max; | ||
| 328 | } else { | ||
| 329 | return $min; | ||
| 330 | }; | ||
| 331 | }; | ||
| 332 | |||
| 333 | $shot = int(($max + $min) * .5); | ||
| 334 | $comp = $$arptr[$shot] <=> $target; | ||
| 335 | if ($comp == 0) { | ||
| 336 | return $shot; | ||
| 337 | } elsif ( $comp < 0 ) { | ||
| 338 | return &bsearch( $target, $shot, $max, $arptr); | ||
| 339 | } else { | ||
| 340 | return &bsearch( $target, $min, $shot, $arptr); | ||
| 341 | }; | ||
| 342 | }; | ||
| 343 | |||
| 344 | sub nupdsort { | ||
| 345 | # numerical push-down sort, with uniq | ||
| 346 | my($stackptr, $inputptr) = @_; | ||
| 347 | my($ss); | ||
| 348 | |||
| 349 | foreach $ss (@$inputptr) { | ||
| 350 | $outind = $#$stackptr; | ||
| 351 | while ($outind >=0 and | ||
| 352 | ($$inputptr[$ss] < $$stackptr[$outind])) { | ||
| 353 | $outind--; | ||
| 354 | }; | ||
| 355 | if ($$inputptr[$ss] == $$stackptr[$outind]) { | ||
| 356 | next; | ||
| 357 | }; | ||
| 358 | $outind++; | ||
| 359 | splice(@$stackptr, $outind, 0, $$inputptr[$ss]); | ||
| 360 | }; | ||
| 361 | |||
| 362 | return $stackptr; | ||
| 363 | }; | ||
| 364 | |||
| 365 | sub usort { | ||
| 366 | # string sort with unique | ||
| 367 | my(@sorted) = sort @_; | ||
| 368 | my($i); | ||
| 369 | |||
| 370 | for($i = $#sorted; $i > 0; $i--) { | ||
| 371 | if ($sorted[$i] eq $sorted[$i - 1]) { | ||
| 372 | splice(@sorted, $i, 1); | ||
| 373 | }; | ||
| 374 | }; | ||
| 375 | |||
| 376 | return \@sorted; | ||
| 377 | }; | ||
| 378 | |||
| 379 | sub dump_hash { | ||
| 380 | my($hashptr) = shift; | ||
| 381 | my($key, $value); | ||
| 382 | |||
| 383 | while (($key,$value) = each %$hashptr) { | ||
| 384 | print "$key $value\n"; | ||
| 385 | }; | ||
| 386 | }; | ||
| 387 | |||
| 388 | return 1; |