Class: OSC::Pattern

Inherits:
String show all
Defined in:
lib/osc/pattern.rb

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from String

#broken_unpack, #unpack

Constructor Details

#initialize(s) ⇒ Pattern

Create an OSC pattern from a string or (experimental) from a Regex.



5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
# File 'lib/osc/pattern.rb', line 5

def initialize(s)
  case s
  when Regexp # This is experimental
   s = Regexp.source s
  	s.gsub! /(\\\\)*\[^\/\]\*/, "\1*"
  	s.gsub! /(\\\\)*\[^\/\]/, "\1?"
  	s.gsub! /(\\\\)*\[^/, "\1[!"
  	s.gsub! /(\\\\)*\(/, "\1{"
  	s.gsub! /(\\\\)*\|/, "\1,"
  	s.gsub! /(\\\\)*\)/, "\1}"
  	s.gsub! /\\\\/, "\\"
  end
  super s
end

Class Method Details

.intersect?(s1, s2) ⇒ Boolean

Do these two patterns intersect? – This might be improved by following the (much simpler, but related) algorithm here:

groups.google.com/group/comp.theory/browse_frm/thread/f33e033269bd5ab0/c87e19081f45454c?lnk=st&q=regular+expression+intersection&rnum=1&hl=en#c87e19081f45454c

That is, convert each regexp into an NFA, then generate the set of valid state pairs, then check if the pair of final states is included. That’s basically what I’m doing here, but I’m not generating all the state pairs, I’m just doing a search. My way may be faster and/or smaller, or it may not. My initial feeling is that it is faster since we’re basically doing a depth-first search and OSC patterns are going to tend to be fairly simple. Still it might be a fun experiment for the masochistic.

Returns:

  • (Boolean) 


48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/osc/pattern.rb', line 48

def self.intersect?(s1,s2)
  r = /\*|\?|\[[^\]]*\]|\{[^\}]*\}|./
  a = s1.to_s.scan r
  b = s2.to_s.scan r
  q = [[a,b]]
  until q.empty?
	q.uniq!
	a,b = q.pop
	a = a.dup
	b = b.dup

	return true if a.empty? and b.empty?
	next if a.empty? or b.empty?

	x,y = a.shift, b.shift

	# branch {}
	if x =~ /^\{/
	  x.scan /[^\{\},]+/ do |x|
 q.push [x.scan(/./)+a,[y]+b]
	  end
	  next
	end
	if y =~ /^\{/
	  y.scan /[^\{\},]+/ do |y|
 q.push [[x]+a,y.scan(/./)+b]
	  end
	  next
	end

	# sort
	if y =~ /^\[/
	  x,y = y,x
	  a,b = b,a
	end
	if y =~ /^(\*|\?)/
	  x,y = y,x
	  a,b = b,a
	end

	# match
	case x
	when '*'
	  unless y == '/'
 q.push [a,b]
 q.push [[x]+a,b]
	  end
	  if y == '*'
 q.push [a,[y]+b]
 q.push [[x]+a,b]
	  end
	when '?'
	  q.push [a,b] unless y == '/'
	  q.push [a,[y]+b] if y == '*'
	when /^\[/
	  xinv = (x[1] == ?!)
	  yinv = (y =~ /^\[!/)
	  x = x[(xinv ? 2 : 1)..-2].scan(/./).to_set
	  if y =~ /^\[/
 y = y[(yinv ? 2 : 1)..-2].scan(/./).to_set
	  else
 y = [y].to_set
	  end

	  # simplifying assumption: nobody in their right mind is going to do
	  # [^everyprintablecharacter]
	  if xinv and yinv
 q.push [a,b]
	  elsif xinv and not yinv
 q.push [a,b] unless (y-x).empty?
	  elsif not xinv and yinv
 q.push [a,b] unless (x-y).empty?
	  else
 q.push [a,b] unless (x&y).empty?
	  end
	else
	  q.push [a,b] if x == y
	end
  end

  false # no intersection
end

Instance Method Details

#regexp ⇒ Object

Return a Regex representing this pattern



21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/osc/pattern.rb', line 21

def regexp
  s = Regexp.escape self
  s.gsub! /\\\?/, '[^/]'
  s.gsub! /\\\*/, '[^/]*'
  s.gsub! /\\\[!/, '[^'
  s.gsub! /\\\]/, ']'
  s.gsub! /\\\{/, '('
  s.gsub! /,/, '|'
  s.gsub! /\\\}/, ')'
  Regexp.new s
end