Class: IntervalTree::ExclusiveTree

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(ranges) ⇒ ExclusiveTree

Returns a new instance of ExclusiveTree.



29
30
31
32
 
# File 'lib/exclusive-interval-tree.rb', line 29

def initialize(ranges)
  ranges_excl = ensure_exclusive_end([ranges].flatten)
  @top_node = divide_intervals(ranges_excl)
end

Instance Attribute Details

#top_node ⇒ Object (readonly)

Returns the value of attribute top_node.



33
34
35
 
# File 'lib/exclusive-interval-tree.rb', line 33

def top_node
  @top_node
end

Instance Method Details

#divide_intervals(intervals) ⇒ Object 



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

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 



57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/exclusive-interval-tree.rb', line 57

def search(interval)
  if interval.respond_to?(:first)
    first = interval.first
    last = interval.last
  else
    first = interval
    last = nil
  end

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