Class: SortedSet

Inherits:
Set
  • Object
show all
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 collapse

@@setup =
false
@@mutex =
Mutex.new

Constants inherited from Set

Set::InspectKey

Class Method Summary collapse

Instance Method Summary collapse

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:


803
804
805
806
807
# File 'lib/set.rb', line 803

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

Class Method Details

.[](*ary) ⇒ Object

:nodoc:


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

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

.setupObject

:nodoc:


700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
# 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