Class: TwitterCldr::Utils::RangeSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/twitter_cldr/utils/range_set.rb

Overview

An integer set, implemented under the hood with ranges. The idea is that it’s more efficient to store sequential data in ranges rather than as single elements. By definition, RangeSets contain no duplicates.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(ranges) ⇒ RangeSet

Returns a new instance of RangeSet.



66
67
68
69
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 66

def initialize(ranges)
  @ranges = ranges
  flatten
end

Instance Attribute Details

#ranges ⇒ Object (readonly)

Returns the value of attribute ranges.



18
19
20
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 18

def ranges
  @ranges
end

Class Method Details

.from_array(array) ⇒ Object 



22
23
24
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 22

def from_array(array)
  new(rangify(array))
end

.rangify(list, compress = false) ⇒ Object

Turns an array of integers into ranges. The “compress” option indicates whether or not to turn isolated elements into zero-length ranges or leave them as single elements.

For example: rangify([1, 2, 4], false) returns [1..2, 4..4] rangify([1, 2, 4], true) returns [1..2, 4]



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 33

def rangify(list, compress = false)
  last_item = nil

  list.sort.inject([]) do |ret, item|
    if last_item
      diff = item - last_item

      if diff > 0
        if diff == 1
          ret[-1] << item
        else
          ret << [item]
        end

        last_item = item
      end
    else
      ret << [item]
      last_item = item
    end

    ret
  end.map do |sub_list|
    if compress && sub_list.size == 1
      sub_list.first
    else
      sub_list.first..sub_list.last
    end
  end
end

Instance Method Details

#<<(range) ⇒ Object 



110
111
112
113
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 110

def <<(range)
  ranges << range
  flatten
end

#difference(range_set) ⇒ Object

symmetric difference (the union without the intersection) en.wikipedia.org/wiki/Symmetric_difference



169
170
171
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 169

def difference(range_set)
  union(range_set).subtract(intersection(range_set))
end

#each(&block) ⇒ Object 



177
178
179
180
181
182
183
184
185
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 177

def each(&block)
  if block_given?
    ranges.each do |range|
      range.each(&block)
    end
  else
    to_enum(__method__)
  end
end

#each_range(&block) ⇒ Object 



173
174
175
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 173

def each_range(&block)
  ranges.each(&block)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


106
107
108
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 106

def empty?
  ranges.empty?
end

#include?(obj) ⇒ Boolean

Returns:

  • (Boolean) 


95
96
97
98
99
100
101
102
103
104
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 95

def include?(obj)
  case obj
    when Numeric
      includes_numeric?(obj)
    when Range
      includes_range?(obj)
    else
      false
  end
end

#intersection(range_set) ⇒ Object 



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 124

def intersection(range_set)
  new_ranges = []

  range_set.ranges.each do |their_range|
    ranges.each do |our_range|
      if overlap?(their_range, our_range)
        if intrsc = find_intersection(our_range, their_range)
          new_ranges << intrsc
        end
      end
    end
  end

  self.class.new(new_ranges)
end

#size ⇒ Object 



187
188
189
190
191
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 187

def size
  ranges.inject(0) do |sum, range|
    sum + range_length(range)
  end
end

#subtract(range_set) ⇒ Object 



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 140

def subtract(range_set)
  return self if range_set.empty?
  remaining = range_set.ranges.dup
  current_ranges = ranges.dup
  new_ranges = []

  while their_range = remaining.shift
    new_ranges = []

    current_ranges.each do |our_range|
      if overlap?(their_range, our_range)
        new_ranges += find_subtraction(their_range, our_range)
      else
        new_ranges << our_range
      end
    end

    current_ranges = new_ranges
  end

  self.class.new(new_ranges)
end

#subtract!(range_set) ⇒ Object 



163
164
165
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 163

def subtract!(range_set)
  @ranges = subtract(range_set).ranges
end

#to_a(compress = false) ⇒ Object 



71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 71

def to_a(compress = false)
  if compress
    ranges.map do |range|
      if range.first == range.last
        range.first
      else
        range
      end
    end
  else
    ranges.dup
  end
end

#to_full_a ⇒ Object 



85
86
87
88
89
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 85

def to_full_a
  ranges.inject([]) do |ret, range|
    ret + range.to_a
  end
end

#to_set ⇒ Object 



91
92
93
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 91

def to_set
  Set.new(to_full_a)
end

#union(range_set) ⇒ Object 



115
116
117
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 115

def union(range_set)
  self.class.new(range_set.ranges + ranges)
end

#union!(range_set) ⇒ Object 



119
120
121
122
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 119

def union!(range_set)
  ranges.concat(range_set.ranges)
  flatten
end