Class: TwitterCldr::Utils::RangeSet
- Inherits:
-
Object
- Object
- TwitterCldr::Utils::RangeSet
- 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
-
#ranges ⇒ Object
readonly
Returns the value of attribute ranges.
Class Method Summary collapse
- .from_array(array) ⇒ Object
-
.rangify(list, compress = false) ⇒ Object
Turns an array of integers into ranges.
Instance Method Summary collapse
-
#difference(range_set) ⇒ Object
symmetric difference (the union without the intersection) en.wikipedia.org/wiki/Symmetric_difference.
- #empty? ⇒ Boolean
- #include?(obj) ⇒ Boolean
-
#initialize(ranges) ⇒ RangeSet
constructor
A new instance of RangeSet.
- #intersection(range_set) ⇒ Object
- #subtract(range_set) ⇒ Object
- #to_a(compress = false) ⇒ Object
- #to_full_a ⇒ Object
- #to_set ⇒ Object
- #union(range_set) ⇒ Object
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
106 107 108 |
# File 'lib/twitter_cldr/utils/range_set.rb', line 106 def empty? ranges.empty? end |
#include?(obj) ⇒ 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 |