Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

1350 lines (1130 sloc) 29.648 kb
#!/usr/bin/env ruby
#--
# set.rb - defines the Set class
#++
# Copyright (c) 2002-2008 Akinori MUSHA <knu@iDaemons.org>
#
# Documentation by Akinori MUSHA and Gavin Sinclair.
#
# All rights reserved. You can redistribute and/or modify it under the same
# terms as Ruby.
#
# $Id: set.rb 26648 2010-02-11 17:38:05Z knu $
#
# == Overview
#
# This library provides the Set class, which deals with a collection
# of unordered values with no duplicates. It is a hybrid of Array's
# intuitive inter-operation facilities and Hash's fast lookup. If you
# need to keep values ordered, use the SortedSet class.
#
# The method +to_set+ is added to Enumerable for convenience.
#
# See the Set and SortedSet documentation for examples of usage.
#
# Set implements a collection of unordered values with no duplicates.
# This is a hybrid of Array's intuitive inter-operation facilities and
# Hash's fast lookup.
#
# The equality of each couple of elements is determined according to
# Object#eql? and Object#hash, since Set uses Hash as storage.
#
# Set is easy to use with Enumerable objects (implementing +each+).
# Most of the initializer methods and binary operators accept generic
# Enumerable objects besides sets and arrays. An Enumerable object
# can be converted to Set using the +to_set+ method.
#
# == Example
#
# require 'set'
# s1 = Set.new [1, 2] # -> #<Set: {1, 2}>
# s2 = [1, 2].to_set # -> #<Set: {1, 2}>
# s1 == s2 # -> true
# s1.add("foo") # -> #<Set: {1, 2, "foo"}>
# s1.merge([2, 6]) # -> #<Set: {6, 1, 2, "foo"}>
# s1.subset? s2 # -> false
# s2.subset? s1 # -> true
#
# == Contact
#
# - Akinori MUSHA <knu@iDaemons.org> (current maintainer)
#
class Set
include Enumerable
# Creates a new set containing the given objects.
def self.[](*ary)
new(ary)
end
# Creates a new set containing the elements of the given enumerable
# object.
#
# If a block is given, the elements of enum are preprocessed by the
# given block.
def initialize(enum = nil, &block) # :yields: o
@hash ||= Hash.new
enum.nil? and return
if block
do_with_enum(enum) { |o| add(block[o]) }
else
merge(enum)
end
end
def do_with_enum(enum, &block)
if enum.respond_to?(:each_entry)
enum.each_entry(&block)
elsif enum.respond_to?(:each)
enum.each(&block)
else
raise ArgumentError, "value must be enumerable"
end
end
private :do_with_enum
# Copy internal hash.
def initialize_copy(orig)
@hash = orig.instance_eval{@hash}.dup
end
def freeze # :nodoc:
super
@hash.freeze
self
end
def taint # :nodoc:
super
@hash.taint
self
end
def untaint # :nodoc:
super
@hash.untaint
self
end
# Returns the number of elements.
def size
@hash.size
end
alias length size
# Returns true if the set contains no elements.
def empty?
@hash.empty?
end
# Removes all elements and returns self.
def clear
@hash.clear
self
end
# Replaces the contents of the set with the contents of the given
# enumerable object and returns self.
def replace(enum)
if enum.class == self.class
@hash.replace(enum.instance_eval { @hash })
else
clear
merge(enum)
end
self
end
# Converts the set to an array. The order of elements is uncertain.
def to_a
@hash.keys
end
def flatten_merge(set, seen = Set.new)
set.each { |e|
if e.is_a?(Set)
if seen.include?(e_id = e.object_id)
raise ArgumentError, "tried to flatten recursive Set"
end
seen.add(e_id)
flatten_merge(e, seen)
seen.delete(e_id)
else
add(e)
end
}
self
end
protected :flatten_merge
# Returns a new set that is a copy of the set, flattening each
# containing set recursively.
def flatten
self.class.new.flatten_merge(self)
end
# Equivalent to Set#flatten, but replaces the receiver with the
# result in place. Returns nil if no modifications were made.
def flatten!
if detect { |e| e.is_a?(Set) }
replace(flatten())
else
nil
end
end
# Returns true if the set contains the given object.
def include?(o)
@hash.include?(o)
end
alias member? include?
# Returns true if the set is a superset of the given set.
def superset?(set)
set.is_a?(Set) or raise ArgumentError, "value must be a set"
return false if size < set.size
set.all? { |o| include?(o) }
end
# Returns true if the set is a proper superset of the given set.
def proper_superset?(set)
set.is_a?(Set) or raise ArgumentError, "value must be a set"
return false if size <= set.size
set.all? { |o| include?(o) }
end
# Returns true if the set is a subset of the given set.
def subset?(set)
set.is_a?(Set) or raise ArgumentError, "value must be a set"
return false if set.size < size
all? { |o| set.include?(o) }
end
# Returns true if the set is a proper subset of the given set.
def proper_subset?(set)
set.is_a?(Set) or raise ArgumentError, "value must be a set"
return false if set.size <= size
all? { |o| set.include?(o) }
end
# Calls the given block once for each element in the set, passing
# the element as parameter. Returns an enumerator if no block is
# given.
def each
block_given? or return enum_for(__method__)
@hash.each_key { |o| yield(o) }
self
end
# Adds the given object to the set and returns self. Use +merge+ to
# add many elements at once.
def add(o)
@hash[o] = true
self
end
alias << add
# Adds the given object to the set and returns self. If the
# object is already in the set, returns nil.
def add?(o)
if include?(o)
nil
else
add(o)
end
end
# Deletes the given object from the set and returns self. Use +subtract+ to
# delete many items at once.
def delete(o)
@hash.delete(o)
self
end
# Deletes the given object from the set and returns self. If the
# object is not in the set, returns nil.
def delete?(o)
if include?(o)
delete(o)
else
nil
end
end
# Deletes every element of the set for which block evaluates to
# true, and returns self.
def delete_if
block_given? or return enum_for(__method__)
to_a.each { |o| @hash.delete(o) if yield(o) }
self
end
# Deletes every element of the set for which block evaluates to
# false, and returns self.
def keep_if
block_given? or return enum_for(__method__)
to_a.each { |o| @hash.delete(o) unless yield(o) }
self
end
# Replaces the elements with ones returned by collect().
def collect!
block_given? or return enum_for(__method__)
set = self.class.new
each { |o| set << yield(o) }
replace(set)
end
alias map! collect!
# Equivalent to Set#delete_if, but returns nil if no changes were
# made.
def reject!
block_given? or return enum_for(__method__)
n = size
delete_if { |o| yield(o) }
size == n ? nil : self
end
# Equivalent to Set#keep_if, but returns nil if no changes were
# made.
def select!
block_given? or return enum_for(__method__)
n = size
keep_if { |o| yield(o) }
size == n ? nil : self
end
# Merges the elements of the given enumerable object to the set and
# returns self.
def merge(enum)
if enum.instance_of?(self.class)
@hash.update(enum.instance_variable_get(:@hash))
else
do_with_enum(enum) { |o| add(o) }
end
self
end
# Deletes every element that appears in the given enumerable object
# and returns self.
def subtract(enum)
do_with_enum(enum) { |o| delete(o) }
self
end
# Returns a new set built by merging the set and the elements of the
# given enumerable object.
def |(enum)
dup.merge(enum)
end
alias + | ##
alias union | ##
# Returns a new set built by duplicating the set, removing every
# element that appears in the given enumerable object.
def -(enum)
dup.subtract(enum)
end
alias difference - ##
# Returns a new set containing elements common to the set and the
# given enumerable object.
def &(enum)
n = self.class.new
do_with_enum(enum) { |o| n.add(o) if include?(o) }
n
end
alias intersection & ##
# Returns a new set containing elements exclusive between the set
# and the given enumerable object. (set ^ enum) is equivalent to
# ((set | enum) - (set & enum)).
def ^(enum)
n = Set.new(enum)
each { |o| if n.include?(o) then n.delete(o) else n.add(o) end }
n
end
# Returns true if two sets are equal. The equality of each couple
# of elements is defined according to Object#eql?.
def ==(other)
if self.equal?(other)
true
elsif other.instance_of?(self.class)
@hash == other.instance_variable_get(:@hash)
elsif other.is_a?(Set) && self.size == other.size
other.all? { |o| @hash.include?(o) }
else
false
end
end
def hash # :nodoc:
@hash.hash
end
def eql?(o) # :nodoc:
return false unless o.is_a?(Set)
@hash.eql?(o.instance_eval{@hash})
end
# Classifies the set by the return value of the given block and
# returns a hash of {value => set of elements} pairs. The block is
# called once for each element of the set, passing the element as
# parameter.
#
# e.g.:
#
# require 'set'
# files = Set.new(Dir.glob("*.rb"))
# hash = files.classify { |f| File.mtime(f).year }
# p hash # => {2000=>#<Set: {"a.rb", "b.rb"}>,
# # 2001=>#<Set: {"c.rb", "d.rb", "e.rb"}>,
# # 2002=>#<Set: {"f.rb"}>}
def classify # :yields: o
block_given? or return enum_for(__method__)
h = {}
each { |i|
x = yield(i)
(h[x] ||= self.class.new).add(i)
}
h
end
# Divides the set into a set of subsets according to the commonality
# defined by the given block.
#
# If the arity of the block is 2, elements o1 and o2 are in common
# if block.call(o1, o2) is true. Otherwise, elements o1 and o2 are
# in common if block.call(o1) == block.call(o2).
#
# e.g.:
#
# require 'set'
# numbers = Set[1, 3, 4, 6, 9, 10, 11]
# set = numbers.divide { |i,j| (i - j).abs == 1 }
# p set # => #<Set: {#<Set: {1}>,
# # #<Set: {11, 9, 10}>,
# # #<Set: {3, 4}>,
# # #<Set: {6}>}>
def divide(&func)
func or return enum_for(__method__)
if func.arity == 2
require 'tsort'
class << dig = {} # :nodoc:
include TSort
alias tsort_each_node each_key
def tsort_each_child(node, &block)
fetch(node).each(&block)
end
end
each { |u|
dig[u] = a = []
each{ |v| func.call(u, v) and a << v }
}
set = Set.new()
dig.each_strongly_connected_component { |css|
set.add(self.class.new(css))
}
set
else
Set.new(classify(&func).values)
end
end
InspectKey = :__inspect_key__ # :nodoc:
# Returns a string containing a human-readable representation of the
# set. ("#<Set: {element1, element2, ...}>")
def inspect
ids = (Thread.current[InspectKey] ||= [])
if ids.include?(object_id)
return sprintf('#<%s: {...}>', self.class.name)
end
begin
ids << object_id
return sprintf('#<%s: {%s}>', self.class, to_a.inspect[1..-2])
ensure
ids.pop
end
end
def pretty_print(pp) # :nodoc:
pp.text sprintf('#<%s: {', self.class.name)
pp.nest(1) {
pp.seplist(self) { |o|
pp.pp o
}
}
pp.text "}>"
end
def pretty_print_cycle(pp) # :nodoc:
pp.text sprintf('#<%s: {%s}>', self.class.name, empty? ? '' : '...')
end
end
#
# SortedSet implements a Set that guarantees that it's element are
# yielded in sorted order (according to the return values of their
# #<=> methods) when iterating over them.
#
# All elements that are added to a SortedSet must respond to the <=>
# method for comparison.
#
# Also, all elements must be <em>mutually comparable</em>: <tt>el1 <=>
# el2</tt> must not return <tt>nil</tt> for any elements <tt>el1</tt>
# and <tt>el2</tt>, else an ArgumentError will be raised when
# iterating over the SortedSet.
#
# == Example
#
# require "set"
#
# set = SortedSet.new([2, 1, 5, 6, 4, 5, 3, 3, 3])
# ary = []
#
# set.each do |obj|
# ary << obj
# end
#
# p ary # => [1, 2, 3, 4, 5, 6]
#
# set2 = SortedSet.new([1, 2, "3"])
# set2.each { |obj| } # => raises ArgumentError: comparison of Fixnum with String failed
#
class SortedSet < Set
@@setup = false
class << self
def [](*ary) # :nodoc:
new(ary)
end
def setup # :nodoc:
@@setup and return
module_eval {
# a hack to shut up warning
alias old_init initialize
remove_method :old_init
}
begin
require 'rbtree'
module_eval %{
def initialize(*args, &block)
@hash = RBTree.new
super
end
def add(o)
o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
super
end
alias << add
}
rescue LoadError
module_eval %{
def initialize(*args, &block)
@keys = nil
super
end
def clear
@keys = nil
super
end
def replace(enum)
@keys = nil
super
end
def add(o)
o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
@keys = nil
super
end
alias << add
def delete(o)
@keys = nil
@hash.delete(o)
self
end
def delete_if
block_given? or return enum_for(__method__)
n = @hash.size
super
@keys = nil if @hash.size != n
self
end
def keep_if
block_given? or return enum_for(__method__)
n = @hash.size
super
@keys = nil if @hash.size != n
self
end
def merge(enum)
@keys = nil
super
end
def each
block_given? or return enum_for(__method__)
to_a.each { |o| yield(o) }
self
end
def to_a
(@keys = @hash.keys).sort! unless @keys
@keys
end
}
end
@@setup = true
end
end
def initialize(*args, &block) # :nodoc:
SortedSet.setup
initialize(*args, &block)
end
end
module Enumerable
# Makes a set from the enumerable object with given arguments.
# Needs to +require "set"+ to use this method.
def to_set(klass = Set, *args, &block)
klass.new(self, *args, &block)
end
end
# =begin
# == RestricedSet class
# RestricedSet implements a set with restrictions defined by a given
# block.
#
# === Super class
# Set
#
# === Class Methods
# --- RestricedSet::new(enum = nil) { |o| ... }
# --- RestricedSet::new(enum = nil) { |rset, o| ... }
# Creates a new restricted set containing the elements of the given
# enumerable object. Restrictions are defined by the given block.
#
# If the block's arity is 2, it is called with the RestrictedSet
# itself and an object to see if the object is allowed to be put in
# the set.
#
# Otherwise, the block is called with an object to see if the object
# is allowed to be put in the set.
#
# === Instance Methods
# --- restriction_proc
# Returns the restriction procedure of the set.
#
# =end
#
# class RestricedSet < Set
# def initialize(*args, &block)
# @proc = block or raise ArgumentError, "missing a block"
#
# if @proc.arity == 2
# instance_eval %{
# def add(o)
# @hash[o] = true if @proc.call(self, o)
# self
# end
# alias << add
#
# def add?(o)
# if include?(o) || !@proc.call(self, o)
# nil
# else
# @hash[o] = true
# self
# end
# end
#
# def replace(enum)
# enum.respond_to?(:each) or raise ArgumentError, "value must be enumerable"
# clear
# enum.each_entry { |o| add(o) }
#
# self
# end
#
# def merge(enum)
# enum.respond_to?(:each) or raise ArgumentError, "value must be enumerable"
# enum.each_entry { |o| add(o) }
#
# self
# end
# }
# else
# instance_eval %{
# def add(o)
# if @proc.call(o)
# @hash[o] = true
# end
# self
# end
# alias << add
#
# def add?(o)
# if include?(o) || !@proc.call(o)
# nil
# else
# @hash[o] = true
# self
# end
# end
# }
# end
#
# super(*args)
# end
#
# def restriction_proc
# @proc
# end
# end
if $0 == __FILE__
eval DATA.read, nil, $0, __LINE__+4
end
__END__
require 'test/unit'
class TC_Set < Test::Unit::TestCase
def test_aref
assert_nothing_raised {
Set[]
Set[nil]
Set[1,2,3]
}
assert_equal(0, Set[].size)
assert_equal(1, Set[nil].size)
assert_equal(1, Set[[]].size)
assert_equal(1, Set[[nil]].size)
set = Set[2,4,6,4]
assert_equal(Set.new([2,4,6]), set)
end
def test_s_new
assert_nothing_raised {
Set.new()
Set.new(nil)
Set.new([])
Set.new([1,2])
Set.new('a'..'c')
}
assert_raises(ArgumentError) {
Set.new(false)
}
assert_raises(ArgumentError) {
Set.new(1)
}
assert_raises(ArgumentError) {
Set.new(1,2)
}
assert_equal(0, Set.new().size)
assert_equal(0, Set.new(nil).size)
assert_equal(0, Set.new([]).size)
assert_equal(1, Set.new([nil]).size)
ary = [2,4,6,4]
set = Set.new(ary)
ary.clear
assert_equal(false, set.empty?)
assert_equal(3, set.size)
ary = [1,2,3]
s = Set.new(ary) { |o| o * 2 }
assert_equal([2,4,6], s.sort)
end
def test_clone
set1 = Set.new
set2 = set1.clone
set1 << 'abc'
assert_equal(Set.new, set2)
end
def test_dup
set1 = Set[1,2]
set2 = set1.dup
assert_not_same(set1, set2)
assert_equal(set1, set2)
set1.add(3)
assert_not_equal(set1, set2)
end
def test_size
assert_equal(0, Set[].size)
assert_equal(2, Set[1,2].size)
assert_equal(2, Set[1,2,1].size)
end
def test_empty?
assert_equal(true, Set[].empty?)
assert_equal(false, Set[1, 2].empty?)
end
def test_clear
set = Set[1,2]
ret = set.clear
assert_same(set, ret)
assert_equal(true, set.empty?)
end
def test_replace
set = Set[1,2]
ret = set.replace('a'..'c')
assert_same(set, ret)
assert_equal(Set['a','b','c'], set)
end
def test_to_a
set = Set[1,2,3,2]
ary = set.to_a
assert_equal([1,2,3], ary.sort)
end
def test_flatten
# test1
set1 = Set[
1,
Set[
5,
Set[7,
Set[0]
],
Set[6,2],
1
],
3,
Set[3,4]
]
set2 = set1.flatten
set3 = Set.new(0..7)
assert_not_same(set2, set1)
assert_equal(set3, set2)
# test2; destructive
orig_set1 = set1
set1.flatten!
assert_same(orig_set1, set1)
assert_equal(set3, set1)
# test3; multiple occurrences of a set in an set
set1 = Set[1, 2]
set2 = Set[set1, Set[set1, 4], 3]
assert_nothing_raised {
set2.flatten!
}
assert_equal(Set.new(1..4), set2)
# test4; recursion
set2 = Set[]
set1 = Set[1, set2]
set2.add(set1)
assert_raises(ArgumentError) {
set1.flatten!
}
# test5; miscellaneous
empty = Set[]
set = Set[Set[empty, "a"],Set[empty, "b"]]
assert_nothing_raised {
set.flatten
}
set1 = empty.merge(Set["no_more", set])
assert_nil(Set.new(0..31).flatten!)
x = Set[Set[],Set[1,2]].flatten!
y = Set[1,2]
assert_equal(x, y)
end
def test_include?
set = Set[1,2,3]
assert_equal(true, set.include?(1))
assert_equal(true, set.include?(2))
assert_equal(true, set.include?(3))
assert_equal(false, set.include?(0))
assert_equal(false, set.include?(nil))
set = Set["1",nil,"2",nil,"0","1",false]
assert_equal(true, set.include?(nil))
assert_equal(true, set.include?(false))
assert_equal(true, set.include?("1"))
assert_equal(false, set.include?(0))
assert_equal(false, set.include?(true))
end
def test_superset?
set = Set[1,2,3]
assert_raises(ArgumentError) {
set.superset?()
}
assert_raises(ArgumentError) {
set.superset?(2)
}
assert_raises(ArgumentError) {
set.superset?([2])
}
assert_equal(true, set.superset?(Set[]))
assert_equal(true, set.superset?(Set[1,2]))
assert_equal(true, set.superset?(Set[1,2,3]))
assert_equal(false, set.superset?(Set[1,2,3,4]))
assert_equal(false, set.superset?(Set[1,4]))
assert_equal(true, Set[].superset?(Set[]))
end
def test_proper_superset?
set = Set[1,2,3]
assert_raises(ArgumentError) {
set.proper_superset?()
}
assert_raises(ArgumentError) {
set.proper_superset?(2)
}
assert_raises(ArgumentError) {
set.proper_superset?([2])
}
assert_equal(true, set.proper_superset?(Set[]))
assert_equal(true, set.proper_superset?(Set[1,2]))
assert_equal(false, set.proper_superset?(Set[1,2,3]))
assert_equal(false, set.proper_superset?(Set[1,2,3,4]))
assert_equal(false, set.proper_superset?(Set[1,4]))
assert_equal(false, Set[].proper_superset?(Set[]))
end
def test_subset?
set = Set[1,2,3]
assert_raises(ArgumentError) {
set.subset?()
}
assert_raises(ArgumentError) {
set.subset?(2)
}
assert_raises(ArgumentError) {
set.subset?([2])
}
assert_equal(true, set.subset?(Set[1,2,3,4]))
assert_equal(true, set.subset?(Set[1,2,3]))
assert_equal(false, set.subset?(Set[1,2]))
assert_equal(false, set.subset?(Set[]))
assert_equal(true, Set[].subset?(Set[1]))
assert_equal(true, Set[].subset?(Set[]))
end
def test_proper_subset?
set = Set[1,2,3]
assert_raises(ArgumentError) {
set.proper_subset?()
}
assert_raises(ArgumentError) {
set.proper_subset?(2)
}
assert_raises(ArgumentError) {
set.proper_subset?([2])
}
assert_equal(true, set.proper_subset?(Set[1,2,3,4]))
assert_equal(false, set.proper_subset?(Set[1,2,3]))
assert_equal(false, set.proper_subset?(Set[1,2]))
assert_equal(false, set.proper_subset?(Set[]))
assert_equal(false, Set[].proper_subset?(Set[]))
end
def test_each
ary = [1,3,5,7,10,20]
set = Set.new(ary)
ret = set.each { |o| }
assert_same(set, ret)
e = set.each
assert_instance_of(Enumerator, e)
assert_nothing_raised {
set.each { |o|
ary.delete(o) or raise "unexpected element: #{o}"
}
ary.empty? or raise "forgotten elements: #{ary.join(', ')}"
}
end
def test_add
set = Set[1,2,3]
ret = set.add(2)
assert_same(set, ret)
assert_equal(Set[1,2,3], set)
ret = set.add?(2)
assert_nil(ret)
assert_equal(Set[1,2,3], set)
ret = set.add(4)
assert_same(set, ret)
assert_equal(Set[1,2,3,4], set)
ret = set.add?(5)
assert_same(set, ret)
assert_equal(Set[1,2,3,4,5], set)
end
def test_delete
set = Set[1,2,3]
ret = set.delete(4)
assert_same(set, ret)
assert_equal(Set[1,2,3], set)
ret = set.delete?(4)
assert_nil(ret)
assert_equal(Set[1,2,3], set)
ret = set.delete(2)
assert_equal(set, ret)
assert_equal(Set[1,3], set)
ret = set.delete?(1)
assert_equal(set, ret)
assert_equal(Set[3], set)
end
def test_delete_if
set = Set.new(1..10)
ret = set.delete_if { |i| i > 10 }
assert_same(set, ret)
assert_equal(Set.new(1..10), set)
set = Set.new(1..10)
ret = set.delete_if { |i| i % 3 == 0 }
assert_same(set, ret)
assert_equal(Set[1,2,4,5,7,8,10], set)
end
def test_collect!
set = Set[1,2,3,'a','b','c',-1..1,2..4]
ret = set.collect! { |i|
case i
when Numeric
i * 2
when String
i.upcase
else
nil
end
}
assert_same(set, ret)
assert_equal(Set[2,4,6,'A','B','C',nil], set)
end
def test_reject!
set = Set.new(1..10)
ret = set.reject! { |i| i > 10 }
assert_nil(ret)
assert_equal(Set.new(1..10), set)
ret = set.reject! { |i| i % 3 == 0 }
assert_same(set, ret)
assert_equal(Set[1,2,4,5,7,8,10], set)
end
def test_merge
set = Set[1,2,3]
ret = set.merge([2,4,6])
assert_same(set, ret)
assert_equal(Set[1,2,3,4,6], set)
end
def test_subtract
set = Set[1,2,3]
ret = set.subtract([2,4,6])
assert_same(set, ret)
assert_equal(Set[1,3], set)
end
def test_plus
set = Set[1,2,3]
ret = set + [2,4,6]
assert_not_same(set, ret)
assert_equal(Set[1,2,3,4,6], ret)
end
def test_minus
set = Set[1,2,3]
ret = set - [2,4,6]
assert_not_same(set, ret)
assert_equal(Set[1,3], ret)
end
def test_and
set = Set[1,2,3,4]
ret = set & [2,4,6]
assert_not_same(set, ret)
assert_equal(Set[2,4], ret)
end
def test_xor
set = Set[1,2,3,4]
ret = set ^ [2,4,5,5]
assert_not_same(set, ret)
assert_equal(Set[1,3,5], ret)
end
def test_eq
set1 = Set[2,3,1]
set2 = Set[1,2,3]
assert_equal(set1, set1)
assert_equal(set1, set2)
assert_not_equal(Set[1], [1])
set1 = Class.new(Set)["a", "b"]
set2 = Set["a", "b", set1]
set1 = set1.add(set1.clone)
# assert_equal(set1, set2)
# assert_equal(set2, set1)
assert_equal(set2, set2.clone)
assert_equal(set1.clone, set1)
assert_not_equal(Set[Exception.new,nil], Set[Exception.new,Exception.new], "[ruby-dev:26127]")
end
# def test_hash
# end
# def test_eql?
# end
def test_classify
set = Set.new(1..10)
ret = set.classify { |i| i % 3 }
assert_equal(3, ret.size)
assert_instance_of(Hash, ret)
ret.each_value { |value| assert_instance_of(Set, value) }
assert_equal(Set[3,6,9], ret[0])
assert_equal(Set[1,4,7,10], ret[1])
assert_equal(Set[2,5,8], ret[2])
end
def test_divide
set = Set.new(1..10)
ret = set.divide { |i| i % 3 }
assert_equal(3, ret.size)
n = 0
ret.each { |s| n += s.size }
assert_equal(set.size, n)
assert_equal(set, ret.flatten)
set = Set[7,10,5,11,1,3,4,9,0]
ret = set.divide { |a,b| (a - b).abs == 1 }
assert_equal(4, ret.size)
n = 0
ret.each { |s| n += s.size }
assert_equal(set.size, n)
assert_equal(set, ret.flatten)
ret.each { |s|
if s.include?(0)
assert_equal(Set[0,1], s)
elsif s.include?(3)
assert_equal(Set[3,4,5], s)
elsif s.include?(7)
assert_equal(Set[7], s)
elsif s.include?(9)
assert_equal(Set[9,10,11], s)
else
raise "unexpected group: #{s.inspect}"
end
}
end
def test_inspect
set1 = Set[1]
assert_equal('#<Set: {1}>', set1.inspect)
set2 = Set[Set[0], 1, 2, set1]
assert_equal(false, set2.inspect.include?('#<Set: {...}>'))
set1.add(set2)
assert_equal(true, set1.inspect.include?('#<Set: {...}>'))
end
# def test_pretty_print
# end
# def test_pretty_print_cycle
# end
end
class TC_SortedSet < Test::Unit::TestCase
def test_sortedset
s = SortedSet[4,5,3,1,2]
assert_equal([1,2,3,4,5], s.to_a)
prev = nil
s.each { |o| assert(prev < o) if prev; prev = o }
assert_not_nil(prev)
s.map! { |o| -2 * o }
assert_equal([-10,-8,-6,-4,-2], s.to_a)
prev = nil
ret = s.each { |o| assert(prev < o) if prev; prev = o }
assert_not_nil(prev)
assert_same(s, ret)
s = SortedSet.new([2,1,3]) { |o| o * -2 }
assert_equal([-6,-4,-2], s.to_a)
s = SortedSet.new(['one', 'two', 'three', 'four'])
a = []
ret = s.delete_if { |o| a << o; o.start_with?('t') }
assert_same(s, ret)
assert_equal(['four', 'one'], s.to_a)
assert_equal(['four', 'one', 'three', 'two'], a)
s = SortedSet.new(['one', 'two', 'three', 'four'])
a = []
ret = s.reject! { |o| a << o; o.start_with?('t') }
assert_same(s, ret)
assert_equal(['four', 'one'], s.to_a)
assert_equal(['four', 'one', 'three', 'two'], a)
s = SortedSet.new(['one', 'two', 'three', 'four'])
a = []
ret = s.reject! { |o| a << o; false }
assert_same(nil, ret)
assert_equal(['four', 'one', 'three', 'two'], s.to_a)
assert_equal(['four', 'one', 'three', 'two'], a)
end
end
class TC_Enumerable < Test::Unit::TestCase
def test_to_set
ary = [2,5,4,3,2,1,3]
set = ary.to_set
assert_instance_of(Set, set)
assert_equal([1,2,3,4,5], set.sort)
set = ary.to_set { |o| o * -2 }
assert_instance_of(Set, set)
assert_equal([-10,-8,-6,-4,-2], set.sort)
set = ary.to_set(SortedSet)
assert_instance_of(SortedSet, set)
assert_equal([1,2,3,4,5], set.to_a)
set = ary.to_set(SortedSet) { |o| o * -2 }
assert_instance_of(SortedSet, set)
assert_equal([-10,-8,-6,-4,-2], set.sort)
end
end
# class TC_RestricedSet < Test::Unit::TestCase
# def test_s_new
# assert_raises(ArgumentError) { RestricedSet.new }
#
# s = RestricedSet.new([-1,2,3]) { |o| o > 0 }
# assert_equal([2,3], s.sort)
# end
#
# def test_restriction_proc
# s = RestricedSet.new([-1,2,3]) { |o| o > 0 }
#
# f = s.restriction_proc
# assert_instance_of(Proc, f)
# assert(f[1])
# assert(!f[0])
# end
#
# def test_replace
# s = RestricedSet.new(-3..3) { |o| o > 0 }
# assert_equal([1,2,3], s.sort)
#
# s.replace([-2,0,3,4,5])
# assert_equal([3,4,5], s.sort)
# end
#
# def test_merge
# s = RestricedSet.new { |o| o > 0 }
# s.merge(-5..5)
# assert_equal([1,2,3,4,5], s.sort)
#
# s.merge([10,-10,-8,8])
# assert_equal([1,2,3,4,5,8,10], s.sort)
# end
# end
Jump to Line
Something went wrong with that request. Please try again.