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) 


250
251
252
253
254
 
# File 'lib/interval_notation/interval_set.rb', line 250

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.



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

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



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

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

#closure ⇒ Object

TODO: optimize. Closure of an interval set



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

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: ~



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

def complement
  R.subtract(self)
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) 


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

def contiguous?
  @intervals.size <= 1
end

#covering_interval ⇒ Object

Minimal contiguous interval, covering interval set



182
183
184
185
186
187
188
189
190
191
 
# File 'lib/interval_notation/interval_set.rb', line 182

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) 


156
157
158
 
# File 'lib/interval_notation/interval_set.rb', line 156

def empty?
  @intervals.empty?
end

#eql?(other) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


197
198
199
 
# File 'lib/interval_notation/interval_set.rb', line 197

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

#hash ⇒ Object

:nodoc:



193
194
195
 
# File 'lib/interval_notation/interval_set.rb', line 193

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) 


149
150
151
152
 
# File 'lib/interval_notation/interval_set.rb', line 149

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)



217
218
219
 
# File 'lib/interval_notation/interval_set.rb', line 217

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

#num_connected_components ⇒ Object

Number of connected components



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

def num_connected_components
  @intervals.size
end

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

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



222
223
224
 
# File 'lib/interval_notation/interval_set.rb', line 222

def subtract(other)
  SubtractCombiner.new.combine([self, other])
end

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

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



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

def symmetric_difference(other)
  SymmetricDifferenceCombiner.new.combine([self, other])
end

#to_interval_set ⇒ Object

Auxiliary method to share part of common interface with basic intervals



244
245
246
 
# File 'lib/interval_notation/interval_set.rb', line 244

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



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

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)



210
211
212
 
# File 'lib/interval_notation/interval_set.rb', line 210

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