ruby-changes:63898
From: Akinori <ko1@a...>
Date: Fri, 4 Dec 2020 19:44:57 +0900 (JST)
Subject: [ruby-changes:63898] a3db08d7b6 (master): [ruby/set] Remove SortedSet implementations
https://git.ruby-lang.org/ruby.git/commit/?id=a3db08d7b6 From a3db08d7b6ff119223f77e3df00b4f6deac971e2 Mon Sep 17 00:00:00 2001 From: Akinori MUSHA <knu@i...> Date: Sun, 20 Sep 2020 22:03:33 +0900 Subject: [ruby/set] Remove SortedSet implementations It required RBTree to perform decently and the external dependency was not suitable for a standard library. The pure ruby fallback implementation was originally meant to be an example of how to write a subclass of Set, and its poor performance was not suitable for use in production. I decided it should be distributed as an external library instead of bundling it with Set. https://github.com/ruby/set/commit/dfcc8e568b diff --git a/lib/set.rb b/lib/set.rb index 844d52e..cb07037 100644 --- a/lib/set.rb +++ b/lib/set.rb @@ -16,12 +16,9 @@ https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L16 # # 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 sorted in some order, use the SortedSet class. +# intuitive inter-operation facilities and Hash's fast lookup. # # The method +to_set+ is added to Enumerable for convenience. -# -# See the Set and SortedSet documentation for examples of usage. # @@ -667,154 +664,6 @@ class Set https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L664 end end -# -# SortedSet implements a Set that guarantees that its elements 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 - @@mutex = Mutex.new - - class << self - def [](*ary) # :nodoc: - new(ary) - end - - def setup # :nodoc: - @@setup and return - - @@mutex.synchronize do - # a hack to shut up warning - alias_method :old_init, :initialize - - begin - require 'rbtree' - - module_eval <<-END, __FILE__, __LINE__+1 - def initialize(*args) - @hash = RBTree.new - super - end - - def add(o) - o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>" - super - end - alias << add - END - rescue LoadError - module_eval <<-END, __FILE__, __LINE__+1 - def initialize(*args) - @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__) { size } - n = @hash.size - super - @keys = nil if @hash.size != n - self - end - - def keep_if - block_given? or return enum_for(__method__) { size } - n = @hash.size - super - @keys = nil if @hash.size != n - self - end - - def merge(enum) - @keys = nil - super - end - - def each(&block) - block or return enum_for(__method__) { size } - to_a.each(&block) - self - end - - def to_a - (@keys = @hash.keys).sort! unless @keys - @keys.dup - end - - def freeze - to_a - super - end - - def rehash - @keys = nil - super - end - END - end - # a hack to shut up warning - remove_method :old_init - - @@setup = true - end - end - end - - def initialize(*args, &block) # :nodoc: - SortedSet.setup - @keys = nil - super - end -end - module Enumerable # Makes a set from the enumerable object with given arguments. # Needs to +require "set"+ to use this method. @@ -822,97 +671,3 @@ module Enumerable https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L671 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 - -# Tests have been moved to test/test_set.rb. diff --git a/test/test_set.rb b/test/test_set.rb index acb1ceb..54ef80b 100644 --- a/test/test_set.rb +++ b/test/test_set.rb @@ -796,116 +796,6 @@ class TC_Set < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/test_set.rb#L796 end end -class TC_SortedSet < Test::Unit::TestCase - def test_sortedset - s = SortedSet[4,5,3,1,2] - - a = s.to_a - assert_equal([1,2,3,4,5], a) - a << -1 - 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 - - def test_each - ary = [1,3,5,7,10,20] - set = SortedSet.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(', ')}" - } - - assert_equal(6, e.size) - set << 42 - assert_equal(7, e.size) - end - - def test_freeze - orig = set = SortedSet[3,2,1] - assert_equal false, set.frozen? - set << 4 - assert_same orig, set.freeze - assert_equal true, set.frozen? - assert_raise(FrozenError) { - set << 5 - } - assert_equal 4, set.size - - # https://bugs.ruby-lang.org/issues/12091 - assert_nothing_raised { - assert_equal [1,2,3,4], set.to_a - } - end - - def test_freeze_dup - set1 = SortedSet[1,2,3] - set1.freeze - set2 = se (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/