require 'dijkstra/nodes_extractor'

class Dijkstra::Graph
  def initialize(edges)
    fail ArgumentError, 'Edges must not be empty.' if edges.empty?

    @edges = edges
    @nodes = Dijkstra::NodesExtractor.extract(edges)
  end

  # taken from https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm
  def shortest_path(from, to)
    # 1
    distance_to = Hash.new(Float::INFINITY)
    distance_to[from] = 0
    nearest_neighbor = Hash.new

    # 2
    current_node = from
    visited = []
    unvisited = @nodes

    # 5
    until visited.include?(to)
      # 3
      unvisited_neighbors(current_node, visited).each do |neighbor|
        tentative_distance = distance_to[current_node] + edge_weight(current_node, neighbor)
        if tentative_distance < distance_to[neighbor]
          distance_to[neighbor] = tentative_distance
          nearest_neighbor[neighbor] = current_node
        end
      end

      # 4
      visited << current_node
      unvisited.reject! { |node| node == current_node }

      # 6
      current_node = node_with_shortest_distance(unvisited, distance_to)
    end

    return traverse(nearest_neighbor, to)
  end

  def cost(path)
    path.each_with_index.inject(0) do |c, (node,index)|
      c += edge_weight(node, path[index+1])
    end
  end

  private

  def traverse(nearest_neighbor, dest, path = [])
    if nearest_neighbor[dest]
      traverse(nearest_neighbor, nearest_neighbor[dest], path)
    end
    path << dest
  end

  def neighbors(node)
    @edges.select { |edge| edge.from == node }.map(&:to)
  end

  def unvisited_neighbors(node, visited)
    neighbors(node) - visited
  end

  def edge_weight(from, to)
    @edges.select { |edge| edge.from == from && edge.to == to }.first.weight rescue 0
  end

  def node_with_shortest_distance(nodes, distance_to)
    nodes.inject do |shortest, node|
      distance_to[shortest] < distance_to[node] ? shortest : node
    end
  end
end
