Class: IntervalTree::InclusiveTree

Inherits:
Object
  • Object
show all
Defined in:
lib/inclusive-interval-tree.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(ranges) ⇒ InclusiveTree

Returns a new instance of InclusiveTree.



30
31
32
33
 
# File 'lib/inclusive-interval-tree.rb', line 30

def initialize(ranges)
  ranges_incl = ensure_inclusive_end([ranges].flatten)
  @top_node = divide_intervals(ranges_incl)
end

Instance Attribute Details

#top_node ⇒ Object (readonly)

Returns the value of attribute top_node.



34
35
36
 
# File 'lib/inclusive-interval-tree.rb', line 34

def top_node
  @top_node
end

Instance Method Details

#divide_intervals(intervals) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/inclusive-interval-tree.rb', line 36

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 < x_center
      s_left << k
    when x_center < k.first
      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(interval) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/inclusive-interval-tree.rb', line 59

def search(interval)
  return [] unless self.top_node
  ret = nil
  if interval.respond_to?(:first)
    first = interval.first
    last = interval.last
  else
    first = interval
    last = nil
  end

  if last
    result = Array.new        
    (interval).each do |j|
      search(j).each{|k|result << k}
      result.uniq!
    end
    ret = result.sort_by{|x|[x.first, x.last]}
  else
    ret = point_search(self.top_node, first, []).sort_by{|x|[x.first, x.last]}
  end
  return ret
end