divert(-1)

# Copyright 2013 Kevin Ryde

# This file is part of Math-PlanePath.
#
# Math-PlanePath is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-PlanePath is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.


# Usage: m4 dragon.m4
#
# This is a bit of fun generating the dragon curve with the predicate
# algorithms of xy_is_visited() from DragonMidpoint and DragonCurve.  The
# output is generated row by row and and column by column with no image
# array or storage.
#
# The macros which return a pair of values x,y expand to an unquoted 123,456
# which is suitable as arguments to a further macro.  The quoting is slack
# because the values are always integers and so won't suffer unwanted macro
# expansion.

#                0,1                 Vertex and segment x,y numbering.
#                 |
#                 |                  Segments are numbered as if a
#                 |s=0,1             square grid turned anti-clockwise
#                 |                  by 45 degrees.
#                 |
#  -1,0 -------- 0,0 -------- 1,0    vertex_to_seg_east(x,y) returns
#        s=-1,1   |   s=0,0          the segment x,y to the East,
#                 |                  so vertex_to_seg_east(0,0) is 0,0
#                 |
#                 |s=-1,0            vertex_to_seg_west(x,y) returns
#                 |                  the segment x,y to the West,
#                0,-1                so vertex_to_seg_west(0,0) is -1,1
#
define(`vertex_to_seg_east',  `eval($1 + $2),     eval($2 - $1)')
define(`vertex_to_seg_west',  `eval($1 + $2 - 1), eval($2 - $1 + 1)')
define(`vertex_to_seg_south', `eval($1 + $2 - 1), eval($2 - $1)')

# Some past BSD m4 didn't have "&" operator, so mod2(n) using % instead.
# mod2() returns 0,1 even if "%" gives -1 for negative odds.
#
define(`mod2', `ifelse(eval($1 % 2),0,0,1)')

# seg_to_even(x,y) returns x,y moved to an "even" position by subtracting an
# offset in a way which suits the segment predicate test.
#
# seg_offset_y(x,y) is a repeating pattern
#
#    | 1,1,0,0
#    | 1,1,0,0
#    | 0,0,1,1
#    | 0,0,1,1
#    +---------
#
# seg_offset_x(x,y) is the same but offset by 1 in x,y
#
#    | 0,1,1,0
#    | 1,0,0,1
#    | 1,0,0,1
#    | 0,1,1,0
#    +---------
#
# Incidentally these offset values also give n which is the segment number
# along the curve.  "x_offset XOR y_offset" is 0,1 and is a bit of n from
# low to high.
#
define(`seg_offset_y', `mod2(eval(($1 >> 1) + ($2 >> 1)))')
define(`seg_offset_x', `seg_offset_y(eval($1+1), eval($2+1))')
define(`seg_to_even', `eval($1 - seg_offset_x($1,$2)),
                       eval($2 - seg_offset_y($1,$2))');

# xy_div_iplus1(x,y) returns x,y divided by complex number i+1.
# So (x+i*y)/(i+1) which means newx = (x+y)/2, newy = (y-x)/2.
# Must have x,y "even", meaning x+y even, so newx and newy are integers.
#
define(`xy_div_iplus1', `eval(($1 + $2)/2), eval(($2 - $1)/2)')

# seg_is_final(x,y) returns 1 if x,y is one of the final four points.
# On these four points xy_div_iplus1(seg_to_even(x,y)) returns x,y
# unchanged, so the seg_pred() recursion does not reduce any further.
#
#       ..   |  ..
#      final | final      y=+1
#      final | final      y=0
#     -------+--------
#       ..   |  ..
#       x=-1    x=0
#
define(`seg_is_final', `eval(($1==-1 || $1==0) && ($2==1 || $2==0))')

# seg_pred(x,y) returns 1 if segment x,y is on the dragon curve.
# If the final point reached is 0,0 then the original x,y was on the curve.
# (If a different final point then x,y was one of four rotated copies of the
# curve.)
#
define(`seg_pred', `ifelse(seg_is_final($1,$2), 1,
                           `eval($1==0 && $2==0)',
                           `seg_pred(xy_div_iplus1(seg_to_even($1,$2)))')')

# vertex_pred(x,y) returns 1 if point x,y is on the dragon curve.
# The curve always turns left or right at a vertex, it never crosses itself,
# so if a vertex is visited then either the segment to the east or to the
# west must have been traversed.  Prefer ifelse() for the two checks since
# eval() || operator is not a short-circuit.
#
define(`vertex_pred', `ifelse(seg_pred(vertex_to_seg_east($1,$2)),1,1,
                             `seg_pred(vertex_to_seg_west($1,$2))')')

# forloop(varname, start,end, body)
# Expand body with varname successively define()ed to integers "start" to
# "end" inclusive.  "start" to "end" can go either increasing or decreasing.
#
define(`forloop', `define(`$1',$2)$4`'dnl
ifelse($2,$3,,`forloop(`$1',eval($2 + 2*($2 < $3) - 1), $3, `$4')')')

#----------------------------------------------------------------------------

# dragon01(xmin,xmax, ymin,ymax) prints an array of 0s and 1s which are the
# vertex_pred() values.  `y' runs from ymax down to ymin so that y
# coordinate increases up the screen.
#
define(`dragon01',
`forloop(`y',$4,$3, `forloop(`x',$1,$2, `vertex_pred(x,y)')
')')

# dragon_ascii(xmin,xmax, ymin,ymax) prints an ascii art dragon curve.
# Each y value results in two output lines.  The first has "+" vertices and
# "--" horizontals.  The second has "|" verticals.
#
define(`dragon_ascii',
`forloop(`y',$4,$3,
`forloop(`x',$1,$2,
`ifelse(vertex_pred(x,y),1, `+', ` ')dnl
ifelse(seg_pred(vertex_to_seg_east(x,y)), 1, `--', `  ')')
forloop(`x',$1,$2,
`ifelse(seg_pred(vertex_to_seg_south(x,y)), 1, `|  ', `   ')')
')')

#--------------------------------------------------------------------------
divert`'dnl

# 0s and 1s directly from vertex_pred().
#
dragon01(-7,23,      dnl X range
         -11,10)     dnl Y range

# ASCII art lines.
#
dragon_ascii(-6,5,      dnl X range
             -10,2)     dnl Y range