Class: ImmutableSet

Inherits:
Set
  • Object
show all
Defined in:
lib/immutable_set/builder_methods.rb,
lib/immutable_set.rb,
lib/immutable_set/pure.rb,
lib/immutable_set/version.rb,
lib/immutable_set/inversion.rb,
lib/immutable_set/native_ext.rb,
lib/immutable_set/ruby_fallback.rb,
lib/immutable_set/disable_mutating_methods.rb,
lib/immutable_set/stdlib_set_method_overrides.rb

Overview

Builder methods that set @hash and @max.

Direct Known Subclasses

Pure

Defined Under Namespace

Modules: RubyFallback Classes: Pure

Constant Summary collapse

VERSION = 
'0.1.0'
DISABLED_METHODS = 
%i[<< clear clone dup keep_if merge replace reset subtract]
.concat(instance_methods.grep(/^add|^delete|.!$/))
STD_INTERSECT_THRESHOLD_RATIO =

Set#intersect? at ~ O(m*n) can surpass ImmutableSet#intersect? at ~ O(m+n) for sets with very different sizes and unfortunately offset members. Example: Set.intersect?(Set.new(1..1_000_000))

1000

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(arg = nil) ⇒ ImmutableSet

Returns a new instance of ImmutableSet.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/immutable_set.rb', line 14

def initialize(arg = nil)
  @hash = Hash.new(false)

  if arg.is_a?(ImmutableSet)
    @hash = arg.instance_variable_get(:@hash)
    @max = arg.max
  elsif arg.is_a?(Range)
    self.class.send(:feed_range_to_hash, arg, @hash)
    @max = arg.max
  elsif arg.respond_to?(:to_a)
    sorted_arg = arg.to_a.sort
    if block_given?
      sorted_arg.each { |o| @hash[yield(o)] = true }
    else
      sorted_arg.each { |o| @hash[o] = true }
    end
    @max = sorted_arg.last
  elsif !arg.nil?
    raise ArgumentError, 'value must be enumerable'
  end

  @hash.freeze
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method

#method_missing(method_name, *args, &block) ⇒ Object

Raises:

  • (NoMethodError) 


7
8
9
10
11
 
# File 'lib/immutable_set/disable_mutating_methods.rb', line 7

def method_missing(method_name, *args, &block)
  super unless DISABLED_METHODS.include?(method_name)
  raise NoMethodError, "##{method_name} can't be called on an ImmutableSet, "\
                       'only on a Set/SortedSet. Use #+, #-, #^, #& instead.'
end

Instance Attribute Details

#max ⇒ Object (readonly)

Returns the value of attribute max.



12
13
14
 
# File 'lib/immutable_set.rb', line 12

def max
  @max
end

Class Method Details

.build_with_hash_and_max(hash = nil, max = nil) ⇒ Object

Returns an ImmutableSet.

This method can be directly passed a Hash and a max value. It also yields the Hash (or a new Hash if none is given) to any given block, to allow filling it while it is already attached to the new set, which can offer performance benefits for large hashes. If a block is given and no max is passed as parameter, the block must return the new max.

Make sure to pass the correct max of the new Set, or things will break.

Raises:

  • (ArgumentError) 


30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/immutable_set/builder_methods.rb', line 30

def build_with_hash_and_max(hash = nil, max = nil)
  hash ||= Hash.new(false)
  set = new
  set.instance_variable_set(:@hash, hash)

  max = yield(hash) if block_given?
  raise ArgumentError, 'pass a comparable max' unless max.respond_to?(:<=>)

  hash.freeze
  set.instance_variable_set(:@max, max)
  set
end

.cast(obj) ⇒ Object

Returns an ImmutableSet.

Used to cast Enumerables to ImmutableSet if needed for comparisons.



46
47
48
 
# File 'lib/immutable_set/builder_methods.rb', line 46

def cast(obj)
  obj.is_a?(ImmutableSet) ? obj : new(obj)
end

.from_ranges(*ranges) ⇒ Object

Returns an ImmutableSet.

Its members will be ordered, irrespective of the order of passed Ranges.



9
10
11
12
13
14
15
16
17
18
 
# File 'lib/immutable_set/builder_methods.rb', line 9

def from_ranges(*ranges)
  build_with_hash_and_max do |new_hash|
    highest_max = nil
    Array(ranges).sort_by(&:min).each do |range|
      feed_range_to_hash(range, new_hash)
      highest_max = [highest_max || range.max, range.max].max
    end
    highest_max
  end
end

.native_ext ⇒ Object 



11
 
# File 'lib/immutable_set/native_ext.rb', line 11

def self.native_ext; ::ImmutableSetExt end

Instance Method Details

#&(other) ⇒ Object Also known as: intersection 



58
59
60
61
62
63
64
65
66
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 58

def &(other)
  raise_unless_enumerable(other)
  return self.class.new if other.empty?

  other = self.class.cast(other)
  return self.class.new if distinct_bounds?(other)

  relate_with_method(:intersection, to_other: other)
end

#-(other) ⇒ Object Also known as: difference 



47
48
49
50
51
52
53
54
55
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 47

def -(other)
  raise_unless_enumerable(other)
  return self if other.empty?

  other = self.class.cast(other)
  return self if distinct_bounds?(other)

  relate_with_method(:difference, to_other: other)
end

#^(other) ⇒ Object 



69
70
71
72
73
74
75
76
77
78
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 69

def ^(other)
  raise_unless_enumerable(other)
  return other if empty?
  return self if other.empty?

  other = self.class.cast(other)
  return self + other if distinct_bounds?(other)

  relate_with_method(:exclusion, to_other: other)
end

#classify ⇒ Object 



98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 98

def classify
  return super unless block_given?

  classification_hash = {}
  each do |o|
    tmp = (classification_hash[yield(o)] ||= { data: {}, max: nil })
    tmp[:data][o] = true
    tmp[:max] = o
  end
  classification_hash.map do |k, v|
    [k, self.class.build_with_hash_and_max(v[:data], v[:max])]
  end.to_h
end

#distinct_bounds?(other) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (ArgumentError) 


46
47
48
49
 
# File 'lib/immutable_set.rb', line 46

def distinct_bounds?(other)
  raise ArgumentError, 'pass an ImmutableSet' unless other.is_a?(ImmutableSet)
  empty? || other.empty? || (min > other.max || max < other.min)
end

#intersect?(other) ⇒ Boolean

Returns:

  • (Boolean) 


85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 85

def intersect?(other)
  raise_unless_enumerable(other)
  return false if empty? || other.empty?

  other = self.class.cast(other)
  return false if distinct_bounds?(other)

  smaller_size, larger_size = [size, other.size].minmax
  return super if larger_size / smaller_size > STD_INTERSECT_THRESHOLD_RATIO

  relate_with_method(:intersect?, to_other: other)
end

#inversion(from: nil, upto: nil, ucp_only: false) ⇒ Object

Returns an ImmutableSet.

The result includes all members from..upto that are not in self. If ucp_only is true, invalid unicode codepoints are omitted.



6
7
8
9
10
11
12
 
# File 'lib/immutable_set/inversion.rb', line 6

def inversion(from: nil, upto: nil, ucp_only: false)
  if native_ext && from.object_id.odd? && upto.object_id.odd?
    native_ext.invert_fixnum_set(self, from..upto, ucp_only)
  else
    RubyFallback.inversion(self, from..upto, ucp_only)
  end
end

#min ⇒ Object 



38
39
40
 
# File 'lib/immutable_set.rb', line 38

def min
  @min ||= (first_key, = @hash.first) && first_key
end

#minmax ⇒ Object 



42
43
44
 
# File 'lib/immutable_set.rb', line 42

def minmax
  [min, max]
end

#native_ext ⇒ Object 



16
17
18
 
# File 'lib/immutable_set/native_ext.rb', line 16

def native_ext
  self.class.native_ext
end

#proper_subset?(set) ⇒ Boolean Also known as: <

Returns:

  • (Boolean) 


27
28
29
30
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 27

def proper_subset?(set)
  return super unless native_ext_can_relate?(set)
  potentially_proper_subset_of?(set) && native_ext.subset?(self, set)
end

#proper_superset?(set) ⇒ Boolean Also known as: >

Returns:

  • (Boolean) 


15
16
17
18
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 15

def proper_superset?(set)
  return super unless native_ext_can_relate?(set)
  potentially_proper_superset_of?(set) && native_ext.superset?(self, set)
end

#subset?(set) ⇒ Boolean Also known as: <=

Returns:

  • (Boolean) 


21
22
23
24
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 21

def subset?(set)
  return super unless native_ext_can_relate?(set)
  potentially_subset_of?(set) && native_ext.subset?(self, set)
end

#superset?(set) ⇒ Boolean Also known as: >=

These comparison methods only offer a big speed gain with the C extension, or on Ruby < 2.3 where Set has no access to Hash#<=>.

In Ruby, bad Enumerator#next performance makes using two of them in parallel slower than just looking up everything (as #super does) for many cases.

Returns:

  • (Boolean) 


9
10
11
12
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 9

def superset?(set)
  return super unless native_ext_can_relate?(set)
  potentially_superset_of?(set) && native_ext.superset?(self, set)
end

#|(other) ⇒ Object Also known as: +, union

These methods are faster both with the C extension and the Ruby fallback.



37
38
39
40
41
42
43
 
# File 'lib/immutable_set/stdlib_set_method_overrides.rb', line 37

def |(other)
  raise_unless_enumerable(other)
  return self if other.empty?

  other = self.class.cast(other)
  relate_with_method(:union, to_other: other)
end