Class: SortedSet

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

@@setup =

false

@@mutex =

Mutex.new

Constants inherited from Set

Set::InspectKey

Class Method Summary

• .[](*ary) ⇒ Object

  :nodoc:.

• .setup ⇒ Object

  :nodoc:.

Instance Method Summary

• #initialize(*args, &block) ⇒ SortedSet constructor

  :nodoc:.

Methods inherited from Set

#&, #-, #==, #^, #add, #add?, #classify, #clear, #collect!, #compare_by_identity, #compare_by_identity?, #delete, #delete?, #delete_if, #disjoint?, #divide, #each, #empty?, #eql?, #flatten, #flatten!, #freeze, #hash, #include?, #initialize_clone, #initialize_dup, #inspect, #intersect?, #keep_if, #merge, #pretty_print, #pretty_print_cycle, #proper_subset?, #proper_superset?, #reject!, #replace, #reset, #select!, #size, #subset?, #subtract, #superset?, #to_a, #to_set, #|

Methods included from Enumerable

#to_set

Constructor Details

#initialize(*args, &block) ⇒ SortedSet

:nodoc:

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

def initialize(*args, &block) # :nodoc:
  SortedSet.setup
  @keys = nil
  super
end

Class Method Details

.[](*ary) ⇒ Object

:nodoc:

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

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

.setup ⇒ Object

:nodoc:

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

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
        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