File Coverage

blib/lib/Math/PlanePath/CellularRule57.pm
Criterion Covered Total %
statement 141 154 91.5
branch 70 80 87.5
condition 17 18 94.4
subroutine 20 23 86.9
pod 6 6 100.0
total 254 281 90.3


line stmt bran cond sub pod time code
1             # Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
2              
3             # This file is part of Math-PlanePath.
4             #
5             # Math-PlanePath is free software; you can redistribute it and/or modify
6             # it under the terms of the GNU General Public License as published by the
7             # Free Software Foundation; either version 3, or (at your option) any later
8             # version.
9             #
10             # Math-PlanePath is distributed in the hope that it will be useful, but
11             # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12             # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13             # for more details.
14             #
15             # You should have received a copy of the GNU General Public License along
16             # with Math-PlanePath. If not, see .
17              
18              
19              
20             package Math::PlanePath::CellularRule57;
21 1     1   30 use 5.004;
  1         4  
22 1     1   5 use strict;
  1         22  
  1         48  
23              
24 1     1   6 use vars '$VERSION', '@ISA';
  1         2  
  1         91  
25             $VERSION = 127;
26 1     1   7 use Math::PlanePath;
  1         3  
  1         49  
27             @ISA = ('Math::PlanePath');
28             *_sqrtint = \&Math::PlanePath::_sqrtint;
29              
30             use Math::PlanePath::Base::Generic
31 1     1   5 'round_nearest';
  1         3  
  1         67  
32              
33 1     1   8 use Math::PlanePath::CellularRule54;
  1         3  
  1         41  
34             *_rect_for_V = \&Math::PlanePath::CellularRule54::_rect_for_V;
35              
36             # uncomment this to run the ### lines
37             #use Smart::Comments;
38              
39              
40 1     1   5 use constant class_y_negative => 0;
  1         3  
  1         88  
41 1     1   6 use constant n_frac_discontinuity => .5;
  1         3  
  1         85  
42              
43 1         131 use constant parameter_info_array =>
44             [ { name => 'mirror',
45             display => 'Mirror',
46             type => 'boolean',
47             default => 0,
48             description => 'Mirror to "rule 99" instead.',
49             },
50             Math::PlanePath::Base::Generic::parameter_info_nstart1(),
51 1     1   6 ];
  1         3  
52              
53             sub x_negative_at_n {
54 0     0 1 0 my ($self) = @_;
55 0 0       0 return $self->n_start + ($self->{'mirror'} ? 1 : 2);
56             }
57 1     1   9 use constant sumxy_minimum => 0; # triangular X>=-Y so X+Y>=0
  1         1  
  1         48  
58 1     1   6 use constant diffxy_maximum => 0; # triangular X<=Y so X-Y<=0
  1         4  
  1         61  
59 1     1   7 use constant dx_maximum => 3;
  1         2  
  1         67  
60 1     1   6 use constant dy_minimum => 0;
  1         2  
  1         51  
61 1     1   5 use constant dy_maximum => 1;
  1         2  
  1         148  
62              
63             sub absdx_minimum {
64 0     0 1 0 my ($self) = @_;
65 0 0       0 return ($self->{'mirror'} ? 0 : 1);
66             }
67 1     1   8 use constant dsumxy_maximum => 3; # straight East dX=+3
  1         1  
  1         48  
68 1     1   13 use constant ddiffxy_maximum => 3; # straight East dX=+3
  1         2  
  1         68  
69 1     1   6 use constant dir_maximum_dxdy => (-1,0); # supremum, West and dY=+1 up
  1         2  
  1         1111  
70              
71              
72             #------------------------------------------------------------------------------
73              
74             sub new {
75 2     2 1 11 my $self = shift->SUPER::new (@_);
76 2 50       12 if (! defined $self->{'n_start'}) {
77 0         0 $self->{'n_start'} = $self->default_n_start;
78             }
79 2         9 return $self;
80             }
81              
82             # left
83             # even y=3 5
84             # 5 12
85             # 7 23
86             # 9 38
87             # [1,2,3,4], [5,12,23,38]
88             #
89             # N = (2 d^2 + d + 2)
90             # = (2*$d**2 + $d + 2)
91             # = ((2*$d + 1)*$d + 2)
92             # d = -1/4 + sqrt(1/2 * $n + -15/16)
93             # = (-1 + 4*sqrt(1/2 * $n + -15/16)) / 4
94             # = (sqrt(8*$n-15)-1)/4
95             # with Y=2*d+1
96              
97             # row 19, d=9
98             # N=173 to N=181 is 9 cells rem=0..8 is d-1
99             # 1/3 section 3 cells rem=0,1,2 floor((d-1)/3)
100             # 2/3 section 6 cells
101             # right solid N=191 to N=200 is 10 of is rem
102             #
103             # row 21, d=10
104             # 1/3 section 4 cells rem=0,1,2,3 floor((d-1)/3)
105             # 2/3 section 6 cells
106             #
107             # row 23, d=11
108             # 1/3 section 4 cells rem=0,1,2,3 floor((d-1)/3)
109             # 2/3 section 7 cells
110             #
111             # row 25, d=12
112             # 2/3 section 8 cells
113             #
114             # row 27, d=13
115             # 2/3 section 8 cells
116             #
117             # row 29, d=14
118             # 2/3 section 9 cells floor(2d/3)
119             #
120             # row 31, d=15
121             # 2/3 section 10 cells floor(2d/3)
122             #
123             #
124             # row 18 d=8
125             # odd 1/3 section 4 cells (d+4)/3
126             #
127             # row 20 d=9
128             # odd 1/3 section 4 cells
129             #
130             # row 22 d=10
131             # odd 1/3 section 4 cells
132             #
133             # row 23 d=11
134             # odd 1/3 section 5 cells
135              
136              
137             sub n_to_xy {
138 51     51 1 387 my ($self, $n) = @_;
139             ### CellularRule57 n_to_xy(): $n
140              
141 51         81 $n = $n - $self->{'n_start'} + 1; # to N=1 basis, and warn if $n undef
142 51         75 my $frac;
143             {
144 51         64 my $int = int($n);
  51         68  
145 51         81 $frac = $n - $int;
146 51         58 $n = $int; # BigFloat int() gives BigInt, use that
147 51 50       107 if (2*$frac >= 1) {
148 0         0 $frac -= 1;
149 0         0 $n += 1;
150             }
151             # -0.5 <= $frac < 0.5
152             ### assert: 2*$frac >= -1
153             ### assert: 2*$frac < 1
154             }
155              
156 51 100       97 if ($n <= 1) {
157 10 100       22 if ($n == 1) {
158 4         14 return (0,0);
159             } else {
160 6         13 return;
161             }
162             }
163              
164             # d is the two-row group number, y=2*d+1, where n belongs
165             #
166 41         92 my $d = int( (_sqrtint(8*$n-15)-1)/4 );
167 41         76 $n -= ((2*$d + 1)*$d + 2); # remainder
168             ### $d
169             ### remainder: $n
170              
171 41 100       79 if ($self->{'mirror'}) {
172 20 100       41 if ($n <= $d) {
173             ### right solid: $n
174 7         20 return ($frac + $n - 2*$d - 1,
175             2*$d+1);
176             }
177 13         20 $n -= $d+1;
178              
179 13 100       31 if ($n < int(2*$d/3)) {
180             ### right 2/3: $n
181 1         5 return ($frac + int(3*$n/2) - $d + 1,
182             2*$d+1);
183             }
184 12         19 $n -= int(2*$d/3);
185              
186 12 100       27 if ($n < int(($d+2)/3)) {
187             ### left 1/3: $n
188 2         8 return ($frac + 3*$n + ((2+$d)%3),
189             2*$d+1);
190             }
191 10         20 $n -= int(($d+2)/3);
192              
193 10 100       19 if ($n < $d) {
194             ### left solid: $n
195 3         8 return ($frac + $n + $d+2,
196             2*$d+1);
197             }
198 7         10 $n -= $d;
199              
200 7 100       28 if ($n < int((2*$d+5)/3)) {
201             ### odd 2/3: $n
202 5         21 return ($frac + int((3*$n)/2) - $d + - 1,
203             2*$d+2);
204             }
205 2         6 $n -= int((2*$d+5)/3);
206              
207             ### odd 1/3: $n
208 2         7 return ($frac + 3*$n + ($d%3) + 1,
209             2*$d+2);
210              
211             } else {
212 21 100       57 if ($n < $d) {
213             ### left solid: $n
214 3         9 return ($frac + $n - 2*$d - 1,
215             2*$d+1);
216             }
217 18         27 $n -= $d;
218              
219 18 100       67 if ($n < int(($d+2)/3)) {
220             ### left 1/3: $n
221 2         6 return ($frac + 3*$n - $d + 1,
222             2*$d+1);
223             }
224 16         26 $n -= int(($d+2)/3);
225              
226 16 100       37 if ($n < int(2*$d/3)) {
227             ### right 2/3: $n
228 1         7 return ($frac + $n + int(($n+(-$d%3))/2) + 1,
229             2*$d+1);
230             }
231 15         29 $n -= int(2*$d/3);
232              
233 15 100       25 if ($n <= $d) {
234             ### right solid: $n
235 7         19 return ($frac + $d + $n + 1,
236             2*$d+1);
237             }
238 8         16 $n -= $d+1;
239              
240 8 100       20 if ($n < int(($d+4)/3)) {
241             ### odd 1/3: $n
242 5         14 return ($frac + 3*$n - $d - 1,
243             2*$d+2);
244             }
245 3         7 $n -= int(($d+4)/3);
246              
247             ### odd 2/3: $n
248 3         11 return ($frac + $n + int(($n+((1-$d)%3))/2) + 1,
249             2*$d+2);
250             }
251             }
252              
253             sub xy_to_n {
254 992     992 1 4749 my ($self, $x, $y) = @_;
255 992         1796 $x = round_nearest ($x);
256 992         1844 $y = round_nearest ($y);
257             ### CellularRule57 xy_to_n(): "$x,$y"
258              
259 992 100 66     3656 if ($y < 0
      100        
260             || $x < -$y
261             || $x > $y) {
262             ### outside pyramid region ...
263 480         898 return undef;
264             }
265              
266 512 100       937 if ($self->{'mirror'}) {
267             # mirrored, rule 99
268              
269 256 100       429 if ($y % 2) {
270 136         228 my $d = ($y+1)/2;
271             ### odd row, solids, d: $d
272              
273 136 100       281 if ($x < -$d) {
274 28         85 return ($y+1)*$y/2 + $x + 1 + $self->{'n_start'};
275             }
276 108 100       216 if ($x < 0) {
    100          
277             ### mirror left 2 of 3 ...
278 36 100       114 if (($x += $d+2) % 3) {
279 24         73 return ($y+1)*$y/2 + $x-int($x/3) - $d + $self->{'n_start'} - 1;
280             }
281             } elsif ($x > $d) {
282 28         78 return ($y+1)*$y/2 + $x - $d + $self->{'n_start'};
283             } else {
284             ### mirror right 1 of 3 ...
285 44         53 $x += 2-$d;
286 44 100       88 unless ($x % 3) {
287 12         37 return ($y+1)*$y/2 + $x/3 + $self->{'n_start'};
288             }
289             }
290              
291             } else {
292             ### even row, sparse ...
293 120         189 my $d = $y/2;
294 120 100       183 if ($x >= 0) {
295             ### mirror sparse right 1 of 3 ...
296 64 100 100     191 if ($x <= $d # only to half way
297             && (($x -= $d) % 3) == 0) {
298 15         43 return ($y+1)*$y/2 + $x/3 + $self->{'n_start'};
299             }
300             } else { # $x < 0
301             ### mirror sparse left 2 of 3 ...
302 56 100 100     176 if ($x >= -$d # only to half way
303             && (($x += $d+1) % 3)) {
304 21         68 return ($y+1)*$y/2 + $x-int($x/3) - $d + $self->{'n_start'} - 1;
305             }
306             }
307             }
308             } else {
309             # unmirrored, rule 57
310              
311 256 100       441 if ($y % 2) {
312 136         218 my $d = ($y+1)/2;
313             ### odd row, solids, d: $d
314              
315 136 100       311 if ($x <= -$d) {
    100          
    100          
316             ### solid left ...
317 36 100       70 if ($x < -$d) { # always skip the -$d cell
318 28         78 return ($y+1)*$y/2 + $x + 1 + $self->{'n_start'};
319             }
320             } elsif ($x <= 0) {
321             ### 1 of 3 ...
322 36 100       76 unless (($x += $d+1) % 3) {
323 12         35 return ($y+1)*$y/2 + $x/3 - $d + $self->{'n_start'};
324             }
325             } elsif ($x >= $d) {
326             ### solid right ...
327 36         130 return ($y+1)*$y/2 + $x - $d + $self->{'n_start'};
328             } else {
329             ### 2 of 3 ...
330 28         50 $x += 1-$d;
331 28 100       47 if ($x % 3) {
332 16         48 return ($y+1)*$y/2 + $x-int($x/3) + $self->{'n_start'};
333             }
334             }
335              
336             } else {
337             ### even row, sparse ...
338              
339 120         177 my $d = $y/2;
340 120 100       236 if ($x > 0) {
341             ### right 2 of 3 ...
342 56 100 100     157 if ($x <= $d # goes to half way only
343             && (($x -= $d+1) % 3)) {
344 21         66 return ($y+1)*$y/2 + $x-int($x/3) + 1 + $self->{'n_start'};
345             }
346             } else { # $x <= 0
347             ### left 1 of 3 ...
348 64 100 100     199 if (($x += $d) >= 0 # goes to half way only
349             && ! ($x % 3)) {
350 15         45 return ($y+1)*$y/2 + $x/3 - $d + $self->{'n_start'};
351             }
352             }
353             }
354             }
355 256         517 return undef;
356             }
357              
358             # left edge ((2*$d + 1)*$d + 2)
359             # where y=2*d+1
360             # d=floor((y-1)/2)
361             # left N = (2*floor((y-1)/2) + 1)*floor((y-1)/2) + 2
362             # = (yodd + 1)*yodd/2 + 2
363              
364              
365             # not exact
366             sub rect_to_n_range {
367 0     0 1   my ($self, $x1,$y1, $x2,$y2) = @_;
368             ### CellularRule57 rect_to_n_range(): "$x1,$y1, $x2,$y2"
369              
370 0 0         ($x1,$y1, $x2,$y2) = _rect_for_V ($x1,$y1, $x2,$y2)
371             or return (1,0); # rect outside pyramid
372              
373 0           my $zero = ($x1 * 0 * $y1 * $x2 * $y2); # inherit bignum
374              
375 0           $y1 -= ! ($y1 % 2);
376 0           $y2 -= ! ($y2 % 2);
377             return ($zero + ($y1 < 1
378             ? $self->{'n_start'}
379             : ($y1-1)*$y1/2 + 1 + $self->{'n_start'}),
380 0 0         $zero + ($y2+2)*($y2+1)/2 + $self->{'n_start'});
381             }
382              
383             1;
384             __END__