class NatSet
NatSet
¶ ↑
NatSet
represents a set of naturals - non-negative integers.
class methods¶ ↑
Attributes
es[R]
Public Class Methods
empty()
click to toggle source
# File lib/natset.rb, line 40 def NatSet.empty self._new end
new(*es)
click to toggle source
# 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
Also aliased as: _new
new(*es)
click to toggle source
# File lib/natset.rb, line 83 def initialize(*es) @es = es end
universal()
click to toggle source
# File lib/natset.rb, line 44 def NatSet.universal self._new(0) end
Public Instance Methods
==(other)
click to toggle source
# File lib/natset.rb, line 108 def ==(other) @es == other.es end
complement()
click to toggle source
# 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
Also aliased as: ~
each_range() { |e1..-1| ... }
click to toggle source
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.
# 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?()
click to toggle source
# File lib/natset.rb, line 88 def empty? @es.empty? end
hash()
click to toggle source
# File lib/natset.rb, line 114 def hash @es.hash end
inspect()
click to toggle source
# File lib/natset.rb, line 286 def inspect require 'pp' PP.singleline_pp(self, '') end
intersect(other)
click to toggle source
# File lib/natset.rb, line 141 def intersect(other) other.intersect_natset(self) end
Also aliased as: &
intersect_natset(natset)
click to toggle source
# 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()
click to toggle source
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.
# File lib/natset.rb, line 246 def max if @es.empty? || open? nil else @es[-1] - 1 end end
merge(other) { |bool1, bool2| ... }
click to toggle source
# 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()
click to toggle source
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.
# File lib/natset.rb, line 235 def min if @es.empty? nil else @es[0] end end
open?()
click to toggle source
# File lib/natset.rb, line 96 def open? @es.length & 1 != 0 end
pretty_print(pp)
click to toggle source
# 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?()
click to toggle source
# 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)
click to toggle source
# File lib/natset.rb, line 226 def split(*natsets) result = [] split_each(*natsets) {|r| result << r} result end
split_each(*natsets) { |self| ... }
click to toggle source
# 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)
click to toggle source
# File lib/natset.rb, line 152 def subtract(other) other.subtract_natset(self) end
Also aliased as: -
subtract_natset(natset)
click to toggle source
# 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)
click to toggle source
# File lib/natset.rb, line 129 def union(other) other.union_natset(self) end
union_natset(natset)
click to toggle source
# 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?()
click to toggle source
# File lib/natset.rb, line 92 def universal? @es == [0] end