Class: ElasticGraph::Support::TimeSet

Inherits:
Object
  • Object
show all
Defined in:
lib/elastic_graph/support/time_set.rb

Overview

Models a set of ‘::Time` objects, but does so using one or more `::Range` objects. This is done so that we can support unbounded sets (such as “all times after midnight on date X”).

Internally, this is a simple wrapper around a set of ‘::Range` objects. Those ranges take a few different forms:

  • ALL: a range with no bounds, which implicitly contains all ‘::Time`s. (It’s like the integer set from negative to positive infinity).

  • An open range: a range with only an upper or lower bound (but not the other).

  • A closed range: a range with an upper and lower bound.

  • An empty range: a range that contains no ‘::Time`s, by virtue of its bounds having no overlap.

Defined Under Namespace

Modules: RangeFactory

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.of_range(gt: nil, gte: nil, lt: nil, lte: nil) ⇒ Object

Factory method to construct a ‘TimeSet` using a range with the given bounds.



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/elastic_graph/support/time_set.rb', line 25

def self.of_range(gt: nil, gte: nil, lt: nil, lte: nil)
  if gt && gte
    raise ArgumentError, "TimeSet got two lower bounds, but can have only one (gt: #{gt.inspect}, gte: #{gte.inspect})"
  end

  if lt && lte
    raise ArgumentError, "TimeSet got two upper bounds, but can have only one (lt: #{lt.inspect}, lte: #{lte.inspect})"
  end

  # To be able to leverage Ruby's Range class, we need to convert to the "inclusive" ("or equal")
  # form. This cuts down on the number of test cases we need to write and also Ruby's range lets
  # you control whether the end of a range is inclusive or exclusive, but doesn't let you control
  # the beginning of the range.
  #
  # This is safe to do because our datastores only work with `::Time`s at millisecond granularity,
  # so `> t` is equivalent to `>= (t + 1ms)` and `< t` is equivalent to `<= (t - 1ms)`.
  lower_bound = gt&.+(CONSECUTIVE_TIME_INCREMENT) || gte
  upper_bound = lt&.-(CONSECUTIVE_TIME_INCREMENT) || lte

  of_range_objects(_ = [RangeFactory.build_non_empty(lower_bound, upper_bound)].compact)
end

.of_range_objects(range_objects) ⇒ Object

Factory method to construct a ‘TimeSet` from a previously built collection of ::Time ranges. Mostly used internally by `TimeSet` and in tests.



55
56
57
58
59
60
61
62
 
# File 'lib/elastic_graph/support/time_set.rb', line 55

def self.of_range_objects(range_objects)
  # Use our singleton EMPTY or ALL instances if we can to save on memory.
  return EMPTY if range_objects.empty?
  first_range = _ = range_objects.first
  return ALL if first_range.begin.nil? && first_range.end.nil?

  new(range_objects)
end

.of_times(times) ⇒ Object

Factory method to construct a ‘TimeSet` from a collection of `::Time` objects. Internally we convert it to a set of `::Range` objects, one per unique time.



49
50
51
 
# File 'lib/elastic_graph/support/time_set.rb', line 49

def self.of_times(times)
  of_range_objects(times.map { |t| ::Range.new(t, t) })
end

Instance Method Details

#-(other) ⇒ Object

Returns a new ‘TimeSet` containing the difference between this `TimeSet` and the given one.



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/elastic_graph/support/time_set.rb', line 110

def -(other)
  new_ranges = other.ranges.to_a.reduce(ranges.to_a) do |accum, other_range|
    accum.flat_map do |self_range|
      if ranges_intersect?(self_range, other_range)
        # Since the ranges intersect, `self_range` must be reduced some how. Depending on what kind of
        # intersection we have (e.g. exact equality, `self_range` fully inside `other_range`, `other_range`
        # fully inside `self_range`, partial overlap where `self_range` begins before `other_range`, or partial
        # overlap where `self_range` ends after `other_range`), we may have a part of `self_range` that comes
        # before `other_range`, a part of `self_range` that comes after `other_range`, both, or neither. Below
        # we build the before and after parts as candidates, but then ignore any resulting ranges that are
        # invalid, which leaves us with the correct result, without having to explicitly handle each possible case.

        # @type var candidates: ::Array[timeRange]
        candidates = []

        if (other_range_begin = other_range.begin)
          # This represents the parts of `self_range` that come _before_ `other_range`.
          candidates << Range.new(self_range.begin, other_range_begin - CONSECUTIVE_TIME_INCREMENT)
        end

        if (other_range_end = other_range.end)
          # This represents the parts of `self_range` that come _after_ `other_range`.
          candidates << Range.new(other_range_end + CONSECUTIVE_TIME_INCREMENT, self_range.end)
        end

        # While some of the ranges produced above may be invalid (due to being descending), we don't have to
        # filter them out here because `#initialize` takes care of it.
        candidates
      else
        # Since the ranges don't intersect, there is nothing to remove from `self_range`; just return it unmodified.
        [self_range]
      end
    end
  end

  TimeSet.of_range_objects(new_ranges)
end

#empty? ⇒ Boolean

Returns true if this TimeSet contains no members.

Returns:

  • (Boolean) 


105
106
107
 
# File 'lib/elastic_graph/support/time_set.rb', line 105

def empty?
  ranges.empty?
end

#intersect?(other_set) ⇒ Boolean

Returns true if this ‘TimeSet` and the given one have a least one time in common.

Returns:

  • (Boolean) 


96
97
98
99
100
101
102
 
# File 'lib/elastic_graph/support/time_set.rb', line 96

def intersect?(other_set)
  other_set.ranges.any? do |r1|
    ranges.any? do |r2|
      ranges_intersect?(r1, r2)
    end
  end
end

#intersection(other_set) ⇒ Object

Returns a new ‘TimeSet` containing `::Time`s common to this set and `other_set`.



65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/elastic_graph/support/time_set.rb', line 65

def intersection(other_set)
  # Here we rely on the distributive and commutative properties of set algebra:
  #
  # https://en.wikipedia.org/wiki/Algebra_of_sets
  # A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (distributive property)
  #       A ∩ B = B ∩ A             (commutative property)
  #
  # We can combine these properties to see how the intersection of sets of ranges would work:
  #          (A₁ ∪ A₂)        ∩        (B₁ ∪ B₂)
  # =        ((A₁ ∪ A₂) ∩ B₁) ∪ ((A₁ ∪ A₂) ∩ B₂)        (expanding based on distributive property)
  # =        (B₁ ∩ (A₁ ∪ A₂)) ∪ (B₂ ∩ (A₁ ∪ A₂))        (rearranging based on commutative property)
  # = ((B₁ ∩ A₁) ∪ (B₁ ∩ A₂)) ∪ ((B₂ ∩ A₁) ∪ (B₂ ∩ A₂)) (expanding based on distributive property)
  # =  (B₁ ∩ A₁) ∪ (B₁ ∩ A₂)  ∪  (B₂ ∩ A₁) ∪ (B₂ ∩ A₂)  (removing excess parens)
  # = union of (intersection of each pair)
  intersected_ranges = ranges.to_a.product(other_set.ranges.to_a)
    .filter_map { |r1, r2| intersect_ranges(r1, r2) }

  TimeSet.of_range_objects(intersected_ranges)
end

#member?(time) ⇒ Boolean

Returns true if the given ‘::Time` is a member of this `TimeSet`.

Returns:

  • (Boolean) 


91
92
93
 
# File 'lib/elastic_graph/support/time_set.rb', line 91

def member?(time)
  ranges.any? { |r| r.cover?(time) }
end

#negate ⇒ Object 



148
149
150
 
# File 'lib/elastic_graph/support/time_set.rb', line 148

def negate
  ALL - self
end

#union(other_set) ⇒ Object

Returns a new ‘TimeSet` containing `::Time`s that are in either this set or `other_set`.



86
87
88
 
# File 'lib/elastic_graph/support/time_set.rb', line 86

def union(other_set)
  TimeSet.of_range_objects(ranges.union(other_set.ranges))
end