module MPathGraph

# File lib/mpath_graph.rb, line 164
def self.compute_paths_graph(paths, output_stream, options = {})
  len = paths.size - 1

  (0..len).each do |i|
    (i+1..len).each do |j|
      unless (paths[i][1...-1] & paths[j]).empty?
        output_stream << [i,j]
        next
      end
    end
    options[:progress_bar].increment unless options[:progress_bar].nil?
  end
end

# File lib/mpath_graph.rb, line 45
def self.find_cycles(worm, edges)
  if is_edge? worm[0], worm[-1], edges
    # Check edges
    (0..worm.length-2).each do |i|
      (i+2..worm.length-1).each do |j|
        unless i==0 && j==worm.length-1 # Avoid check endpoints
          return [worm[i],worm[j]] if is_edge? worm[i], worm[j], edges
        end
      end
    end
  end
  nil
end

# File lib/mpath_graph.rb, line 138
def self.find_neighbors(vertex, edges)
  neighbors = []

  edges.each do |e|
    if vertex == e[0]
      neighbors << e[1]
    elsif vertex == e[1]
      neighbors << e[0]
    end
  end

  neighbors
end

# File lib/mpath_graph.rb, line 178
def self.from_csv(file)
  pbar = ProgressBar.create(
    title: "Reading paths graph",
    starting_at: 1,
    total: nil)

  paths = []
  CSV.foreach(file) do |row|
    paths << JSON.parse(row[0])
    pbar.increment
  end
  
  paths
end

# File lib/mpath_graph.rb, line 201
def self.gen_mpath_graph_from_paths(paths)
  mp_graph_edges = []

  pbar = ProgressBar.create(
    title: "Computing mPath graph",
    output: STDERR,
    format: "%t [%B] [%c/%C - %P%%]",
    total: paths.size-1)

  (0..paths.size-2).each do |i|
    ((i+1)...paths.size).each do |j|
      share = MPathGraph::share_inner_vertices?(paths[i],paths[j])
      mp_graph_edges << [i,j] if share
    end
    pbar.increment
  end
  pbar.finish

  mp_graph_edges
end

# File lib/mpath_graph.rb, line 25
def self.has_cycles?(worm, edges, options = {})
  if is_edge? worm[0], worm[-1], edges
    # Check edges
    (0..worm.length-2).each do |i|
      (i+2..worm.length-1).each do |j|
        unless i==0 && j==worm.length-1 # Avoid check endpoints
          if is_edge? worm[i], worm[j], edges
            if options[:verbose] # Verbose cycle
              puts "Cycle\t#{worm[i]},#{worm[j]}"
            end

            return true 
          end
        end
      end
    end
  end
  false
end

# File lib/mpath_graph.rb, line 15
def self.is_edge?(i, j, edges)
  edges.include?([i,j]) || edges.include?([j,i])
end

# File lib/mpath_graph.rb, line 59
def self.random_walk(edges, options = {})
  worm         = []
  neighbors    = nil
  steps_walked = 0
  options[:initial_vertex]   ||= 0
  options[:worm_size]        ||= 5
  options[:walk_limit]       ||= -1
  options[:pause]            ||= false
  options[:induced_cycles_limit] ||= -1
  options[:print_non_cycles] ||= false

  # Initialize worm with initial vertex
  worm << options[:initial_vertex]

  # Initialize pseudo-random number generator
  prng = Random.new

  # Flush csv row headers to STDIN
  puts ["k-path","Induced cycle","Steps walked"].to_csv

  # Fill worm
  while worm.size < options[:worm_size]
    # Find neighbors of last vertex
    neighbors = find_neighbors(worm.last, edges) unless neighbors

    rnd_idx = prng.rand(neighbors.size) # Compute random index

    # Avoid cycles in worm
    if worm.include?(neighbors[rnd_idx])
      # Delete non-valid neighbors for current last vertex
      neighbors.delete(neighbors[rnd_idx])

      # Useless last vertex in worm, drop it!
      if neighbors.empty?
        worm.pop          # Drop last vertex
        neighbors = nil   # Clean neighbors
      end
    else
      worm << neighbors[rnd_idx]  # Append vertex
      neighbors = nil             # Clean neighbors

      if worm.size == options[:worm_size] # When worm is full
        steps_walked += 1       # Increment worm steps walked

        # Output well-formed worm
        # puts "Checking\t#{worm.inspect}"
        csv_row = [worm]

        # if has_cycles?(worm, edges, verbose: options[:verbose])
        if (cycle = find_cycles(worm, edges))
          # Flush csv row data to STDIN
          puts [worm, cycle, steps_walked].to_csv

          # if options[:verbose]           # Verbose worm with cycle
          #   puts "Worm\t#{worm.inspect}"
          #   puts "Steps walked\t#{steps_walked}"
          # end

          # Pause when verbose
          # if options[:pause]
          #   STDERR.puts "Press a key to continue..."
          #   STDIN.getc
          # end

          # Check induced cycles counter limit
          return if options[:induced_cycles_limit]==0
          options[:induced_cycles_limit]-=1
        else
          # Flush csv row data to STDIN
          puts [worm, nil, steps_walked].to_csv if options[:print_non_cycles]
        end

        worm.shift              # Drop first vertex in worm (as queue)
        break if steps_walked > options[:walk_limit] && options[:walk_limit] > 0 # Stop walking
      end
    end
  end
end

# File lib/mpath_graph.rb, line 193
def self.share_inner_vertices?(path_a, path_b)
  raise ArgumentError, "Path must have same lenght" if path_a.size != path_b.size

  path_a[1..-2].each { |a| path_b.each { |b| return true if a == b } }
  path_b[1..-2].each { |b| return true if b == path_a[0] || b == path_a[-1] }
  false
end