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