Class: SortedSet

Inherits:
Set
  • Object
show all
Defined in:
lib/set.rb

Overview

SortedSet implements a Set that guarantees that it's element 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

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, #divide, #each, #empty?, #eql?, #flatten, #flatten!, #freeze, #hash, #include?, #initialize_copy, #inspect, #keep_if, #merge, #pretty_print, #pretty_print_cycle, #proper_subset?, #proper_superset?, #reject!, #replace, #select!, #size, #subset?, #subtract, #superset?, #taint, #to_a, #untaint, #|

Methods included from Enumerable

#to_set

Constructor Details

- (SortedSet) initialize(*args, &block)

:nodoc:



616
617
618
619
# File 'lib/set.rb', line 616

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

Class Method Details

+ (Object) [](*ary)

:nodoc:



518
519
520
# File 'lib/set.rb', line 518

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

+ (Object) setup

:nodoc:



522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
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
# File 'lib/set.rb', line 522

def setup   # :nodoc:
  @@setup and return

  module_eval {
    # a hack to shut up warning
    alias old_init initialize
  }
  begin
    require 'rbtree'

    module_eval %{
      def initialize(*args, &block)
        @hash = RBTree.new
        super
      end

      def add(o)
        o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
        super
      end
      alias << add
    }
  rescue LoadError
    module_eval %{
      def initialize(*args, &block)
        @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_given? or return enum_for(__method__)
        to_a.each { |o| yield(o) }
        self
      end

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

  @@setup = true
end