Class: IntervalList::TreeNode

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(intervals) ⇒ TreeNode

Returns a new instance of TreeNode.



150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/intervals.rb', line 150

def initialize intervals
  # assume they are sorted by start
  
  low, high = intervals.each_slice((intervals.size/2.0).round).to_a

  @node = low.pop
  @left = TreeNode.new low unless low.empty?
  @right = TreeNode.new high unless high.nil?

  update_max
end

Instance Attribute Details

#max ⇒ Object (readonly)

Returns the value of attribute max.



148
149
150
 
# File 'lib/intervals.rb', line 148

def max
  @max
end

Instance Method Details

#add(interval) ⇒ Object 



162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/intervals.rb', line 162

def add interval
  if interval.start < @node.start
    if @left
      @left.add interval
    else
      @left = TreeNode.new [interval]
    end
  else
    if @right
      @right.add interval
    else
      @right = TreeNode.new [interval]
    end
  end
  update_max
end

#breadth_traverse {|@node| ... } ⇒ Object

Yields:

  • (@node) 


191
192
193
194
195
 
# File 'lib/intervals.rb', line 191

def breadth_traverse &block
  @left.breadth_traverse(&block) if @left
  yield @node
  @right.breadth_traverse(&block) if @right
end

#depth_traverse {|@node| ... } ⇒ Object

Yields:

  • (@node) 


197
198
199
200
201
 
# File 'lib/intervals.rb', line 197

def depth_traverse &block
  yield @node
  @left.breadth_traverse(&block) if @left
  @right.breadth_traverse(&block) if @right
end

#is_max? ⇒ Boolean

Returns:

  • (Boolean) 


186
187
188
 
# File 'lib/intervals.rb', line 186

def is_max?
  @max == @node
end

#nearest(interval) ⇒ Object 



203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/intervals.rb', line 203

def nearest interval
  # if there are overlaps, pick the one with the closest distance
  
  ol = overlap(interval)
  if !ol.empty?
    return ol.min do |a,b|
      interval.dist(a) <=> interval.dist(b)
    end
  end

  # there are no overlaps. Find the highest stop that is less than interval.start
  [ nearest_stop(interval),
    nearest_start(interval) ].compact.min do |a,b|
    interval.dist(a) <=> interval.dist(b)
  end
end

#overlap(interval) ⇒ Object 



220
221
222
223
224
225
226
227
 
# File 'lib/intervals.rb', line 220

def overlap interval
  ols = []
  return ols if interval.start > @max.stop
  ols.concat @left.overlap(interval) if @left
  ols.push @node if @node.overlaps? interval
  ols.concat @right.overlap(interval) if @right && !@node.above?(interval)
  ols
end

#update_max ⇒ Object 



179
180
181
182
183
184
 
# File 'lib/intervals.rb', line 179

def update_max
  # set your max to the max of your children
  @max = @node
  @max = @left.max if @left && @left.max.stop > @max.stop
  @max = @right.max if @right && @right.max.stop > @max.stop
end