;; Copyright 2012, 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: M-x load-file dragon-curve.el
;;
;; And thereafter M-x dragon-picture.
;;

(unless (fboundp 'ignore-errors)
  (require 'cl)) ;; Emacs 22 and earlier `ignore-errors'

(defun dragon-ensure-line-above ()
  "If point is in the first line of the buffer then insert a new line above."
  (when (= (line-beginning-position) (point-min))
    (save-excursion
      (goto-char (point-min))
      (insert "\n"))))

(defun dragon-ensure-column-left ()
  "If point is in the first column then insert a new column to the left.
This is designed for use in `picture-mode'."
  (when (zerop (current-column))
    (save-excursion
      (goto-char (point-min))
      (insert " ")
      (while (= 0 (forward-line 1))
        (insert " ")))
    (picture-forward-column 1)))

(defun dragon-insert-char (char len)
  "Insert CHAR repeated LEN many times.
After each CHAR move point in the current `picture-mode'
direction (per `picture-set-motion' etc).

This is the same as `picture-insert' except in column 0 or row 0
a new row or column is inserted to make room, with existing
buffer contents shifted down or right."

  (dotimes (i len)
    (dragon-ensure-line-above)
    (dragon-ensure-column-left)
    (picture-insert char 1)))

(defun dragon-bit-above-lowest-0bit (n)
  "Return the bit above the lowest 0-bit in N.
For example N=43 binary \"101011\" has lowest 0-bit at \"...0..\"
and the bit above that is \"..1...\" so return 8 which is that
bit."
  (logand n (1+ (logxor n (1+ n)))))

(defun dragon-next-turn-right-p (n)
  "Return non-nil if the dragon curve should turn right after segment N.
Segments are numbered from N=0 for the first, so calling with N=0
is whether to turn right at the end of that N=0 segment."
  (zerop (dragon-bit-above-lowest-0bit n)))

(defun dragon-picture (len step)
  "Draw the dragon curve in a *dragon* buffer.
LEN is the number of segments of the curve to draw.
STEP is the length of each segment, in characters.

Any LEN can be given but a power-of-2 such as 256 shows the
self-similar nature of the curve.

If STEP >= 2 then the segments are lines using \"-\" or \"|\"
characters (`picture-rectangle-h' and `picture-rectangle-v').
If STEP=1 then only \"+\" corners.

There's a `sit-for' delay in the drawing loop to draw the curve
progressively on screen."

  (interactive (list (read-number "Length of curve " 256)
                     (read-number "Each step size " 3)))
  (unless (>= step 1)
    (error "Step length must be >= 1"))

  (switch-to-buffer "*dragon*")
  (erase-buffer)
  (setq truncate-lines t)
  (ignore-errors ;; ignore error if already in picture-mode
    (picture-mode))

  (dotimes (n len)  ;; n=0 to len-1, inclusive
    (dragon-insert-char ?+ 1)  ;; corner char
    (dragon-insert-char (if (zerop picture-vertical-step)
                                    picture-rectangle-h picture-rectangle-v)
                                (1- step))  ;; line chars

    (if (dragon-next-turn-right-p n)
        ;; turn right
        (picture-set-motion (- picture-horizontal-step) picture-vertical-step)
      ;; turn left
      (picture-set-motion picture-horizontal-step (- picture-vertical-step)))

    ;; delay to display the drawing progressively
    (sit-for .01))

  (picture-insert ?+ 1) ;; endpoint
  (picture-mode-exit)
  (goto-char (point-min)))

(dragon-picture 128 2)