Class: ToknInternal::CodeSet

Inherits:
Object
  • Object
show all
Defined in:
lib/tokn/code_set.rb

Overview

A CodeSet is an ordered set of character or token codes that are used as labels on DFA edges.

In addition to unicode character codes 0…0x10ffff, they also represent epsilon transitions (-1), or token identifiers ( < -1).

Each CodeSet is represented as an array with 2n elements; each pair represents a closed lower and open upper range of values.

Thus a value x is within the set [a1,a2,b1,b2,..] iff (a1 <= x < a2) or (b1 <= x < b2) or …

Instance Method Summary collapse

Constructor Details

#initialize(lower = nil, upper = nil) ⇒ CodeSet

Initialize set; optionally add an initial contiguous range



29
30
31
32
33
34
 
# File 'lib/tokn/code_set.rb', line 29

def initialize(lower = nil, upper = nil)
  @elem = []
  if lower
    add(lower,upper)
  end
end

Instance Method Details

#add(lower, upper = nil) ⇒ Object

Add a contiguous range of values to the set

Parameters:

  • lower —

    min value in range

  • upper (defaults to: nil) —

    one plus max value in range



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
 
# File 'lib/tokn/code_set.rb', line 72

def add(lower, upper = nil)
  if not upper
    upper = lower + 1
  end
  
  if lower >= upper
    raise RangeError
  end
  
  newSet = [] 
  i = 0
  while i < @elem.size and @elem[i] < lower
    newSet.push(@elem[i])
    i += 1
  end 
  
  if (i & 1) == 0
    newSet.push(lower)
  end
  
  while i < @elem.size and @elem[i] <= upper
    i += 1
  end
  
  if (i & 1) == 0
    newSet.push(upper)
  end
  
  while i < @elem.size 
    newSet.push(@elem[i])
    i += 1
  end
  
  @elem = newSet
  
end

#addSet(s) ⇒ Object

Add every value from another CodeSet to this one



174
175
176
177
178
179
180
 
# File 'lib/tokn/code_set.rb', line 174

def addSet(s)
  sa = s.array
  
  (0 ... sa.length).step(2) {
    |i| add(sa[i],sa[i+1])
  }
end

#array ⇒ Object

Get the array containing the code set range pairs



44
45
46
 
# File 'lib/tokn/code_set.rb', line 44

def array
  @elem
end

#cardinality ⇒ Object

Determine how many distinct values are represented by this set



297
298
299
300
301
302
303
304
305
 
# File 'lib/tokn/code_set.rb', line 297

def cardinality
  c = 0
  i = 0
  while i < @elem.length
    c += @elem[i+1] - @elem[i]
    i += 2
  end
  c
end

#contains?(val) ⇒ Boolean

Determine if this set contains a particular value

Returns:

  • (Boolean) 


183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
# File 'lib/tokn/code_set.rb', line 183

def contains?(val)
  ret = false
  i = 0
  while i < @elem.size
    if val < @elem[i]
      break
    end 
    if val < @elem[i+1]
      ret = true
      break
    end
    i += 2
  end  
  
  ret
  
end

#difference(s) ⇒ Object

Calculate difference of this set minus another



158
159
160
 
# File 'lib/tokn/code_set.rb', line 158

def difference(s)
  combineWith(s, 'd')
end

#difference!(s) ⇒ Object

Replace this set with itself minus another



153
154
155
 
# File 'lib/tokn/code_set.rb', line 153

def difference!(s)
  setTo(difference(s))
end

#empty? ⇒ Boolean

Determine if this set is empty

Returns:

  • (Boolean) 


309
310
311
 
# File 'lib/tokn/code_set.rb', line 309

def empty?
  @elem.empty?
end

#eql?(other) ⇒ Boolean

Determine if this set is equivalent to another, by comparing the contained arrays

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/tokn/code_set.rb', line 63

def eql?(other)
  @elem == other.array
end

#hash ⇒ Object

Get hash code; just uses hash code of the contained array



56
57
58
 
# File 'lib/tokn/code_set.rb', line 56

def hash
  @elem.hash
end

#inspect ⇒ Object

Calls to_s



224
225
226
 
# File 'lib/tokn/code_set.rb', line 224

def inspect
  to_s
end

#intersect(s) ⇒ Object

Calculate the intersection of this set and another



163
164
165
 
# File 'lib/tokn/code_set.rb', line 163

def intersect(s)
  combineWith(s, 'i')
end

#intersect!(s) ⇒ Object

Set this set equal to its intersection with another



169
170
171
 
# File 'lib/tokn/code_set.rb', line 169

def intersect!(s)
  setTo(intersect(s))
end

#makeCopy ⇒ Object

Construct a copy of this set



21
22
23
24
25
 
# File 'lib/tokn/code_set.rb', line 21

def makeCopy
  c = CodeSet.new
  c.setTo(self)
  c
end

#negate(lower = 0, upper = CODEMAX) ⇒ Object

Negate the inclusion of a contiguous range of values

Parameters:

  • lower (defaults to: 0) —

    min value in range

  • upper (defaults to: CODEMAX) —

    one plus max value in range



256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/tokn/code_set.rb', line 256

def negate(lower = 0, upper =  CODEMAX)
  s2 = CodeSet.new(lower,upper)
  if lower >= upper
    raise RangeError
  end
  
  newSet = [] 
  i = 0
  while i < @elem.size and @elem[i] <= lower
    newSet.push(@elem[i])
    i += 1
  end 
  
  if i > 0 and newSet[i-1] == lower
    newSet.pop
  else
    newSet.push(lower)
  end
  
  while i < @elem.size and @elem[i] <= upper
    newSet.push(@elem[i])
    i += 1
  end 
  
  
  if newSet.length > 0 and newSet.last == upper
    newSet.pop
  else
    newSet.push(upper)
  end
  
  while i < @elem.size 
    newSet.push(@elem[i])
    i += 1
  end 
  
  @elem = newSet
  
end

#remove(lower, upper = nil) ⇒ Object

Remove a contiguous range of values from the set

Parameters:

  • lower —

    min value in range

  • upper (defaults to: nil) —

    one plus max value in range



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/tokn/code_set.rb', line 114

def remove(lower, upper = nil)
  if not upper
    upper = lower + 1
  end
  
  if lower >= upper
    raise RangeError
  end
  
  newSet = [] 
  i = 0
  while i < @elem.size and @elem[i] < lower
    newSet.push(@elem[i])
    i += 1
  end 
  
  if (i & 1) == 1
    newSet.push(lower)
  end
  
  while i < @elem.size and @elem[i] <= upper
    i += 1
  end
  
  if (i & 1) == 1
    newSet.push(upper)
  end
  
  while i < @elem.size 
    newSet.push(@elem[i])
    i += 1
  end
  
  setArray(newSet)
  
end

#setArray(a) ⇒ Object

Replace this set’s array

Parameters:

  • a —

    array to point to (does not make a copy of it)



51
52
53
 
# File 'lib/tokn/code_set.rb', line 51

def setArray(a)
  @elem = a
end

#setTo(otherSet) ⇒ Object

Replace this set with a copy of another



38
39
40
 
# File 'lib/tokn/code_set.rb', line 38

def setTo(otherSet)
  @elem.replace(otherSet.array)  
end

#to_s ⇒ Object

Get string representation of set, treating them (where possible) as printable ASCII characters



204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/tokn/code_set.rb', line 204

def to_s
  s = ''
  i = 0
  while i < @elem.size
    if s.size
      s += ' '
    end
    
    lower = @elem[i]
    upper = @elem[i+1]
    s += dbStr(lower)
    if upper != 1+lower
      s += '..' + dbStr(upper-1)
    end
    i += 2
  end
  return s
end

#to_s_alt ⇒ Object

Get string representation of set, treating them as integers



231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
 
# File 'lib/tokn/code_set.rb', line 231

def to_s_alt
  s = ''
  i = 0
  while i < @elem.size
    if s.length > 0
      s += ' '
    end
    low = @elem[i]
    upr = @elem[i+1]
    s += low.to_s
    if upr > low+1
      s += '..'
      s += (upr-1).to_s
    end
    i += 2
  end
  return s
end