lib/set.rb

   1 # frozen_string_literal: true
   2 # :markup: markdown
   3 #
   4 # set.rb - defines the Set class
   5 #
   6 # Copyright (c) 2002-2023 Akinori MUSHA <knu@iDaemons.org>
   7 #
   8 # Documentation by Akinori MUSHA and Gavin Sinclair.
   9 #
  10 # All rights reserved.  You can redistribute and/or modify it under the same
  11 # terms as Ruby.
  12
  13
  14 ##
  15 # This library provides the Set class, which implements a collection
  16 # of unordered values with no duplicates. It is a hybrid of Array's
  17 # intuitive inter-operation facilities and Hash's fast lookup.
  18 #
  19 # The method `to_set` is added to Enumerable for convenience.
  20 #
  21 # Set is easy to use with Enumerable objects (implementing `each`).
  22 # Most of the initializer methods and binary operators accept generic
  23 # Enumerable objects besides sets and arrays.  An Enumerable object
  24 # can be converted to Set using the `to_set` method.
  25 #
  26 # Set uses Hash as storage, so you must note the following points:
  27 #
  28 # * Equality of elements is determined according to Object#eql? and
  29 #   Object#hash.  Use Set#compare_by_identity to make a set compare
  30 #   its elements by their identity.
  31 # * Set assumes that the identity of each element does not change
  32 #   while it is stored.  Modifying an element of a set will render the
  33 #   set to an unreliable state.
  34 # * When a string is to be stored, a frozen copy of the string is
  35 #   stored instead unless the original string is already frozen.
  36 #
  37 # ## Comparison
  38 #
  39 # The comparison operators `<`, `>`, `<=`, and `>=` are implemented as
  40 # shorthand for the {proper_,}{subset?,superset?} methods.  The `<=>`
  41 # operator reflects this order, or return `nil` for sets that both
  42 # have distinct elements (`{x, y}` vs. `{x, z}` for example).
  43 #
  44 # ## Example
  45 #
  46 # ```ruby
  47 # require 'set'
  48 # s1 = Set[1, 2]                        #=> #<Set: {1, 2}>
  49 # s2 = [1, 2].to_set                    #=> #<Set: {1, 2}>
  50 # s1 == s2                              #=> true
  51 # s1.add("foo")                         #=> #<Set: {1, 2, "foo"}>
  52 # s1.merge([2, 6])                      #=> #<Set: {1, 2, "foo", 6}>
  53 # s1.subset?(s2)                        #=> false
  54 # s2.subset?(s1)                        #=> true
  55 # ```
  56 #
  57 # ## Contact
  58 #
  59 # - Akinori MUSHA <<knu@iDaemons.org>> (current maintainer)
  60 #
  61 # ## What's Here
  62 #
  63 #  First, what's elsewhere. \Class \Set:
  64 #
  65 # - Inherits from {class Object}[rdoc-ref:Object@What-27s+Here].
  66 # - Includes {module Enumerable}[rdoc-ref:Enumerable@What-27s+Here],
  67 #   which provides dozens of additional methods.
  68 #
  69 # In particular, class \Set does not have many methods of its own
  70 # for fetching or for iterating.
  71 # Instead, it relies on those in \Enumerable.
  72 #
  73 # Here, class \Set provides methods that are useful for:
  74 #
  75 # - [Creating a Set](#class-Set-label-Methods+for+Creating+a+Set)
  76 # - [Set Operations](#class-Set-label-Methods+for+Set+Operations)
  77 # - [Comparing](#class-Set-label-Methods+for+Comparing)
  78 # - [Querying](#class-Set-label-Methods+for+Querying)
  79 # - [Assigning](#class-Set-label-Methods+for+Assigning)
  80 # - [Deleting](#class-Set-label-Methods+for+Deleting)
  81 # - [Converting](#class-Set-label-Methods+for+Converting)
  82 # - [Iterating](#class-Set-label-Methods+for+Iterating)
  83 # - [And more....](#class-Set-label-Other+Methods)
  84 #
  85 # ### Methods for Creating a \Set
  86 #
  87 # - ::[]:
  88 #   Returns a new set containing the given objects.
  89 # - ::new:
  90 #   Returns a new set containing either the given objects
  91 #   (if no block given) or the return values from the called block
  92 #   (if a block given).
  93 #
  94 # ### Methods for \Set Operations
  95 #
  96 # - [|](#method-i-7C) (aliased as #union and #+):
  97 #   Returns a new set containing all elements from +self+
  98 #   and all elements from a given enumerable (no duplicates).
  99 # - [&](#method-i-26) (aliased as #intersection):
 100 #   Returns a new set containing all elements common to +self+
 101 #   and a given enumerable.
 102 # - [-](#method-i-2D) (aliased as #difference):
 103 #   Returns a copy of +self+ with all elements
 104 #   in a given enumerable removed.
 105 # - [\^](#method-i-5E):
 106 #   Returns a new set containing all elements from +self+
 107 #   and a given enumerable except those common to both.
 108 #
 109 # ### Methods for Comparing
 110 #
 111 # - [<=>](#method-i-3C-3D-3E):
 112 #   Returns -1, 0, or 1 as +self+ is less than, equal to,
 113 #   or greater than a given object.
 114 # - [==](#method-i-3D-3D):
 115 #   Returns whether +self+ and a given enumerable are equal,
 116 #   as determined by Object#eql?.
 117 # - \#compare_by_identity?:
 118 #   Returns whether the set considers only identity
 119 #   when comparing elements.
 120 #
 121 # ### Methods for Querying
 122 #
 123 # - \#length (aliased as #size):
 124 #   Returns the count of elements.
 125 # - \#empty?:
 126 #   Returns whether the set has no elements.
 127 # - \#include? (aliased as #member? and #===):
 128 #   Returns whether a given object is an element in the set.
 129 # - \#subset? (aliased as [<=](#method-i-3C-3D)):
 130 #   Returns whether a given object is a subset of the set.
 131 # - \#proper_subset? (aliased as [<](#method-i-3C)):
 132 #   Returns whether a given enumerable is a proper subset of the set.
 133 # - \#superset? (aliased as [>=](#method-i-3E-3D])):
 134 #   Returns whether a given enumerable is a superset of the set.
 135 # - \#proper_superset? (aliased as [>](#method-i-3E)):
 136 #   Returns whether a given enumerable is a proper superset of the set.
 137 # - \#disjoint?:
 138 #   Returns +true+ if the set and a given enumerable
 139 #   have no common elements, +false+ otherwise.
 140 # - \#intersect?:
 141 #   Returns +true+ if the set and a given enumerable:
 142 #   have any common elements, +false+ otherwise.
 143 # - \#compare_by_identity?:
 144 #   Returns whether the set considers only identity
 145 #   when comparing elements.
 146 #
 147 # ### Methods for Assigning
 148 #
 149 # - \#add (aliased as #<<):
 150 #   Adds a given object to the set; returns +self+.
 151 # - \#add?:
 152 #   If the given object is not an element in the set,
 153 #   adds it and returns +self+; otherwise, returns +nil+.
 154 # - \#merge:
 155 #   Merges the elements of each given enumerable object to the set; returns +self+.
 156 # - \#replace:
 157 #   Replaces the contents of the set with the contents
 158 #   of a given enumerable.
 159 #
 160 # ### Methods for Deleting
 161 #
 162 # - \#clear:
 163 #   Removes all elements in the set; returns +self+.
 164 # - \#delete:
 165 #   Removes a given object from the set; returns +self+.
 166 # - \#delete?:
 167 #   If the given object is an element in the set,
 168 #   removes it and returns +self+; otherwise, returns +nil+.
 169 # - \#subtract:
 170 #   Removes each given object from the set; returns +self+.
 171 # - \#delete_if - Removes elements specified by a given block.
 172 # - \#select! (aliased as #filter!):
 173 #   Removes elements not specified by a given block.
 174 # - \#keep_if:
 175 #   Removes elements not specified by a given block.
 176 # - \#reject!
 177 #   Removes elements specified by a given block.
 178 #
 179 # ### Methods for Converting
 180 #
 181 # - \#classify:
 182 #   Returns a hash that classifies the elements,
 183 #   as determined by the given block.
 184 # - \#collect! (aliased as #map!):
 185 #   Replaces each element with a block return-value.
 186 # - \#divide:
 187 #   Returns a hash that classifies the elements,
 188 #   as determined by the given block;
 189 #   differs from #classify in that the block may accept
 190 #   either one or two arguments.
 191 # - \#flatten:
 192 #   Returns a new set that is a recursive flattening of +self+.
 193 #  \#flatten!:
 194 #   Replaces each nested set in +self+ with the elements from that set.
 195 # - \#inspect (aliased as #to_s):
 196 #   Returns a string displaying the elements.
 197 # - \#join:
 198 #   Returns a string containing all elements, converted to strings
 199 #   as needed, and joined by the given record separator.
 200 # - \#to_a:
 201 #   Returns an array containing all set elements.
 202 # - \#to_set:
 203 #   Returns +self+ if given no arguments and no block;
 204 #   with a block given, returns a new set consisting of block
 205 #   return values.
 206 #
 207 # ### Methods for Iterating
 208 #
 209 # - \#each:
 210 #   Calls the block with each successive element; returns +self+.
 211 #
 212 # ### Other Methods
 213 #
 214 # - \#reset:
 215 #   Resets the internal state; useful if an object
 216 #   has been modified while an element in the set.
 217 #
 218 class Set
 219   VERSION = "1.1.0"
 220
 221   include Enumerable
 222
 223   # Creates a new set containing the given objects.
 224   #
 225   #     Set[1, 2]                   # => #<Set: {1, 2}>
 226   #     Set[1, 2, 1]                # => #<Set: {1, 2}>
 227   #     Set[1, 'c', :s]             # => #<Set: {1, "c", :s}>
 228   def self.[](*ary)
 229     new(ary)
 230   end
 231
 232   # Creates a new set containing the elements of the given enumerable
 233   # object.
 234   #
 235   # If a block is given, the elements of enum are preprocessed by the
 236   # given block.
 237   #
 238   #     Set.new([1, 2])                       #=> #<Set: {1, 2}>
 239   #     Set.new([1, 2, 1])                    #=> #<Set: {1, 2}>
 240   #     Set.new([1, 'c', :s])                 #=> #<Set: {1, "c", :s}>
 241   #     Set.new(1..5)                         #=> #<Set: {1, 2, 3, 4, 5}>
 242   #     Set.new([1, 2, 3]) { |x| x * x }      #=> #<Set: {1, 4, 9}>
 243   def initialize(enum = nil, &block) # :yields: o
 244     @hash ||= Hash.new(false)
 245
 246     enum.nil? and return
 247
 248     if block
 249       do_with_enum(enum) { |o| add(block[o]) }
 250     else
 251       merge(enum)
 252     end
 253   end
 254
 255   # Makes the set compare its elements by their identity and returns
 256   # self.  This method may not be supported by all subclasses of Set.
 257   def compare_by_identity
 258     if @hash.respond_to?(:compare_by_identity)
 259       @hash.compare_by_identity
 260       self
 261     else
 262       raise NotImplementedError, "#{self.class.name}\##{__method__} is not implemented"
 263     end
 264   end
 265
 266   # Returns true if the set will compare its elements by their
 267   # identity.  Also see Set#compare_by_identity.
 268   def compare_by_identity?
 269     @hash.respond_to?(:compare_by_identity?) && @hash.compare_by_identity?
 270   end
 271
 272   def do_with_enum(enum, &block) # :nodoc:
 273     if enum.respond_to?(:each_entry)
 274       enum.each_entry(&block) if block
 275     elsif enum.respond_to?(:each)
 276       enum.each(&block) if block
 277     else
 278       raise ArgumentError, "value must be enumerable"
 279     end
 280   end
 281   private :do_with_enum
 282
 283   # Dup internal hash.
 284   def initialize_dup(orig)
 285     super
 286     @hash = orig.instance_variable_get(:@hash).dup
 287   end
 288
 289   # Clone internal hash.
 290   def initialize_clone(orig, **options)
 291     super
 292     @hash = orig.instance_variable_get(:@hash).clone(**options)
 293   end
 294
 295   def freeze    # :nodoc:
 296     @hash.freeze
 297     super
 298   end
 299
 300   # Returns the number of elements.
 301   def size
 302     @hash.size
 303   end
 304   alias length size
 305
 306   # Returns true if the set contains no elements.
 307   def empty?
 308     @hash.empty?
 309   end
 310
 311   # Removes all elements and returns self.
 312   #
 313   #     set = Set[1, 'c', :s]             #=> #<Set: {1, "c", :s}>
 314   #     set.clear                         #=> #<Set: {}>
 315   #     set                               #=> #<Set: {}>
 316   def clear
 317     @hash.clear
 318     self
 319   end
 320
 321   # Replaces the contents of the set with the contents of the given
 322   # enumerable object and returns self.
 323   #
 324   #     set = Set[1, 'c', :s]             #=> #<Set: {1, "c", :s}>
 325   #     set.replace([1, 2])               #=> #<Set: {1, 2}>
 326   #     set                               #=> #<Set: {1, 2}>
 327   def replace(enum)
 328     if enum.instance_of?(self.class)
 329       @hash.replace(enum.instance_variable_get(:@hash))
 330       self
 331     else
 332       do_with_enum(enum)  # make sure enum is enumerable before calling clear
 333       clear
 334       merge(enum)
 335     end
 336   end
 337
 338   # Converts the set to an array.  The order of elements is uncertain.
 339   #
 340   #     Set[1, 2].to_a                    #=> [1, 2]
 341   #     Set[1, 'c', :s].to_a              #=> [1, "c", :s]
 342   def to_a
 343     @hash.keys
 344   end
 345
 346   # Returns self if no arguments are given.  Otherwise, converts the
 347   # set to another with `klass.new(self, *args, &block)`.
 348   #
 349   # In subclasses, returns `klass.new(self, *args, &block)` unless
 350   # overridden.
 351   def to_set(klass = Set, *args, &block)
 352     return self if instance_of?(Set) && klass == Set && block.nil? && args.empty?
 353     klass.new(self, *args, &block)
 354   end
 355
 356   def flatten_merge(set, seen = Set.new) # :nodoc:
 357     set.each { |e|
 358       if e.is_a?(Set)
 359         if seen.include?(e_id = e.object_id)
 360           raise ArgumentError, "tried to flatten recursive Set"
 361         end
 362
 363         seen.add(e_id)
 364         flatten_merge(e, seen)
 365         seen.delete(e_id)
 366       else
 367         add(e)
 368       end
 369     }
 370
 371     self
 372   end
 373   protected :flatten_merge
 374
 375   # Returns a new set that is a copy of the set, flattening each
 376   # containing set recursively.
 377   def flatten
 378     self.class.new.flatten_merge(self)
 379   end
 380
 381   # Equivalent to Set#flatten, but replaces the receiver with the
 382   # result in place.  Returns nil if no modifications were made.
 383   def flatten!
 384     replace(flatten()) if any?(Set)
 385   end
 386
 387   # Returns true if the set contains the given object.
 388   #
 389   # Note that <code>include?</code> and <code>member?</code> do not test member
 390   # equality using <code>==</code> as do other Enumerables.
 391   #
 392   # See also Enumerable#include?
 393   def include?(o)
 394     @hash[o]
 395   end
 396   alias member? include?
 397
 398   # Returns true if the set is a superset of the given set.
 399   def superset?(set)
 400     case
 401     when set.instance_of?(self.class) && @hash.respond_to?(:>=)
 402       @hash >= set.instance_variable_get(:@hash)
 403     when set.is_a?(Set)
 404       size >= set.size && set.all?(self)
 405     else
 406       raise ArgumentError, "value must be a set"
 407     end
 408   end
 409   alias >= superset?
 410
 411   # Returns true if the set is a proper superset of the given set.
 412   def proper_superset?(set)
 413     case
 414     when set.instance_of?(self.class) && @hash.respond_to?(:>)
 415       @hash > set.instance_variable_get(:@hash)
 416     when set.is_a?(Set)
 417       size > set.size && set.all?(self)
 418     else
 419       raise ArgumentError, "value must be a set"
 420     end
 421   end
 422   alias > proper_superset?
 423
 424   # Returns true if the set is a subset of the given set.
 425   def subset?(set)
 426     case
 427     when set.instance_of?(self.class) && @hash.respond_to?(:<=)
 428       @hash <= set.instance_variable_get(:@hash)
 429     when set.is_a?(Set)
 430       size <= set.size && all?(set)
 431     else
 432       raise ArgumentError, "value must be a set"
 433     end
 434   end
 435   alias <= subset?
 436
 437   # Returns true if the set is a proper subset of the given set.
 438   def proper_subset?(set)
 439     case
 440     when set.instance_of?(self.class) && @hash.respond_to?(:<)
 441       @hash < set.instance_variable_get(:@hash)
 442     when set.is_a?(Set)
 443       size < set.size && all?(set)
 444     else
 445       raise ArgumentError, "value must be a set"
 446     end
 447   end
 448   alias < proper_subset?
 449
 450   # Returns 0 if the set are equal,
 451   # -1 / +1 if the set is a proper subset / superset of the given set,
 452   # or nil if they both have unique elements.
 453   def <=>(set)
 454     return unless set.is_a?(Set)
 455
 456     case size <=> set.size
 457     when -1 then -1 if proper_subset?(set)
 458     when +1 then +1 if proper_superset?(set)
 459     else 0 if self.==(set)
 460     end
 461   end
 462
 463   # Returns true if the set and the given enumerable have at least one
 464   # element in common.
 465   #
 466   #     Set[1, 2, 3].intersect? Set[4, 5]   #=> false
 467   #     Set[1, 2, 3].intersect? Set[3, 4]   #=> true
 468   #     Set[1, 2, 3].intersect? 4..5        #=> false
 469   #     Set[1, 2, 3].intersect? [3, 4]      #=> true
 470   def intersect?(set)
 471     case set
 472     when Set
 473       if size < set.size
 474         any?(set)
 475       else
 476         set.any?(self)
 477       end
 478     when Enumerable
 479       set.any?(self)
 480     else
 481       raise ArgumentError, "value must be enumerable"
 482     end
 483   end
 484
 485   # Returns true if the set and the given enumerable have
 486   # no element in common.  This method is the opposite of `intersect?`.
 487   #
 488   #     Set[1, 2, 3].disjoint? Set[3, 4]   #=> false
 489   #     Set[1, 2, 3].disjoint? Set[4, 5]   #=> true
 490   #     Set[1, 2, 3].disjoint? [3, 4]      #=> false
 491   #     Set[1, 2, 3].disjoint? 4..5        #=> true
 492   def disjoint?(set)
 493     !intersect?(set)
 494   end
 495
 496   # Calls the given block once for each element in the set, passing
 497   # the element as parameter.  Returns an enumerator if no block is
 498   # given.
 499   def each(&block)
 500     block_given? or return enum_for(__method__) { size }
 501     @hash.each_key(&block)
 502     self
 503   end
 504
 505   # Adds the given object to the set and returns self.  Use `merge` to
 506   # add many elements at once.
 507   #
 508   #     Set[1, 2].add(3)                    #=> #<Set: {1, 2, 3}>
 509   #     Set[1, 2].add([3, 4])               #=> #<Set: {1, 2, [3, 4]}>
 510   #     Set[1, 2].add(2)                    #=> #<Set: {1, 2}>
 511   def add(o)
 512     @hash[o] = true
 513     self
 514   end
 515   alias << add
 516
 517   # Adds the given object to the set and returns self.  If the
 518   # object is already in the set, returns nil.
 519   #
 520   #     Set[1, 2].add?(3)                    #=> #<Set: {1, 2, 3}>
 521   #     Set[1, 2].add?([3, 4])               #=> #<Set: {1, 2, [3, 4]}>
 522   #     Set[1, 2].add?(2)                    #=> nil
 523   def add?(o)
 524     add(o) unless include?(o)
 525   end
 526
 527   # Deletes the given object from the set and returns self.  Use
 528   # `subtract` to delete many items at once.
 529   def delete(o)
 530     @hash.delete(o)
 531     self
 532   end
 533
 534   # Deletes the given object from the set and returns self.  If the
 535   # object is not in the set, returns nil.
 536   def delete?(o)
 537     delete(o) if include?(o)
 538   end
 539
 540   # Deletes every element of the set for which block evaluates to
 541   # true, and returns self. Returns an enumerator if no block is
 542   # given.
 543   def delete_if
 544     block_given? or return enum_for(__method__) { size }
 545     # @hash.delete_if should be faster, but using it breaks the order
 546     # of enumeration in subclasses.
 547     select { |o| yield o }.each { |o| @hash.delete(o) }
 548     self
 549   end
 550
 551   # Deletes every element of the set for which block evaluates to
 552   # false, and returns self. Returns an enumerator if no block is
 553   # given.
 554   def keep_if
 555     block_given? or return enum_for(__method__) { size }
 556     # @hash.keep_if should be faster, but using it breaks the order of
 557     # enumeration in subclasses.
 558     reject { |o| yield o }.each { |o| @hash.delete(o) }
 559     self
 560   end
 561
 562   # Replaces the elements with ones returned by `collect()`.
 563   # Returns an enumerator if no block is given.
 564   def collect!
 565     block_given? or return enum_for(__method__) { size }
 566     set = self.class.new
 567     each { |o| set << yield(o) }
 568     replace(set)
 569   end
 570   alias map! collect!
 571
 572   # Equivalent to Set#delete_if, but returns nil if no changes were
 573   # made. Returns an enumerator if no block is given.
 574   def reject!(&block)
 575     block_given? or return enum_for(__method__) { size }
 576     n = size
 577     delete_if(&block)
 578     self if size != n
 579   end
 580
 581   # Equivalent to Set#keep_if, but returns nil if no changes were
 582   # made. Returns an enumerator if no block is given.
 583   def select!(&block)
 584     block_given? or return enum_for(__method__) { size }
 585     n = size
 586     keep_if(&block)
 587     self if size != n
 588   end
 589
 590   # Equivalent to Set#select!
 591   alias filter! select!
 592
 593   # Merges the elements of the given enumerable objects to the set and
 594   # returns self.
 595   def merge(*enums, **nil)
 596     enums.each do |enum|
 597       if enum.instance_of?(self.class)
 598         @hash.update(enum.instance_variable_get(:@hash))
 599       else
 600         do_with_enum(enum) { |o| add(o) }
 601       end
 602     end
 603
 604     self
 605   end
 606
 607   # Deletes every element that appears in the given enumerable object
 608   # and returns self.
 609   def subtract(enum)
 610     do_with_enum(enum) { |o| delete(o) }
 611     self
 612   end
 613
 614   # Returns a new set built by merging the set and the elements of the
 615   # given enumerable object.
 616   #
 617   #     Set[1, 2, 3] | Set[2, 4, 5]         #=> #<Set: {1, 2, 3, 4, 5}>
 618   #     Set[1, 5, 'z'] | (1..6)             #=> #<Set: {1, 5, "z", 2, 3, 4, 6}>
 619   def |(enum)
 620     dup.merge(enum)
 621   end
 622   alias + |
 623   alias union |
 624
 625   # Returns a new set built by duplicating the set, removing every
 626   # element that appears in the given enumerable object.
 627   #
 628   #     Set[1, 3, 5] - Set[1, 5]                #=> #<Set: {3}>
 629   #     Set['a', 'b', 'z'] - ['a', 'c']         #=> #<Set: {"b", "z"}>
 630   def -(enum)
 631     dup.subtract(enum)
 632   end
 633   alias difference -
 634
 635   # Returns a new set containing elements common to the set and the
 636   # given enumerable object.
 637   #
 638   #     Set[1, 3, 5] & Set[3, 2, 1]             #=> #<Set: {3, 1}>
 639   #     Set['a', 'b', 'z'] & ['a', 'b', 'c']    #=> #<Set: {"a", "b"}>
 640   def &(enum)
 641     n = self.class.new
 642     if enum.is_a?(Set)
 643       if enum.size > size
 644         each { |o| n.add(o) if enum.include?(o) }
 645       else
 646         enum.each { |o| n.add(o) if include?(o) }
 647       end
 648     else
 649       do_with_enum(enum) { |o| n.add(o) if include?(o) }
 650     end
 651     n
 652   end
 653   alias intersection &
 654
 655   # Returns a new set containing elements exclusive between the set
 656   # and the given enumerable object.  `(set ^ enum)` is equivalent to
 657   # `((set | enum) - (set & enum))`.
 658   #
 659   #     Set[1, 2] ^ Set[2, 3]                   #=> #<Set: {3, 1}>
 660   #     Set[1, 'b', 'c'] ^ ['b', 'd']           #=> #<Set: {"d", 1, "c"}>
 661   def ^(enum)
 662     n = Set.new(enum)
 663     each { |o| n.add(o) unless n.delete?(o) }
 664     n
 665   end
 666
 667   # Returns true if two sets are equal.  The equality of each couple
 668   # of elements is defined according to Object#eql?.
 669   #
 670   #     Set[1, 2] == Set[2, 1]                       #=> true
 671   #     Set[1, 3, 5] == Set[1, 5]                    #=> false
 672   #     Set['a', 'b', 'c'] == Set['a', 'c', 'b']     #=> true
 673   #     Set['a', 'b', 'c'] == ['a', 'c', 'b']        #=> false
 674   def ==(other)
 675     if self.equal?(other)
 676       true
 677     elsif other.instance_of?(self.class)
 678       @hash == other.instance_variable_get(:@hash)
 679     elsif other.is_a?(Set) && self.size == other.size
 680       other.all? { |o| @hash.include?(o) }
 681     else
 682       false
 683     end
 684   end
 685
 686   def hash      # :nodoc:
 687     @hash.hash
 688   end
 689
 690   def eql?(o)   # :nodoc:
 691     return false unless o.is_a?(Set)
 692     @hash.eql?(o.instance_variable_get(:@hash))
 693   end
 694
 695   # Resets the internal state after modification to existing elements
 696   # and returns self.
 697   #
 698   # Elements will be reindexed and deduplicated.
 699   def reset
 700     if @hash.respond_to?(:rehash)
 701       @hash.rehash # This should perform frozenness check.
 702     else
 703       raise FrozenError, "can't modify frozen #{self.class.name}" if frozen?
 704     end
 705     self
 706   end
 707
 708   # Returns true if the given object is a member of the set,
 709   # and false otherwise.
 710   #
 711   # Used in case statements:
 712   #
 713   #     require 'set'
 714   #
 715   #     case :apple
 716   #     when Set[:potato, :carrot]
 717   #       "vegetable"
 718   #     when Set[:apple, :banana]
 719   #       "fruit"
 720   #     end
 721   #     # => "fruit"
 722   #
 723   # Or by itself:
 724   #
 725   #     Set[1, 2, 3] === 2   #=> true
 726   #     Set[1, 2, 3] === 4   #=> false
 727   #
 728   alias === include?
 729
 730   # Classifies the set by the return value of the given block and
 731   # returns a hash of {value => set of elements} pairs.  The block is
 732   # called once for each element of the set, passing the element as
 733   # parameter.
 734   #
 735   #     require 'set'
 736   #     files = Set.new(Dir.glob("*.rb"))
 737   #     hash = files.classify { |f| File.mtime(f).year }
 738   #     hash       #=> {2000=>#<Set: {"a.rb", "b.rb"}>,
 739   #                #    2001=>#<Set: {"c.rb", "d.rb", "e.rb"}>,
 740   #                #    2002=>#<Set: {"f.rb"}>}
 741   #
 742   # Returns an enumerator if no block is given.
 743   def classify # :yields: o
 744     block_given? or return enum_for(__method__) { size }
 745
 746     h = {}
 747
 748     each { |i|
 749       (h[yield(i)] ||= self.class.new).add(i)
 750     }
 751
 752     h
 753   end
 754
 755   # Divides the set into a set of subsets according to the commonality
 756   # defined by the given block.
 757   #
 758   # If the arity of the block is 2, elements o1 and o2 are in common
 759   # if block.call(o1, o2) is true.  Otherwise, elements o1 and o2 are
 760   # in common if block.call(o1) == block.call(o2).
 761   #
 762   #     require 'set'
 763   #     numbers = Set[1, 3, 4, 6, 9, 10, 11]
 764   #     set = numbers.divide { |i,j| (i - j).abs == 1 }
 765   #     set        #=> #<Set: {#<Set: {1}>,
 766   #                #           #<Set: {11, 9, 10}>,
 767   #                #           #<Set: {3, 4}>,
 768   #                #           #<Set: {6}>}>
 769   #
 770   # Returns an enumerator if no block is given.
 771   def divide(&func)
 772     func or return enum_for(__method__) { size }
 773
 774     if func.arity == 2
 775       require 'tsort'
 776
 777       class << dig = {}         # :nodoc:
 778         include TSort
 779
 780         alias tsort_each_node each_key
 781         def tsort_each_child(node, &block)
 782           fetch(node).each(&block)
 783         end
 784       end
 785
 786       each { |u|
 787         dig[u] = a = []
 788         each{ |v| func.call(u, v) and a << v }
 789       }
 790
 791       set = Set.new()
 792       dig.each_strongly_connected_component { |css|
 793         set.add(self.class.new(css))
 794       }
 795       set
 796     else
 797       Set.new(classify(&func).values)
 798     end
 799   end
 800
 801   # Returns a string created by converting each element of the set to a string
 802   # See also: Array#join
 803   def join(separator=nil)
 804     to_a.join(separator)
 805   end
 806
 807   InspectKey = :__inspect_key__         # :nodoc:
 808
 809   # Returns a string containing a human-readable representation of the
 810   # set ("#<Set: {element1, element2, ...}>").
 811   def inspect
 812     ids = (Thread.current[InspectKey] ||= [])
 813
 814     if ids.include?(object_id)
 815       return sprintf('#<%s: {...}>', self.class.name)
 816     end
 817
 818     ids << object_id
 819     begin
 820       return sprintf('#<%s: {%s}>', self.class, to_a.inspect[1..-2])
 821     ensure
 822       ids.pop
 823     end
 824   end
 825
 826   alias to_s inspect
 827
 828   def pretty_print(pp)  # :nodoc:
 829     pp.group(1, sprintf('#<%s:', self.class.name), '>') {
 830       pp.breakable
 831       pp.group(1, '{', '}') {
 832         pp.seplist(self) { |o|
 833           pp.pp o
 834         }
 835       }
 836     }
 837   end
 838
 839   def pretty_print_cycle(pp)    # :nodoc:
 840     pp.text sprintf('#<%s: {%s}>', self.class.name, empty? ? '' : '...')
 841   end
 842 end
 843
 844 module Enumerable
 845   # Makes a set from the enumerable object with given arguments.
 846   # Needs to `require "set"` to use this method.
 847   def to_set(klass = Set, *args, &block)
 848     klass.new(self, *args, &block)
 849   end unless method_defined?(:to_set)
 850 end
 851
 852 autoload :SortedSet, "#{__dir__}/set/sorted_set"