require 'journey/nfa/dot'

module Journey
  module NFA
    class TransitionTable
      include Journey::NFA::Dot

      attr_accessor :accepting
      attr_reader :memos

      def initialize
        @table     = Hash.new { |h,f| h[f] = {} }
        @memos     = {}
        @accepting = nil
        @inverted  = nil
      end

      def accepting? state
        accepting == state
      end

      def accepting_states
        [accepting]
      end

      def add_memo idx, memo
        @memos[idx] = memo
      end

      def memo idx
        @memos[idx]
      end

      def []= i, f, s
        @table[f][i] = s
      end

      def merge left, right
        @memos[right] = @memos.delete left
        @table[right] = @table.delete(left)
      end

      def states
        (@table.keys + @table.values.map(&:keys).flatten).uniq
      end

      ###
      # Returns a generalized transition graph with reduced states.  The states
      # are reduced like a DFA, but the table must be simulated like an NFA.
      #
      # Edges of the GTG are regular expressions
      def generalized_table
        gt       = GTG::TransitionTable.new
        marked   = {}
        state_id = Hash.new { |h,k| h[k] = h.length }
        alphabet = self.alphabet

        stack = [eclosure(0)]

        until stack.empty?
          state = stack.pop
          next if marked[state] || state.empty?

          marked[state] = true

          alphabet.each do |alpha|
            next_state = eclosure(following_states(state, alpha))
            next if next_state.empty?

            gt[state_id[state], state_id[next_state]] = alpha
            stack << next_state
          end
        end

        final_groups = state_id.keys.find_all { |s|
          s.sort.last == accepting
        }

        final_groups.each do |states|
          id = state_id[states]

          gt.add_accepting id
          save = states.find { |s|
            @memos.key?(s) && eclosure(s).sort.last == accepting
          }

          gt.add_memo id, memo(save)
        end

        gt
      end

      ###
      # Returns set of NFA states to which there is a transition on ast symbol
      # +a+ from some state +s+ in +t+.
      def following_states t, a
        Array(t).map { |s| inverted[s][a] }.flatten.uniq
      end

      ###
      # Returns set of NFA states to which there is a transition on ast symbol
      # +a+ from some state +s+ in +t+.
      def move t, a
        Array(t).map { |s|
          inverted[s].keys.compact.find_all { |sym|
            sym === a
          }.map { |sym| inverted[s][sym] }
        }.flatten.uniq
      end

      def alphabet
        inverted.values.map(&:keys).flatten.compact.uniq.sort_by { |x| x.to_s }
      end

      ###
      # Returns a set of NFA states reachable from some NFA state +s+ in set
      # +t+ on nil-transitions alone.
      def eclosure t
        stack = Array(t)
        seen  = {}
        children = []

        until stack.empty?
          s = stack.pop
          next if seen[s]

          seen[s] = true
          children << s

          stack.concat inverted[s][nil]
        end

        children.uniq
      end

      def transitions
        @table.map { |to, hash|
          hash.map { |from, sym| [from, sym, to] }
        }.flatten(1)
      end

      private
      def inverted
        return @inverted if @inverted

        @inverted = Hash.new { |h,from|
          h[from] = Hash.new { |j,s| j[s] = [] }
        }

        @table.each { |to, hash|
          hash.each { |from, sym|
            if sym
              sym = Nodes::Symbol === sym ? sym.regexp : sym.left
            end

            @inverted[from][sym] << to
          }
        }

        @inverted
      end
    end
  end
end