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

Constants inherited from Set

Set::InspectKey

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Set

#&, #-, #==, #^, #add, #add?, #classify, #clear, #collect!, #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, #select!, #size, #subset?, #subtract, #superset?, #taint, #to_a, #to_set, #untaint, #|

Methods included from Enumerable

#to_set

Constructor Details

#initialize(*args, &block) ⇒ SortedSet

:nodoc:



681
682
683
684
# File 'lib/set.rb', line 681

def initialize(*args, &block) # :nodoc:
  SortedSet.setup
  initialize(*args, &block)
end

Class Method Details

.[](*ary) ⇒ Object

:nodoc:



583
584
585
# File 'lib/set.rb', line 583

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

.setupObject

:nodoc:



587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
# File 'lib/set.rb', line 587

def setup   # :nodoc:
  @@setup and return

  module_eval {
    # a hack to shut up warning
    alias 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__)
        n = @hash.size
        super
        @keys = nil if @hash.size != n
        self
      end

      def keep_if
        block_given? or return enum_for(__method__)
        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__)
        to_a.each(&block)
        self
      end

      def to_a
        (@keys = @hash.keys).sort! unless @keys
        @keys
      end
    END
  end
  module_eval {
    # a hack to shut up warning
    remove_method :old_init
  }

  @@setup = true
end