alias $std.data as data
alias $std.fun as fun
alias $std.strings as strings
alias $std.math as math

alias $std.data.map as map
alias $std.data.reduce as reduce
alias $std.data.reduce_until as reduce_until
alias $std.data.put as put
alias $std.data.put_in as put_in
alias $std.data.update as update
alias $std.data.update_in as update_in
alias $std.data.size as size
alias $std.data.shuffle as shuffle
alias $std.data.values as values
alias $std.data.find as find
alias $std.data.last as last
alias $std.data.delete as delete
alias $std.data.repeat as repeat
alias $std.data.insert as insert
alias $std.data.any? as any?

alias $std.core.hash as hash
alias $std.core.inspect as inspect
alias $std.core.nil? as nil?
alias $std.core.present? as present?

alias lib.empty? as empty?

library matrix_2d {

  make: (w, h, f) ->
    if any?([w, h], nil?) then nil
    if w <= 0 then throw "width must be positive"
    if h <= 0 then throw "height must be positive"
    let {
      matrix: data.map(repeat(w), (_) -> repeat(h))
    }
    if f == nil
      matrix
    else
      data.map(matrix,
        (col, x) -> data.map(col,
          (row, y) -> f(x, y)))

  # maps over each matrix cell building a new matrix of same shape
  # f receives three arguments: input cell, x coordinate, y coordinate
  mmap: (m, f) ->
    map(m,
      (col, x) -> map(col,
        (row, y) -> f(m[x y], x, y)))

  col: (m, x) ->
    m[x]

  row: (m, y) ->
    map(m, (col) -> col[y])

  width: (m) ->
    if m == nil then nil
    size(row(m, 0))

  height: (m) ->
    if m == nil then nil
    size(m[0])

  transpose: (m) ->
    if m == nil then nil
    mmap(
      make(height(m), width(m)),
      (_, x, y) -> m[y x]
    )
}

library maze {

  # simple mapping of directions to their opposites
  opposite: {
    :north :south
    :east  :west
    :south :north
    :west  :east
  }

  # returns a cell with all walls intact
  make_cell: (x, y) -> {
    :x x
    :y y
    :walls {
      :north true
      :east  true
      :south true
      :west  true
    }
    :travel []      # neigbor coordinates of the cell put here when building travel paths
    :visited false  # helper during backtracking through maze
  }

  # returns a map of coordinates to neighboring cells, if any
  # neighbors_map(gen(5,5), {:x 0, :y 0})
  # {
  #   :south {
  #     :x 0,
  #     :y 1
  #   },
  #   :east {
  #     :x 1,
  #     :y 0
  #   }
  # }
  neighbors_map: (maze, pos) ->
    let {
      x: pos[:x]
      y: pos[:y]
      cells: maze[:cells]
      neighbor_cells: data.filter(
        {
          :north  cells[x   y-1]
          :east   cells[x+1 y  ]
          :south  cells[x   y+1]
          :west   cells[x-1 y  ]
        },
        present?
      )
    }
    # just retain the addresses, not the cell payload
    map(neighbor_cells, (cell) -> cell_pos(cell))

  # given a cell, returns only its coordinates in a map
  cell_pos: (cell) ->
    {
      :x cell[:x],
      :y cell[:y]
    }

  # just the values of the neighbor_map, losing the direction keys
  neighbors_list: (maze, pos) ->
    values(neighbors_map(maze, pos))

  # given two neighboring cell positions
  # returns the wall direction from the first to the second
  # return value is undefined if the cells are not actually neighboring cells
  # > wall_between({:x 0, :y 0}, {:x 0 :y 1})
  # "south"
  # > wall_between({:x 0, :y 1}, {:x 0 :y 0})
  # "north"
  #
  wall_between: (c1, c2) ->
    if c1[:x] == c2[:x]
      if c1[:y] < c2[:y]
        :south
      else
        :north
    else
      if c1[:x] < c2[:x]
        :east
      else
        :west

  break_wall_between: (maze, c1, c2) ->
    let {
      wall_c1_to_c2: wall_between(c1, c2)
      wall_c2_to_c1: opposite[wall_c1_to_c2]
    }
    ->> (maze)
        (maze) -> put_in(maze, [:cells c1[:x] c1[:y] :walls wall_c1_to_c2], false)
        (maze) -> put_in(maze, [:cells c2[:x] c2[:y] :walls wall_c2_to_c1], false)

  init: (w, h, seed) ->
    {
      :cells matrix_2d.make(w, h, make_cell)
      :size {:w w, :h h}
      :seed seed
      :path []
      :path_done false
      :total_visited 0
      :cell_count w * h
    }

  mark_visited: (maze, pos) ->
    ->> (maze)
        (maze) -> update_in(maze, [:total_visited], lib.inc)
        (maze) -> put_in(maze, [:cells, pos[:x] pos[:y], :visited], true)

  update_seed: (maze, randomness) ->
    update(maze, :seed, (seed) -> hash([randomness, seed]))

  update_cell: (maze, pos, f) ->
    update_in(maze, [:cells pos[:x] pos[:y]], f)

  all_coords: (maze) ->
    lib.flatten(
      matrix_2d.mmap(maze[:cells], (_, x, y) -> {:x x, :y y})
    )

  build_travel_path: (maze) ->
    reduce(
      all_coords(maze),
      maze,
      (maze, at) ->
        let {
          shuffled_neighbors:   shuffle(neighbors_list(maze, at), maze[:seed])
        }
        ->> (maze)
            (maze) -> update_seed(maze, shuffled_neighbors)
            (maze) -> update_cell(maze, at, (cell) -> {...cell, :travel shuffled_neighbors})
    )

  random_cell_pos: (maze) ->
    let {
      x:    math.rand(maze[:seed])
      y:    math.rand(hash([x, maze[:seed]]))
    }
    {
      :x (x * maze[:size :w]) as long,
      :y (y * maze[:size :h]) as long
    }

  step: (maze) ->
    # short circuit out if done
    if maze[:path_done] then maze

    # not started yet?
    if empty?(maze[:path])
      # pick a random starting point
      let {
        pos: random_cell_pos(maze)
      }
      ->> (maze)
          (maze) -> update_seed(maze, pos)
          (maze) -> mark_visited(maze, pos)
          (maze) -> put(maze, :path, [pos])

    else
      # move on from the last item
      let {
        at:       last(maze[:path])
        travel:   maze[:cells at[:x] at[:y] :travel]
        next:     find(travel, (pos) -> !maze[:cells pos[:x] pos[:y] :visited])
      }
      if next
        # there is a cell we can visit from here
        ->> (maze)
            (maze) -> break_wall_between(maze, at, next)
            (maze) -> mark_visited(maze, next)
            (maze) -> update(maze, :path, (path) -> [...path, next])

      else
        # there is no more cells we can visit from here
        # already done?
        if maze[:cell_count] == maze[:total_visited]
          {...maze, :path_done true, :path []}
        else
          # need to backtrack on path
          ->> (maze)
              (maze) -> put(maze, :path, data.init(maze[:path]))
              # if backtracked completely, the path is complete
              (maze) ->
                if empty?(maze[:path])
                  put(maze, :path_done, true)
                else
                  maze

  gen: (w=8, h=8, seed=nil) ->
    let {
      maze: build_travel_path(init(w, h, seed))
    }
    fun.until(step, maze, (m) -> m[:path_done])

  str: (maze) ->

    let {

      cell_to_top_str: (cell) ->
        (if cell[:x] == 0 "+" "") .. (if cell[:walls :north] "---" "   ") .. "+"

      cell_to_mid_str: (cell) ->
        (if cell[:x] == 0 (if cell[:walls :west] "|" " ") "") .. "   " .. (if cell[:walls :east] "|" " ")

      cell_to_bot_str: (cell) ->
        (if cell[:x] == 0 "+" "") .. (if cell[:walls :south] "---" "   ") .. "+"

    }

    reduce(
      # transposing inverts rows and columns
      # so the transposed cells are a list of rows vs. the original representation as a list of columns
      matrix_2d.transpose(maze[:cells]),
      "",
      (a, row, y) ->
        let {
          row_top_line: if y==0 then strings.join(map(row, (cell) -> cell_to_top_str(cell))) else nil
          row_mid_line: strings.join(map(row, (cell) -> cell_to_mid_str(cell)))
          row_bot_line: strings.join(map(row, (cell) -> cell_to_bot_str(cell)))
        }
        a .. "\n" ..
          if y==0
            strings.join([row_top_line, row_mid_line, row_bot_line], "\n")
          else
            strings.join([row_mid_line, row_bot_line], "\n")
    )

}

library lib {

  empty?: (xs) ->
    size(xs) == 0

  mapcat: (xs, f) ->
    reduce(map(xs, f), [], (a, x) -> if x is list then [...a, ...x] else a)

  flatten: (list xs) ->
    reduce(xs, [], (a, x) -> if x is list then [...a, ...x] else [...a, x])

  fibl: (list xs) ->
    if !xs then [nil, 0]
    if xs == [nil, 0] then [0,1]
    [xs[1], xs[0]+xs[1]]

  fib: (long x) ->
    if (x <= 0) then 0
    fun.iterate(fibl, fibl(), x)[1]

  reverse: (list xs) ->
    if (xs == nil) then nil
    reduce(xs, [], (a, x) -> data.prepend(x, a))

  inc: (long x) ->
    x+1

  zipmap: (list keys, list values) ->
    reduce(keys, {}, (a, k, i) -> put(a, k, values[i]))

  interpose: (list xs, s) ->
    if xs == nil then nil
    reduce(xs, [],          # build a new list
      (a, x, i) ->
        if i == 0
          [x]               # first item remains as is
          [...a, s, x]      # follow-up items are preceded with seperator
    )

}