Class: RangeSet

Inherits:
Object
  • Object
show all
Defined in:
lib/range-set.rb,
lib/range-set/version.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.

Constant Summary collapse

VERSION = 
"1.0.0"

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(ranges) ⇒ RangeSet

Returns a new instance of RangeSet.



58
59
60
61
 
# File 'lib/range-set.rb', line 58

def initialize(ranges)
  @ranges = ranges
  flatten
end

Instance Attribute Details

#ranges ⇒ Object (readonly)

Returns the value of attribute ranges.



10
11
12
 
# File 'lib/range-set.rb', line 10

def ranges
  @ranges
end

Class Method Details

.from_array(array) ⇒ Object 



14
15
16
 
# File 'lib/range-set.rb', line 14

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]



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/range-set.rb', line 25

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



149
150
151
 
# File 'lib/range-set.rb', line 149

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


100
101
102
 
# File 'lib/range-set.rb', line 100

def empty?
  ranges.empty?
end

#include?(obj) ⇒ Boolean

Returns:

  • (Boolean) 


87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/range-set.rb', line 87

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 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/range-set.rb', line 108

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 



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/range-set.rb', line 124

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 



63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/range-set.rb', line 63

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 



77
78
79
80
81
 
# File 'lib/range-set.rb', line 77

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

#to_set ⇒ Object 



83
84
85
 
# File 'lib/range-set.rb', line 83

def to_set
  Set.new(to_full_a)
end

#union(range_set) ⇒ Object 



104
105
106
 
# File 'lib/range-set.rb', line 104

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