#!/usr/bin/ruby

require 'io/console'

# {{{ Eye
CHAR_HEIGHT = 2.0
LINE_SCALE = 1 / 6.0
EYE_POSITION_SCALE = 0.7
EYE_SCALE = 0.23
EYE_HORIZONTAL_SCALE = 2.5
MOUTH_POSITION_SCALE = 1.4
MOUTH_HEIGHT_SCALE = 0.5
MOUTH_WIDTH_SCALE = 3.7
MOUTH_BAR1_SCALE = 0.35
MOUTH_BAR2_SCALE = 0.7

# Distance between two points.
def distance(ax, ay, bx, by)
   Math.hypot(ax - bx, ay - by)
end

# Approximate distance from point to ellipse.
def ellipse_distance(x, y, cx, cy, rx, ry)
   angle = 0
   min_distance = 1e99
   step = Math::PI

   # Search for closest point on ellipse.
   16.times{
      min_angle = angle
      (-1..1).each{|d|
         a = angle + d * step
         px = rx * Math.cos(a)
         py = ry * Math.sin(a)
         d = distance(x - cx, y - cy, px, py)
         if min_distance > d
            min_distance = d
            min_angle = a
         end
      }
      angle = min_angle
      step /= 2.0
   }
   return min_distance
end

# Approximate distance from point to line segment.
#
# There is a more analytical way to do this, but it's simpler to handle
# the edge cases with a straightforward binary search.  This costs a
# bit of precision and time, but we are mostly optimizing for code size.
def line_distance(x, y, ax, ay, bx, by)
   dx = bx - ax
   dy = by - ay
   min_distance = 1e99
   t0 = 0
   t1 = 1
   16.times{
      d0 = distance(x, y, ax + dx * t0, ay + dy * t0)
      d1 = distance(x, y, ax + dx * t1, ay + dy * t1)
      if d0 < d1
         t1 = (t0 + t1) / 2.0
      else
         t0 = (t0 + t1) / 2.0
      end
      min_distance = (d0 + d1) / 2.0
   }
   return min_distance
end

# Return minimum distance to closest drawing edge.
def shape_distance(x, y, r1, r2)
   ry = r1 * EYE_POSITION_SCALE
   rh1 = r1 * EYE_HORIZONTAL_SCALE
   my = -r1 * MOUTH_POSITION_SCALE
   mw = r1 * MOUTH_WIDTH_SCALE
   mh = r1 * MOUTH_HEIGHT_SCALE

   [line_distance(x, y, -mw, my, mw, my),
    line_distance(x, y, -mw * MOUTH_BAR2_SCALE, my - mh,
                        -mw * MOUTH_BAR2_SCALE, my + mh),
    line_distance(x, y, -mw * MOUTH_BAR1_SCALE, my - mh,
                        -mw * MOUTH_BAR1_SCALE, my + mh),
    line_distance(x, y, 0, my - mh, 0, my + mh),
    line_distance(x, y, mw * MOUTH_BAR1_SCALE, my - mh,
                        mw * MOUTH_BAR1_SCALE, my + mh),
    line_distance(x, y, mw * MOUTH_BAR2_SCALE, my - mh,
                        mw * MOUTH_BAR2_SCALE, my + mh),
    ellipse_distance(x, y, 0, ry, rh1, r1),
    ellipse_distance(x, y, 0, ry, r2, r2)].min
end
# }}}

# {{{ Fill

# 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 /= 2
   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

# 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 group of pixels around a central point.
def draw_group(cx, cy, painted, dir_x, dir_y, r1, r2, line_size, width, height)
   (-1 .. 1).each{|dy|
      sy = cy + dy
      y = (sy - height / 2.0) * CHAR_HEIGHT

      (-1 .. 1).each{|dx|
         sx = cx + dx
         if sx >= 0 && sx <= width && sy >= 0 && sy <= height
            if painted[sy][sx]
               pixel = painted[sy][sx]
            else
               if dx == 0 && dy == 0
                  pixel = ["M", "W"][(sx + sy) % 2]
                  painted[sy][sx] = pixel
               else
                  pixel = " "
               end
            end

            x = sx - width / 2.0

            # Bright white on yellow background near shape edges,
            # otherwise use gray on black background.
            #
            # Yellow is chosen to match Miko's eye color.  Actual
            # color depends on terminal palette and might be anything
            # from bright yellow to dark brown to something else
            # entirely.
            color = shape_distance(x, y, r1, r2) < line_size ? "\e[97;43m"
                                                             : "\e[90;40m"
            print dir_y[1 + dy], dir_x[1 + dx], color, pixel, "\e[1D\e[0m",
                  dir_x[1 - dx], dir_y[1 - dy]
         end
      }
   }

   STDOUT.flush
end

# Draw a list of line segments.
def draw(points, total_time, r1, r2, line_size, width, height)
   # Allocate array to remember which cells had curve points.  This
   # will be used to make sure that we don't overwrite existing curve
   # points with empty space.
   painted = []
   (height + 2).times{ painted += [Array.new(width + 2)] }

   start_time = Time.now
   dir_x = ["\e[1D", "", "\e[1C"]
   dir_y = ["\e[1B", "", "\e[1A"]

   # 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]
   draw_group(cx, cy, painted, dir_x, dir_y, r1, r2, line_size, width, height)
   frame_count = 1
   pause(start_time, frame_delay, frame_count)

   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]
         draw_group(cx, cy, painted,
                    dir_x, dir_y, r1, r2, line_size, width, height)
         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
   # Compute eye parameters.
   s = [width, height * CHAR_HEIGHT].min
   r1 = s * EYE_SCALE

   # Scale line thickness proportional to radius.
   line_size = r1 * LINE_SCALE

   # Inner eye circle will be slightly smaller than outer eye ellipse.
   r2 = r1 - line_size * 2

   # Check if mouth would fit horizontally, scale everything down if it doesn't.
   if (r1 * MOUTH_WIDTH_SCALE + line_size) * 2 > width
      scale = width / ((r1 * MOUTH_WIDTH_SCALE + line_size) * 2.0)
      r1 *= scale
      r2 *= scale
      line_size *= scale
   end

   # 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.  This works reasonably well for terminal sizes up to
   # 132x40 or so, any larger and all the distance computation time would
   # dominate, and we might end up taking a minute or so.
   print "\n" * height
   draw(points, 30.0 - (Time.now - start_time),
        r1, r2, line_size, width, height)

   # 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