class RegexpTrie

Constants

VERSION

Public Class Methods

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

  strings.flatten.each do |str|
    add(str)
  end
end
union(*strings, option: nil) click to toggle source

@param [Array<String>] strings Set of patterns @param [Fixnum,Boolean] option The second argument of Regexp.new() @return [Regexp]

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

Public Instance Methods

add(str) click to toggle source

@param [String] str

# 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
to_regexp(option = nil) click to toggle source

@return [Regexp]

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

@return [String]

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

Private Instance Methods

build(entry) click to toggle source
# 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