module Bresenham

function line(f, x0::Int, y0::Int, x1::Int, y1::Int)
  dx = 2 * (x1 - x0)
  dy = 2 * (y1 - y0)

  if dx != 0
    if dy != 0
      if abs(dx) >= abs(dy)
        e = dx / 2
        y = y0
        for x = x0:sign(dx):x1
          f(x, y)
          # (a) following code runs even if
          # the loop exits after this iteration
          # but we don't care about that side effect
          e -= sign(dx) * sign(dy) * dy
          if sign(dx) > 0 && e < 0 ||
             sign(dx) < 0 && e >= 0
            y += sign(dy)
            e += dx
          end
        end
      else # abs(dx) < abs(dy) (steep case)
        e = dy / 2
        x = x0
        for y = y0:sign(dy):y1
          f(x, y)
          # see (a)
          e -= sign(dx) * sign(dy) * dx
          if sign(dy) > 0 && e < 0 ||
             sign(dy) < 0 && e >= 0
            x += sign(dx)
            e += dy
          end
        end
      end
    else # dy == 0 (horizontal line)
      for x = x0:sign(dx):x1
        f(x, y0)
      end
    end
  else # dx == 0 (vertical line)
    for y = y0:sign(dy):y1
      f(x0, y)
    end
  end
end # function

function circle(f, x0::Int, y0::Int, r::Int)
  x = r - 1
  y = 0
  dx = 1
  dy = 1
  err = dx - (r << 1)

  while x >= y
    f(x0 + x, y0 + y)
    f(x0 + y, y0 + x)
    f(x0 - y, y0 + x)
    f(x0 - x, y0 + y)
    f(x0 - x, y0 - y)
    f(x0 - y, y0 - x)
    f(x0 + y, y0 - x)
    f(x0 + x, y0 - y)

    if err <= 0
      y += 1
      err += dy
      dy += 2
    end

    if err > 0
      x -= 1
      dx += 2
      err += dx - (r << 1)
    end
  end
end # function

function ordered_circle(f, x0::Int, y0::Int, r::Int)
  pts = Vector{Tuple{Int, Int}}()
  Bresenham.circle(x0, y0, r) do x, y
    push!(pts, (x, y))
  end

  unique!(sort!(pts, by=(X -> atan(X[2], X[1]))))
  for X in pts
    f(X...)
  end
end # function

export line, circle, ordered_circle

end # module
