Class: TwitterCldr::Utils::RangeSet

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



64
65
66
67
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 64

def initialize(ranges)
  @ranges = ranges
  flatten
end

Instance Attribute Details

#ranges ⇒ Object (readonly)

Returns the value of attribute ranges.



16
17
18
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 16

def ranges
  @ranges
end

Class Method Details

.from_array(array) ⇒ Object 



20
21
22
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 20

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

.rangify(list, compress = false) ⇒ Object

Turns an array of integers into ranges. The “compress” option indicates wether 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]



31
32
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
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 31

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

#difference(range_set) ⇒ Object

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



155
156
157
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 155

def difference(range_set)
  union(range_set).subtract(intersection(range_set))
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) 


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

def include?(obj)
  case obj
    when Numeric
      ranges.any? { |range| range.include?(obj) }
    when Range
      ranges.any? do |range|
        range.first <= obj.first && range.last >= obj.last
      end
    else
      false
  end
end

#intersection(range_set) ⇒ Object 



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 114

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

#subtract(range_set) ⇒ Object 



130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 130

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

#to_a(compress = false) ⇒ Object 



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

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 



83
84
85
86
87
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 83

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

#to_set ⇒ Object 



89
90
91
 
# File 'lib/twitter_cldr/utils/range_set.rb', line 89

def to_set
  Set.new(to_full_a)
end

#union(range_set) ⇒ Object 



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

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