Class: IntervalNotation::Combiner

Inherits:
Object
  • Object
show all
Defined in:
lib/interval_notation/combiners.rb

Overview

Combiner is an internal helper class for combining interval sets using sweep line. It starts moving from -∞ to +∞ and keep which intervals are crossed by sweep line. Class helps to effectively recalculate number of crossed intervals without rechecking all intervals each time, and dramatically reduces speed of operations on large number of intervals.

Usage example:

UnionCombiner.new(3).combine([interval_1, interval_2, interval_3])

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(num_interval_sets) ⇒ Combiner

Returns a new instance of Combiner.



15
16
17
18
19
 
# File 'lib/interval_notation/combiners.rb', line 15

def initialize(num_interval_sets)
  @num_interval_sets = num_interval_sets
  @inside = Array.new(num_interval_sets, false)
  @num_intervals_inside = 0 # number of intervals, we are inside (for efficiency)
end

Instance Attribute Details

#num_interval_sets ⇒ Object (readonly)

Returns the value of attribute num_interval_sets.



12
13
14
 
# File 'lib/interval_notation/combiners.rb', line 12

def num_interval_sets
  @num_interval_sets
end

#previous_state ⇒ Object (readonly)

Returns the value of attribute previous_state.



13
14
15
 
# File 'lib/interval_notation/combiners.rb', line 13

def previous_state
  @previous_state
end

Instance Method Details

#combine(interval_sets) ⇒ Object

Combines intervals according on an information given by #state/#include_last_point functions which tell whether current section or point should be included to a new interval.



23
24
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
55
56
57
58
59
60
61
62
 
# File 'lib/interval_notation/combiners.rb', line 23

def combine(interval_sets)
  points = interval_sets.each_with_index.flat_map{|interval_set, interval_set_index|
    interval_set.intervals.flat_map{|interval|
      interval.interval_boundaries(interval_set_index)
    }
  }.sort_by(&:value)

  intervals = []

  incl_from = nil
  from = nil

  points.chunk(&:value).each do |point_value, points_on_place|
    pass(points_on_place)

    if previous_state
      if state
        unless include_last_point
          intervals << BasicIntervals.interval_by_boundary_inclusion(incl_from, from, false, point_value)
          incl_from = false
          from = point_value
        end
      else
        to = point_value
        incl_to = include_last_point
        intervals << BasicIntervals.interval_by_boundary_inclusion(incl_from, from, incl_to, to)
        from = nil # easier to find an error (but not necessary code)
        incl_from = nil # ditto
      end
    else
      if state
        from = point_value
        incl_from = include_last_point
      else
        intervals << BasicIntervals::Point.new(point_value)  if include_last_point
      end
    end
  end
  IntervalSet.new_unsafe(intervals)
end

#pass(points_on_place) ⇒ Object

When sweep line pass several interval boundaries, #pass should get all those points at once and update status of crossing sweep line. It also stores previous state, because it’s actively used downstream.



67
68
69
70
 
# File 'lib/interval_notation/combiners.rb', line 67

def pass(points_on_place)
  @previous_state = state
  pass_recalculation(points_on_place)
end