CCS/Utils/ccsutils.pd

filter: Statementstmt 75.0% 3 / 4 Branchbran n/a Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 1 / 1 Podpod n/a totaltotal 80.0% 4 / 5 CC 1 SCAR 0.0
CC
1
Cov
75%
BEGIN
1.0
CRAP 1.0
« CCS/Utils/t/03_decode.t ↑ Summary CCS/Ufunc/Ufunc.pm »
1 ##-*- Mode: CPerl -*-
2  
3 ##======================================================================
4 ## Header Administrivia
5 ##======================================================================
6  
7 use PDL::VectorValued::Dev;
8 my $VERSION = '1.24.1'; ##-- update with perl-reversion from Perl::Version module
9 pp_setversion($VERSION);
10  
11 ##------------------------------------------------------
12 ## pm headers
13 pp_addpm({At=>'Top'},<<'EOPM');
14  
15 3 ▶#use PDL::CCS::Config;
Subroutine BEGIN: called CC=1 SCAR=0.0
16 use strict;
17  
18 =pod
19  
20 =head1 NAME
21  
22 PDL::CCS::Utils - Low-level utilities for compressed storage sparse PDLs
23  
24 =head1 SYNOPSIS
25  
26 use PDL;
27 use PDL::CCS::Utils;
28  
29 ##---------------------------------------------------------------------
30 ## ... stuff happens
31  
32 =cut
33  
34 EOPM
35 ## /pm additions
36 ##------------------------------------------------------
37  
38 ##------------------------------------------------------
39 ## Exports: None
40 #pp_export_nothing();
41  
42 ##------------------------------------------------------
43 ## Includes / defines
44 pp_addhdr(<<'EOH');
45 #include "ccsutils.h"
46 EOH
47  
48 ##------------------------------------------------------
49 ## index datatype
50 require "../Config.pm";
51 our $INDX = $PDL::CCS::Config::ccsConfig{INDX_SIG};
52 pp_addpm( $PDL::CCS::Config::ccsConfig{INDX_FUNCDEF} );
53 0 pp_addhdr( $PDL::CCS::Config::ccsConfig{INDX_TYPEDEF} );
54  
55  
56 ##======================================================================
57 ## C Utilities
58 ##======================================================================
59 # (none)
60  
61 ##======================================================================
62 ## PDL::PP Wrappers
63 ##======================================================================
64  
65  
66 ##======================================================================
67 ## Non-missing Value Counts
68 ##======================================================================
69  
70 pp_addpm(<<'EOPM');
71  
72 =pod
73  
74 =head1 Non-missing Value Counts
75  
76 =cut
77  
78 EOPM
79  
80 ##------------------------------------------------------
81 ## nnz() : get number of nonzero values
82 pp_def(
83 'nnz',
84 Pars => "a(N); $INDX\ [o]nnz()",
85 HandleBad => 1,
86 Code => q{
87 broadcastloop %{
88 $nnz()=0;
89 loop (N) %{
90 if ($a()!=0) ++$nnz();
91 %}
92 %}
93 $PDLSTATESETGOOD(nnz); /*-- output is always good --*/
94 },
95  
96 Doc => <<'EOD',
97 Get number of non-zero values in a PDL $a();
98 For 1d PDLs, should be equivalent to:
99  
100 $nnz = nelem(which($a!=0));
101  
102 For k>1 dimensional PDLs, projects via number of nonzero elements
103 to N-1 dimensions by computing the number of nonzero elements
104 along the the 1st dimension.
105  
106 EOD
107  
108 BadDoc=> 'The output PDL $nnz() never contains BAD values.',
109 );
110  
111  
112 ##------------------------------------------------------
113 ## nnza() : get number of non-approximate zero values
114 use PDL;
115 my %absfunc = (
116 map {
117 my $typ = PDL->can($_);
118 ($typ
119 ? ($typ->()->ppsym => ($typ->()->ctype eq 'long' ? "labs" : "llabs"))
120 : qw())
121 } qw (longlong indx)
122 );
123 pp_def(
124 'nnza',
125 Pars => "a(N); eps(); $INDX\ [o]nnz();",
126 HandleBad => 1,
127 Code => '
128 broadcastloop %{
129 $nnz()=0;
130 loop (N) %{
131 types(BSUL) %{ if ( abs($a()) > $eps()) ++$nnz(); %}
132 '.join("\n ", map {"types($_) %{ if ($absfunc{$_}(\$a()) > \$eps()) ++\$nnz(); %}"} sort keys(%absfunc)).'
133 types(F) %{ if (fabsf($a()) > $eps()) ++$nnz(); %}
134 types(D) %{ if (fabs ($a()) > $eps()) ++$nnz(); %}
135 %}
136 %}
137 $PDLSTATESETGOOD(nnz); /*-- output is always good --*/
138 ',
139  
140 Doc => <<'EOD',
141 Like nnz() using tolerance constant $eps().
142 For 1d PDLs, should be equivalent to:
143  
144 $nnz = nelem(which(!$a->approx(0,$eps)));
145  
146 EOD
147  
148 BadDoc=> 'The output PDL $nnz() never contains BAD values.',
149 );
150  
151  
152 ##======================================================================
153 ## Encoding
154 ##======================================================================
155  
156 pp_addpm(<<'EOPM');
157  
158 =pod
159  
160 =head1 Encoding Utilities
161  
162 =cut
163  
164 EOPM
165  
166 ##------------------------------------------------------
167 ## ccs_encode_pointers() : get encoded pointer & index translation PDL
168 pp_def(
169 'ccs_encode_pointers',
170 Pars => "$INDX\ ix(Nnz); $INDX\ N(); $INDX\ [o]ptr(Nplus1); $INDX\ [o]ixix(Nnz);",
171 PMCode=> q{
172 sub PDL::ccs_encode_pointers {
173 my ($ix,$N,$ptr,$ixix) = @_;
174 barf("Usage: ccs_encode_pointers(ix(Nnz), N(), [o]ptr(N+1), [o]ixix(Nnz)") if (!defined($ix));
175 &PDL::_ccs_encode_pointers_int($ix, ($N // $ix->max+1), ($ptr //= null), ($ixix //= null));
176 return ($ptr,$ixix);
177 }
178 },
179  
180 RedoDimsCode => q{
181 if ($SIZE(Nplus1) < 0) {
182 $SIZE(Nplus1) = $N() + 1;
183 }
184 else if ($SIZE(Nplus1) <= $N()) {
185 $CROAK("dimension Nplus1 (=%td) must be greater than N (=%td)", $SIZE(Nplus1), $N());
186 }
187 },
188  
189 Code => q{
190 /*-- Local variables --*/
191 CCS_Indx ixval, ixval_next, ixval_prev, nzi, nzj, sizeN=$SIZE(Nplus1)-1, sizeNnz=$SIZE(Nnz);
192 //
193 /*-- Count number of NZs in each column; store in ptr[N=>ixval] --*/
194 loop (Nplus1) %{ $ptr()=0; %}
195 loop (Nnz) %{ ixval=$ix(); ++$ptr(Nplus1=>ixval); %}
196 //
197 /*-- tweak ptr(): fill each cell with the starting point of the previous row --*/
198 ixval_prev = sizeN-1;
199 $ptr(Nplus1=>sizeN) = sizeNnz - $ptr(Nplus1=>ixval_prev);
200 for (ixval_next=sizeN, ixval=ixval_prev; ixval > 0; ixval_next=ixval--) {
201 ixval_prev = ixval-1;
202 $ptr(Nplus1=>ixval) = $ptr(Nplus1=>ixval_next) - $ptr(Nplus1=>ixval_prev);
203 }
204 $ptr(Nplus1=>0) = 0;
205 //
206 /*-- Assign columns and values --*/
207 for (nzi=0; nzi < sizeNnz; nzi++) {
208 ixval = $ix(Nnz=>nzi);
209 ixval_next = ixval+1;
210 nzj = $ptr(Nplus1=>ixval_next)++;
211 $ixix(Nnz=>nzj) = nzi;
212 }
213 },
214  
215 Doc => <<'EOD'
216 General CCS encoding utility.
217  
218 Get a compressed storage "pointer" vector $ptr
219 for a dimension of size $N with non-missing values at indices $ix. Also returns a vector
220 $ixix() which may be used as an index for $ix() to align its elements with $ptr()
221 along the compressed dimension.
222  
223 The induced vector $ix-E<gt>index($ixix) is
224 guaranteed to be stably sorted along dimension $N():
225  
226 \forall $i,$j with 1 <= $i < $j <= $Nnz :
227  
228 $ix->index($ixix)->at($i) < $ix->index($ixix)->at($j) ##-- primary sort on $ix()
229 or
230 $ixix->at($i) < $ixix->at($j) ##-- ... stable
231  
232 EOD
233 );
234  
235  
236 ##======================================================================
237 ## Decoding
238 ##======================================================================
239 pp_addpm(<<'EOPM');
240  
241 =pod
242  
243 =head1 Decoding Utilities
244  
245 =cut
246  
247 EOPM
248  
249 ##------------------------------------------------------
250 ## ccs_decode_pointer() : decode a CCS-encoded pointer
251 pp_def(
252 'ccs_decode_pointer',
253 Pars => "$INDX ptr(Nplus1); $INDX proj(Nproj); $INDX\ [o]projix(NnzProj); $INDX\ [o]nzix(NnzProj)",
254 OtherPars => 'PDL_Indx nnzProj;',
255 PMCode=> q{
256 sub PDL::ccs_decode_pointer {
257 my ($ptr,$proj,$projix,$nzix,$nnzproj) = @_;
258 barf("Usage: ccs_decode_pointer(ptr(N+1), proj(Nproj), [o]projix(NnzProj), [o]nzix(NnzProj), NnzProj?")
259 if (!defined($ptr));
260 if (!defined($proj)) {
261 $proj = PDL->sequence(ccs_indx(), $ptr->dim(0)-1);
262 $nnzproj //= $ptr->at(-1);
263 }
264 $projix //= null;
265 $nzix //= null;
266 $nnzproj //= ($projix->isnull && $nzix->isnull
267 ? ($ptr->index($proj+1)-$ptr->index($proj))->sum
268 : -1);
269 return (null,null) if (!$nnzproj);
270 &PDL::_ccs_decode_pointer_int($ptr,$proj, $projix,$nzix, $nnzproj);
271 return ($projix,$nzix);
272 }
273 },
274  
275 RedoDimsCode => q{
276 if ($SIZE(NnzProj) < 0) {
277 $SIZE(NnzProj) = $COMP(nnzProj);
278 }
279 },
280  
281 Code => q{
282 /*-- Local variables --*/
283 CCS_Indx ni,ni_next, nzi,nzi_next, ixi=0, sizeNproj=$SIZE(Nproj), sizeNnzProj=$SIZE(NnzProj);
284 loop (Nproj) %{
285 ni = $proj();
286 ni_next = ni+1;
287 nzi = $ptr(Nplus1=>ni);
288 nzi_next = $ptr(Nplus1=>ni_next);
289 for ( ; nzi < nzi_next && ixi < sizeNnzProj; nzi++, ixi++) {
290 $projix(NnzProj=>ixi) = Nproj;
291 $nzix(NnzProj=>ixi) = nzi;
292 }
293 %}
294 },
295  
296 Doc=><<'EOD'
297 General CCS decoding utility.
298  
299 Project indices $proj() from a compressed storage "pointer" vector $ptr().
300 If unspecified, $proj() defaults to:
301  
302 sequence($ptr->dim(0) - 1)
303  
304 EOD
305 );
306  
307  
308 ##======================================================================
309 ## Indexing
310 ##======================================================================
311 pp_addpm(<<'EOPM');
312  
313 =pod
314  
315 =head1 Indexing Utilities
316  
317 =cut
318  
319 EOPM
320  
321 ##------------------------------------------------------
322 ## ccs_xindex1d()
323 ## + optimized dice_axis on 0th dimension, no pointer required
324 vvpp_def(
325 'ccs_xindex1d',
326 Pars => "$INDX which(Ndims,Nnz); $INDX a(Na); $INDX\ [o]nzia(NnzA); $INDX\ [o]nnza()",
327 OtherPars => 'PDL_Indx sizeNnzA;',
328  
329 PMCode=> q{
330 sub PDL::ccs_xindex1d {
331 my ($which,$a,$nzia,$nnza) = @_;
332 barf("Usage: ccs_xindex2d(which(Ndims,Nnz), a(Na), [o]nzia(NnzA), [o]nnza()")
333 if ((grep {!defined($_)} @_[0..1]) || $which->ndims < 2 || $which->dim(0) < 1);
334 $nzia //= null;
335 $nnza //= null;
336 &PDL::_ccs_xindex1d_int($which,$a,$nzia,$nnza, ($nnza ? $nnza->sclr : -1));
337 return wantarray ? ($nzia,$nnza) : $nzia->reshape($nnza->sclr);
338 }
339 },
340  
341 RedoDimsCode => q(
342 if ($SIZE(NnzA) < 0) {
343 $SIZE(NnzA) = $COMP(sizeNnzA) >= 0 ? $COMP(sizeNnzA) : $SIZE(Nnz);
344 }
345 ),
346  
347 Code => q{
348 CCS_Indx a_min=0, a_max=$SIZE(Nnz);
349 CCS_Indx a_lb, a_ub, a_ubmax=a_max;
350 CCS_Indx nnzai = 0;
351 #if 0
352 /*-- DEBUG --*/
353 CCS_Indx size_nnz = $SIZE(Nnz);
354 CCS_Indx size_na = $SIZE(Na);
355 CCS_Indx size_nnza = $SIZE(NnzA);
356 printf("Nnz=%td, Na=%td [%td:%td], NnzA=%td\n", size_nnz, size_na,$a(Na=>0),$a(Na=>size_na-1), size_nnza);
357 #endif
358 loop (Na) %{
359 a_ubmax = a_max;
360 $LB('$a()', '$which(Ndims=>0,Nnz=>$_)', 'a_min','a_max', 'a_lb',ubmaxvar=>'a_ubmax');
361 if ($which(Ndims=>0,Nnz=>a_lb) != $a()) { a_min=a_lb; continue; }
362  
363 $LB('$a()+1', '$which(Ndims=>0,Nnz=>$_)', 'a_lb' ,'a_ubmax', 'a_ub');
364 if ($which(Ndims=>0,Nnz=>a_ub) <= $a()) ++a_ub;
365  
366 for ( ; a_lb < a_ub && nnzai < $SIZE(NnzA); ++a_lb, ++nnzai ) {
367 $nzia(NnzA=>nnzai) = a_lb;
368 }
369 if (nnzai >= $SIZE(NnzA)) break;
370 if (a_ub < a_max) a_min = a_ub;
371 %}
372 $nnza() = nnzai;
373 for ( ; nnzai < $SIZE(NnzA); ++nnzai) {
374 $nzia(NnzA=>nnzai) = -1;
375 }
376 },
377  
378 Doc=><<'EOD'
379 Compute indices $nzai() along dimension C<Nnz> of $which() whose initial values $which(0,$nzai)
380 match some element of $a(). Appropriate for indexing a sparse encoded PDL
381 with non-missing entries at $which()
382 along the 0th dimension, a la L<dice_axis(0,$a)|PDL::Slices/dice_axis>.
383 $which((0),) and $a() must be both sorted in ascending order.
384  
385 In list context, returns a list ($nzai,$nnza), where $nnza() is the number of indices found,
386 and $nzai are those C<Nnz> indices. In scalar context, trims the output vector $nzai() to $nnza()
387 elements.
388  
389 EOD
390 );
391  
392  
393 ##------------------------------------------------------
394 ## ccs_xindex2d()
395 ## + Cartesian-product index
396 vvpp_def(
397 'ccs_xindex2d',
398 Pars => "$INDX which(Ndims,Nnz); $INDX a(Na); $INDX b(Nb); $INDX\ [o]ab(Nab); $INDX\ [o]nab()",
399  
400 PMCode=> q{
401 sub PDL::ccs_xindex2d {
402 my ($which,$a,$b,$ab,$nab) = @_;
403 barf("Usage: ccs_xindex2d(which(2,Nnz), a(Na), b(Nb), [o]nab(), [o]ab(Nab)")
404 if ((grep {!defined($_)} @_[0..2]) || $which->ndims != 2 || $which->dim(0) < 2);
405 &PDL::_ccs_xindex2d_int($which,$a,$b, ($ab//=null), ($nab//=null));
406 return wantarray ? ($ab,$nab) : $ab->reshape($nab->sclr);
407 }
408 },
409  
410 RedoDimsCode => q{
411 if ($SIZE(Nab) < 0) {
412 if ($PDL(nab)->nvals > 0) {
413 $SIZE(Nab) = $nab();
414 } else {
415 $SIZE(Nab) = ($SIZE(Na)*$SIZE(Nb)) < $SIZE(Nnz) ? ($SIZE(Na)*$SIZE(Nb)) : $SIZE(Nnz);
416 }
417 }
418 },
419  
420 Code => q{
421 CCS_Indx a_min=0, a_max=$SIZE(Nnz);
422 CCS_Indx a_lb, a_ub, a_ubmax=a_max;
423 CCS_Indx b_min, b_max, b_lb;
424 CCS_Indx abi = 0;
425 #if 0
426 /*-- DEBUG --*/
427 CCS_Indx size_nnz = $SIZE(Nnz);
428 CCS_Indx size_na = $SIZE(Na);
429 CCS_Indx size_nb = $SIZE(Nb);
430 CCS_Indx size_nab = $SIZE(Nab);
431 printf("Nnz=%td, Na=%td [%td:%td], Nb=%td [%td:%td], Nab=%td\n", size_nnz, size_na,$a(Na=>0),$a(Na=>size_na-1), size_nb,$b(Nb=>0),$b(Nb=>size_nb-1), size_nab);
432 #endif
433 loop (Na) %{
434 a_ubmax = a_max;
435 $LB('$a()', '$which(Ndims=>0,Nnz=>$_)', 'a_min','a_max', 'a_lb',ubmaxvar=>'a_ubmax');
436 //printf("a:LB(a=%td,min=%td,max=%td)=%td --> %td (ubmax=%td)\n", $a(),a_min,a_max,a_lb, $which(Ndims=>0,Nnz=>a_lb), a_ubmax); fflush(stdout);
437 if ($which(Ndims=>0,Nnz=>a_lb) != $a()) { a_min=a_lb; continue; }
438 //
439 $LB('$a()+1', '$which(Ndims=>0,Nnz=>$_)', 'a_lb' ,'a_ubmax', 'a_ub');
440 if ($which(Ndims=>0,Nnz=>a_ub) <= $a()) ++a_ub;
441 //printf("a:UB(a=%td,min=%td,max=%td)=%td --> %td\n", $a(),a_lb,a_ubmax,a_ub, $which(Ndims=>0,Nnz=>a_ub)); fflush(stdout);
442 //
443 b_min = a_lb;
444 b_max = a_ub;
445 loop (Nb) %{
446 if (b_min >= b_max) break;
447 //printf("+ b:LB(a=%td,b=%td,min=%td,max=%td)=", $a(),$b(),b_min,b_max); fflush(stdout);
448 $LB('$b()', '$which(Ndims=>1,Nnz=>$_)', 'b_min','b_max', 'b_lb');
449 //printf("%td --> %td", b_lb, $which(Ndims=>1,Nnz=>b_lb));
450 if ($which(Ndims=>1,Nnz=>b_lb) == $b()) {
451 //printf(" *[%td]", abi); fflush(stdout);
452 $ab(Nab=>abi) = b_lb;
453 ++abi;
454 ++b_lb;
455 if (abi >= $SIZE(Nab)) break;
456 }
457 b_min = b_lb;
458 //printf("\n"); fflush(stdout);
459 %}
460 if (abi >= $SIZE(Nab)) break;
461 if (a_ub < a_max) a_min = a_ub;
462 %}
463 $nab() = abi;
464 for ( ; abi < $SIZE(Nab); ++abi) {
465 $ab(Nab=>abi) = -1;
466 }
467 },
468  
469 Doc=><<'EOD'
470 Compute indices along dimension C<NNz> of $which() corresponding to any combination
471 of values in the Cartesian product of $a() and $b(). Appropriate for indexing a
472 2d sparse encoded PDL with non-missing entries at $which() via the ND-index piddle
473 $a-E<gt>slice("*1,")-E<gt>cat($b)-E<gt>clump(2)-E<gt>xchg(0,1), i.e. all pairs $ai,$bi with $ai in $a()
474 and $bi in $b(). $a() and $b() values must be be sorted in ascending order
475  
476 In list context, returns a list ($ab,$nab), where $nab() is the number of indices found,
477 and $ab are those C<Nnz> indices. In scalar context, trims the output vector $ab() to $nab()
478 elements.
479  
480 EOD
481 );
482  
483  
484 ##======================================================================
485 ## Debugging
486 ##======================================================================
487 pp_addpm(<<'EOPM');
488  
489 =pod
490  
491 =head1 Debugging Utilities
492  
493 =cut
494  
495 EOPM
496  
497 ##------------------------------------------------------
498 ## ccs_dump_which()
499 ## + prints a text dump of an index
500 pp_def(
501 'ccs_dump_which',
502 Pars => "$INDX which(Ndims,Nnz)",
503 OtherPars => 'SV *HANDLE; char *fmt; char *fsep; char *rsep',
504  
505 PMCode=> q{
506 sub PDL::ccs_dump_which {
507 my ($which,$fh,$fmt,$fsep,$rsep) = @_;
508 $fmt = '%td' if (!defined($fmt) || $fmt eq '');
509 $fsep = " " if (!defined($fsep) || $fsep eq '');
510 $rsep = "$/" if (!defined($rsep) || $rsep eq '');
511 $fh = \*STDOUT if (!defined($fh));
512 &PDL::_ccs_dump_which_int($which,$fh,$fmt,$fsep,$rsep);
513 }
514 },
515  
516 Code => q{
517 CCS_Indx dimi, sizeNdims=$SIZE(Ndims);
518 char *fmt_str = $COMP(fmt);
519 char *fsep_str = $COMP(fsep);
520 char *rsep_str = $COMP(rsep);
521 PerlIO *pio;
522 IO *io;
523  
524 /*-- get PerlIO from SV (lifted from _rasc() n PDL_SRC_ROOT/IO/Misc/misc.pd) --*/
525 io = sv_2io($COMP(HANDLE));
526 if (!io || !(pio = IoIFP(io))) {
527 croak("can\'t get PerlIO pointer from HANDLE");
528 }
529  
530 loop (Nnz) %{
531 PerlIO_printf(pio, fmt_str, $which(Ndims=>0));
532 for (dimi=1; dimi<sizeNdims; dimi++) {
533 PerlIO_puts(pio,fsep_str);
534 PerlIO_printf(pio, fmt_str, $which(Ndims=>dimi));
535 }
536 PerlIO_puts(pio,rsep_str);
537 %}
538 },
539  
540 Doc=><<'EOD'
541 Print a text dump of an index PDL to the filehandle C<HANDLE>, which default to C<STDUT>.
542 C<$fmt> is a printf() format to use for output, which defaults to "%td".
543 C<$fsep> and C<$rsep> are field-and record separators, which default to
544 a single space and C<$/>, respectively.
545  
546 EOD
547 );
548  
549  
550  
551  
552 ##======================================================================
553 ## Footer Administrivia
554 ##======================================================================
555  
556 ##------------------------------------------------------
557 ## pm additions: footer
558 pp_addpm(<<'EOPM');
559  
560 ##---------------------------------------------------------------------
561 =pod
562  
563 =head1 ACKNOWLEDGEMENTS
564  
565 Perl by Larry Wall.
566  
567 PDL by Karl Glazebrook, Tuomas J. Lukka, Christian Soeller, and others.
568  
569 =cut
570  
571 ##----------------------------------------------------------------------
572 =pod
573  
574 =head1 KNOWN BUGS
575  
576 Probably many.
577  
578 =cut
579  
580  
581 ##---------------------------------------------------------------------
582 =pod
583  
584 =head1 AUTHOR
585  
586 Bryan Jurish E<lt>moocow@cpan.orgE<gt>
587  
588 =head2 Copyright Policy
589  
590 Copyright (C) 2007-2024, Bryan Jurish. All rights reserved.
591  
592 This package is free software, and entirely without warranty.
593 You may redistribute it and/or modify it under the same terms
594 as Perl itself.
595  
596 =head1 SEE ALSO
597  
598 perl(1), PDL(3perl)
599  
600 =cut
601  
602 EOPM
603  
604  
605 # Always make sure that you finish your PP declarations with
606 # pp_done
607 pp_done();
608 ##----------------------------------------------------------------------
« CCS/Utils/t/03_decode.t ↑ Summary CCS/Ufunc/Ufunc.pm »