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