Class: NatSet

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

Overview

NatSet

NatSet represents a set of naturals - non-negative integers.

class methods

— NatSet.empty — NatSet.universal — NatSet.new(integer_or_range, …)

methods

— empty? — universal? — open? — singleton? — self == other — self === other — eql?(other) — hash — ~self — self + other — self - other — self & other

— split_each(ns, …) {|region, *nss| … } — split(ns, …)

— min — max

— each_range {|range| … }

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*es) ⇒ NatSet

Returns a new instance of NatSet.



83
84
85
 
# File 'lib/natset.rb', line 83

def initialize(*es)
  @es = es
end

Instance Attribute Details

#es ⇒ Object (readonly)

Returns the value of attribute es.



86
87
88
 
# File 'lib/natset.rb', line 86

def es
  @es
end

Class Method Details

._new ⇒ Object 



37
 
# File 'lib/natset.rb', line 37

alias _new new

.empty ⇒ Object 



40
41
42
 
# File 'lib/natset.rb', line 40

def NatSet.empty
  self._new
end

.new(*es) ⇒ Object 



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
 
# File 'lib/natset.rb', line 48

def NatSet.new(*es)
  r = self.empty
  es.each {|e|
    if String === e
      e = e.ord
    end
    case e
    when Range
      if String === e.begin
        e = Range.new(e.begin.ord, e.end.ord, e.exclude_end?)
      end
	unless Integer === e.begin && 0 <= e.begin
 raise ArgumentError.new("bad value for #{self}.new: #{e}")
	end
      if e.end < 0
 r += self._new(e.begin)
	elsif e.exclude_end?
 r += self._new(e.begin, e.end)
	else
 r += self._new(e.begin, e.end+1)
	end
    when Integer
	unless 0 <= e
 raise ArgumentError.new("bad value for #{self}.new: #{e}")
	end
	r += self._new(e, e+1)
    when NatSet
	r += e
    else
      raise ArgumentError.new("bad value for #{self}.new: #{e}")
    end
  }
  r
end

.universal ⇒ Object 



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

def NatSet.universal
  self._new(0)
end

Instance Method Details

#==(other) ⇒ Object Also known as: ===, eql? 



108
109
110
 
# File 'lib/natset.rb', line 108

def ==(other)
  @es == other.es
end

#complement ⇒ Object Also known as: ~ 



118
119
120
121
122
123
124
125
126
 
# File 'lib/natset.rb', line 118

def complement
  if @es.empty?
    self.class.universal
  elsif @es[0] == 0
    self.class._new(*@es[1..-1])
  else
    self.class._new(0, *@es)
  end
end

#each_range ⇒ Object

each_range iterates on continuous ranges of the set from smallest to largest. For each range, it yields Range object which represent it. For last range in open set, the end of the object is -1. For all Range objects it yields, exclude_end? is true.



258
259
260
261
262
263
264
265
266
267
268
 
# File 'lib/natset.rb', line 258

def each_range
  (0...@es.length).step(2) {|i|
    e1 = @es[i]
    if i+1 == @es.length
      yield e1..-1
    else
      e2 = @es[i+1]
      yield e1..(e2-1)
    end
  }
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


88
89
90
 
# File 'lib/natset.rb', line 88

def empty?
  @es.empty?
end

#hash ⇒ Object 



114
115
116
 
# File 'lib/natset.rb', line 114

def hash
  @es.hash
end

#inspect ⇒ Object 



286
287
288
289
 
# File 'lib/natset.rb', line 286

def inspect
  require 'pp'
  PP.singleline_pp(self, '')
end

#intersect(other) ⇒ Object Also known as: & 



141
142
143
 
# File 'lib/natset.rb', line 141

def intersect(other)
  other.intersect_natset(self)
end

#intersect_natset(natset) ⇒ Object 



146
147
148
149
150
 
# File 'lib/natset.rb', line 146

def intersect_natset(natset)
  return self if self.empty? || natset.universal?
  return natset if natset.empty? || self.universal?
  merge(natset) {|a, b| a && b}
end

#max ⇒ Object

max returns a maximum element of the set. It returns nil if the set has no maximum element, i.e. the set is open or has no element.



246
247
248
249
250
251
252
 
# File 'lib/natset.rb', line 246

def max
  if @es.empty? || open?
    nil
  else
    @es[-1] - 1
  end
end

#merge(other) ⇒ Object 



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/natset.rb', line 166

def merge(other)
  es1 = @es.dup
  es2 = other.es.dup
  es0 = []
  bool1 = bool2 = bool0 = false
  s = 0
  while !es1.empty? || !es2.empty?
    if es2.empty? || !es1.empty? && es1[0] < es2[0]
	e = es1.shift
	if s < e && bool0 != yield(bool1, bool2)
 es0 << s
 bool0 = !bool0
	end
	s = e
	bool1 = !bool1
    elsif es1.empty? || !es2.empty? && es1[0] > es2[0]
	e = es2.shift
	if s < e && bool0 != yield(bool1, bool2)
 es0 << s
 bool0 = !bool0
	end
	s = e
	bool2 = !bool2
    else
	e = es1.shift
	es2.shift
	if s < e && bool0 != yield(bool1, bool2)
 es0 << s
 bool0 = !bool0
	end
	s = e
	bool1 = !bool1
	bool2 = !bool2
    end
  end
  if bool0 != yield(bool1, bool2)
    es0 << s
  end
  self.class._new(*es0)
end

#min ⇒ Object

min returns a minimum element of the set. It returns nil if the set has no minimum element, i.e. the set has no element.



235
236
237
238
239
240
241
 
# File 'lib/natset.rb', line 235

def min
  if @es.empty?
    nil
  else
    @es[0]
  end
end

#open? ⇒ Boolean

Returns:

  • (Boolean) 


96
97
98
 
# File 'lib/natset.rb', line 96

def open?
  @es.length & 1 != 0
end

#pretty_print(pp) ⇒ Object 



270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
 
# File 'lib/natset.rb', line 270

def pretty_print(pp)
  pp.object_group(self) {
    pp.text ':'
    each_range {|r|
	pp.breakable
      if r.end == -1
        pp.text "#{r.begin}..inf"
      elsif r.begin == r.end
        pp.text r.begin.to_s
      else
        pp.text "#{r.begin}..#{r.end}"
      end
    }
  }
end

#singleton? ⇒ Boolean

Returns:

  • (Boolean) 


100
101
102
103
104
105
106
 
# File 'lib/natset.rb', line 100

def singleton?
  if @es.length == 2 && @es[0] == @es[1] - 1
    @es[0]
  else
    nil
  end
end

#split(*natsets) ⇒ Object 



226
227
228
229
230
 
# File 'lib/natset.rb', line 226

def split(*natsets)
  result = []
  split_each(*natsets) {|r| result << r}
  result
end

#split_each(*natsets) ⇒ Object 



207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 
# File 'lib/natset.rb', line 207

def split_each(*natsets)
  if natsets.empty?
    yield [self]
  else
    current = natsets.pop
    
    a = self - current
    unless a.empty?
      a.split_each(*natsets) {|nss| yield nss}
    end
    
    a = self & current
    unless a.empty?
      a.split_each(*natsets) {|nss| nss.push current; yield nss}
    end
  end
  nil
end

#subtract(other) ⇒ Object Also known as: - 



152
153
154
 
# File 'lib/natset.rb', line 152

def subtract(other)
  other.subtract_natset(self)
end

#subtract_natset(natset) ⇒ Object

natset - self



157
158
159
160
161
162
163
164
 
# File 'lib/natset.rb', line 157

def subtract_natset(natset) # natset - self
  # Since double dispatch *inverses* a receiver and an argument, 
  # condition should be inversed.
  return natset if self.empty? || natset.empty?
  return NatSet.empty if self.universal?
  return ~self if natset.universal?
  merge(natset) {|a, b| !a && b}
end

#union(other) ⇒ Object Also known as: +, | 



129
130
131
 
# File 'lib/natset.rb', line 129

def union(other)
  other.union_natset(self)
end

#union_natset(natset) ⇒ Object 



135
136
137
138
139
 
# File 'lib/natset.rb', line 135

def union_natset(natset)
  return self if natset.empty? || self.universal?
  return natset if self.empty? || natset.universal?
  merge(natset) {|a, b| a || b}
end

#universal? ⇒ Boolean

Returns:

  • (Boolean) 


92
93
94
 
# File 'lib/natset.rb', line 92

def universal?
  @es == [0]
end