class RegexpTrie

# File lib/regexp_trie.rb, line 14
def initialize(*strings)
  @head = {}

  strings.flatten.each do |str|
    add(str)
  end
end

# File lib/regexp_trie.rb, line 10
def self.union(*strings, option: nil)
  new(*strings).to_regexp(option)
end

# File lib/regexp_trie.rb, line 23
def add(str)
  return self if !str || str.empty?

  entry = @head
  str.each_char do |c|
    entry[c] ||= {}
    entry = entry[c]
  end
  entry[:end] = nil
  self
end

# File lib/regexp_trie.rb, line 45
def to_regexp(option = nil)
  Regexp.new(to_source, option)
end

# File lib/regexp_trie.rb, line 36
def to_source
  if @head.empty?
    Regexp.union.source
  else
    build(@head)
  end
end

# File lib/regexp_trie.rb, line 51
def build(entry)
  return nil if entry.include?(:end) && entry.size == 1

  alt = []
  cc = []
  q = false

  entry.keys.each do |c|
    if entry[c]
      recurse = build(entry[c])
      qc = Regexp.quote(c)
      if recurse
        alt.push(qc + recurse)
      else
        cc.push(qc)
      end
    else
      q = true
    end
  end

  cconly = alt.empty?
  unless cc.empty?
    alt.push(cc.size == 1 ? cc.first : "[#{cc.join('')}]")
  end

  result = alt.size == 1 ? alt.first : "(?:#{alt.join('|')})"
  if q
    if cconly
      "#{result}?"
    else
      "(?:#{result})?"
    end
  else
    result
  end
end