module Chapter03

  def sum(xs)
    xs.inject(0.0) { |x, s| s+x }
  end

  def mean(xs)
    (sum xs) / xs.size
  end

  def make_palindrome(xs)
    xs + xs.reverse
  end

  def palindrome?(xs)
    xs == xs.reverse
  end

  def length_sort(xxs)
    xxs.sort_by { |xs| xs.length }
  end

  def intersperse(sep,xs)
    return xs if xs.length < 2
    [xs.shift].push(sep) + intersperse(sep, xs)
  end

  class Tree
    attr_reader :node,:left,:right

    def initialize(node=:empty, left=:empty, right=:empty)
      @node  = node
      @left  = left
      @right = right
    end

    def height
      0 if empty?
      l = @left  == :empty ? 0 : @left.height
      r = @right == :empty ? 0 : @right.height
      1 + [l,r].max
    end

    def empty?
      @node == :empty
    end

  end

  class Point
    attr_reader :x,:y
    def initialize(x,y)
      @x = x
      @y = y
    end

    def <=>(other)
      return -1 if @y < other.y
      return  1 if @y > other.y
      return -1 if @x < other.x
      return  1 if @x > other.x
      0
    end

    def inspect()
      "(#{@x},#{@y})"
    end

  end

  class Polygon
    attr_accessor :vertices

    def initialize(vertices)
      @vertices = vertices
    end

    def directions(ps)
      return [] if ps.size < 3
      (0..@vertices.size-2).inject([]) do |i,dirs|
        dirs << direction(@vertices[i], @vertices[i+1], @vertices[i+2])
      end
    end

    def graham_scan
      raise "Polygon#graham_scan : at least 3 vertices are needed : given #{@vertices.size}" if @vertices.size < 3
      clockwise_points = sort_by_angle
      initial_hull = clockwise_points[0..2]
      remaining_points = clockwise_points[3..@vertices.size-1]
      contiguous_left_turns(initial_hull, remaining_points)
    end

    :private

    def contiguous_left_turns(hull, ps)
      return hull if ps.size == 0
      p = ps[0]
      h1 = hull[-2]
      h2 = hull[-1]
      case direction(h1, h2, p)
      when :left
        contiguous_left_turns(hull.push( ps.shift), ps)
      when :straight
        contiguous_left_turns(hull.push( ps.shift), ps)
      when :right
        hull.pop
        contiguous_left_turns(hull, ps)
      end
    end

    def sort_by_angle
      # 1. Find the origin or lowest point
      initial_sort = @vertices.sort
      origin = initial_sort[0]
      # 2. Sort all points by the angle each point makes with the origin
      [origin] + initial_sort[1..-1].sort! {|v, pivot| compare_angles(origin, v, pivot)}
    end

  end


  TestPoints = [Point.new(0,0),  Point.new(3,-10), Point.new(-3,-4), Point.new(-7,-1),
                Point.new(-7,1), Point.new(-3,4),  Point.new(3,7),   Point.new(5,0)]


  TestGrid   = [Point.new(0,0), Point.new(2,0), Point.new(4,0), Point.new(6,0),
                Point.new(1,1), Point.new(3,1), Point.new(5,1),
                Point.new(0,2), Point.new(2,2), Point.new(4,2), Point.new(6,2),
                Point.new(1,3), Point.new(3,3), Point.new(5,3),
                Point.new(0,4), Point.new(2,4), Point.new(4,4), Point.new(6,4),
                Point.new(1,5), Point.new(3,5), Point.new(5,5),
                Point.new(0,6), Point.new(2,6), Point.new(4,6), Point.new(6,6)]


  :private

  def direction(a, b, c)
    mag = cross_size(a, b, c)
    return :right if mag < 0
    return :left  if mag > 0
    return :straight
  end

  # compare the angles that origin->p1 and origin->p2 make with the horizontal
  def compare_angles(origin, p1, p2)
    p = (p1.x - origin.x)*(p1.y - p2.y)
    q = (p1.y - origin.y)*(p1.x - p2.x)
    return -1 if p < q
    return  1 if p > q
    return -1 if p1.y > p2.y
    return  1 if p1.y < p2.y
    0
  end

  def cross_size(a, b, c)
    (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
  end

end