Class: IntervalNotation::IntervalSet

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(intervals) ⇒ IntervalSet

IntervalSet.new accepts an ordered list of intervals. Intervals should be sorted from leftmost to rightmost and should not overlap. It’s not recommended to use this constructor directly. Instead take a look at IntervalNotation::Syntax module.

Example:

# don't use this
IntervalSet.new([OpenOpenInterval.new(1,3), Point.new(5)])
# instead use
oo(1,3) | pt(5)



19
20
21
22
23
24
25
 
# File 'lib/interval_notation/interval_set.rb', line 19

def initialize(intervals)
  unless IntervalSet.check_valid?(intervals)
    raise Error,  "IntervalSet.new accepts non-overlapping, sorted regions.\n" +
                  "Try to use IntervalNotation.union(...) to create interval from overlapping or not-sorted intervals"
  end
  @intervals = intervals.freeze
end

Instance Attribute Details

#intervals ⇒ Object (readonly)

Returns the value of attribute intervals.



7
8
9
 
# File 'lib/interval_notation/interval_set.rb', line 7

def intervals
  @intervals
end

Class Method Details

.check_valid?(intervals) ⇒ Boolean

auxiliary method to check that intervals are sorted and don’t overlap

Returns:

  • (Boolean) 


270
271
272
273
274
 
# File 'lib/interval_notation/interval_set.rb', line 270

def check_valid?(intervals)
  intervals.each_cons(2).all? do |interval_1, interval_2|
    interval_1.to <= interval_2.from && !(interval_1.to == interval_2.from && (interval_1.include_to? || interval_2.include_from?))
  end
end

.from_string(str) ⇒ Object

Method to create an interval set from string. It accepts strings obtained by #to_s and many other formats. Spaces inside are ignored Intervals can be joined with u or U letters and unicode union character ∪ Points can go separately or be combined inside of single curly braces. Single point can go without braces at all , and ; are both valid value separators. Infinity can be represented by inf, infty, \infty, infinity, ∞ (each can go with or without sign) Empty set is empty string, word Empty or unicode character ∅ R represents whole 1-D line (-∞, ∞)



36
37
38
39
40
41
 
# File 'lib/interval_notation/interval_set.rb', line 36

def self.from_string(str)
  intervals = str.split(/[uU∪]/).flat_map{|interval_str|
    BasicIntervals.from_string(interval_str)
  }.map(&:to_interval_set)
  Operations.union(intervals)
end

.new_unsafe(intervals) ⇒ Object

An IntervalSet.new_unsafe is a constructor which skips validation. It’s designed mostly for internal use. It can be used when you are absolutely sure, that intervals are ordered and don’t overlap.



278
279
280
281
282
 
# File 'lib/interval_notation/interval_set.rb', line 278

def new_unsafe(intervals)
  obj = allocate
  obj.instance_variable_set(:@intervals, intervals.freeze)
  obj
end

Instance Method Details

#==(other) ⇒ Object

Intervals are equal only if they contain exactly the same intervals. Point inclusion is also considered



213
214
215
 
# File 'lib/interval_notation/interval_set.rb', line 213

def ==(other)
  other.is_a?(IntervalSet) && intervals == other.intervals
end

#closure ⇒ Object

TODO: optimize. Closure of an interval set



187
188
189
 
# File 'lib/interval_notation/interval_set.rb', line 187

def closure
  Operations.union(@intervals.map(&:closure).map(&:to_interval_set))
end

#complement ⇒ Object Also known as: ~

Complement of an interval set in R. Alias: ~



242
243
244
 
# File 'lib/interval_notation/interval_set.rb', line 242

def complement
  R.subtract(self)
end

#connected_components ⇒ Object

Obtain nonadjacent contiguous intervals (connected components) from which whole interval set consists



259
260
261
 
# File 'lib/interval_notation/interval_set.rb', line 259

def connected_components
  intervals.map(&:to_interval_set)
end

#contain?(other) ⇒ Boolean Also known as: include?

Checks whether an interval set contains another interval set. Alias: #include?

Returns:

  • (Boolean) 


66
67
68
 
# File 'lib/interval_notation/interval_set.rb', line 66

def contain?(other)
  self.intersection(other) == other
end

#contained_by?(other) ⇒ Boolean Also known as: covered_by?

Checks whether an interval set is covered by another interval set. Alias: #covered_by?

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/interval_notation/interval_set.rb', line 72

def contained_by?(other)
  self.intersection(other) == self
end

#contiguous? ⇒ Boolean

Checks whether an interval set is contiguous (empty set treated contiguous)

Returns:

  • (Boolean) 


171
172
173
 
# File 'lib/interval_notation/interval_set.rb', line 171

def contiguous?
  @intervals.size <= 1
end

#covering_interval ⇒ Object

Minimal contiguous interval, covering interval set



192
193
194
195
196
197
198
199
200
201
 
# File 'lib/interval_notation/interval_set.rb', line 192

def covering_interval
  if @intervals.size == 0
    Empty
  elsif @intervals.size == 1
    self
  else
    BasicIntervals.interval_by_boundary_inclusion(@intervals.first.include_from?, @intervals.first.from,
                                                  @intervals.last.include_to?, @intervals.last.to).to_interval_set
  end
end

#deep_include_position?(value) ⇒ Boolean

Returns:

  • (Boolean) 


60
61
62
63
 
# File 'lib/interval_notation/interval_set.rb', line 60

def deep_include_position?(value)
  interval = @intervals.bsearch{|interv| value <= interv.to }
  interval && interval.deep_include_position?(value)
end

#empty? ⇒ Boolean

Checks whether an interval set is empty

Returns:

  • (Boolean) 


166
167
168
 
# File 'lib/interval_notation/interval_set.rb', line 166

def empty?
  @intervals.empty?
end

#eql?(other) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


207
208
209
 
# File 'lib/interval_notation/interval_set.rb', line 207

def eql?(other) # :nodoc:
  other.class.equal?(self.class) && intervals == other.intervals
end

#hash ⇒ Object

:nodoc:



203
204
205
 
# File 'lib/interval_notation/interval_set.rb', line 203

def hash # :nodoc:
  @intervals.hash
end

#include_position?(value) ⇒ Boolean

Checks whether an interval set contains certain position. Operation complexity is O(ln N), where N is a number of contiguous regions in an interval set

Returns:

  • (Boolean) 


55
56
57
58
 
# File 'lib/interval_notation/interval_set.rb', line 55

def include_position?(value)
  interval = @intervals.bsearch{|interv| value <= interv.to }
  interval && interval.include_position?(value)
end

#inspect ⇒ Object

:nodoc:



49
50
51
 
# File 'lib/interval_notation/interval_set.rb', line 49

def inspect # :nodoc:
  to_s
end

#intersect?(other) ⇒ Boolean Also known as: overlap?

Checks whether an interval set intersects another interval set. Alias: #overlap?

Returns:

  • (Boolean) 


159
160
161
162
 
# File 'lib/interval_notation/interval_set.rb', line 159

def intersect?(other)
  intersect_n_log_n?(other) # ToDo: balance different implementations for different interval set sizes
  # ! intersection(other).empty? # Simplest and too slow implementation
end

#intersection(other) ⇒ Object Also known as: &

Intersection of an interval set with another interval set other. Alias: & To unite many (tens of thousands intervals) intervals use IntervalNotation::Operations.intersection method. (Operations.intersection is dramatically faster than sequentially intersecting intervals one-by-one)



227
228
229
 
# File 'lib/interval_notation/interval_set.rb', line 227

def intersection(other)
  Operations.intersection([self, other])
end

#interval_covering_point(value) ⇒ Object

Find connected component of an interval set which covers a point. Return ‘BasicIntervals` for this connected component or nil if point is not covered.



79
80
81
82
83
84
85
86
 
# File 'lib/interval_notation/interval_set.rb', line 79

def interval_covering_point(value)
  interval = @intervals.bsearch{|interv| value <= interv.to }
  if interval && interval.include_position?(value)
    interval
  else
    nil
  end
end

#make_segmentation ⇒ Object

Create true/false ‘Segmentation` corresponding to an `IntervalSet`



264
265
266
 
# File 'lib/interval_notation/interval_set.rb', line 264

def make_segmentation
  SweepLine.make_segmentation({self => nil}, SweepLine::TraceState::Union.initial_state(1))
end

#num_connected_components ⇒ Object

Number of connected components



181
182
183
 
# File 'lib/interval_notation/interval_set.rb', line 181

def num_connected_components
  @intervals.size
end

#subtract(other) ⇒ Object Also known as: -

Difference between an interval set and another interval set other. Alias: -



232
233
234
 
# File 'lib/interval_notation/interval_set.rb', line 232

def subtract(other)
  SweepLine.make_interval_set([self, other], SweepLine::TraceState::Subtract.initial_state)
end

#symmetric_difference(other) ⇒ Object Also known as: ^

Symmetric difference between an interval set and another interval set other. Alias: ^



237
238
239
 
# File 'lib/interval_notation/interval_set.rb', line 237

def symmetric_difference(other)
  SweepLine.make_interval_set([self, other], SweepLine::TraceState::SymmetricDifference.initial_state)
end

#to_interval_set ⇒ Object

Auxiliary method to share part of common interface with basic intervals



254
255
256
 
# File 'lib/interval_notation/interval_set.rb', line 254

def to_interval_set # :nodoc:
  self
end

#to_s ⇒ Object

Output standard mathematical notation of interval set in left-to-right order. Each singular point is listed separately in curly braces.



45
46
47
 
# File 'lib/interval_notation/interval_set.rb', line 45

def to_s
  @intervals.empty? ? EMPTY_SET_SYMBOL : intervals.map(&:to_s).join(UNION_SYMBOL)
end

#total_length ⇒ Object

Total length of all intervals in set



176
177
178
 
# File 'lib/interval_notation/interval_set.rb', line 176

def total_length
  @intervals.map(&:length).inject(0, &:+)
end

#union(other) ⇒ Object Also known as: |

Union of an interval set with another interval set other. Alias: | To unite many (tens of thousands intervals) intervals use IntervalNotation::Operations.unite method. (Operations.unite is dramatically faster than sequentially uniting intervals one-by-one)



220
221
222
 
# File 'lib/interval_notation/interval_set.rb', line 220

def union(other)
  Operations.union([self, other])
end