File Coverage

blib/lib/Encode/Positive/Pairs.pm
Criterion Covered Total %
statement 54 54 100.0
branch 18 24 75.0
condition n/a
subroutine 11 11 100.0
pod 4 5 80.0
total 87 94 92.5


line stmt bran cond sub pod time code
1             #!/usr/bin/perl
2             #-------------------------------------------------------------------------------
3             # Encode pairs of positive integers as a single integer and vice-versa
4             #
5             # Philip R Brenan at gmail dot com, Appa Apps Ltd Inc, 2017
6             #-------------------------------------------------------------------------------
7             # podDocumentation
8              
9             package Encode::Positive::Pairs;
10             require v5.16.0;
11 1     1   355 use warnings FATAL => qw(all);
  1         2  
  1         30  
12 1     1   4 use strict;
  1         2  
  1         16  
13 1     1   4 use Carp;
  1         1  
  1         61  
14 1     1   751 use Math::BigInt;
  1         19450  
  1         4  
15              
16             our $VERSION = '20170808';
17              
18             #1 Convert # Encode pairs of positive integers as a single integer and vice-versa
19              
20             sub equation($) #P The sum of the numbers from 1 to a specified number
21 144314     144314 1 2270714 {my ($t) = @_; # The number of leading integers to sum
22 144314         286885 $t * ($t + 1) / 2
23             }
24              
25             sub search($$$) #P Return the pair that decodes t
26 5145     5145 1 2262354 {my ($n, $l, $u) = @_; # Number to decode, lower limit, upper limit
27              
28 5145         14826 for(1..4*length($n))
29 36006         919523 {my ($L, $U) = map{equation(Math::BigInt->new($_))} $l, $u;
  72012         12751026  
30              
31 36006 50       12631198 return ($l, 0) if $n == $L;
32 36006 50       947948 return ($u, 0) if $n == $U;
33              
34 36006         843066 my $m = ($l+$u) >> 1;
35              
36 36006 100       7596246 if ($l == $m)
37 5052         134241 {my $d = $n - $L;
38 5052         530893 return ($l - $d, $d);
39             }
40              
41 30954         808233 my $M = equation($m);
42 30954 100       10895285 return ($m, 0) if $M == $n;
43 30861 100       819639 ($M > $n ? $u : $l) = $m
44             }
45             }
46              
47             sub singleToPair($) # Decode a single integer into a pair of integers
48 5153     5153 1 11513 {my ($N) = @_; # Number to decode
49 5153 50       13626 $N =~ m/\A\d+\Z/s or confess "$N is not an integer";
50 5153 100       123481 return (0, 0) unless $N; # Simple case
51              
52 5152         117360 my $n = Math::BigInt->new($N);
53              
54 5152         164575 for my $x(0..4*length($N)) # Maximum number of searches required
55 41348         1019996 {my $t = Math::BigInt->new(1)<<$x;
56 41348         8806020 my $steps = equation($t);
57 41348 100       14627109 return ($t, 0) if $steps == $n;
58 41341 100       1107238 next if $steps < $n;
59 5145         129336 return search($n, Math::BigInt->new(1)<<($x-1), Math::BigInt->new(1)<<$x);
60             }
61             }
62              
63             sub pairToSingle($$) # Return the single integer representing a pair of integers
64 5153     5153 1 14126 {my ($I, $J) = @_; # First number of pair to encode, second number of pair to encode
65 5153         18005 my $i = Math::BigInt->new($I);
66 5153         187926 my $j = Math::BigInt->new($J);
67 5153         158819 my $d = $i + $j;
68 5153         357116 ($d * $d + $d) / 2 + $j
69             }
70              
71             #-------------------------------------------------------------------------------
72             # Export
73             #---------------------------------------/lib/Encode/Positive/Pairs.pm ----------------------------------------
74              
75             require Exporter;
76              
77 1     1   18008 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
  1         2  
  1         179  
78              
79             @ISA = qw(Exporter);
80             @EXPORT = qw();
81             @EXPORT_OK = qw();
82             %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]);
83              
84             # podDocumentation
85              
86             =pod
87              
88             =encoding utf-8
89              
90             =head1 Name
91              
92             Encode::Positive::Pairs - encode pairs of positive integers as a single integer and vice versa
93              
94             =head1 Synopsis
95              
96             use Encode::Positive::Pairs;
97              
98             my ($i, $j) = Encode::Positive::Pairs::singleToPair(4);
99             ok $i == 1 && $j == 1;
100              
101             ok 4 == Encode::Positive::Pairs::pairToSingle(1, 1);
102              
103             Larger numbers are automatically supported via L:
104              
105             my $n = '1'.('0'x121).'1';
106             my ($i, $j) = Encode::Positive::Pairs::singleToPair($n);
107              
108             ok $i == "1698366900312561357458283662619176178439283700581622961703001";
109             ok $j == "12443768723418389130558603579477804607257435053187857770063795";
110              
111             ok $n == Encode::Positive::Pairs::pairToSingle($i, $j);
112              
113              
114             =head1 Description
115              
116             =head2 Convert
117              
118             Encode pairs of positive integers as a single integer and vice-versa
119              
120             =head3 equation
121              
122             The sum of the numbers from 1 to a specified number
123              
124             1 $t The number of leading integers to sum
125              
126             This is a private method.
127              
128              
129             =head3 search
130              
131             Return the pair that decodes t
132              
133             1 $n Number to decode
134             2 $l Lower limit
135             3 $u Upper limit
136              
137             This is a private method.
138              
139              
140             =head3 singleToPair
141              
142             Decode a single integer into a pair of integers
143              
144             1 $N Number to decode
145              
146             =head3 pairToSingle
147              
148             Return the single integer representing a pair of integers
149              
150             1 $I First number of pair to encode
151             2 $J Second number of pair to encode
152              
153              
154             =head1 Index
155              
156              
157             L
158              
159             L
160              
161             L
162              
163             L
164              
165             =head1 Installation
166              
167             This module is written in 100% Pure Perl and, thus, it is easy to read, use,
168             modify and install.
169              
170             Standard Module::Build process for building and installing modules:
171              
172             perl Build.PL
173             ./Build
174             ./Build test
175             ./Build install
176              
177             =head1 Author
178              
179             L
180              
181             L
182              
183             =head1 Copyright
184              
185             Copyright (c) 2016-2017 Philip R Brenan.
186              
187             This module is free software. It may be used, redistributed and/or modified
188             under the same terms as Perl itself.
189              
190             =cut
191              
192              
193             # Tests and documentation
194              
195             sub test
196 1     1 0 8 {my $p = __PACKAGE__;
197 1 50       47 return if eval "eof(${p}::DATA)";
198 1         40 my $s = eval "join('', <${p}::DATA>)";
199 1 50       4 $@ and die $@;
200 1     1   351 eval $s;
  1         43183  
  1         11  
  1         49  
201 1 50       1101 $@ and die $@;
202             }
203              
204             test unless caller;
205              
206             1;
207             # podDocumentation
208             __DATA__