Class: SublimeDSL::Tools::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/sublime_dsl/tools/helpers.rb

Overview

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

Constant Summary collapse

NULL =

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

self.new('')

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(start) ⇒ Node

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



39
40
41
42
 
# File 'lib/sublime_dsl/tools/helpers.rb', line 39

def initialize(start)
  @start = start
  @children = []
end

Instance Attribute Details

#children ⇒ Object (readonly)

The child nodes.



36
37
38
 
# File 'lib/sublime_dsl/tools/helpers.rb', line 36

def children
  @children
end

#start ⇒ Object (readonly)

The start string.



33
34
35
 
# File 'lib/sublime_dsl/tools/helpers.rb', line 33

def start
  @start
end

Instance Method Details

#add_children(words) ⇒ Object

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"
             ""



64
65
66
67
68
69
70
71
72
73
74
 
# 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 = '') ⇒ Object

The display tree for the current node.



142
143
144
145
146
147
 
# 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! ⇒ Object

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"



101
102
103
104
105
106
107
108
 
# 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 ⇒ Object

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))'



117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# 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