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) 


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

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.



182
183
184
185
186
 
# File 'lib/interval_notation/interval_set.rb', line 182

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



127
128
129
 
# File 'lib/interval_notation/interval_set.rb', line 127

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

#closure ⇒ Object

TODO: optimize. Closure of an interval set



101
102
103
 
# File 'lib/interval_notation/interval_set.rb', line 101

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



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

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) 


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

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) 


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

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

#contiguous? ⇒ Boolean

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

Returns:

  • (Boolean) 


85
86
87
 
# File 'lib/interval_notation/interval_set.rb', line 85

def contiguous?
  @intervals.size <= 1
end

#covering_interval ⇒ Object

Minimal contiguous interval, covering interval set



106
107
108
109
110
111
112
113
114
115
 
# File 'lib/interval_notation/interval_set.rb', line 106

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

#empty? ⇒ Boolean

Checks whether an interval set is empty

Returns:

  • (Boolean) 


80
81
82
 
# File 'lib/interval_notation/interval_set.rb', line 80

def empty?
  @intervals.empty?
end

#eql?(other) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


121
122
123
 
# File 'lib/interval_notation/interval_set.rb', line 121

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

#hash ⇒ Object

:nodoc:



117
118
119
 
# File 'lib/interval_notation/interval_set.rb', line 117

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| interv.to >= value }
  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?

TODO: optimize if possible. Checks whether an interval set intersects another interval set. Alias: #intersect?

Returns:

  • (Boolean) 


74
75
76
 
# File 'lib/interval_notation/interval_set.rb', line 74

def intersect?(other)
  ! intersection(other).empty?
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)



141
142
143
 
# File 'lib/interval_notation/interval_set.rb', line 141

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

#num_connected_components ⇒ Object

Number of connected components



95
96
97
 
# File 'lib/interval_notation/interval_set.rb', line 95

def num_connected_components
  @intervals.size
end

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

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



146
147
148
 
# File 'lib/interval_notation/interval_set.rb', line 146

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

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

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



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

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

#to_interval_set ⇒ Object

Auxiliary method to share part of common interface with basic intervals



168
169
170
 
# File 'lib/interval_notation/interval_set.rb', line 168

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



90
91
92
 
# File 'lib/interval_notation/interval_set.rb', line 90

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)



134
135
136
 
# File 'lib/interval_notation/interval_set.rb', line 134

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