class TwitterCldr::Utils::RangeSet
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.
Attributes
ranges[R]
Public Class Methods
from_array(array)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 22 def from_array(array) new(rangify(array)) end
new(ranges)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 66 def initialize(ranges) @ranges = ranges flatten end
rangify(list, compress = false)
click to toggle source
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]
# 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
Public Instance Methods
<<(range)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 110 def <<(range) ranges << range flatten end
difference(range_set)
click to toggle source
symmetric difference (the union without the intersection) en.wikipedia.org/wiki/Symmetric_difference
# File lib/twitter_cldr/utils/range_set.rb, line 169 def difference(range_set) union(range_set).subtract(intersection(range_set)) end
each(&block)
click to toggle source
# 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)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 173 def each_range(&block) ranges.each(&block) end
empty?()
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 106 def empty? ranges.empty? end
include?(obj)
click to toggle source
# 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)
click to toggle source
# 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()
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 163 def subtract!(range_set) @ranges = subtract(range_set).ranges end
to_a(compress = false)
click to toggle source
# 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()
click to toggle source
# 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()
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 91 def to_set Set.new(to_full_a) end
union(range_set)
click to toggle source
# 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)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 119 def union!(range_set) ranges.concat(range_set.ranges) flatten end
Private Instance Methods
adjacent?(range1, range2)
click to toggle source
returns true if range1 and range2 are within 1 of each other
# File lib/twitter_cldr/utils/range_set.rb, line 281 def adjacent?(range1, range2) is_numeric_range?(range1) && is_numeric_range?(range2) && (range1.last == range2.first - 1 || range2.first == range1.last + 1) end
bsearch() { |ranges| ... }
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 233 def bsearch low = 0 mid = 0 high = ranges.size - 1 while low <= high mid = (low + high) / 2 case yield(ranges[mid]) when 0 return ranges[mid] when -1 high = mid - 1 else low = mid + 1 end end nil end
find_intersection(range1, range2)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 319 def find_intersection(range1, range2) # range2 entirely contains range1 if fully_overlapped_by?(range1, range2) range1.dup elsif front_overlap?(range1, range2) range2.first..range1.last elsif rear_overlap?(range1, range2) range1.first..range2.last elsif full_overlap?(range1, range2) [range1.first, range2.first].max..[range1.last, range2.last].min end end
find_subtraction(range1, range2)
click to toggle source
subtracts range1 from range2 (range2 - range1)
# File lib/twitter_cldr/utils/range_set.rb, line 333 def find_subtraction(range1, range2) # case: range1 contains range2 entirely (also handles equal case) result = if full_overlap?(range1, range2) [] # case: range1 comes in the middle elsif fully_overlapped_by?(range1, range2) [range2.first..(range1.first - 1), (range1.last + 1)..range2.last] # case: range1 trails elsif rear_overlap?(range1, range2) [range2.first..(range1.first - 1)] # case: range1 leads elsif front_overlap?(range1, range2) [(range1.last + 1)..range2.last] end result.reject { |r| r.first > r.last } end
flatten()
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 290 def flatten return if ranges.size <= 1 sorted_ranges = ranges.sort do |a, b| if is_numeric_range?(a) && is_numeric_range?(b) a.first <=> b.first else 1 end end new_ranges = [sorted_ranges.first] sorted_ranges.each do |range| previous_range = new_ranges.pop if adjacent?(previous_range, range) || overlap?(previous_range, range) new_ranges.push( [range.first, previous_range.first].min..[range.last, previous_range.last].max ) else new_ranges.push(previous_range) new_ranges.push(range) end end @ranges = new_ranges end
front_overlap?(range1, range2)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 262 def front_overlap?(range1, range2) range1.last >= range2.first && range1.last <= range2.last end
full_overlap?(range1, range2)
click to toggle source
range1 entirely contains range2
# File lib/twitter_cldr/utils/range_set.rb, line 271 def full_overlap?(range1, range2) range1.first <= range2.first && range1.last >= range2.last end
fully_overlapped_by?(range1, range2)
click to toggle source
range2 entirely contains range1
# File lib/twitter_cldr/utils/range_set.rb, line 276 def fully_overlapped_by?(range1, range2) range2.first <= range1.first && range1.last <= range2.last end
includes_numeric?(num)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 200 def includes_numeric?(num) result = bsearch do |range| if num >= range.first && num <= range.last 0 elsif num < range.first -1 else 1 end end !!result end
includes_range?(range)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 214 def includes_range?(range) result = bsearch do |cur_range| fo = front_overlap?(cur_range, range) ro = rear_overlap?(cur_range, range) return false if fo || ro if full_overlap?(cur_range, range) 0 elsif range.first < cur_range.first -1 else 1 end end !!result end
is_numeric_range?(range)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 286 def is_numeric_range?(range) range.first.is_a?(Numeric) && range.last.is_a?(Numeric) end
overlap?(range1, range2)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 254 def overlap?(range1, range2) is_numeric_range?(range1) && is_numeric_range?(range2) && ( front_overlap?(range1, range2) || rear_overlap?(range1, range2) || full_overlap?(range1, range2) ) end
range_length(range)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 195 def range_length(range) len = (range.last - range.first) range.exclude_end? ? len : len + 1 end
rear_overlap?(range1, range2)
click to toggle source
# File lib/twitter_cldr/utils/range_set.rb, line 266 def rear_overlap?(range1, range2) range1.first >= range2.first && range1.first <= range2.last end