[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

2 files changed, 1 insertions, 364 deletions

diff --git a/lib/set.rb b/lib/set.rb
index 844d52ed54..cb07037e82 100644
--- a/lib/set.rb
+++ b/lib/set.rb
@@ -16,12 +16,9 @@
 #
 # 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
   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
     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 acb1cebe16..54ef80b067 100644
--- a/test/test_set.rb
+++ b/test/test_set.rb
@@ -796,116 +796,6 @@ class TC_Set < Test::Unit::TestCase
   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 = set1.dup
-
-    assert_not_predicate set2, :frozen?
-    assert_nothing_raised {
-      set2.add 4
-    }
-  end
-
-  def test_freeze_clone
-    set1 = SortedSet[1,2,3]
-    set1.freeze
-    set2 = set1.clone
-
-    assert_predicate set2, :frozen?
-    assert_raise(FrozenError) {
-      set2.add 5
-    }
-  end
-end
-
 class TC_Enumerable < Test::Unit::TestCase
   def test_to_set
     ary = [2,5,4,3,2,1,3]
@@ -920,13 +810,5 @@ class TC_Enumerable < Test::Unit::TestCase
 
     assert_same set, set.to_set
     assert_not_same set, set.to_set { |o| o }
-
-    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