Class: SegmentTree

Inherits:
Object
  • Object
show all
Defined in:
lib/segment_tree.rb,
lib/segment_tree/version.rb

Overview

Synopsys

Segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built.

Example

data = [
  [IPAddr.new('87.224.241.0/24').to_range, {:city => "YEKT"}],
  [IPAddr.new('195.58.18.0/24').to_range, {:city => "MSK"}]
  # and so on
]
ip_tree = SegmentTree.new(data)

client_ip = IPAddr.new("87.224.241.66")
ip_tree.find(client_ip).value # => {:city=>"YEKT"}

Defined Under Namespace

Classes: Segment

Constant Summary collapse

VERSION = 
'0.1.1'

Instance Method Summary collapse

Constructor Details

#initialize(data, sorted = false) ⇒ SegmentTree

Build a segment tree from data.

Data can be one of the following:

  1. Hash - a hash, where ranges are keys, i.e. <code>=> some_value1, (4..6) => some_value2, …<code>

  2. 2-dimensional array - an array of arrays where first element of each element is range, and second is value: <code>[[(0..3), some_value1], [(4..6), some_value2] …]<code>

You can pass optional argument sorted. If sorted is true then tree consider that data already sorted in proper order. Use it at your own risk!



48
49
50
51
52
53
54
55
56
57
 
# File 'lib/segment_tree.rb', line 48

def initialize(data, sorted = false)
  # build elementary segments
  @segments = case data
    when Hash, Array, Enumerable then
      data.collect { |range, value| Segment.new(range, value) }
    else raise ArgumentError, '2-dim Array or Hash expected'
  end

  @segments.sort! unless sorted
end

Instance Method Details

#find(x) ⇒ Segment|NilClass

Find first interval containing point x.

Returns:



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/segment_tree.rb', line 61

def find(x)
  return nil if x.nil?
  low = 0
  high = @segments.size - 1
  while low <= high
    mid = (low + high) / 2

    case matches?(x, low, high, mid)
      when -1 then high = mid - 1
      when 1 then low = mid + 1
      when 0 then return @segments[mid]
      else return nil
    end
  end
  nil
end

#inspect ⇒ Object 



78
79
80
81
82
83
84
 
# File 'lib/segment_tree.rb', line 78

def inspect
  if @segments.size > 0
    "SegmentTree(#{@segments.first.range.begin}..#{@segments.last.range.end})"
  else
    "SegmentTree(empty)"
  end
end