Class: SortedSet

Relationships & Source Files
Super Chains via Extension / Inclusion / Inheritance
Class Chain: self, `::Set`
Instance Chain: self, `::Set`, `::Enumerable`
Inherits:	Set Object Set SortedSet
Defined in:	lib/set.rb

Overview

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 mutually comparable: el1 <=> el2 must not return nil for any elements el1 and el2, 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

Constant Summary

`::Set` - Inherited

InspectKey

Class Method Summary

.[](*ary) Internal use only
.new(*args, &block) ⇒ SortedSet constructor Internal use only
.setup Internal use only

`::Set` - Inherited

.[]	Creates a new set containing the given objects.
.new	Creates a new set containing the elements of the given enumerable object.

Instance Attribute Summary

`::Set` - Inherited

#compare_by_identity	Makes the set compare its elements by their identity and returns self.
#compare_by_identity?	Returns true if the set will compare its elements by their identity.
#empty?	Returns true if the set contains no elements.

Instance Method Summary

`::Set` - Inherited

#&	Returns a new set containing elements common to the set and the given enumerable object.
#+	Alias for Set#\|.
#-	Returns a new set built by duplicating the set, removing every element that appears in the given enumerable object.
#<	Alias for Set#proper_subset?.
#<<	Alias for Set#add.
#<=	Alias for Set#subset?.
#==	Returns true if two sets are equal.
#===	Alias for Set#include?.
#>	Alias for Set#proper_superset?.
#>=	Alias for Set#superset?.
#^	Returns a new set containing elements exclusive between the set and the given enumerable object.
#add	Adds the given object to the set and returns self.
#add?	Adds the given object to the set and returns self.
#classify	Classifies the set by the return value of the given block and returns a hash of `=> set of elements` pairs.
#clear	Removes all elements and returns self.
#collect!	Replaces the elements with ones returned by collect().
#delete	Deletes the given object from the set and returns self.
#delete?	Deletes the given object from the set and returns self.
#delete_if	Deletes every element of the set for which block evaluates to true, and returns self.
#difference	Alias for Set#-.
#disjoint?	Returns true if the set and the given set have no element in common.
#divide	Divides the set into a set of subsets according to the commonality defined by the given block.
#each	Calls the given block once for each element in the set, passing the element as parameter.
#filter!	Alias for Set#select!.
#flatten	Returns a new set that is a copy of the set, flattening each containing set recursively.
#flatten!	Equivalent to Set#flatten, but replaces the receiver with the result in place.
#include?	Returns true if the set contains the given object.
#initialize_clone	Clone internal hash.
#initialize_dup	Dup internal hash.
#inspect	Returns a string containing a human-readable representation of the set (“#<Set: `element2, …`>”).
#intersect?	Returns true if the set and the given set have at least one element in common.
#intersection	Alias for Set#&.
#keep_if	Deletes every element of the set for which block evaluates to false, and returns self.
#length	Alias for Set#size.
#map!	Alias for Set#collect!.
#member?	Alias for Set#include?.
#merge	Merges the elements of the given enumerable object to the set and returns self.
#proper_subset?	Returns true if the set is a proper subset of the given set.
#proper_superset?	Returns true if the set is a proper superset of the given set.
#reject!	Equivalent to Set#delete_if, but returns nil if no changes were made.
#replace	Replaces the contents of the set with the contents of the given enumerable object and returns self.
#reset	Resets the internal state after modification to existing elements and returns self.
#select!	Equivalent to Set#keep_if, but returns nil if no changes were made.
#size	Returns the number of elements.
#subset?	Returns true if the set is a subset of the given set.
#subtract	Deletes every element that appears in the given enumerable object and returns self.
#superset?	Returns true if the set is a superset of the given set.
#to_a	Converts the set to an array.
#to_s	Alias for Set#inspect.
#to_set	Returns self if no arguments are given.
#union	Alias for Set#\|.
#\|	Returns a new set built by merging the set and the elements of the given enumerable object.
#eql?, #freeze, #hash, #pretty_print, #pretty_print_cycle, #flatten_merge, #do_with_enum

`::Enumerable` - Included

#to_set

Makes a set from the enumerable object with given arguments.

Constructor Details

.new(*args, &block) ⇒ `SortedSet`

This method is for internal use only.

[ GitHub ]

# File 'lib/set.rb', line 799


def initialize(*args, &block) # :nodoc:
  if SortedSet.setup == :rbtree
    @hash = RBTree.new
  else
    @keys = nil
  end
  super
end

Class Method Details

.[](*ary)

This method is for internal use only.

[ GitHub ]

# File 'lib/set.rb', line 688


def [](*ary)        # :nodoc:
  new(ary)
end

.setup

This method is for internal use only.

[ GitHub ]

# File 'lib/set.rb', line 692


def setup   # :nodoc:
  @@setup and return
  ret = nil

  @@mutex.synchronize do
    # a hack to shut up warning
    alias_method :old_init, :initialize

    begin
      require 'rbtree'
      ret = :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
      ret = true
      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
        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
    ret
  end
end

Class: SortedSet

Overview

Example

Constant Summary

::Set - Inherited

Class Method Summary

::Set - Inherited

Instance Attribute Summary

::Set - Inherited

Instance Method Summary

::Set - Inherited

::Enumerable - Included

Constructor Details

.new(*args, &block) ⇒ SortedSet

Class Method Details

.[](*ary)

.setup

`::Set` - Inherited

`::Set` - Inherited

`::Set` - Inherited

`::Set` - Inherited

`::Enumerable` - Included

.new(*args, &block) ⇒ `SortedSet`