class NatSet

NatSet

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

class methods

Attributes

es[R]

Public Class Methods

_new(*es)
Alias for: new
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)
Alias for: intersect
+(other)
Alias for: union
-(other)
Alias for: subtract
==(other) click to toggle source
# File lib/natset.rb, line 108
def ==(other)
  @es == other.es
end
Also aliased as: ===, eql?
===(other)
Alias for: ==
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
eql?(other)
Alias for: ==
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
Also aliased as: +, |
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
|(other)
Alias for: union
~()
Alias for: complement