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.2.0'

Instance Attribute Summary collapse

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!



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

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 Attribute Details

#segments ⇒ Object (readonly)

Returns the value of attribute segments.



64
65
66
 
# File 'lib/segment_tree.rb', line 64

def segments
  @segments
end

Instance Method Details

#==(other) ⇒ Object 



116
117
118
 
# File 'lib/segment_tree.rb', line 116

def ==(other)
  other.is_a?(self.class) && @segments == other.segments
end

#eql?(other) ⇒ Boolean

Returns:

  • (Boolean) 


120
121
122
 
# File 'lib/segment_tree.rb', line 120

def eql?(other)
  other.is_a?(self.class) && @segments.eql?(other.segments)
end

#find(x) ⇒ Segment|NilClass

Find first interval containing point x.

Returns:



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/segment_tree.rb', line 91

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

#hash ⇒ Object 



124
125
126
 
# File 'lib/segment_tree.rb', line 124

def hash
  @segments.hash
end

#inspect ⇒ Object 



108
109
110
111
112
113
114
 
# File 'lib/segment_tree.rb', line 108

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

#marshal_dump ⇒ Object 



128
129
130
131
132
 
# File 'lib/segment_tree.rb', line 128

def marshal_dump
  {
    segments: @segments,
  }
end

#marshal_load(serialized_tree) ⇒ Object 



134
135
136
 
# File 'lib/segment_tree.rb', line 134

def marshal_load(serialized_tree)
  @segments = serialized_tree[:segments]
end