require_relative 'graph/dfs'
require_relative 'graph/scc'
require_relative 'graph/kruskal'

module Silicium
  module Graphs
    Pair = Struct.new(:first, :second)

    class GraphError < Error
    end

    ##
    # Class represents oriented graph
    class OrientedGraph
      def initialize(initializer = [])
        @vertices = {}; @vertex_labels = {}
        @edge_labels = {}; @edge_number = 0
        initializer.each do |v|
          add_vertex!(v[:v])
          v[:i].each do |iv|
            add_vertex!(v[:v])
            add_vertex!(iv)
            add_edge!(v[:v], iv)
          end
        end
      end

      ##
      # Adds vertex to graph
      def add_vertex!(vertex_id)
        if @vertices.has_key?(vertex_id); return end
        @vertices[vertex_id] = [].to_set
      end

      ##
      # Adds edge to graph
      def add_edge!(from, to)
        protected_add_edge!(from, to)
        @edge_number += 1
      end

      # should only be used in constructor
      def add_edge_force!(from, to)
        add_vertex!(from)
        add_vertex!(to)
        add_edge!(from, to)
      end

      ##
      # Returns array of vertices which adjacted with vertex
      # @raise [GraphError] if graph does not contain vertex
      def adjacted_with(vertex)
        raise GraphError.new("Graph does not contain vertex #{vertex}") unless @vertices.has_key?(vertex)
        @vertices[vertex].clone
      end

      ##
      # Adds label to edge
      # @raise [GraphError] if graph does not contain edge
      def label_edge!(from, to, label)
        unless @vertices.has_key?(from) && @vertices[from].include?(to)
          raise GraphError.new("Graph does not contain edge (#{from}, #{to})")
        end
        @edge_labels[Pair.new(from, to)] = label
      end

      ##
      # Adds label to vertex
      # @raise [GraphError] if graph does not contain vertex
      def label_vertex!(vertex, label)
        unless @vertices.has_key?(vertex)
          raise GraphError.new("Graph does not contain vertex #{vertex}")
        end
        @vertex_labels[vertex] = label
      end

      ##
      # Returns edge label
      # @raise [GraphError] if graph does not contain edge
      def get_edge_label(from, to)
        if !@vertices.has_key?(from) || ! @vertices[from].include?(to)
          raise GraphError.new("Graph does not contain edge (#{from}, #{to})")
        end
        @edge_labels[Pair.new(from, to)]
      end

      ##
      # Returns vertex label
      # @raise [GraphError] if graph does not contain vertex
      def get_vertex_label(vertex)
        unless @vertices.has_key?(vertex)
          raise GraphError.new("Graph does not contain vertex #{vertex}")
        end

        @vertex_labels[vertex]
      end
      ##
      # Returns number of vertices
      def vertex_number
        @vertices.count
      end
      ##
      # Returns number of edges
      def edge_number
        @edge_number
      end
      ##
      # Returns number of vertex labels
      def vertex_label_number
        @vertex_labels.count
      end
      ##
      # Returns number of edge labels
      def edge_label_number
        @edge_labels.count
      end
      ##
      # Checks if graph contains vertex
      def has_vertex?(vertex)
        @vertices.has_key?(vertex)
      end
      ##
      # Checks if graph contains edge
      def has_edge?(from, to)
        @vertices.has_key?(from) && @vertices[from].include?(to)
      end
      ##
      # Deletes vertex from graph
      def delete_vertex!(vertex)
        if has_vertex?(vertex)
          @vertices.keys.each { |key| delete_edge!(key, vertex) }
          @vertices.delete(vertex)
          @vertex_labels.delete(vertex)
          @vertices.keys.each { |key| @edge_labels.delete(Pair.new(vertex, key)) }
        end
      end
      ##
      # Deletes edge from graph
      def delete_edge!(from, to)
        protected_delete_edge!(from, to)
        @edge_number -= 1
      end
      ##
      # Reverses graph
      def reverse!
        l = {}; v = {}
        @vertices.keys.each { |from| v[from] = [].to_set }
        @vertices.keys.each do |from|
          @vertices[from].each do |to|
            v[to] << from
            if @edge_labels.include?(Pair.new(from, to))
              l[Pair.new(to, from)] = @edge_labels[Pair.new(from, to)]
            end
          end
        end
        @vertices = v; @edge_labels = l
      end


      # Returns array of vertices
      def vertices
        @vertices
      end

      # Returns labels of edges
      def edge_labels
        @edge_labels
      end


      # Returns labels of vertices
      def vertex_labels
        @vertex_labels
      end

      protected
      ##
      # Adds edge to graph
      def protected_add_edge!(from, to)
        @vertices[from] << to if @vertices.has_key?(from) && @vertices.has_key?(to)
      end
      ##
      # Deletes edge from graph
      def protected_delete_edge!(from, to)
        if has_edge?(from, to)
          @vertices[from].delete(to)
          @edge_labels.delete(Pair.new(from, to))
        end
      end

    end
    ##
    # Class represents unoriented graph
    class UnorientedGraph < OrientedGraph
      ##
      # Adds edge to graph
      def add_edge!(from, to)
        protected_add_edge!(from, to)
        protected_add_edge!(to, from)
        @edge_number += 1
      end
      ##
      # Adds label to edge
      def label_edge!(from, to, label)
        super(from, to, label)
        super(to, from, label)
      end
      ##
      # Deletes edge from graph
      def delete_edge!(from, to)
        protected_delete_edge!(from, to)
        protected_delete_edge!(to, from)
        @edge_number -= 1
      end

    end
    ##
    # Implements breadth-first search (BFS)
    def breadth_first_search?(graph, start, goal)
      visited = Hash.new(false)
      queue = Queue.new
      queue.push(start)
      visited[start] = true
      until queue.empty? do
        node = queue.pop
        return true if node == goal
        add_to_queue(graph, queue, node, visited)
      end
      false
    end
    ##
    # Adds to queue not visited vertices
    def add_to_queue(graph, queue, node, visited)
      graph.vertices[node].each do |child|
        unless visited[child]
          queue.push(child)
          visited[child] = true
        end
      end
    end
    ##
    # Checks if graph is connected
    def connected?(graph)
      start = graph.vertices.keys[0]
      goal = graph.vertices.keys[graph.vertex_number - 1]
      pred = breadth_first_search?(graph, start, goal)
      graph.reverse!
      pred = pred and breadth_first_search?(graph, goal, start)
      graph.reverse!
      pred
    end
    ##
    # Returns number of connected vertices
    def number_of_connected(graph)
      visited = Hash.new(false)
      res = 0
      graph.vertices.keys.each do |v|
        unless visited[v]
          dfu(graph, v, visited)
          res += 1
        end
      end
      res
    end
    ##
    # Passes graph's vertices and marks them visited
    def dfu(graph, vertice, visited)
      visited[vertice] = true
      graph.vertices[vertice].each { |item| dfu(graph, item, visited) unless visited[item] }
    end

    def add_edge!(mst, edge, label)
      mst.add_vertex!(edge[0])
      mst.add_vertex!(edge[1])
      mst.add_edge!(edge[0], edge[1])
      mst.label_edge!(edge[0], edge[1], label)
    end



    ##
    # "Split" graph into elements like :[from, to] = label
    def graph_to_sets(graph)
      labels = {}
      graph.vertices.keys.each do |from|
        graph.adjacted_with(from).each { |to| labels[Pair.new(from, to)] = graph.get_edge_label(from, to) }
      end
      labels.to_set.sort_by { |elem| elem[1] }.to_h
    end

    def sum_labels(graph)
      labels = 0
      graph.vertices.keys.each do |from|
        graph.adjacted_with(from).each { |to| labels += graph.get_edge_label(from, to) }
      end
      labels / 2
    end



   ##
    # Implements algorithm of Dijkstra
    def dijkstra_algorithm(graph, starting_vertex)
      if !graph.has_vertex?(starting_vertex)
        raise GraphError.new("Graph does not contains vertex #{starting_vertex}")
      end
      unvisited_vertices = graph.vertices.clone.to_a
      labels = {}
      paths = {}
      initialize_labels_and_paths(graph, labels,paths,starting_vertex)
      while unvisited_vertices.size > 0
        unvisited_vertices.sort { |a, b| compare_labels(a, b, labels) }
        vertex = unvisited_vertices.first
        vertex[1].each do |adj|
          new_label = labels[vertex[0]] + graph.get_edge_label(vertex[0], adj)
          if change_label?(labels[adj], new_label)
            labels[adj] = new_label
            paths[adj] = paths[vertex[0]].clone
            paths[adj].push adj
          end
        end
        unvisited_vertices.delete_at(0)
      end
      {"labels" => labels, "paths" => paths}
    end

    private

    def initialize_labels_and_paths(graph, labels,paths,starting_vertex)
      graph.vertices.each_key do |vertex|
        labels[vertex] = -1
        paths[vertex] = [starting_vertex]
      end
      labels[starting_vertex] = 0
    end

    def compare_labels(a, b, labels)
      return -1 if labels[b[0]] == -1
      return 1 if labels[a[0]] == -1
      return labels[a[0]] <=> labels[b[0]]
    end

    def change_label?(label, new_label)
      return true if label == -1
      return false if new_label == -1
      return new_label < label
    end
    
  end
end