# sentence

class Sentence
  def initialize(ary)
    @sent = ary
  end

  def to_s
    @sent.join('')
  end

  def to_a
    @sent
  end

  def [](i)
    Sentence.new(@sent[i])
  end

  def inspect
    "#<#{self.class}: #{@sent.inspect}>"
  end

  def subst(target, &b)
    Sentence.new(subst_rec(@sent, target, &b))
  end

  def subst_rec(obj, target, &b)
    if obj.respond_to? :to_ary
      a = []
      obj.each {|e| a << subst_rec(e, target, &b) }
      a
    elsif target === obj
      yield obj
    else
      obj
    end
  end

  def find_subtree(&b)
    if r = find_subtree_rec(@sent, &b)
      Sentence.new(r)
    else
      nil
    end
  end

  def find_subtree_rec(obj, &b)
    if obj.respond_to? :to_ary
      if b.call obj
        return obj
      else
        obj.each {|e|
          r = find_subtree_rec(e, &b)
          return r if r
        }
      end
    end
    nil
  end

  def expand(&b)
    Sentence.new(expand_rec(@sent, &b))
  end

  def expand_rec(obj, r=[], &b)
    #puts "#{obj.inspect}\t\t#{r.inspect}"
    if obj.respond_to? :to_ary
      if b.call obj
        obj.each {|o|
          expand_rec(o, r, &b)
        }
      else
        a = []
        obj.each {|o|
          expand_rec(o, a, &b)
        }
        r << a
      end
    else
      r << obj
    end
    r
  end

  def Sentence.each(syntax, sym, limit)
    Gen.new(syntax).each_tree(sym, limit) {|tree|
      yield Sentence.new(tree)
    }
  end

  class Gen
    def Gen.each_tree(syntax, sym, limit, &b)
      Gen.new(syntax).each_tree(sym, limit, &b)
    end

    def Gen.each_string(syntax, sym, limit, &b)
      Gen.new(syntax).each_string(sym, limit, &b)
    end

    def initialize(syntax)
      @syntax = syntax
    end

    def self.expand_syntax(syntax)
      syntax = remove_underivable_rules(syntax)
      syntax = expand_justempty_rules(syntax)
      syntax = remove_emptyable_rules(syntax)
      syntax = expand_channel_rules(syntax)

      syntax = expand_noalt_rules(syntax)
      syntax = reorder_rules(syntax)
    end

    def self.remove_underivable_rules(syntax)
      deribable_syms = {}
      changed = true
      while changed
        changed = false
        syntax.each {|sym, rules|
          next if deribable_syms[sym]
          rules.each {|rhs|
            if rhs.all? {|e| String === e || deribable_syms[e] }
              deribable_syms[sym] = true
              changed = true
              break
            end
          }
        }
      end
      result = {}
      syntax.each {|sym, rules|
        next if !deribable_syms[sym]
        rules2 = []
        rules.each {|rhs|
          rules2 << rhs if rhs.all? {|e| String === e || deribable_syms[e] }
        }
        result[sym] = rules2.uniq
      }
      result
    end

    def self.expand_justempty_rules(syntax)
      justempty_syms = {}
      changed = true
      while changed
        changed = false
        syntax.each {|sym, rules|
          next if justempty_syms[sym]
          if rules.all? {|rhs| rhs.all? {|e| justempty_syms[e] } }
            justempty_syms[sym] = true
            changed = true
          end
        }
      end
      result = {}
      syntax.each {|sym, rules|
        result[sym] = rules.map {|rhs| rhs.reject {|e| justempty_syms[e] } }.uniq
      }
      result
    end

    def self.expand_emptyable_syms(rhs, emptyable_syms)
      if rhs.empty?
      elsif rhs.length == 1
        if emptyable_syms[rhs[0]]
          yield rhs
          yield []
        else
          yield rhs
        end
      else
        butfirst = rhs[1..-1]
        if emptyable_syms[rhs[0]]
          expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2| 
            yield [rhs[0]] + rhs2
            yield rhs2
          }
        else
          expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2|
            yield [rhs[0]] + rhs2
          }
        end
      end
    end

    def self.remove_emptyable_rules(syntax)
      emptyable_syms = {}
      changed = true
      while changed
        changed = false
        syntax.each {|sym, rules|
          next if emptyable_syms[sym]
          rules.each {|rhs|
            if rhs.all? {|e| emptyable_syms[e] }
              emptyable_syms[sym] = true
              changed = true
              break
            end
          }
        }
      end
      result = {}
      syntax.each {|sym, rules|
        rules2 = []
        rules.each {|rhs|
          expand_emptyable_syms(rhs, emptyable_syms) {|rhs2|
            rules2 << rhs2
          }
        }
        result[sym] = rules2.uniq
      }
      result
    end

    def self.expand_channel_rules(syntax)
      channel_rules = {}
      syntax.each {|sym, rules|
        channel_rules[sym] = {sym=>true}
        rules.each {|rhs|
          if rhs.length == 1 && Symbol === rhs[0]
            channel_rules[sym][rhs[0]] = true
          end
        }
      }
      changed = true
      while changed
        changed = false 
        channel_rules.each {|sym, set|
          n1 = set.size
          set.keys.each {|s|
            set.update(channel_rules[s])
          }
          n2 = set.size
          changed = true if n1 < n2
        }
      end
      result = {}
      syntax.each {|sym, rules|
        rules2 = []
        channel_rules[sym].each_key {|s|
          syntax[s].each {|rhs|
            unless rhs.length == 1 && Symbol === rhs[0]
              rules2 << rhs
            end
          }
        }
        result[sym] = rules2.uniq
      }
      result
    end

    def self.expand_noalt_rules(syntax)
      noalt_syms = {}
      syntax.each {|sym, rules|
        if rules.length == 1
          noalt_syms[sym] = true
        end
      }
      result = {}
      syntax.each {|sym, rules|
        rules2 = []
        rules.each {|rhs|
          rhs2 = []
          rhs.each {|e|
            if noalt_syms[e]
              rhs2.concat syntax[e][0]
            else
              rhs2 << e
            end
          }
          rules2 << rhs2
        }
        result[sym] = rules2.uniq
      }
      result
    end

    def self.reorder_rules(syntax)
      result = {}
      syntax.each {|sym, rules|
        result[sym] = rules.sort_by {|rhs|
          [rhs.find_all {|e| Symbol === e }.length, rhs.length]
        }
      }
      result
    end

    def each_tree(sym, limit)
      generate_from_sym(sym, limit) {|_, tree|
        yield tree
      }
      nil
    end

    def each_string(sym, limit)
      generate_from_sym(sym, limit) {|_, tree|
        yield [tree].join('')
      }
      nil
    end

    def generate_from_sym(sym, limit, &b)
      return if limit < 0
      if String === sym
        yield limit, sym
      else
        rules = @syntax[sym]
        raise "undefined rule: #{sym}" if !rules
        rules.each {|rhs|
          if rhs.length == 1 || rules.length == 1
            limit1 = limit
          else
            limit1 = limit-1
          end
          generate_from_rhs(rhs, limit1, &b)
        }
      end
      nil
    end

    def generate_from_rhs(rhs, limit)
      return if limit < 0
      if rhs.empty?
        yield limit, []
      else
        generate_from_sym(rhs[0], limit) {|limit1, child|
          generate_from_rhs(rhs[1..-1], limit1) {|limit2, arr|
            yield limit2, [child, *arr]
          }
        }
      end
      nil
    end
  end

end