 Math::PlanePath::CornerReplicate(3) replicating U parts

## SYNOPSIS

use Math::PlanePath::CornerReplicate;
my \$path = Math::PlanePath::CornerReplicate->new;
my (\$x, \$y) = \$path->n_to_xy (123);

## DESCRIPTION

This path is a self-similar replicating corner fill with 2x2 blocks. It's sometimes called a ``U order'' since the base N=0 to N=3 is like a ``U'' (sideways).

```     7  | 63--62  59--58  47--46  43--42
|      |       |       |       |
6  | 60--61  56--57  44--45  40--41
|          |               |
5  | 51--50  55--54  35--34  39--38
|      |       |       |       |
4  | 48--49  52--53  32--33  36--37
|                  |
3  | 15--14  11--10  31--30  27--26
|      |       |       |       |
2  | 12--13   8-- 9  28--29  24--25
|          |               |
1  |  3-- 2   7-- 6  19--18  23--22
|      |       |       |       |
Y=0 |  0-- 1   4-- 5  16--17  20--21
+--------------------------------
X=0  1   2   3   4   5   6   7
```

The pattern is the initial N=0 to N=3 section,

```    +-------+-------+
|       |       |
|   3   |   2   |
|       |       |
+-------+-------+
|       |       |
|   0   |   1   |
|       |       |
+-------+-------+
```

It repeats as 2x2 blocks arranged in the same pattern, then 4x4 blocks, etc. There's no rotations or reflections within sub-parts.

X axis N=0,1,4,5,16,17,etc is all the integers which use only digits 0 and 1 in base 4. For example N=17 is 101 in base 4.

Y axis N=0,3,12,15,48,etc is all the integers which use only digits 0 and 3 in base 4. For example N=51 is 303 in base 4.

The X=Y diagonal N=0,2,8,10,32,34,etc is all the integers which use only digits 0 and 2 in base 4.

The X axis is the same as the "ZOrderCurve". The Y axis here is the X=Y diagonal of the "ZOrderCurve", and conversely the X=Y diagonal here is the Y axis of the "ZOrderCurve".

The N value at a given X,Y is converted to or from the "ZOrderCurve" by transforming base-4 digit values 2<->3. This can be done by a bitwise ``X xor Y''. When Y has a 1-bit the xor swaps 2<->3 in N.

```    ZOrder X  = CRep X xor CRep Y
ZOrder Y  = CRep Y
CRep X  = ZOrder X xor ZOrder Y
CRep Y  = ZOrder Y
```

## Level Ranges

A given replication extends to

```    Nlevel = 4^level - 1
0 <= X < 2^level
0 <= Y < 2^level
```

## Hamming Distance

The Hamming distance between two integers X and Y is the number of bit positions where the two values differ when written in binary. In this corner replicate each bit-pair of N becomes a bit of X and a bit of Y,

```       N      X   Y
------   --- ---
0 = 00    0   0
1 = 01    1   0     <- difference 1 bit
2 = 10    1   1
3 = 11    0   1     <- difference 1 bit
```

So the Hamming distance is the number of base4 bit-pairs of N which are 01 or 11. Counting bit positions from 0 for the least significant bit then this is the 1-bits in even positions,

```    HammingDist(X,Y) = count 1-bits at even bit positions in N
```

## FUNCTIONS

See ``FUNCTIONS'' in Math::PlanePath for behaviour common to all path classes.
"\$path = Math::PlanePath::CornerReplicate->new ()"
Create and return a new path object.
"(\$x,\$y) = \$path->n_to_xy (\$n)"
Return the X,Y coordinates of point number \$n on the path. Points begin at 0 and if "\$n < 0" then the return is an empty list.
"(\$n_lo, \$n_hi) = \$path->rect_to_n_range (\$x1,\$y1, \$x2,\$y2)"
The returned range is exact, meaning \$n_lo and \$n_hi are the smallest and biggest in the rectangle.

## Level Methods

"(\$n_lo, \$n_hi) = \$path->level_to_n_range(\$level)"
Return "(0, 4**\$level - 1)".

## N to dX,dY

The change dX,dY is given by N in base 4 count trailing 3s and the digit above those trailing 3s.

```    N = ...[d]333...333      base 4
\--exp--/
```

When N to N+1 crosses between 4^k blocks it goes as follows. Within a block the pattern is the same, since there's no rotations or transposes etc.

```    N, N+1        X      Y        dX       dY       dSum     dDiffXY
--------   -----  -------   -----  --------    ------    -------
033..33       0    2^k-1      2^k  -(2^k-1)        +1    2*2^k-1
100..00      2^k       0
133..33      2^k    2^k-1       0       +1         +1       -1
200..00      2^k    2^k
133..33      2^k  2*2^k-1    -2^k     1-2^k   -(2^k-1)      -1
200..00       0     2^k
133..33       0   2*2^k-1   2*2^k -(2*2^k-1)       +1    4*2^k-1
200..00    2*2^k      0
```

It can be noted dSum=dX+dY the change in X+Y is at most +1, taking values 1, -1, -3, -7, -15, etc. The crossing from block 2 to 3 drops back, such as at N=47=``233'' to N=48=``300''. Everywhere else it advances by +1 anti-diagonal.

The difference dDiffXY=dX-dY the change in X-Y decreases at most -1, taking similar values -1, 1, 3, 7, 15, etc but in a different order to dSum.

## OEIS

This path is in Sloane's Online Encyclopedia of Integer Sequences as

<http://oeis.org/A000695> (etc)

```    A059906    Y coordinate
A059905    X xor Y, being ZOrderCurve X
A139351    HammingDist(X,Y), count 1-bits at even positions in N
A000695    N on X axis, base 4 digits 0,1 only
A001196    N on Y axis, base 4 digits 0,3 only
A062880    N on diagonal, base 4 digits 0,2 only
A163241    permutation base-4 flip 2<->3,
converts N to ZOrderCurve N, and back
A048647    permutation N at transpose Y,X
base4 digits 1<->3
```

<http://user42.tuxfamily.org/math-planepath/index.html>