#!/usr/bin/ruby

require 'io/console'

# Flip points across the line Y=X.
#
#   B C      D C
#   A D  ->  A B
#
#  f g J K      p m L K
#  e h I L      o n I J
#  D C n m  ->  B C h g
#  A B o p      A D e f
def d_flip(points)
   points.map{|x, y| [y, x]}
end

# Flip points across the line Y=-X.
#
#  B C      B A
#  A D  ->  C D
#
#  f g J K      f e D A
#  e h I L      g h C B
#  D C n m  ->  J I n o
#  A B o p      K L m p
def d2_flip(points)
   points.map{|x, y| [-y, -x]}
end

# Rotate points 90 degrees counterclockwise about (0, 0)
#
#  B C      C D
#  A D  ->  B A
#
#  f g J K      K L m p
#  e h I L      J I n o
#  D C n m  ->  g h C B
#  A B o p      f e D A
def rotate(points)
   points.map{|x, y| [-y, x]}
end

# Shift points by some offset.
def shift(points, dx, dy)
   points.map{|x, y| [x + dx, y + dy]}
end

# Add list of points to table, preserving existing table entries.
def add_points(table, width, height, points)
   table[width] ||= {}
   table[width][height] ||= points
end

# Generate rectangles of the same height as a particular unit rectangle.
def add_rectangles(table, width, r_width, r_height)
   w = r_width
   while w <= width * 2
      add_points(table, w + r_width, r_height,
                 table[w][r_height] + shift(table[r_width][r_height], w, 0))
      w += r_width
   end
end

# Generate table of space filling curves.
#
# Returns a table indexed by [width][height] with list of points as values.
# All point list start in lower left corner and end in lower right corner.
def generate_table(width, height)
   if width < height
      raise "Expected landscape orientation"
   end

   # Seed table with all rectangles of height 1.
   table = {}
   (1 .. width * 2).each{|w|
      add_points(table, w, 1, (0 .. w - 1).to_a.map{|x| [x, 0]})
   }

   # Expand table.
   s = 1
   while s <= height
      # Generate all rectangles from size (s * 2, s) up to (width, s * 2).
      (1 .. s).each{|h|
         # Generate rectangle of size (s * 2, s + h), using the
         # following pattern:
         # +-----------+
         # |     R     |
         # +-----+-----+
         # |     |     |
         # |  S' |  S" |
         # |     |     |
         # +-----+-----+
         # * S' is a square of size "s" starting in lower left corner
         #   and ending in upper left corner.
         #
         # * R is a rectangle starting in lower left corner and ending
         #   in lower right corner.
         #
         # * S" is a square starting in upper right corner and ending
         #   in lower right corner.
         #
         # When height of R is "s", this essentially generates a
         # Hilbert curve of size 2*s.
         add_points(table, s * 2, s + h,
                    d_flip(table[s][s]) +
                    shift(table[s * 2][h], 0, s) +
                    shift(d2_flip(table[s][s]), s * 2 - 1, s - 1))

         # Copy rectangles to the right.
         add_rectangles(table, width, s * 2, s + h)
      }

      s *= 2
   end

   # Generate additional rectangles to fill smaller gaps.
   s = height
   while s >= 2
      p = height - s
      while p >= 1
         q = s + p
         while q >= 1
            w = s + q
            h = s + p
            if !table[w][h] && table[s][s] && table[s + q][p] && table[s][q]
               # Generate rectangles using the following pattern:
               # +--------+
               # |   P    |
               # +-----+--+
               # |     |  |
               # |  S' |Q |
               # |     |  |
               # +-----+--+
               # * S' is a square of size "s" starting in lower left
               #   corner and ending in upper left corner.
               #
               # * P is a rectangle of width "s+q" and height "p" starting
               #   lower left corner and ending in lower right corner.
               #
               # * Q is a rectangle of width "q" and height "s" starting
               #   upper right corner and ending in lower right corner.
               add_points(table, w, h,
                          d_flip(table[s][s]) +
                          shift(table[w][p], 0, s) +
                          shift(d2_flip(table[s][q]), w - 1, s - 1))

               # Copy rectangles to the right.
               add_rectangles(table, width, w, h)
            end
            q -= 1
         end
         p -= 1
      end
      s -= 1
   end
   return table
end

# Given a generated table of point lists, recursively fill rectangle.
#
# This function is needed because generate_table isn't guaranteed to
# cover the expected size.  This function fills those gaps by relaxing
# the constraint that paths have to end in lower right corner.
def recursive_fill(table, width, height)
   # Degenerate cases from recursive calls.
   if width == 0 || height == 0
      return []
   end

   # Try dividing rectangle into left and right halves.
   # +-------+---+
   # |   L   | R |
   # +-------+---+
   w = width
   while w >= 1
      if table[w] && table[w][height]
         return table[w][height] +
                shift(d_flip(recursive_fill(table, height, width - w)), w, 0)
      end
      w -= 1
   end

   # Don't have any rectangle of the right height, try shaving off the
   # bottom edge.
   return table[width][1] +
          shift(rotate(recursive_fill(table, height - 1, width)), width - 1, 1)
end

# Build curve that fills a particular rectangular area.
def fill_rectangle(width, height)
   if width < height
      return d_flip(fill_rectangle(height, width))
   end
   return recursive_fill(generate_table(width, height), width, height)
end

# Scale a list of points by 2.
def scale2x(points)
   points.map{|x, y| [2 * x, 2 * y]}
end

# Return pixel that should be drawn at a particular point.
def pixel(x, y)
   ["M", "W"][(x + y) % 2]
end

# Optionally pause after each frame to maintain desired total runtime.
#
# The goal is to maintain total runtime, hence how delay is based on
# total elapsed time so far.  A different alternative is to try to
# maintain a constant frame rate, but that is more difficult because
# sleep isn't that precise.
def pause(start_time, frame_delay, frame_count)
   sleep [frame_delay * frame_count - (Time.now - start_time), 0].max
end

# Draw a list of line segments.
def draw(points, total_time)
   start_time = Time.now

   # Calculate frame_delay based on number of points.  Due to scale2x,
   # the number of frames will be almost exactly twice the number of
   # points, hence the 2.0 below.
   frame_delay = total_time / (points.length * 2.0)

   cx, cy = points[0]
   print pixel(cx, cy), "\e[1D"
   STDOUT.flush
   frame_count = 1
   pause(start_time, frame_delay, frame_count)

   dir_x = ["\e[1D", "", "\e[1C"]
   dir_y = ["\e[1B", "", "\e[1A"]

   points.each{|x, y|
      # Move cursor toward current point.
      #
      # (0, 0) is bottom left corner.
      while cx != x || cy != y
         dx = cx < x ? 1 : cx > x ? -1 : 0
         dy = cy < y ? 1 : cy > y ? -1 : 0
         cx += dx
         cy += dy
         print dir_x[dx + 1], dir_y[dy + 1], pixel(cx, cy), "\e[1D"
         STDOUT.flush
         frame_count += 1
         pause(start_time, frame_delay, frame_count)
      end
   }
end


start_time = Time.now
height, width = IO.console.winsize

points = scale2x(fill_rectangle(width / 2, height / 2))
width = points.map{|x, y| x}.max
height = points.map{|x, y| y}.max

# Only draw if there are enough points to draw.
if width && width > 1 && height > 1
   # Try to satisfy two timing constraints:
   # - Program takes same amount of total time regardless of terminal size.
   # - Drawing routine tries to maintain constant frame rate at each frame.
   #
   # 30.0 below is the target total time (seconds), for which we
   # subtract the time taken to generate the curve itself to get the
   # total time allocated for drawing.
   #
   # The theme is perfect fit: we want to fill the terminal perfectly
   # and we want to take exactly the same predetermined amount of time
   # to do so.
   print "\n" * height
   draw(points, 30.0 - (Time.now - start_time))

   # Return cursor to start of line, plus extra adjustment to move
   # cursor down if we ended up somewhere other than the bottom line.
   print "\n" * (points[-1][1] + 1)
end