class SublimeDSL::Tools::Node

A node in the optimization of a Regexp matching a list of keywords.

Constants

NULL

The node representing the end of a string: an empty string with no child.

Attributes

children[R]

The child nodes.

start[R]

The start string.

Public Class Methods

new(start) click to toggle source

Creates a new node for the start string, with an empty list of children.

# File lib/sublime_dsl/tools/helpers.rb, line 39
def initialize(start)
  @start = start
  @children = []
end

Public Instance Methods

add_children(words) click to toggle source

Adds words to the children of the current node: the children of the current node are the unique initial letters of words, and the following letters are recurisvely added as grandchildren:

x = Node.new('')
x.add_children %w(a abc abd abde)
=> tree:
   ""
     "a"
       ""
       "b"
         "c"
           ""
         "d"
           ""
           "e"
             ""
# File lib/sublime_dsl/tools/helpers.rb, line 64
def add_children(words)
  words.group_by { |w| w[0] }.each_pair do |letter, list|
    if letter.nil?
      self.children << Node::NULL
    else
      n = Node.new(letter.dup)
      self.children << n
      n.add_children list.map { |w| w[1..-1] }
    end
  end
end
display_tree(indent = '') click to toggle source

The display tree for the current node.

# File lib/sublime_dsl/tools/helpers.rb, line 142
def display_tree(indent = '')
  return indent + start.inspect if children.empty?
  [ indent + start.inspect,
    children.map { |c| c.display_tree(indent+'  ') },
  ].join("\n")
end
reduce!() click to toggle source

Reduce the current node:

  • first reduce all children

  • then if there is only one child left:

    • append the child#start value to self#start

    • replace the children of self by the children of child

Example:

x = Node.new('')
x.add_children %w(abs addr addrlong airy allcomb allperm anyalnum anyalpha anycntrl)
x.reduce!
=> tree:
   "a"
     "bs"
     "ddr"
       ""
       "long"
     "iry"
     "ll"
       "comb"
       "perm"
     "ny"
       "al"
         "num"
         "pha"
       "cntrl"
# File lib/sublime_dsl/tools/helpers.rb, line 101
def reduce!
  children.each(&:reduce!)
  if children.length == 1
    child = children.first
    @start << child.start
    @children = child.children
  end
end
to_re() click to toggle source

Converts the current node to a regular expression string:

x = Node.new('')
x.add_children %w(abs addr addrlong airy allcomb allperm anyalnum anyalpha anycntrl)
x.reduce!
x.to_re
=> 'a(bs|ddr(long)?|iry|ll(comb|perm)|ny(al(num|pha)|cntrl))'
# File lib/sublime_dsl/tools/helpers.rb, line 117
def to_re
  t, list = children.partition { |c| c == NULL }
  t = t.first
  start + (
    case list.length
    when 0
      ''
    when 1
      r = list.first.to_re
      r.length == 1 ? r : '(' + r + ')'
    else
      r = list.map(&:to_re)
      if r.all? { |s| s.length == 1 }
        '[' + r.join + ']'
      else
        '(' + r.join('|') + ')'
      end
    end
  ) + (
    ( t ? '?' : '' )
  )
end