Class: IntervalTree::Tree

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

Constant Summary collapse

DEFAULT_OPTIONS =

Search by range or point

{unique: true}

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(ranges, &range_factory) ⇒ Tree

Returns a new instance of Tree.



6
7
8
9
10
 
# File 'lib/interval_tree.rb', line 6

def initialize(ranges, &range_factory)
  range_factory = lambda { |l, r| (l ... r+1) } unless block_given?
  ranges_excl = ensure_exclusive_end([ranges].flatten, range_factory)
  @top_node = divide_intervals(ranges_excl)
end

Instance Attribute Details

#top_node ⇒ Object (readonly)

Returns the value of attribute top_node.



11
12
13
 
# File 'lib/interval_tree.rb', line 11

def top_node
  @top_node
end

Instance Method Details

#==(other) ⇒ Object 



50
51
52
 
# File 'lib/interval_tree.rb', line 50

def ==(other)
  top_node == other.top_node
end

#divide_intervals(intervals) ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/interval_tree.rb', line 13

def divide_intervals(intervals)
  return nil if intervals.empty?
  x_center = center(intervals)
  s_center = Array.new
  s_left = Array.new
  s_right = Array.new

  intervals.each do |k|
    case
    when k.last.to_r < x_center
      s_left << k
    when k.first.to_r > x_center
      s_right << k
    else
      s_center << k
    end
  end
  Node.new(x_center, s_center,
           divide_intervals(s_left), divide_intervals(s_right))
end

#search(query, options = {}) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/interval_tree.rb', line 36

def search(query, options = {})
  options = DEFAULT_OPTIONS.merge(options)

  return nil unless @top_node

  if query.respond_to?(:first)
    result = top_node.search(query)
    options[:unique] ? result.uniq : result
  else
    point_search(self.top_node, query, [], options[:unique])
  end
    .sort_by{|x|[x.first, x.last]}
end