This module is intended to supplement the regular set-handling features that arrays in Ruby have. It is more of an exercise than a real project, though anyone who finds it useful is of course welcome to use it.

Some features it adds are: Subset and superset operators; an "in" method added to Object so that any object can be tested for membership in a set; a powerset method; a constant Null set; and so on. Sets can hold any type, i.e., integers, strings, arrays, other sets, etc.

#
# Ruby set module
# Hal E. Fulton
# (C) 1999-2000 (See Ruby license)
#

class Object   # Why has to be outside module?
  def in(x)
    x.include? self
  end
end

module Sets

class Array
  alias old_inspect inspect
  def inspect
    "["+(self*",")+"]"
  end
  def to_s
    inspect
  end
end

def Set(*elts)
  Set.new(*elts)
end

def Internal_set(*elts)
  Set.new(*elts)
end


class Set

  attr_reader   :elts
  attr_accessor :delim
  attr_accessor :sep

  U = [[]]    # in a later Ruby, this should be a class variable.

  def initialize(*elts)
    @delim = "{}"
    @sep = ", "
    @elts = Array.new
    @elts = elts.dup
    @elts.uniq!
    @elts.sort! {|x,y| x.to_s <=> y.to_s}  # Not really necessary
    if caller[1] =~ /Set/
      U[0] |= @elts
    end
  end

  def |(other)
    Set(*(@elts | other.elts))
  end

  def &(other)
    Set(*(@elts & other.elts))
  end

  def -(other)
    Set(*(@elts - other.elts))
  end

  def <(other)
    self.elts.each  {|x| if (!(other.elts.include? x)); return false; end }
    true
  end

  def >(other)
    other < self
  end

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

  def <=(other)
    self < other || self == other
  end

  def >=(other)
    self > other || self == other
  end

  def include?(elt)
    @elts.include? elt
  end

  def union!(other)
    @elts |= other.elts
    self
  end

  def intersection!(other)
    @elts &= other.elts
    self
  end

  def difference!(other)
    @elts -= other.elts
    self
  end

  def -@
    @U - self
  end

  def *(other)
    result = Array.new
    @elts.each do |x|
      other.elts.each do |y|
        $sum += 1
        result << [x, y]
      end
    end
    Internal_set(*result)
  end

  def powerset
    lim=(2**@elts.size)-1
    ps = (0..lim).collect {|x| []}
    @elts.each_index do |i| 
      a=(2**i)
      b=2**(i+1)-1
      j=0
      while j < lim
        for j in j+a..j+b
          ps[j] += [@elts[i]]
        end
        j += 1
      end
    end
    Internal_set(*ps)
  end

  def empty?
    @elts.size==0
  end

  def size
    @elts.size
  end

  def Set.universe
    Internal_set(*U[0])
  end

  def min
    @elts.min
  end

  def max
    @elts.max
  end


  alias union         |
  alias +             &

  alias intersection  &
  alias inter         &
  alias inter!        intersection!
  # alias *             &

  alias difference    -              # Set difference
  alias diff          -
  alias diff!         difference!

  alias subset        <
  alias superset      >

  alias contains?     include?
  alias null?         empty?

  alias cardinality   size
  alias card          size

  def inspect
    s=""
    @elts.each_index { |x|
      z = @elts[x].inspect
      case x
        when 0
          s += z+(@elts.size>1?@sep:"")
        when 1..(@elts.size-2)
          s += z+@sep
        when (@elts.size-1)
          s += z
      end
    }
    s = @delim[0..0] + s + @delim[1..1]
  end

  def to_s
    inspect
  end

  def size
    @elts.size
  end

  def each
    @elts.each {|x| yield x}
  end

  def to_a
    @elts
  end

end  # class

  Null = Set.new()


end  # module


###################################

if __FILE__ == $0      # Test code below...

include Sets

####
# Run a function named test_TESTCASE and report pass/fail
####

def run(testcase)
  result = eval("test_"+testcase)
  passfail = result ? "passed" : "FAILED..."
  print "Test #{'%10s' % testcase} #{passfail}\n"
end

####
# Test functions...
####

def test_output_01
  x = Set(1,2,3)
  x.inspect == "{1, 2, 3}"
end

def test_output_02
  x = Set(1,2,3)
  x.to_s == "{1, 2, 3}"
end

def test_output_03
  x = Set(1,2,3)
  x.sep = ";"
  x.to_s == "{1;2;3}"
end

def test_output_04
  x = Set(1,2,3)
  x.delim = "<>"
  x.to_s == "<1, 2, 3>"
end

def test_output_05
  Null.to_s == "{}"
end

def test_output_06
  words = %w[alpha beta gamma delta epsilon]
  wordset = Set(*words)
  str = wordset.inspect # '{"alpha", "beta", "gamma", "delta", "epsilon"}'
  first3 = str.include?("alpha") && str.include?("beta") && str.include?("gamma")
  last2 = str.include?("delta") && str.include?("epsilon")
  counts = str.count("\"")==10 && str.count(",")==4 && str[0..0]=="{" && str[-1..-1]=="}"
  first3 && last2 && counts
end

def test_member_01
  x = Set(2,3,4)
  (2.in x) && (3.in x) && (4.in x)
end

def test_member_02
  x = Set(2,3,4)
  !(1.in x) && !(5.in x)
end

def test_member_03
  x = Set(2,3,4)
  x.include? 3
end

def test_equal_01
  x = Set(1,2,3)
  x == Set(3,2,1)
end

def test_equal_02
  Set(1,2,3) != Set(1,2,4)
end

def test_equal_03
  Set(1,2,3) != Set()
end

def test_null_01
  Null.empty?
end

def test_null_02
  Null.size == 0
end

def test_null_03
  Null.cardinality == 0
end

def test_null_04
  Null < Null
end

def test_subset_01
  Set(1,2,3) < Set(1,2,3)
end

def test_subset_02
  Set(1,2,3) < Set(1,2,3,4)
end

def test_subset_03
  Set() < Set(1,2,3)
end

def test_subset_04
  ! (Set(1,2,4) < Set(1,2,3))
end

def test_subset_05
  Set(1,2) <= Set(1,2,3)
end

def test_subset_06
  ! (Set(1,2,4) <= Set(1,2,3))
end

def test_subset_07
  ! (Set(1,2) >= Set(1,2,3))
end

def test_subset_08
  Set(1,2,3) >= Set(1,2)
end



####
# "Main"
####

run "output_01"
run "output_02"
run "output_03"
run "output_04"
run "output_05"
run "output_06"

run "member_01"
run "member_02"
run "member_03"

run "equal_01"
run "equal_02"
run "equal_03"

run "null_01"
run "null_02"
run "null_03"
run "null_04"

run "subset_01"
run "subset_02"
run "subset_03"
run "subset_04"
run "subset_05"
run "subset_06"
run "subset_07"
run "subset_08"

# More to come...

end  # if __FILE__

Back to my Ruby page